4.6.5.1 Using Boolean Algebra

Addition

Boolean numbers can be added together. This is equivalent to an OR gate.

A B Q Algebra
0 0 0 \(0 + 0 = 0\)
0 1 1 \(0 + 1 = 1\)
1 0 1 \(1 + 0 = 1\)
1 1 1 \(1 + 1 = 1\)

In boolean algebra, since you cannot have 2, adding two numbers will stop at 1.

Multiplication

Boolean numbers can also be multiplied together. This is equivalent to an AND gate.

A B Q Algebra
0 0 0 \(0 \times 0 = 0\)
0 1 0 \(0 \times 1 = 0\)
1 0 0 \(1 \times 0 = 0\)
1 1 1 \(1 \times 1 = 1\)

Note that 1 multiplied by 0 in both decimal and binary algebra is 0. Later on, the multiplication symbol will be replaced with a dot.

Complement

Boolean numbers can be inverted. This is equivalent to a NOT gate.

A Q Algebra
0 1 \(\overline 0 = 1\)
1 0 \(\overline 1 = 0\)

Identities

Combining these above algebraic formulae can cause complex equations to arise. Sometimes, these needs to be simplified, as reducing the number of gates required saves space, cost and time producing circuits.

Unfortunately, there's quite a few to remember.

Name AND form OR form
Identity \(A.1 = A\) \(A+0 = A\)
Null (or Dominance) Law \(A.0 = 0\) \(A+1 = 1\)
Idempotence Law \(A.A = A\) \(A+A = A\)
Inverse Law \(A.\overline A = 0\) \(A+\overline A = 1\)
Commutative Law \(A.B = B.A\) \(A+B = B+A\)
Associative Law \((A.B).C = A.(B.C)\) \((A+B)+C = A+(B+C)\)
Distributive Law \(A+(B.C) = (A+B).(A+C)\) \(A.(B+C) = (A.B)+(A.C)\)
Absorption Law \(A.(A+B) = A\) \(A+(A.B) = A\)
De Morgan's Law \(\overline{(A.B)} = \overline A + \overline B\) \(\overline{(A+B)} = \overline A . \overline B\)
Double Complement Law \(\overline{\overline A} = A\)

Questions

Answer

  1. Simplify \(\overline{(\overline A+B)}+\overline{(\overline A+C)}\)