03Composing Gates

Last chapter ended on a promise that sounds almost too big. A single gate is trivially dumb. You can write down every input it will ever see on a scrap of paper, and yet the whole machine is hiding inside these dumb little parts. The trick isn't a smarter gate, because there is no smarter gate. The trick is composition: feed one gate's output into another gate's input, and then do it again, and again, until behaviour that no single gate could produce simply appears. But composition on its own would just bury us in a tangle of wires we can't reason about, which is why this chapter is really about two ideas that travel together. First, chaining: how a pile of gates becomes a circuit with its own single truth table. Second, the escape hatch that keeps the tangle from swallowing us: if two circuits share a truth table, they are the same circuit. Once you trust one, you can seal it inside a box and never look in again. We'll earn both by building the single most reused block in the entire course: a circuit that, given two data lines and one control wire, actually chooses. Watch for it. This is where gates stop being logic puzzles and start being a machine.

01Wiring one gate into the next

Here's the whole seed of the chapter in one sentence. A gate's output is just a voltage on a wire, and a gate's input is just a voltage on a wire too. So nothing stops you from running the output of one straight into the input of the next. That's it. No new part, no special connector — you already have everything. Let's do the smallest possible version and feel it work. Below are two gates in series: an AND feeding a NOT. Flip the two switches on the left and watch the signal travel: it runs through the first gate, down the middle wire, into the second, and lights the output on the right.

Notice the middle wire, the one between the two gates. It isn't an input you control, and it isn't the final answer: it's an internal signal, computed by the first gate and used by the second. That intermediate wire is the essence of composition, and it's also exactly the thing we're about to learn to stop worrying about.

Because here's the shift. From the outside, nobody cares that there are two gates in there: you hand in two bits and get one bit back. That relationship, all four rows of it, is a single truth table, like any gate has. The tangle is a function. Toggle the inputs again below, but this time watch the table fill itself in — each combination you set lights up its own row.

So the two-gate chain has collapsed, in our heads, into one box with one table. That collapse is the one move we will make over and over, all the way up, and the rest of this chapter is really just learning to trust it enough to build cities out of it.

02A worked build: NAND from AND and NOT

Let's make that first composition earn its keep, because the chain you just wired isn't a toy. Work out its column before we name it. An AND outputs 1 only when both inputs are 1, and hanging a NOT on its output flips that answer over. So the chain reads 0 only when both inputs are 1, and 1 the rest of the time. Three ones and a zero, with the zero sitting in the one corner where both inputs are high. Where have you seen that column before? It's a famous gate: that's NAND, short for "not-and", the very gate the last chapter called the universal brick, and here we are building it out of two plainer parts we already trust. Look at the anatomy first.

The claim is bold: this two-gate contraption is indistinguishable from a NAND. Not similar. Identical, on every input. The only honest way to check a claim like that is to check every row, and with two inputs there are only four. So let's build both truth tables at once: the composed AND-then-NOT goes on one side, a real NAND on the other. But before you toggle anything, ask the question a saboteur would ask: could this thing match on all four rows today and betray us tomorrow?

Only if something in there remembered. That's the whole risk, so let's kill it. Last chapter we hammered a single gate a hundred times and it never once disagreed with itself: no dice, no memory, no drift. A gate's output depends on the voltages sitting on its pins right now, and on nothing else. Now trace our chain: A and B into the AND, the AND into the NOT, the NOT to the lamp. The signal only walks forward, and nothing loops back, so every gate in there is answering to this instant only, and the whole tangle answers to this instant only too. That property has a name — a forward-only circuit like this one is combinational — and it's what turns counting into proving. Two inputs means four possible situations, ever, which means the list of four isn't a sample of the behaviour. It is the behaviour. One honest flag for later: memory will break this rule, and it breaks it in exactly one way, by feeding an output back into an input so a circuit can see its own past. No loops here. Toggle the inputs and watch the tables fill.

Four rows settled it, and that is worth a second look. The proof was complete only because there were four rows to walk. Two inputs give four and three give eight, because add one input and the whole table doubles. So before we lean on exhaustive checking forever, ask the honest question: how far does walk every row actually carry us?

Row for row, they agree. But agreement across a whole table is worth slowing down for, so let's not just toggle randomly. Let's march through all four combinations deliberately, one beat at a time. Watch the AND settle, the NOT flip it, and the NAND on the far side land on the exact same bit.

Four rows, four matches, no exceptions. We didn't take NAND on faith this time: we manufactured it from an AND and a NOT, and then proved the forgery is perfect. Which raises the question the whole next section is built on: if a homemade circuit matches a real gate on every row, in what sense is it a forgery at all?

03Same table, same gate

Name one measurement a gate downstream could make to spot the impostor. Every probe you propose is a probe of the output voltage, and by construction that voltage agrees. A gate downstream has one sense organ: the voltage on its input pin. There is no second pin labelled "how were you made." The difference has no channel to travel down, so there is nothing to catch, because no organ exists that could catch it. That's the law, and you just derived it: behaviour, not structure, is identity. Two circuits are the same circuit if and only if they have the same truth table, no matter how differently they're wired inside. Our AND-plus-NOT and a factory NAND are not "equivalent for our purposes." They are the same gate. One limit, banked now and paid before this chapter ends: that argument proved the output value agrees, never when it agrees. Put them side by side, drive both from the same switches, and try to catch them disagreeing.

You couldn't catch them out, because there's nothing to catch: they compute the same function. But one match could still be a fluke of NAND. So take a classic case that looks like it shouldn't work: "not (A and B)" versus "(not A) or (not B)." One is an AND with an inverter after it. The other is two inverters with an OR. Different parts, different count, different shape. Before you touch the widget, commit to an answer: do those two match on all four rows, or is there a row where they part? Say which, then check.

All four rows agreed. Different shape, different parts, same table, so the law wasn't a fluke of NAND after all. That the two match is a real theorem, and engineers call it a De Morgan equivalence. But the point for us isn't the name, it's the license: if two circuits share a table, you may swap one for the other anywhere, inside any larger machine. Nothing downstream can read a different 0 or 1 because of it. Let's prove that license is safe. We'll drop an equivalent circuit into the middle of a bigger one and confirm the final output never so much as twitches.

The output held. That swap-without-consequence is the whole reason we're allowed to think in boxes instead of wires, and, by the end of the chapter, the licence to trade a slow circuit for a faster one that means exactly the same thing. Now let's put you in the driver's seat. Here's a target truth table, and here are a few gates: wire something, anything, that produces that table. The widget will tell you the instant your circuit becomes equivalent to the goal.

However you got there, if the table matches, you're done — there's no "more correct" answer hiding behind it. That confidence is exactly what we need for the next step, because we're about to build something with real moving parts, and we'll want to trust it completely before we seal it away.

04A circuit that chooses

Everything so far has been logic: and, or, not. Now we build the first thing that feels like a machine, a circuit that chooses. The goal is simple to say. We want two data lines, call them A and B, and one control wire, call it C. We want the output to be A when C says so, and B when C says otherwise. A wire that steers data. To get there, we need to notice something we already have, and it has been sitting in the AND table since last chapter. You've always read that table by rows: two inputs in, one answer out. Read it by columns instead. Cover the rows where A is 1: with A held at 0, the output column reads 0, 0. Dead, whatever B does. Now cover the rows where A is 0: with A held at 1, the output column reads 0, 1, and that is B's column, copied verbatim. Nothing new was added. Only the reading direction changed. So the AND earns a second name, borrowed from plumbing: it is a valve. Hold one of its legs at 0 and the output is stuck at 0 no matter what the other leg does — the pipe is shut. Open that leg to 1 and the output simply copies the other leg — the pipe is open. One honest note: the AND has no idea which leg is control, because it is symmetric, and its table marks no boss. We hand out those roles. Try it.

So one leg of an AND is an on/off switch for the signal on the other leg. That's the valve. But notice what a shut valve really does: it does not disconnect, it sits there driving a solid 0 onto its wire. So the part that collects two valves has to ignore a shouted 0 and keep the live line: the OR as a merge. Read it off the OR table. OR(x, 0) = x, whether x is 0 or 1. Zero is OR's do-nothing input, its identity element, and that, not the plumbing, is why a merge passes the survivor untouched. So if at most one of its inputs is ever 1 at a time, an OR just passes whichever line is live onto its output, like two pipes joining into one. We'll see who guarantees that. Confirm it below: light one input or the other, and the merge carries it through.

Now you can see the plan before we draw it. Two valves, one for A and one for B, wired so the control line opens exactly one of them at a time, and then an OR merges the single surviving signal onto the output. Let's state the goal cleanly, then build to it.

Here's the assembly, and it's exactly the parts we just rehearsed. A NOT splits the control wire into "C" and "not-C." Two AND valves follow, one fed C and one fed not-C, and then one OR merges them. That's it: four gates, and they make a decision. And that little NOT is what pays the promise the merge asked for, because it isn't something we ask you to keep. C and not-C are opposite bits, so they can never both be 1 — both valves open isn't unlikely, it's unreachable. If both ever did open, the OR would compute A OR B and the selector would be a liar. It can't. This little block has a name engineers use everywhere: the multiplexer, or MUX for short, a selector. Trace the wiring.

The beauty is in watching the control wire do its work. Flip C and one of the two AND valves goes dark, its output pinned to 0 and silenced, while the other opens and lets its data line flow straight through the merge. The control doesn't touch the data — it just decides which door is open. Watch one branch die as the other lights.

Now take the finished selector for a full drive. Set A and B to whatever you like, then flip C back and forth, and watch the output lock onto whichever input C has chosen, with the truth table confirming every case.

You have written this exact decision a thousand times without knowing it was a circuit. if C, take B, else take A is not software magic — it is the selector you just built, running in silicon. Flip C below and watch the taken branch of the code light up the very same lane through the gates.

Sit with what that is for a second. One wire now steers a whole signal: pick this source or that one, on command. You just watched it run as the hardware if; remember the block itself, because it also returns as the beating heart of memory and of RAM. But a four-gate tangle is a lot to carry around in your head every time you want a selector, so let's do the thing this whole chapter has been arguing we're allowed to do.

05Hide it in a box

We trust the multiplexer now: we built it, we checked its table, we watched it steer. So by the equivalence principle we earned in section 3, we never have to look inside it again. We collapse the whole tangle into a single labelled rectangle with three pins going in, A, B, and C, and one coming out. That act has a name: black-boxing, or abstraction. Same behaviour, less to think about. Toggle between the guts and the box below, and confirm they do the identical thing.

This is not a diagram trick — it's how you build anything big. Once the MUX is a box, you compose boxes, exactly the way you composed gates. Watch: stack three 2-way selectors and you get a 4-way one, where two control wires now pick one of four inputs. At no point do you think about a single AND or NOT. You think in selectors.

Boxes made of boxes: you just did it once, stacking three selectors into one. But how high does the trick actually go? The honest answer is all the way, from a single transistor to a finished CPU, and always with the same move. Stop reading the ladder and climb it yourself, one rung at a time.

That's the ladder out of gate-soup. Gates compose into circuits. Circuits you trust become boxes. Boxes compose into bigger boxes. Every layer of a computer is this same move done again, and by the end of the course, "CPU" will just be the biggest box on the page. There's only one piece of honesty left to add before we move on, and it's the reason these boxes can't be treated as pure math.

06Fast, but not instant

Every gate we've drawn has behaved as if it answers the instant its inputs change. Real gates don't. Think back to the MOSFET from chapter 1: its gate leg rules the channel from a distance, without ever touching the wire, and that gap is the whole reason a transistor is not instant. To turn the channel on you have to pile charge onto the gate side of that gap, and to turn it off you have to drain that charge away again. Charge does not teleport — it arrives as a current, through wires with resistance, and filling the gap takes time. A gap that stores charge like that has a name: capacitance. So a gate is transistors charging and draining real capacitance, and that takes a small but nonzero slice of time. Call it the propagation delay. On its own it's absurdly tiny, trillionths of a second. But composition stacks it. Send a change through a chain of gates and each one waits for the one before it, so the delays add up. Flip the input below and watch the pulse crawl down the chain. The output lands a beat after you asked for it.

The longer the chain, the longer the wait for the whole thing to settle, to stop changing and hold a valid answer. But length is a decoy: what the clock truly waits on is depth, the number of gates on the longest path from input to output. Two circuits can share a table, share a gate count, and still settle at different speeds. Build one deep and one shallow, then race them.

Now collect the debt from section 3. Our AND-then-NOT NAND is a perfect forgery, and two gate delays deep where a factory NAND is one. Both true, because the identity law promised the value, never the timing. Here's the leak: a box hides what it computes, but it cannot hide how long it takes, and every box you stack adds its depth to the path. It's a seed we won't harvest for many chapters. Someday the machine will have to wait for its slowest chain of gates to settle before it dares read the answer, and that waiting is what puts a ceiling on how fast a computer can be clocked. For now it's enough to know the boxes are fast but not free.

And that's Chapter 3. You learned to compose. You chained one gate's output into the next and watched a new function appear, and you forged NAND out of an AND and a NOT and proved the forgery perfect. You saw that a truth table, not a wiring diagram, is a circuit's true identity, which bought you the right to swap equals for equals anywhere. Then you cashed that right in. You built the multiplexer, the first circuit that chooses, and sealed it in a box so you could stack it into bigger boxes without ever reopening it. That black-boxing is the ladder we'll climb for the rest of the course. But we've been steering these 0s and 1s around as if they were just abstract tokens. They're not. They're numbers, and the next chapter shows that "1011" is nothing more exotic than the place-value counting you learned as a child, with the base dialed down to two.