Logic basics
Why NAND can build every other gate
Give an engineer an unlimited supply of NAND gates and nothing else, and they can build any digital circuit there is. This page explains why that is true, without spoiling the fun of finding the wiring yourself.
What “universal” means
A logic function takes some bits in and gives some bits out. With two inputs there are exactly 16 different functions, because a truth table has four rows and each row can be 0 or 1 (24 = 16). AND, OR, XOR, NAND and NOR are five of them. The rest include “always 0”, “just copy A”, “A but not B” and so on. With three inputs there are 256, with four there are 65,536, and the count keeps exploding from there.
A set of gates is functionally complete (or universal) if you can wire copies of them together to make every one of those functions, for any number of inputs. NAND alone is such a set. So is NOR. Most other single gates are not.
Step one: every truth table is an OR of ANDs
Pick any truth table, however large. Look only at the rows where the output is 1. Each of those rows describes one exact situation, such as “A is 1 and B is 0 and C is 1”. You can recognise that situation with an AND of the inputs, inverting the ones that must be 0. The output is 1 exactly when one of those situations is happening, which is an OR of all the recognisers.
| A | B | C | Q |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
For the table above, Q is 1 in two rows, so Q = (¬A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ ¬C). This recipe is called the sum of products or disjunctive normal form. It is rarely the smallest circuit, but it always works, and that is all a proof needs. So AND, OR and NOT together are universal.
Step two: NAND can stand in for all three
The second half of the argument is that NOT, AND and OR can each be made from NAND gates. Once you have those three, step one does the rest, and the whole tower of a computer follows.
We won’t draw those three circuits here, because finding them is how the game begins and it is a genuinely nice “oh!” moment. Two clues:
- NAND is AND with an inversion attached. If you had a way to cancel an inversion, you would be most of the way to AND.
- De Morgan’s laws link AND and OR through inversion:
¬(A ∧ B) = ¬A ∨ ¬Band¬(A ∨ B) = ¬A ∧ ¬B. Read the first one slowly: a NAND is an OR of inverted inputs.
Why AND, OR or XOR can’t do it alone
It is just as interesting to ask why most gates are not universal. In 1941 the logician Emil Post answered the question completely. A set of gates is universal exactly when, for each of the following five properties, at least one gate in the set breaks it:
| Property | Meaning | Gates trapped by it |
|---|---|---|
| Keeps 0 | All-0 inputs always give 0 | AND, OR, XOR |
| Keeps 1 | All-1 inputs always give 1 | AND, OR, XNOR |
| Monotone | Turning an input on never turns the output off | AND, OR |
| Linear | Built only from XOR and constants (each input either always flips the output or never matters) | XOR, XNOR, NOT |
| Self-dual | Inverting every input inverts the output | NOT |
Every circuit made from gates that share one of these properties has that property too. Wire AND and OR gates together any way you like and the result is still monotone, so it can never invert anything. A pile of XOR gates stays linear, so it can never compute AND. NAND breaks all five at once: two 0s give 1, two 1s give 0, turning an input on can switch the output off, it isn’t linear, and it isn’t self-dual. That is the whole secret of its universality, and NOR breaks all five in the same way.
Constants matter too. With a steady 1 available, XOR can invert (A XOR 1 = NOT A), which is why the full statement of Post’s theorem treats constants carefully. NAND doesn’t need any. A circuit of nothing but NANDs is self-sufficient.
Is it efficient?
“Can” and “should” are different questions. A NAND-only circuit is sometimes a little larger than one made from a richer set of gates. In real chips that doesn’t matter much, because in CMOS a NAND is about as cheap as a gate gets (see what a NAND gate is). It also turns into a game: every circuit has a smallest known NAND count and a shortest delay, and squeezing a design down to them is a satisfying puzzle in its own right.