Boolean Algebra

Boolean algebra is the algebra of two-valued variables (0 and 1) developed by George Boole and applied to switching circuits by Claude Shannon in 1938. Every digital circuit in this course is a physical realisation of a Boolean expression.

1. The Three Basic Operations

Precedence (highest to lowest): NOT → AND → OR. So A + B·C' means A + (B·(C')).

2. Basic Laws of Boolean Algebra

Identity and Null laws

   A + 0 = A          A . 1 = A          (Identity)
   A + 1 = 1          A . 0 = 0          (Null / Dominance)

Idempotent law

   A + A = A          A . A = A

(Unlike ordinary algebra, where A + A = 2A. There is no 2 in Boolean algebra.)

Complement law

   A + A' = 1         A . A' = 0

Involution (double negation)

   (A')' = A

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 — note the second one, it has no ordinary-algebra equivalent

   A . (B + C) = A.B + A.C            (familiar)
   A + (B . C) = (A + B) . (A + C)    (NOT true in ordinary algebra!)

Proof of the second distributive law by truth table:

Columns 5 and 8 are identical → the identity holds. ✓

Absorption law

   A + A.B = A                Proof: A + AB = A(1 + B) = A.1 = A
   A . (A + B) = A            Proof: AA + AB = A + AB = A

Absorption (second form) — the "redundancy" law

   A + A'.B = A + B           Proof: (A + A')(A + B) = 1.(A + B) = A + B
   A . (A' + B) = A.B

Consensus theorem

   A.B + A'.C + B.C = A.B + A'.C          (the BC term is redundant)
   (A + B)(A' + C)(B + C) = (A + B)(A' + C)

   Proof:  AB + A'C + BC
         = AB + A'C + BC(A + A')          [since A + A' = 1]
         = AB + A'C + ABC + A'BC
         = AB(1 + C) + A'C(1 + B)
         = AB + A'C   ✓

How to spot the consensus term: find two terms in which one variable appears complemented in one and un-complemented in the other (here A and A'). The consensus is the product of the remaining literals (B·C). That term is always redundant.

3. Summary Table of Laws

4. The Principle of Duality

Duality: interchange every AND with OR, and every 0 with 1. Variables and their complements stay unchanged. If the original expression is a valid identity, the dual is also valid.

Careful: duality is not the same as complementation. The dual of A + A'B is A(A' + B); the complement of A + A'B is A'(A + B').

5. Worked Simplification Problems

Problem 1

   F = A.B + A.B' + A'.B

   = A(B + B') + A'B          [factor A]
   = A.1 + A'B                [complement law]
   = A + A'B                  [identity]
   = A + B                    [redundancy law]

   F = A + B      (3 AND gates + 2 OR gates  ->  1 OR gate)

Problem 2

   F = (A + B)(A + B')(A' + C)

   = (A + B.B')(A' + C)       [distributive: A + BC = (A+B)(A+C) used in reverse]
   = (A + 0)(A' + C)
   = A(A' + C)
   = A.A' + A.C
   = 0 + A.C
   = A.C

Problem 3

   F = A'B'C + A'BC + AB'C + ABC'

   = A'C(B' + B) + AB'C + ABC'
   = A'C + AB'C + ABC'
   = C(A' + AB') + ABC'
   = C(A' + B') + ABC'        [redundancy: A' + AB' = A' + B']
   = A'C + B'C + ABC'

Problem 4 — using consensus

   F = AB + BC + B'D + AD

   Look at BC and B'D  ->  consensus is CD ... not present, keep going.
   Look at AB and B'D  ->  consensus is AD  <- present, and REDUNDANT.

   F = AB + BC + B'D

Problem 5

   F = (A + B + C')(A' + B' + C)(A + B + C)

   First two brackets share nothing simple; combine bracket 1 and 3:
   (A + B + C')(A + B + C) = A + B + C.C' = A + B      [distributive]

   F = (A + B)(A' + B' + C)
     = AA' + AB' + AC + A'B + BB' + BC
     = 0 + AB' + AC + A'B + 0 + BC
     = AB' + A'B + AC + BC
     = AB' + A'B + AC + BC

   Consensus check: AC and BC with A'B -> ... AB' + A'B is XOR.
   F = (A XOR B) + C(A + B)

6. Why Simplification Matters

Boolean algebra gives correct simplification but requires insight — you must spot which law to apply. The K-map (two lessons ahead) gives a mechanical procedure that never requires insight. First, though, we need to see the gates these expressions turn into.