Functional completeness: NOT, AND, OR from NAND — NAND gate
corewhy one gate type suffices
Answer
3 NAND gates realising B + A
Why this example is worth doing
The proof that NAND alone can build everything: tie the inputs for NOT, invert the NAND for AND, and invert both inputs for OR. Since every Boolean function has a sum-of-products form built from those three, NAND is functionally complete. The page gives the gate counts, which are what actually matter in a design exercise, and links to the universal gates page for the full conversion table including XOR.
Try your own input in the NAND gate. Truth table, symbol and algebraic form for (A·B)′, the universal gate.
How the answer is reached
Gate list
| Node | Gate | Inputs |
|---|---|---|
| g1 | nand | A, A |
| g2 | nand | B, B |
| g3 | nand | g1, g2 |
NAND-only realisation
A ↑ A ↑ (B ↑ B)B + A— 3 NAND gates, verified by reading the network back out.
Truth table
| # | A | B | A ↑ A ↑ (B ↑ B) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 1 |
| 3 | 1 | 1 | 1 |