De Morgan's Theorems
De Morgan's theorems are the two most-used identities in all of digital design — they are what let a designer build any circuit out of only NAND gates or only NOR gates.
Theorem 1: (A + B)' = A' . B' "NOR = bubbled AND"
Theorem 2: (A . B)' = A' + B' "NAND = bubbled OR"In words: the complement of a sum is the product of the complements; the complement of a product is the sum of the complements.
Proof by Truth Table
Theorem 1: (A + B)' = A'·B'
| A | B | A+B | (A+B)' | A' | B' | A'·B' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Theorem 2: (A·B)' = A' + B'
| A | B | A·B | (A·B)' | A' | B' | A'+B' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Both pairs of highlighted columns match → both theorems proved. ✓
Generalised Form (n variables)
(A + B + C + ... + N)' = A' . B' . C' ... N'
(A . B . C . ... . N)' = A' + B' + C' + ... + N'The Graphical Meaning — Bubble Pushing
Bubble-pushing rule: you may push a bubble (inverter) through a gate provided you change the gate shape — AND becomes OR, OR becomes AND — and bubbles appear on all the other terminals.
How to Complement a Whole Function
Method: apply De Morgan repeatedly. Shortcut: take the dual of the expression, then complement every individual literal.
F = A.B' + C.D'
Step 1 (dual): (A + B')(C + D')
Step 2 (complement
each literal): (A' + B)(C' + D)
F' = (A' + B)(C' + D)
Verify with De Morgan directly:
F' = (AB' + CD')' = (AB')'.(CD')' = (A' + B)(C' + D) ✓Worked example 2
F = A + B'C + (D + E')F' [F here is also used as a variable name inside — rename output to Y]
Y = A + B'C + (D + E')G'
Y' = A' . (B'C)' . [(D + E')G']'
= A' . (B + C') . [(D + E')' + G]
= A' . (B + C') . [(D'E) + G]Universality — the practical payoff
Because of De Morgan, NAND alone and NOR alone are each functionally complete — every Boolean function can be built from just one of them.
Using only NAND:
NOT A = A NAND A
A AND B = (A NAND B) NAND (A NAND B)
A OR B = (A NAND A) NAND (B NAND B) [by De Morgan]
Using only NOR:
NOT A = A NOR A
A OR B = (A NOR B) NOR (A NOR B)
A AND B = (A NOR A) NOR (B NOR B)Why manufacturers care: in CMOS, NAND and NOR are simpler and faster than AND and OR (an AND gate is literally a NAND followed by an inverter). Designing with a single gate type also means one standard cell, one mask, one test procedure.
Converting SOP to All-NAND (the exam procedure)
F = AB + CD
Step 1: draw as AND-OR (2 AND gates feeding 1 OR gate)
Step 2: place two bubbles on every internal line (double negation = no change)
Step 3: the AND + bubble becomes NAND;
the OR with bubbled inputs becomes NAND (De Morgan)
F = ((AB)' . (CD)')' <- three NAND gates, two levelsConverting POS to All-NOR
F = (A + B)(C + D)
F = ((A + B)' + (C + D)')' <- three NOR gates, two levelsCommon Mistakes
| Wrong | Right | Why |
|---|---|---|
| (A + B)' = A' + B' | (A + B)' = A'B' | The operator must flip |
| (ABC)' = A'B'C' | (ABC)' = A' + B' + C' | The operator must flip |
| (A')' = A' | (A')' = A | Involution |
| Complement = dual | They differ: dual keeps literals as they are | Dual only swaps AND/OR and 0/1 |
Quick Practice
1. Simplify: ((A + B)' + (AB)')'
= (A'B' + A' + B')' [De Morgan on both]
= (A' (B' + 1) + B')' [not needed — A'B' is absorbed by A']
= (A' + B')'
= A.B
2. Simplify: (A' + B)' + (A + B')'
= A.B' + A'.B
= A XOR B
3. Express F = A'B + AB' using NAND only:
A XOR B = ((A(AB)')' ((AB)'B)')' -> four NAND gatesDe Morgan's theorems tell you how gates relate. The next lesson looks at the gates themselves — symbols, truth tables and real ICs.