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

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.