Universal Gates — Building Everything from NAND or NOR
On this page 5 headings
Start here Imagine a LEGO box with only one kind of brick, yet you can still build anything. NAND gates are like that: with enough NAND gates, you can build NOT, AND, OR and every other circuit. Chip factories love this, because making one kind of gate again and again is cheap and fast.
A gate is universal if NOT, AND and OR (and so any circuit) can be built from it alone. NAND and NOR are both universal.
| Want | How, using only 2-input NAND | NAND gates |
|---|---|---|
| NOT A | NAND(A, A) | 1 |
| A AND B | NAND, then a NOT made from NAND | 2 |
| A OR B | NOT A, NOT B, then NAND them (De Morgan: ) | 3 |
| A XOR B | G1 = NAND(A,B); G2 = NAND(A,G1); G3 = NAND(B,G1); out = NAND(G2,G3) | 4 |
| A XNOR B | XOR, then NOT | 5 |
| Want | How, using only 2-input NOR | NOR gates |
|---|---|---|
| NOT A | NOR(A, A) | 1 |
| A OR B | NOR, then NOT | 2 |
| A AND B | NOT A, NOT B, then NOR them | 3 |
| A XNOR B | same 4-gate pattern as NAND-XOR, but with NORs | 4 |
| A XOR B | XNOR, then NOT | 5 |
Notice the mirror: NAND makes AND cheap (2) and OR expensive (3). NOR is the opposite. XOR is cheap with NAND (4); XNOR is cheap with NOR (4).
All these counts were checked by a computer search over every possible circuit. They really are the minimum.
Rule 1: an AND–OR (SOP) circuit = a NAND–NAND circuit with the same shape. Just swap every gate for a NAND.
Why? Put two “bubbles” (NOTs) on each wire between the levels. Two NOTs cancel, so nothing changes. Then the bubble becomes NAND, and the bubbles + OR becomes NAND too (De Morgan).
Rule 2: an OR–AND (POS) circuit = a NOR–NOR circuit with the same shape.
Watch out for single letters. If a product term is just one letter (like A in ), it needs a NAND used as an inverter in the NAND–NAND version.
Example: G1 = ; G2 = NAND(B, C); out = NAND(G1, G2) → 3 NAND gates.
In one line: NAND and NOR can each build every circuit (NAND: NOT 1, AND 2, OR 3, XOR 4; NOR: NOT 1, OR 2, AND 3, XNOR 4), and an AND–OR circuit turns into NAND–NAND just by swapping the gates. Exam words: universal gate, NAND-only, NOR-only, NAND–NAND realisation, NOR–NOR realisation, bubble pushing, De Morgan.