Chapter 2
What can gates do?

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 every gate the rest of the book will use: OR, NOR, XOR, and XNOR. 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, which is the seed of every adder ever built.

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 the gates are more of the same. Each is a short composition of nand calls; each truth table drops out of the algebra without being typed in by hand.

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). Inverting both inputs of a NAND turns AND into OR. In circuitikz 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: nand of the two inverted inputs."""
    return nand(not_(a), not_(b))1

• De Morgan: NOT(NOT a AND NOT b) is a OR b; nand of the inverted inputs delivers exactly that in one call.

NOR adds only an outer inversion. nor_(a,b) calls not_(or_(a,b)) and nothing else; the three-gate chain still contains nothing but nand.

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 standard 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. Figure 2.3 shows both OR and XOR side by side, making the structural contrast plain.

The interactive version needs the in-browser runtime.

The key trick in XOR is computing nand(a, b) once and reusing the result in both second-level gates. Computing it twice would be redundant; the single shared value is the structural reason the network works.

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

Note that XOR foreshadows the adder in Chapter 3: this gate, beside one other you already have, will turn out to be an arithmetic circuit with nothing added. 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 sum. 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 in one NAND call: a + b is a sum (OR), which equals NOT(AND), which is NAND. The second law would let you build NOR from a single AND-with-inverted-inputs in the same way.

The four gates built here, together with NOT, AND, and NAND from Chapter 1, are the complete 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.