First PrinciplesStart anywhere. Prove it, then move on.

Rung 15

Boolean algebra

Truth tables and gates — the arithmetic underneath the hardware.

Best attempted after 2. Loops and branches. Nothing stops you trying this now — the gate will tell you if you were right.

The gate

Build XOR out of NAND gates only, and verify it with a complete truth table you filled in by hand — all four rows, every intermediate wire. Then say why NAND alone is enough to build anything.

Nobody checks this but you. Do it honestly and the rungs above hold; do it loosely and they will not, somewhere further up where the cause is much harder to find.

Two values, a handful of operations, and complete rules for combining them. That is the entire system, and a computer is built out of nothing else.

The startling fact is that one gate suffices. NAND — "not both" — can be wired into NOT, AND, OR, and everything above them. Every chip you have ever used is, underneath, an enormous pile of one operation.

Why this is on the ladder

Because rung 2's if/else and this rung's AND/OR/NOT are the same thing at two altitudes, and seeing that connection makes both solid. A compound condition in code is a circuit; a circuit is a compound condition.

It also pays off directly at rung 17, where set operations turn out to be these operations again — union is OR, intersection is AND, complement is NOT — and at rung 44, where a neuron's decision to fire is a soft version of exactly this.

Do this

Start with truth tables by hand. AND, OR, NOT, then NAND. Four rows each, filled in completely — no pattern-matching.

Then build up from NAND alone:

  • NOT: feed the same input into both legs of a NAND.
  • AND: NAND followed by that NOT.
  • OR: invert both inputs, then NAND them. Convince yourself with a table, not by believing me.
  • XOR: assemble it from the above, then verify all four rows including every intermediate wire.

If you want the full version of this, nand2tetris project 1 is exactly this exercise with a simulator that checks your work.

Where people get stuck

Inclusive versus exclusive OR. Everyday "or" usually means one or the other but not both; Boolean OR means at least one, possibly both. XOR is the everyday one, which is why it needs building rather than assuming.

The other snag is verifying by argument instead of by table. Four rows takes a minute and is a complete proof for two inputs. Do the rows.

Reading