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 and then a four-transistor part called a NAND, and then 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, because a resistor can't be told anything and so is 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.

Two switches, wired backwards from each other. On its own that's a curiosity, but 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.

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.

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, but 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, and 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.

You just watched four transistors decide, and the verdict hung entirely on their arrangement. The two pull-downs sat in series, so ground was reachable only when both switched on. The two pull-ups sat in parallel, so either one alone could pull the output high. Strip the silicon away and that is just a plumbing fact about switches. Flip the plain switches below and trace the single current path with your finger.

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.

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, because 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.

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 but 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.

Picture a function on ordinary numbers: its input dial slides through endless values, so no table could ever hold it and you only ever approximate. A gate is the opposite kind of animal: it takes a handful of inputs, so the table is the gate — exact, complete, and true forever. That finiteness is the bedrock the whole 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 — the same idea you met in school as f(x), a rule that swallows inputs and hands back one output. The only twist is the alphabet: every input and the output is 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 — no mood, no memory, no drift. Feed this gate the same pair a hundred times and watch it never once disagree with itself.

That reliability sounds boring. It is the exact opposite of boring, because 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 give four rows, and three give 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.

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.

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

"Either." Two gates in, and we are already 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. A number and a truth value are the very same bit. Read one wire twice, once as a number and once as a truth, and it is the identical voltage both times. The wire has no idea which you meant, and it never needs to. But notice the one thing these two gates can never do: feed nothing but 0s into any pile of ANDs and ORs, wired however you like, and no 1 will ever crawl 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.

XOR fired whenever its two inputs disagreed, but chain several of them in a row and a deeper pattern wakes up. Does the output care how many inputs are on, rather than which particular ones? Flip a single bit and predict the result before you look. This little chain is the parity bit that guards real data against one flipped wire.

XOR is the family's odd one out, and I want it parked in the corner of your eye. A few chapters from now, when we build an adder, this quiet "different" detector turns out to be addition wearing a disguise. For now, one word to log: 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.

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, but 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, because 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.

You just made a NOT by tying one NAND's two inputs together. That is the first brick, and the rest are yours to lay. Can you coax a plain AND out of NANDs alone, and what about OR? Wire the blocks below yourself, predict each row of the truth table, then run it. If your circuit lights the very same rows as the target gate, you have proven it by hand.

NOT, from one NAND. That alone is a big deal, because 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, because NAND is literally "NOT AND": 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.

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."

That OR worked because of a law we only stated. Now feel it. Take an AND with an inversion bubble on its output and push the bubble through the gate. The body flips to OR, a bubble pops onto each input, and the symbol becomes a completely different drawing. Keep your eye on the four-row truth table the whole time, because not one bit of it changes.

That's not a coincidence you have to memorise but 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.

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, but 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, and 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.

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 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.

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.