How Computers Work from the transistor up · chapter 02

02Logic Gates

Last chapter ended on a promise. Take the switch that electricity flips, and wire a few of them into something that can reason — if this and that, then…. This chapter keeps that promise, at the metal, one transistor at a time. And here's the strange, wonderful thing waiting at the end. Out of the fickle, trembling voltage we just barely tamed, we're going to build a device with a complete description. It's so small and so honest that you could write down, on a single index card, every input it will ever see and exactly what it does with each one. We'll build two of these gates for real out of transistors: an inverter, then a four-transistor part called a NAND. Then we abstract them up into clean symbols we never have to open again. And we land on the one fact that makes the entire rest of the machine possible: this single part, the NAND, is enough to build every other gate there is. No new physics beyond the switch. Just switches, wired to command switches.

01Two switches, and the pair that wastes no power

Chapter 1 left us holding one switch: a transistor whose gate voltage opens or shuts a channel between two legs. Try building a NOT with only that: wire it from the output down to ground, and a high input drags the output to 0. For the other half, let a plain resistor from the power rail pull the output up. It works, and it's awful. A resistor can't be told anything, so it's on all the time. While the switch holds the output low, that resistor bleeds the rail straight to ground, forever. You want a pull-up you can switch off. And that's the small lie of omission I left you with. Transistors come in two complementary flavours, and you need both to build anything clean. One kind — call it the N-type — conducts when its gate is high and blocks when it's low, which is exactly the switch you already met. Its mirror twin, the P-type, does the opposite: it conducts when its gate is low. It's the pull-up you just asked for. Toggle each gate below and watch them behave as perfect opposites.

N‑type: gate LOW · channel shut

P‑type: gate HIGH · channel shut

Predict first: both channels are shut. To open the N‑type you'll push its gate up. What do you think opens the P‑type — the same move, or the opposite one?

N conducts on HIGH · P conducts on LOW. Same valve, mirrored trigger — you need both to build clean logic.

Fig 1. Transistors come in two complementary flavours. The N‑type (n+ islands in a p‑type body) conducts only when its gate is pulled HIGH — the field drags electrons up to bridge source and drain. The P‑type is its mirror image (p+ islands in an n‑type body): it conducts only when its gate is pulled LOW. Same valve, opposite trigger. Neither alone can pass both a clean 0 and a clean 1 — which is why real logic is built from both at once.

Two switches, wired backwards from each other. On its own that's a curiosity. Wired together, it's the foundation of every chip on Earth.

Here's the wiring, and it's only two parts. Hang a P-type from the power rail. That's the pull-up, and its job is to yank the output toward 1. Put an N-type below it down to ground. That's the pull-down, whose job is to drag the output to 0. Tie their two gates together into one shared input, and tap the output from the joint between them. Feed in a 0: the pull-up conducts, the pull-down is shut, and the output is pulled up to 1. Feed in a 1 and they trade places, so the output drops to 0. It hands you back the opposite of whatever you give it: a NOT. This complementary pull-up / pull-down pair has a name — CMOS. Toggle the input.

Before you flip it — the gates are tied together as one input. The output is tapped in the middle. Predict: put the input high — where does the output go?

in 0→out 1

in 1→out 0

input LOW → pull-up conducts → output driven HIGH · that's a NOT

exactly one transistor is ever on: the P-type opens when the input is low, the N-type when it's high — so the output is always the clean opposite, hard-driven to power or ground.

Fig. A CMOS inverter — a NOT built from exactly two transistors. A P-type pull-up reaches for +5 V power, an N-type pull-down reaches for 0 V ground, their gates tied together as one input, and the output tapped between them. The P-type opens only when the input is low; the N-type only when it's high — so exactly one conducts at a time and the output is hard-driven to the opposite rail, never left floating. Toggle the input and watch the conducting transistor light up while the output snaps to the clean inverse. That is a NOT, in the CMOS style — and the seed of every gate to come.

Notice what the complementary pair guarantees. Exactly one of the two transistors is conducting at any instant. So the output is always firmly tied to either power or ground — never left floating, never guessing. That clean, decisive push is why the bit you read off the top stays crisp.

And there's a bonus hiding in that phrase "exactly one conducts." If only ever one of the pair is open, then there is never a straight-through path from power all the way to ground. So at rest, holding a steady 0 or 1, the gate draws almost no current at all. It only gulps power in the brief instant it switches, when both transistors are momentarily half-open as the input slides across the threshold. Toggle the input and watch the current meter: dead flat while it holds, a spike only on the flip.

It's holding a 1 right now. One transistor of the pair is switched off, so the path from 5 V to ground is broken. Guess the current — then flip it.

flips so far: 0

holding 1 — current ≈ 0

Fig. A CMOS inverter: a pull-up (P) and a pull-down (N) transistor stacked between 5 V and ground, both steered by the same input. Because the two are wired to be opposites, at rest exactly one is switched off — so the path from power to ground is broken, and the supply meter sits at zero whether the output is holding a 1 or a 0. Flip the input and watch the trace: for the instant both are half-open there's a straight path down the spine and the current spikes, then falls back to nothing. A logic gate spends energy only when it changes its mind — hold it still and it costs almost nothing, which is exactly why billions of them can share one chip.

That's the quiet reason your phone doesn't cook itself in your pocket. A billion of these gates, and each one is electrically silent unless it's actually changing its mind. Now let's wire four transistors instead of two, and make a gate that decides on two inputs at once.

02Four transistors that make a NAND

One input gave us NOT. Two inputs open up something far richer. Try the obvious one first: build an AND, output high only when both inputs are high. And here's the catch. In CMOS, the network you get to design sits underneath the output, between it and ground. All it can decide is when the output gets dragged to 0. So whatever condition you build down there, the gate hands you back its opposite. A single CMOS stage is always inverting. Plain AND is not the cheap gate at all — you'd build it by wiring a NAND and then spending two more transistors to invert it, six in total. What silicon wants to make is NOT-AND. So we're going to build the single most important two-input gate, the NAND, and we build it by asking exactly one question: when should the output be pulled down to 0? We want it low only when input A is high and input B is high. So we put two N-type pull-downs in series, stacked one on top of the other. Now current can only reach ground if both are conducting, both gates high. Then, to keep the output cleanly high the rest of the time, we mirror it: two P-type pull-ups in parallel. That way, if either input is low, at least one pull-up yanks the output up. Toggle A and B and watch which network wins.

Predict first: the output only drops to 0 when a path reaches ground. Those two N-types sit in series. How many of them must be ON for the path to complete?

input A

input B

a P-type is on · output held at +5V → OUT = 1

gold body = channel open (conducting). A P-type opens when its gate is low; an N-type when its gate is high. The ground path only lights when both series N-types are open.

Fig. A two-input NAND in four transistors — the complementary switch, scaled up. The pull-down is two N-types in series: current reaches ground only when both gates are high, so the output is dragged to 0 at exactly one input pair, A=B=1. The pull-up is two P-types in parallel: either gate going low opens a path to +5V, so the output stays at 1 for every other case. Series demands all; parallel accepts any — and the two networks are wired so that whenever one conducts, the other is shut.

Series on the bottom, parallel on top. That complementary structure is the CMOS signature again, just scaled up to two inputs. Trace it with your eye: the only way to open a clean path all the way down to ground is to switch both pull-downs on together.

That pairing — series below, parallel above — isn't a rule of thumb, and it's worth slowing down for, because it is the entire grammar of CMOS. Start from one switch. An N-type wired down to ground says "go low when this input is high." Put two of them in series and trace the path to ground with a finger: it only completes if both are on. Series means all. Now set them side by side in parallel, and either one alone completes it. Parallel means any. That is the whole dictionary. Write a condition in it and you have drawn a pull-down network. The pull-up isn't a second decision. It's forced. The output has to be high in exactly the cases where it is not being pulled low. Our pull-down goes low on "A and B", so the pull-up must conduct on NOT(A and B), and that is the same thing as (NOT A) or (NOT B). The identity has a name: De Morgan's law. Now read it back in transistors. "Or" means parallel, and a P-type is already a "not" on its own input, so either P-type will do. Series flips to parallel because AND flips to OR. Which means you can now build a gate I never built for you. Draw the NOR: it should pull down on "A or B", so that's two N-types in parallel, and the law tells you the top must be two P-types in series.

Four transistors, two inputs, four possible input pairs. That's the whole life of this gate, with nothing left to chance. Let's walk every case and read the output.

input A

input B

A=0, B=0 → a PMOS pulls the output up to +5V → 1

A	B		OUT
0	0	→	1
0	1	→	1
1	0	→	1
1	1	→	0

Only one of the four pairs turns the lamp off. Step through them and find the lone 0 — it sits at input (1,1), where both NMOS switches close a path to ground. NAND = NOT-AND.

Fig. A NAND gate at the metal — four transistors, two inputs. Up top, two PMOS sit in parallel (each conducts when its input is 0); down below, two NMOS sit in series (the chain to ground only closes when both inputs are 1). Step through all four input pairs and read the lamp: it stays lit — output 1 — for (0,0), (0,1) and (1,0), because in each of those at least one PMOS is still pulling the output up to +5V. Only at (1,1) do both PMOS shut and both NMOS close, dragging the output down to 0. That lone zero is the whole gate: NAND is NOT-AND — high everywhere except where AND would be true. (And notice: in either resting state current never runs straight from +5V to ground, which is exactly why CMOS won.)

There it is: the output is 0 in exactly one case, when both inputs are 1, and high in the other three. Four rows, and there is no fifth. That little list has a name, the gate's truth table, and we'll come back to why it's everything. "NAND" is just "NOT-AND." It's the AND you'd expect — a 1 only when both inputs are 1 — flipped upside down. Hold onto that lone 0 in the corner. It turns out to be the most powerful single entry in this whole book.

Now, we are never going to want to think about those four transistors again, and the wonderful news is that we don't have to. The instant we trust that the wiring does what we just watched it do, we can draw a box around it, give it a symbol, and forget the insides forever. This is abstraction, the single most important habit in all of engineering. Once a thing is verified, it stops being a circuit and becomes a part. Here's the same NAND collapsed to its symbol. Toggle the inputs and confirm it behaves identically.

Four transistors, once verified, collapse into one part — this symbol. Predict Y, then click A and B (on the symbol, or a row below). It answers with the exact same four rows the transistors did — that's abstraction.

A	B	Y = A NAND B
0	0	1	✓
0	1	1	✓
1	0	1	✓
1	1	0	✓

matches the transistor version, row for row

A·B = 0·0 → high unless BOTH are 1, so Y = 1

Fig 6. The same four transistors you just wired up have been black-boxed — sealed inside one symbol you never have to open again. Click A and B (or any row) and read Y: it stays high for every combination except both-inputs-1, where the bubble flips the output to 0. That's exactly the truth table the transistors produced — so we stop thinking in transistors and start thinking in NAND. Verify a part once, then trust the symbol forever: that trade is what lets you build a whole computer without drowning in electrons.

Same gate, not a transistor in sight. From here on, NAND is a LEGO brick, not a schematic.

And now the deep idea, the one that quietly separates digital logic from every other kind of engineering. The inputs can only ever be 0 or 1 — never 3.7, never a fraction, never a wobble. That isn't an assumption we're making about the physics. It's a promise the previous gate made. A gate's input is some other gate's output, and you just watched every output get slammed onto a rail, with exactly one transistor of the pair ever conducting. The two-valued world isn't found. It's manufactured, gate by gate, and that is the real moral of the last section. So a two-input gate has exactly four possible inputs, full stop. That means we can write down its entire behaviour, for all time, in a four-row table. Nothing hidden, nothing approximate, no untested case lurking. That's the truth table we met back at the transistors, and it is the complete, honest specification of the gate. Toggle the inputs to fill in the NAND's.

rows proven: 1 / 4 — flip the inputs to find the rest

A·B = 0 → NAND outputs 1

Only 0 or 1 can go in, so two inputs have exactly four combinations — and that's the whole list. Exercise all four and the table is complete: nothing about NAND is left unsaid.

Fig 7. A wire can only carry a 0 or a 1, so a two-input gate has just 2 × 2 = 4 possible inputs — and that's the entire list. Click the A and B nodes (or the toggles) to flip them: each combination lights the matching row, reveals its output, and stamps a ✓. Hit all four — 00, 01, 10, 11 — and you've written down everything NAND will ever do. That's a complete, exact specification: a luxury a real-valued function, with its endless uncountable inputs, can never have.

A real-valued function has infinitely many inputs. You can never tabulate it; you can only approximate. A binary gate has a handful, and the table is the gate, exactly and forever. That finiteness is the bedrock the entire machine gets poured onto.

03What a gate really is

Step back from the silicon for a second and name what we've actually got. A logic gate is a function. It's the same idea you met in school as f(x), a rule that turns inputs into an output. The only difference is that its inputs and its output are drawn from just the set {0, 1}. And it is perfectly deterministic: give it the same inputs and it returns the same output every single time, with no mood, no memory, no drift. Feed this gate the same pair a hundred times and watch it never once disagree with itself.

A gate has no dice inside and no memory. Set A and B, predict Y, then hit Run again and again. Watch the disagreement count.

0 runs — predict Y, then Run

Fig 8. A logic gate is a function on {0,1} — it maps a pair of bits to one bit, and that map is fixed. Pick a gate, set A and B, then hammer Run: every chip on the tape drops the same colour, the run count climbs into the dozens, and the disagreement tally stays nailed to 0. No dice, no drift, no memory of the last run — the hundredth press answers exactly like the first. That perfect repeatability is the whole reason a billion of these can stack into a computer: change an input and you ask a new question, but ask the same question and a gate can never change its mind.

That reliability sounds boring. It is the exact opposite of boring. It's the property that lets us stack a billion of these and still trust the answer that pops out the top. Determinism is what makes the whole tower stand up.

So how big does the truth table get? One input, two rows — just 0 and 1. Two inputs, four rows. Three inputs, eight. Every input you add doubles the number of rows, because each new wire can be 0 or 1 independently of all the others. That's 2ⁿ combinations for n inputs, the very same doubling that filled up a byte last chapter. Slide the input count and watch the table grow.

possible combinations

2² = 4

rows in the table

each wire doubles it

1 input→×22

2 inputs→×24

3 inputs→×28

4 inputs→×216

number of inputs (drag — watch every row split in two)

2 inputs, each 0 or 1 → 4 rows

Add a wire and the whole table you had is copied twice — once beneath a new 0, once beneath a new 1. It grows fast, but it's always a finite list.

Fig. Drag the slider from 1 input upward. Each new wire is independently a 0 or a 1, so it copies the entire table you already had — once under a fresh 0, once under a fresh 1 — and the row count doubles: 2 → 4 → 8 → 16. That's why n inputs give exactly 2ⁿ combinations, the same doubling that filled a byte (8 wires → 256 rows). It grows fast, yet it's always a finite list you could write out in full.

It grows fast, but it always stops. However many inputs, the behaviour still fits in a finite table you could, in principle, print on paper. Now let's meet the family, each gate defined by nothing more than its truth table.

First the AND: output 1 only when both inputs are 1. It's the gate that means "both." Tilt your head and it's also the minimum of the two bits, and the intersection of two sets. That's one idea wearing three different hats. Toggle the inputs.

Before you flip them — of the four combinations, which single one lights the output?

not both 1 → output 0

logic · and

0 ∧ 0 = 0

arithmetic · minimum

min(0, 0) = 0

sets · intersection

A ∩ B = ∅

Watch the three tiles agree, always. Logical and, the minimum of two bits, and set intersection are not three facts to memorise — they're one operation wearing three costumes.

Fig. The AND gate — the demanding one. Flip the two inputs and the output lamp stays dark until both read 1. The same click ripples through three readings that never disagree: logical A ∧ B, the minimum of the two bits, and the intersection of two sets. One operation, three costumes — that's the whole trick.

"Both." Now its mirror. The OR: output 1 when either input is 1. It's the gate that means "either." It's the maximum of the two bits, and the union of two sets. Toggle it.

The OR gate is the mirror of AND: it outputs 1 when either input is 1 — it only stays 0 when both are 0. Toggle the two inputs and watch the lamp.

0 OR 0 → 0 · both off, so the light stays dark

Fig. The OR gate — “either.” Flip the two inputs (click the pads or pick a row): the lamp lights the instant either A or B is 1, and goes dark only in the single case where both are 0. That one fact wears three costumes at once — it's logical-or (either one), it's max(a, b) (the larger of the two bits), and it's set union (an element is in A ∪ B if it's in either set). It is the exact mirror of AND: where AND demanded both, OR is satisfied by one.

"Either." Two gates in, and we are standing in boolean logic — the algebra of true and false. That's because 0 and 1 are quietly doing double duty as false and true. Binary numbers and boolean truth values are the same substrate. Read one wire twice, once as a number and once as a truth, and it's the same voltage both times. A wire has no idea which one you meant, and it doesn't need to. But notice what these two can never do. Feed nothing but 0s into any pile of ANDs and ORs, wired any way you like, and no 1 will ever come out the far end. Hold on to that.

One more, and it's the interesting one. The XOR — exclusive-or — is 1 when the inputs are different, and 0 when they're the same. Not "either" but "either, but not both." Toggle it and watch for the pattern.

inputs match · out = 0

A	B		OUT
0	0	→	0
0	1	→	1
1	0	→	1
1	1	→	0

the odd one out: XOR fires only when the inputs disagree — either, but not both. Hold that pattern; it's the sum bit when you add two binary digits.

Fig 12. The XOR gate — the family’s odd one out. Its output goes high only when its two inputs disagree: 0&1 or 1&0 light it, while 0&0 and 1&1 leave it dark. Read it as “either, but not both.” Toggle A and B and watch the lamp track the same/different pattern rather than any single input — that exact behaviour is the sum digit when you add two bits (0+1=1, but 1+1=0 with a carry), which is why XOR sits at the heart of binary addition.

XOR is the odd one out of the family, and I want you to keep it in the corner of your eye. A few chapters from now, when we build an adder, XOR turns out to be addition in disguise. For now, just log it: it means "different."

That's four of the six gates we'll use in this book. The other two are just inversions: NAND is AND flipped (we built it from four transistors), and NOR is OR flipped. And six is not how many gates there are — it's barely how many got names (XNOR, XOR flipped, is a seventh). Two inputs give four rows, and each row's output is a free bit you could set either way, so there are 2⁴ = 16 different two-input gates in all. Most of them never got a name. They're perfectly real, just unloved. Here's the whole family on one panel, six gates fed by the same two switches. Flip the switches and watch all six answer at once — same inputs, six different verdicts.

A 0 · B 0 — one input pair, six verdicts

Before you flip, predict one card. Then flip a switch and watch all six answer the same two inputs at once — that's the whole gate family in one glance.

NAND is just AND flipped; NOR is just OR flipped. NOT ignores B entirely — it only ever has one input.

Fig. Six gates, one pair of switches. Flip A and B and every card answers the same two inputs at once — NOT hands back the opposite (and ignores B, because it only ever takes one input), AND lights only when both are 1, OR when either is, XOR only when they differ. The bottom two are the top two turned inside out: NAND is AND inverted, NOR is OR inverted. Each gate is nothing more than a lookup table — four rows for the two-input gates, two for NOT — the switches just pick which row you're standing on, and six different verdicts light up side by side.

Six little functions, each one completely captured by its lookup table — four rows for the two-input gates, two for NOT. It feels like you'd need every one of them in your toolbox to build a computer. You don't. As it happens, you need exactly one.

Before I tell you which one, pick your own champion. If exactly one gate survives and everything else has to be rebuilt out of copies of it, which do you keep? Most people reach for AND. Watch AND fail. Tie its two inputs together so they're always the same bit: feed it 0 and out comes 0, feed it 1 and out comes 1. AND(x, x) = x. The gate handed your bit straight back, unchanged. And that isn't a quirk of tying the inputs. An AND only ever says 1 when it is fed a 1, so wire a million of them into any shape you like, feed the whole thing 0s, and every wire inside it stays 0. A NOT is not merely hard to reach that way. It is unreachable, forever, and the whole family goes with it. So that's the real bar for a universal gate. It has to be able to flip.

04One gate to build them all

So keep the flip and you keep everything. And that is exactly what NAND is: an AND with the inversion already welded onto it, where one wire is all it takes to set the flip loose. Here's the punchline the whole chapter has been walking toward, and it still startles me every time: every gate you just met can be built out of NAND alone. Not "in principle," not "if you squint" — literally, by wiring NANDs together. We call NAND universal because of it. It's why a real chip isn't a zoo of different parts but a vast, repeating sea of one part. Let's prove it, starting with the easiest. Tie a NAND's two inputs together so they're always the same bit, and a NAND becomes a NOT. Feed it 0, both inputs read 0, and NAND says 1. Feed it 1, both read 1, and NAND says 0. Toggle it.

A = 0 → NAND(0,0) = 1 → the output is the opposite: a clean 1

A	A	Y
0	0	1
0	1	1
1	0	1
1	1	0

NAND only outputs 0 when both inputs are 1. Tie the two inputs together and the middle two rows can never happen — only the top and bottom survive, and 0→1, 1→0 is exactly a NOT gate.

Fig. Wire a single line into both of a NAND's inputs and it stops being a two-input gate — because the inputs are always equal, only the 0,0 and 1,1 rows can ever happen, and NAND turns those into 1 and 0. That is a NOT gate, recovered with nothing but one NAND and a piece of wire — the first hint that NAND alone can build everything. Click the input and watch the output come out inverted.

NOT, from one NAND. That alone is a big deal. It means we've recovered the inverter without any of the P-type-on-top wiring, just by reusing the part we already have.

AND is almost a joke now. NAND is literally "NOT AND," so to get plain AND we just need to un-NOT it. Feed A and B into a NAND, then feed that result into a second NAND wired as a NOT. NAND, then invert, and the double negative lands you right back on AND. Toggle A and B.

OUT = 0 — the double negative lands on plain AND

A	B	N1 = NAND	OUT = AND
0	0	1	0
1	0	1	0
0	1	1	0
1	1	0	1

NAND is NOT-AND: it does AND, then flips it. The second NAND — both inputs tied to the same wire — is just an inverter, so it flips it back. Two NOTs cancel, and what's left is the AND you wanted all along.

Fig. Two NANDs make an AND. A NAND is just AND with the answer flipped — NOT-AND. Feed its output into a second NAND with both inputs tied together, and that second gate is simply an inverter: it flips the answer back. The two flips cancel, and the double negative lands you exactly on plain AND — OUT is 1 only when A and B are both 1. Toggle the inputs and watch the NOT-AND on the middle wire un-NOT itself at the far right.

Two NANDs, one honest AND. The pattern is emerging: a NAND followed by a NAND-inverter undoes the inversion and leaves you the gate hiding underneath.

OR takes a cleverer move, and it's a genuinely beautiful one: it's De Morgan's law made physical. You have met this law already. It's the one that stood two P-types in parallel over our NAND's pull-down. You have built it in silicon. Now build it in wiring. The trick is to invert both inputs first, then NAND them. Watch why it works. A NAND of (NOT A) and (NOT B) is true unless both inverted inputs are true — that is, unless both A and B are 0. And that is exactly "A OR B." Three NANDs: one to invert A, one to invert B, one to combine. Toggle A and B and check it against "either."

Two NANDs flip A and B; the third NANDs the flips together. Predict the output before you toggle.

A	B	¬A	¬B	OUT = A OR B
0	0	1	1	0
0	1	1	0	1
1	0	0	1	1
1	1	0	0	1

both off — neither line is on → OUT 0

Fig. Feed A into a NAND with itself and it comes out flipped; do the same to B. NAND those two flipped wires together and — by De Morgan's law, NOT(¬A AND ¬B) = A OR B — the output is a perfect OR: it lights whenever either input is on. Toggle A and B (click the buttons or the input dots) and watch the third gate track the OR column exactly. AND and OR aren't different animals; they're the same gate viewed through inversions.

That's not a coincidence you have to memorise. It's a law — De Morgan's — telling you that ANDs and ORs are the same shape seen through a set of inversions. Flip the inputs, flip the output, and an OR becomes an AND. NAND sits right at the crossroads of both, so it can play either role on demand.

Now the hard one: the odd gate, XOR, "different." Don't start from the wiring. Start from the words: either, but not both. Written out, that's (A OR B) AND NOT(A AND B) — an OR, an AND and a NOT, and you have already built all three out of NANDs. So XOR needs no new idea. The classic circuit is that same build, squeezed: four NANDs. The first derives a signal the middle two share, those two produce the intermediates, and the fourth combines them into "A and B disagree." Step through it and watch the value ripple to the output.

beat 0 / 4 — inputs are set, the four NANDs are still dark. Press Step ▸.

A0 B0 → 0A0 B1 → 1A1 B0 → 1A1 B1 → 0

Predict before the last beat: A=1, B=0 — will N4 come up 1 or 0? XOR fires only when the two inputs disagree.

Fig. XOR is the awkward one — "output 1 only when A and B differ" — and it falls out of just four identical NANDs. Set A and B, then press Step ▸ to let the value ripple forward beat by beat: N1 = NAND(A,B) settles first and feeds the middle pair; N2 and N3 settle next; N4 = NAND(N2,N3) settles last and is the XOR. Green wires carry a 1, blue a 0; a gate stays dark until its inputs are ready. Try A=1,B=1 versus A=1,B=0 and watch the last beat land on 0 (they agree) or 1 (they disagree) — the whole idea of "different" built from one repeated switch.

Four identical parts, and out the far end comes "different" — the very gate that will, before long, become the sum bit of binary addition. Now let's be exact about what we have shown and what we haven't. We have built four gates out of NAND, and four is not all. The claim on the table is much bigger: NAND is enough for every gate there could ever be. A handful of examples cannot carry a claim that size. One more move can.

Here is the move, and it costs one idea. Take any truth table at all — invent one, three inputs, eight rows, and fill the output column however you like. Now look only at the rows where you wrote a 1. Say one of them is A=1, B=0, C=1. You can write an AND that fires on that row and no other: A AND (NOT B) AND C. Every other row disagrees with it somewhere, so every other row gives that term a 0. Do the same for each of your 1-rows, then OR all the terms together. The result is 1 on exactly the rows you marked and 0 everywhere else. That is your table, rebuilt from scratch. The technique is called sum of products, and look at what it spent: NOT, AND, OR. Nothing else, ever, for any table. (The one table with no 1-rows to gather is the gate that always answers 0. Feed an AND both x and NOT x and you have it.) So every gate that could exist, at any number of inputs, named or not, is reachable with NOT, AND and OR. And you have just built all three out of NANDs. That's the proof, and now the word is earned: NAND is enough. One part, stamped out, and the entire zoo comes back.

But don't take my word for the truth tables. Check them. Pick any target gate below. The widget rebuilds it from NANDs only and lays its truth table right beside the real one, row for row. If a single row disagreed, the whole edifice would fall. Try each one.

NOT a = a NAND a

A copy sewn only from NANDs — will its table match the real gate on every row?

2 / 2 rows identical

The right column is computed by running the NAND wiring — not copied. It lands on the reference every time. That's a proof.

Fig. Pick a target — NOT, AND, OR, XOR — and it is re-grown from nothing but NAND gates. Toggle a and b to trace one row live through the wiring; the right-hand column of the table is computed by running that NAND network, never copied from the reference. It matches every single row. That row-for-row agreement is the proof: NAND is universal — one gate is enough to build them all.

Every row matches, every time. That's the whole difference between a story and a proof. The tables are identical because the circuits compute the same function, and the function is all a gate is. And it's worth tallying the price, because the ladder comes out almost poetic.

NOT = 1 NAND

One NAND with both inputs tied together already inverts. The cheapest gate on the ladder — a single part.

Notice what never changes: the part. Every gate above is the same NAND block, copied 1, 2, 3, or 4 times. Learn one gate at the metal and you own the whole family.

Fig. One currency for the whole family. Pick a gate — or climb the ladder — and watch its price appear in a single unit: the NAND. NOT costs 1, AND costs 2, OR costs 3, XOR costs 4, and nothing else ever changes but the count. These are the standard minimal two-input NAND builds (De Morgan does the heavy lifting), and they're why a chip needs to fabricate only one kind of gate perfectly: master the NAND at the metal and every other gate is just copies of that one part.

NOT costs one NAND, AND costs two, OR costs three, XOR costs four. Every gate in the family, priced in a single currency. One currency. One part. So step all the way back and look at what that buys us.

One part — four transistors wired into a NAND — plus a fistful of ways to wire copies of it together, and you can build any gate, and (we'll see) any circuit, and (much later) the whole computer. That's why a chip photographed under a microscope looks like a sprawling city grid. It's the same tiny block, stamped out millions of times over, wired into different patterns. Here's that idea in one picture.

toggle inputs: — identical blocks, real logic

zoom out — how much of the chip you see

XOR = 4 NANDs — same block, wired four ways.

showing 36 identical tiles · ≈ one 1970s logic chip

Fig. Every gate on the left is built from one part and one part only — the identical NAND block, wired a different way each time (NOT needs 1, XOR needs 4). Toggle A and B and the real logic falls out; the blocks never change, only the wiring between them does. On the right, that same tile is stamped out across the die — zoom out and a handful becomes a controller becomes a chip holding billions of the exact same block. A chip isn't a clever part repeated cleverly; it's one dumb part, repeated relentlessly, and all the intelligence lives in the wiring.

And that's Chapter 2: you built logic out of switches. You wired two transistors into a NOT that wastes no power, four into a NAND, and learned to read any gate's whole soul off a four-row truth table. You met the family — AND, OR, XOR, NOR — and then watched that family collapse back down into a single universal part. Every gate here has been trivially dumb and perfectly predictable: same inputs, same output, no surprises, ever. But hold that thought, because it's about to break in the best possible way. Feed one gate's output into another gate's input, and then another, and the behaviour doesn't just add up. It explodes into something none of the parts could do alone. The whole machine is hiding inside a single word: composition. Next chapter, we start chaining.

‹ prevThe Switch next ›Composing Gates

iolinked.com

Written by Ajai Raj