The Machine · Chapter 2
What can gates do?

Watch the opener · 1:25

Transcript

What can gates do? Our two switches made one, NAND. Apollo's Moon computer used one kind, in thousands of copies.

Really? AND gates, OR gates, XOR gates, all different rules. Surely each needs its own part. But turn the answers from NAND upside down, and you get OR.

Upside down means both inputs flipped. And the last chapter showed how to flip: tie the two inputs of a NAND together, and it's a NOT gate. So first, put a NOT gate on each input. Then feed both flipped signals into one more NAND. Now run it. Both inputs off? The flips turn them on, and NAND answers off. Switch either one on, and NAND answers on. That's an OR gate, built from three NAND gates. The trick has a name: De Morgan's law.

So one kind of gate really can do it all! NAND is universal. Any gate you want is just NAND gates, wired differently.

Four NANDs can even tell when two bits disagree, and that's how adding starts. Flip the bits below and find that gate.

Chapter 1 closed with one gate and a promissory note: NAND alone is enough. This chapter cashes it. Starting from nothing but NAND calls, the program builds the next useful gates: OR, NOR, XOR, and XNOR. Together with NOT, AND, and NAND from the previous chapter, they form the small toolkit the next circuits reuse. By the end you will have met the short algebra of 0 and 1 that organises the whole family and seen why a four-gate network can detect whether two bits disagree, the seed of the adder in the next chapter.

2.1 NAND is universal, made concrete

Chapter 1 showed two derivations: tie both inputs of a NAND together and you get NOT; feed the output of a NAND through that NOT and you recover AND. Those two gates, together with NAND, span the full set of Boolean functions. In code the derivation is already done: the switch chapter’s code, collected in switch.py, exports not_ and and_, both written in terms of nand, with no built-in boolean operator in sight. The rest of this chapter is more of the same: each new gate is a short composition of nand calls, and its truth table is produced by running the gate, not by typing the answers in prose.

2.2 OR, NOR, and the De Morgan bridge

OR is the first gate that needs a conceptual lever: De Morgan’s first law. The law says that NOT(NOT a AND NOT b) equals (a OR b). Feed inverted inputs into a NAND and it behaves as OR. In circuit terms: put an inversion bubble on each input of a NAND and you have drawn an OR gate. Figure 2.2 puts the two symbols side by side so the equivalence is visible as geometry.

The code is as short as the law:

Example 2-1. OR from NAND, via De Morgan

def or_(a: int, b: int) -> int:
    """OR via De Morgan: invert the inputs, then NAND."""
    return nand(not_(a), not_(b))1

• the two not_ calls supply the input bubbles; the final nand gives NOT(NOT a AND NOT b), which is a OR b.

NOR adds only an outer inversion. nor_(a,b) calls not_(or_(a,b)) and nothing else. Counted as NANDs, that is two input inverters, the OR NAND, and one final NAND-as-NOT.

2.3 XOR, the odd one out

XOR outputs 1 when its inputs differ. The algebraic identity is a ⊕ b = (a ∨ b) ∧ (a ∧ b), but the compact NAND implementation avoids OR entirely and uses four NANDs in three levels: a shared NAND, two NANDs combining it with each input, then an output NAND.

Example 2-2. XOR from four NANDs

def xor_(a: int, b: int) -> int:
    """XOR from four NANDs across three levels."""
    shared = nand(a, b)1
    return nand(nand(a, shared), nand(b, shared))2

• the shared NAND, computed once and reused in both calls below
• the two second-level NANDs combine a (or b) with the shared value; the outer NAND completes the network

Computing nand(a, b) twice would produce the same value, but it would waste a gate. Sharing it is what keeps the network to four NANDs, which Figure 2.3 makes visible beside the simpler OR construction.

The interactive version needs the in-browser runtime.

XNOR inverts XOR, so it outputs 1 when the two inputs are equal. For inputs 00,01,10,11, its outputs are 1,0,0,1.

Example 2-3. XNOR: equality from inverted XOR

def xnor_(a: int, b: int) -> int:
    """XNOR (equality): invert XOR."""
    return not_(xor_(a, b))

Note that XOR foreshadows the adder in Chapter 3: this gate will compute the sum bit, while AND will compute the carry bit. The four-NAND network here is part of the skeleton of every binary adder.

2.4 Boolean algebra: the algebra of 0 and 1

The gates make sense in isolation, but they make even more sense as a system. Boolean algebra is the algebra whose variables take only the values 0 and 1 and whose three operations correspond directly to the gates above:

• conjunction (AND), written a · b or ab, is the product. a · b = 1 only when both are 1.
• disjunction (OR), written a + b, is the Boolean sum, not ordinary addition. a + b = 0 only when both are 0.
• complement (NOT), written a, flips the value.

A handful of identities follow directly from those definitions and are worth memorising because they recur constantly:

De Morgan’s two laws tie AND and OR together through complementation:

The first law is what made OR possible after the inputs were inverted: a· b = a + b. In code, the two input inversions prepare the arguments and the final NAND supplies the outer bar. The second law lets you read NOR as an AND of inverted inputs in the same way.

The four gates built here, together with NOT, AND, and NAND from Chapter 1, are the working toolkit for the arithmetic and memory circuits ahead.

Exercises

• Build a three-input AND from two-input ANDs. How many do you need?
• Build a two-to-one selector (pass a when the control is low, b when it is high) from these gates.