NAND is all you need
Every digital circuit you own, from a wristwatch to a data center, is built from a tiny vocabulary of gates. The surprising part is that the vocabulary can be shrunk to one word. Any Boolean function, however complicated, can be built from NAND gates alone. Chip designers call such a gate functionally complete or universal.
What NAND does
NAND is "not AND": its output is 1 unless both inputs are 1.
| A | B | NAND(A, B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
That one asymmetry, "only 11 gives 0", is enough to build everything else.
Step 1: NOT from NAND
Feed the same signal into both inputs. Then "both inputs are 1" means "the input is 1", so the output is the opposite of the input: NOT A = NAND(A, A). One gate.
Step 2: AND from NAND
AND is NAND followed by NOT, and we just built NOT: A AND B = NAND(NAND(A, B), NAND(A, B)). Two gates. In the simulator, wire the first NAND's output into both pins of a second NAND.
Try it: Practice puzzle 1, "First Spark" asks for exactly this. Two gates is the best known.
Step 3: OR from NAND
This one uses De Morgan's law: A OR B = NOT(NOT A AND NOT B). Invert each input with a NAND, then NAND the two results: A OR B = NAND(NAND(A, A), NAND(B, B)). Three gates.
Step 4: XOR from NAND, the classic
XOR is 1 when the inputs differ. The famous four-gate construction shares one intermediate signal:
M = NAND(A, B)P = NAND(A, M)Q = NAND(B, M)A XOR B = NAND(P, Q)
Why it works: M is 0 only when A and B are both 1. When A is 1 and B is 0, M is 1, so P = NAND(1, 1) = 0 and the final NAND outputs 1. When both are 0, M is 1, P and Q are both 1, and the output is 0. Check the remaining rows yourself, or let the simulator do it.
Try it: open the XOR example (built from AND, OR and NOT) and rebuild it with four NANDs, then compare truth tables. Then solve practice puzzle 2, "Mirror, Mirror".
Why anyone cares
In silicon, a NAND gate is the cheapest two-input gate to make with CMOS transistors (four of them), and a chip that uses one kind of cell everywhere is easier to manufacture and test. Flash memory is literally named after it: "NAND flash" strings its cells together in a NAND-like arrangement. NOR is universal too, for the mirror-image reasons; try building the same gates from NOR as an exercise.
Going further
Three-input parity (the "even parity" bit that detects a flipped bit in transmission) is just XOR chained twice, which means eight NANDs. That is practice puzzle 12, and it is the longest circuit in the practice set.