One gate is enough for all of digital logic.
The NAND gate is the simplest computer hardware you can hold in your head. The Builder lets you swap between gates and watch their NAND skeleton update in real time.
One tiny logic gate is enough to build every computer ever made. NAND — short for 'not-and' — outputs 0 only when both inputs are 1. Wire enough of them together, and you can compute anything that any other digital circuit can compute. Sheffer proved this in 1913, and modern chips still run on it.
NAND is just AND with the answer flipped. Look at the truth table: only one row is 0 (when both inputs are 1); the other three are 1. From that single fact: NOT a = a NAND a. Wire two NANDs and you get AND. Three give OR. Four give XOR. Everything else is composition.
Modern CPUs are physically a sea of NAND gates etched into silicon — billions of them, identical, in tidy rows. The complexity of a processor is not in the parts but in the wiring. Pick the right primitive, and everything becomes assembly.
The Sheffer stroke a ↑ b takes two binary inputs and returns one binary output. It outputs 1 in three of the four possible cases — only when both inputs are 1 does it output 0. That is literally the definition: a ↑ b = ¬(a ∧ b). The little arrow is sometimes called the Sheffer stroke, sometimes drawn as a bar (a | b). It is the same operation in every notation.
| a | b | a ↑ b |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Think of a NAND gate as a tiny suspicious guard. It only refuses (outputs 0) when both witnesses agree (a = 1 and b = 1). Any other testimony — a disagreement, a silence — and it nods through with a 1. That single distrust, repeated, is enough to compute anything.
The first miracle is NOT. Take a single NAND and wire the same signal a into both of its inputs. The result is a ↑ a = ¬(a ∧ a) = ¬a. One gate, no extras. From that moment on, anything you can build from AND, OR, and NOT — which is everything in classical logic — you can build from NAND alone, because NAND already gives you the AND part and now you have the NOT.
Tie the two inputs of a single NAND together and feed both with the same wire a. The gate sees (a, a). If a = 1, both inputs are 1, output is 0 = ¬a. If a = 0, at least one input is 0, output is 1 = ¬a. One gate, both branches verified.
| a | b | a ↑ b | ¬a | a ∧ b | a ∨ b | a ⊕ b |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 |
AND is two NANDs: first compute a ↑ b, then negate the result with one more NAND (tied inputs). OR follows from De Morgan: a ∨ b = ¬(¬a ∧ ¬b), which is exactly (a ↑ a) ↑ (b ↑ b) — three NANDs. XOR needs four, arranged like a tiny diamond. Once you see the pattern, every Boolean function becomes a directed acyclic graph of identical NAND cells. There is no other building block.
A set of Boolean operators is functionally complete if every Boolean function can be expressed using only those operators. {AND, OR, NOT} is complete — that is the standard textbook fact. {AND, OR} alone is not: you can never produce NOT from AND and OR. {NAND} alone is complete because it can produce NOT (by tying inputs) and AND (by negating its own output), and {AND, NOT} is already enough. Inductively: any Boolean function has a normal form built from AND, OR, NOT; rewrite each of those in NANDs; you are done.
A set of Boolean operators is functionally complete if every truth table on n inputs can be realised with a circuit using only those operators. Some sets work, some do not.
| {NAND} | ✓ complete | alone-complete · Sheffer 1913 |
| {NOR} | ✓ complete | alone-complete · Peirce 1880 (unpublished) |
| {AND, OR, NOT} | ✓ complete | the textbook basis |
| {AND, NOT} | ✓ complete | OR via De Morgan: ¬(¬a ∧ ¬b) |
| {OR, NOT} | ✓ complete | AND via De Morgan: ¬(¬a ∨ ¬b) |
| {AND, OR} | ✗ not complete | no way to flip a 1 to a 0 — needs NOT |
| {XOR, AND} | ✓ complete | Zhegalkin / algebraic normal form |
| {XOR} | ✗ not complete | only linear functions reachable |
CMOS — the technology behind essentially every modern chip — implements NAND with only four transistors: two p-type pull-ups in parallel, two n-type pull-downs in series. AND needs six (a NAND followed by an inverter), OR needs six as well. Every gate is cheaper as a NAND, and a NAND output can drive other NANDs without extra buffering. Photolithography then tiles billions of identical NAND cells across a wafer. The CPU you are reading this on is, at the transistor level, an ocean of NANDs.
Modern chips are CMOS — pairs of n-type and p-type transistors that pull the output high or low. NAND is the cheapest two-input gate to build.
| gate | transistors | build |
|---|---|---|
| NAND | 4 | 2 PMOS in parallel + 2 NMOS in series |
| NOR | 4 | 2 PMOS in series + 2 NMOS in parallel |
| NOT | 2 | 1 PMOS + 1 NMOS (CMOS inverter) |
| AND | 6 | NAND + inverter |
| OR | 6 | NOR + inverter |
| XOR | 12 | complex-gate (AOI) design; 16 as 4 NANDs, fewer with pass-transistor tricks |
Because NAND is cheap and alone-complete, ASIC tools often synthesise an entire circuit into NAND2 cells before placement-and-routing. The chip is, literally, a sea of NANDs.
NAND is not alone in being alone-sufficient. Charles Sanders Peirce had already noticed, in an unpublished 1880 manuscript, that NOR — written a ↓ b = ¬(a ∨ b) — is also functionally complete by itself. Sheffer rediscovered the NAND version in 1913 and published. These two are the only binary Boolean operators with this property: every other binary operator needs help. The Apollo Guidance Computer was built entirely from NOR gates; the chip in your pocket runs on NANDs. Two ways to build a universe.
NAND and NOR are the only binary Boolean operators that are each, on their own, functionally complete. NOR was first noted by Charles Sanders Peirce in a manuscript dated 1880 (published posthumously). NAND was published by Henry Sheffer in 1913, who showed it could replace the entire system of Principia Mathematica's primitives. Russell and Whitehead added a note about it in the second edition.
The Builder lets you pick a target gate and watch its NAND skeleton appear, transistor by transistor. Wire your own circuits and see them reduce to a forest of identical strokes.
→ Open the Builder