Logic Gates

Gate-Level CPU Simulator

Every operation the CPU performs eventually reduces to boolean gates on individual bits: AND, OR, XOR, NAND, NOR, XNOR, NOT. Adders are XORs and ANDs glued together. Multiplexers are ANDs and ORs glued together. Memory cells are gates wired in feedback loops. So before we build anything, we need a clean way to represent a gate — something we can instantiate, compose, and simulate without redundant code.

Piece 1 — What a gate is, formally

Two inputs, each 0 or 1. That's four possible input combinations: (0,0), (0,1), (1,0), (1,1). The gate produces one bit of output for each combination. A gate is therefore nothing more than an assignment of a single output bit to each of the four input rows. That mapping is the gate's truth table.

Aside: I noticed while learning this that the truth table is structurally the same problem as enumerating spin configurations of an H₂ molecule. Each row of the table is like a basis state of two spins (↑↑, ↑↓, ↓↑, ↓↓), and the "gate" is just a labelling of those four basis states with output values. So if you ever get asked "what's the similarity between the H₂ atom and logic gates," now you have an answer.

The six famous 2-input gates

$a$	$b$	AND	OR	XOR	NAND	NOR	XNOR
0	0	0	0	0	1	1	1
0	1	0	1	1	1	0	0
1	0	0	1	1	1	0	0
1	1	1	1	0	0	0	1

Notice that every column on the right is just a length-4 string of 0s and 1s. AND is 0001. OR is 0111. XOR is 0110. The gate is the column. Hold onto that — it's the whole insight of this page.

Click the a and b toggles on any gate to flip them between 0 and 1 — all six gates share the same inputs so you can compare them side by side. Or hit Cycle through 4 configs to step through every combination automatically. Wires light green when carrying a 1; the bulb at the right shows the gate's output, and the highlighted character of tt = ... is the row of the truth table currently selected by $(a, b)$ .

a = 0, b = 0click any toggle to set inputs manually

ANDtt =0001

ORtt =0111

XORtt =0110

NANDtt =1110

NORtt =1000

XNORtt =1001

Gates compose into circuits

The six named gates aren't the whole picture. A circuit almost never uses just one of them — it wires several together, with the output of one feeding the input of the next. Composition is what turns these primitives into useful behavior.

Quick worked example: build XOR from AND, OR, and NOT. (Pretend for a moment that XOR isn't already in your toolbox.)

Look at when XOR fires. Its column is 0110 — output 1 only on rows (0,1) and (1,0). So you want a circuit that's true exactly when " $a = 0$ and $b = 1$ " OR " $a = 1$ and $b = 0$ ". Each clause is itself a small circuit:

NOT(a) AND b — fires only when $a = 0$ and $b = 1$ .
a AND NOT(b) — fires only when $a = 1$ and $b = 0$ .

XOR is true when either clause is true. So OR them together: $e x t XOR (a, b); =; (l n o t a, l an d, b); l or; (a, l an d, l n o t b)$

Five gates total — 2 NOTs, 2 ANDs, 1 OR. Walk the truth table to confirm:

$a$	$b$	¬a	¬b	¬a ∧ b	a ∧ ¬b	OR (= XOR)
0	0	1	1	0	0	0
0	1	1	0	1	0	1
1	0	0	1	0	1	1
1	1	0	0	0	0	0

Every row in the rightmost column matches XOR's 0110. We didn't need a new gate type — XOR is just AND, OR, and NOT in a different shape. (On real chips XOR usually is a primitive because the composition costs five transistors more than a dedicated XOR cell. The composition is still what defines it.)

There's a deeper version of the same trick. Any 2-input gate, all sixteen of them, can be built from AND, OR, and NOT alone — and every one of those, in turn, can be built from just NAND. (One-line proofs: NOT(a) = NAND(a, a); AND(a, b) = NOT(NAND(a, b)); OR follows from De Morgan.) That's why CMOS chips lean on NAND so heavily — one universal building block, four transistors per cell, replicate by the million. The next page wires AND and XOR together to build an adder; every layer above that is more of the same.

Piece 2 — The naive way: one function per gate

The most direct implementation is what you'd write the first time through. Each gate is its own function, body full of if statements that hard-code the truth table.

def AND(a, b):
    if a == 1 and b == 1:
        return 1
    return 0

def OR(a, b):
    if a == 1 or b == 1:
        return 1
    return 0

def XOR(a, b):
    if a != b:
        return 1
    return 0

def NAND(a, b):
    if a == 1 and b == 1:
        return 0
    return 1

def NOR(a, b):
    if a == 0 and b == 0:
        return 1
    return 0

def XNOR(a, b):
    if a == b:
        return 1
    return 0

def NOT(a):
    if a == 1:
        return 0
    return 1

This works. You can build adders out of AND and XOR calls, multiplexers out of AND and OR, and so on. But look at the pattern: each function body is structurally identical — read two bits, decide an output bit. The only thing that varies is which input combinations get mapped to 1. We're writing the same shape of code seven times.

There's also a problem of scope. There are exactly $2^{2^{2}} = 16$ possible 2-input gates (one for each 4-bit truth table). The named six are common, but if a circuit needs output = a AND NOT b as a single gate, we'd have to write a new function for it. The "function-per-gate" approach silently caps the design space at "gates we bothered to name."

Piece 3 — Each gate is the same object with a different setting

The realization: every 2-input gate has the same interface (read two bits, produce one bit) and the same shape of behavior (lookup in a 4-row table). What differs is the contents of the table. So instead of seven functions, write one — a Gate class — and parameterize it by the truth table itself.

The truth table is a 4-bit string. Index (a,b) by packing a and b into a 2-bit integer (2a + b) and looking up that position in the string. AND is the gate constructed with "0001". OR with "0111". And so on.

class Gate:
    """A 2-input boolean gate, parameterized by its 4-bit truth table.

    The bit at position (2*a + b) is the gate's output for inputs (a, b).
    Read the string left-to-right as the outputs for inputs
    (0,0), (0,1), (1,0), (1,1).
    """
    def __init__(self, truth_table, name=""):
        assert len(truth_table) == 4, "2-input gate needs a 4-bit table"
        self.tt = truth_table
        self.name = name

    def __call__(self, a, b):
        return int(self.tt[(a << 1) | b])

    def __repr__(self):
        return f"Gate({self.name or self.tt!r})"


# Every 2-input gate is now the same object, with a different setting.
AND  = Gate("0001", "AND")
OR   = Gate("0111", "OR")
XOR  = Gate("0110", "XOR")
NAND = Gate("1110", "NAND")
NOR  = Gate("1000", "NOR")
XNOR = Gate("1001", "XNOR")

# Some gates that don't have famous names:
A_AND_NOT_B = Gate("0010")     # output = a AND (NOT b)
ALWAYS_ONE  = Gate("1111")     # tautology
NOT_A       = Gate("1100")     # ignores b, inverts a

Now the seven gates collapse to seven one-liners — and we get the other nine 2-input gates for free, just by writing different bit strings. Gate("1100") is "ignore b, return NOT a". Gate("1111") is the constant-1 gate. We didn't have to invent any new code; we just set a different value of the same parameter.

Piece 4 — Generalizing to any number of inputs

Once you see gates as truth tables, the 2-input restriction is arbitrary. An $n$ -input gate has $2^{n}$ input rows and therefore needs a $2^{n}$ -bit truth table. The same Gate class handles any $n$ : just check that the table length is a power of two, deduce $n$ from $lo g_{2}$ of that, and pack the inputs into an integer index of that many bits.

class Gate:
    """A boolean gate with any number of inputs.
    Truth table is a 2**n-bit string for an n-input gate.
    """
    def __init__(self, truth_table, name=""):
        n_bits = len(truth_table)
        assert n_bits & (n_bits - 1) == 0 and n_bits >= 1, \
            "table length must be a power of two"
        self.tt = truth_table
        self.n_inputs = n_bits.bit_length() - 1
        self.name = name

    def __call__(self, *inputs):
        assert len(inputs) == self.n_inputs
        # Pack inputs as the bits of an integer index.
        index = 0
        for bit in inputs:
            index = (index << 1) | bit
        return int(self.tt[index])


NOT_GATE = Gate("10",       "NOT")     # 1 input  → 2 rows
AND      = Gate("0001",     "AND")     # 2 inputs → 4 rows
MAJ3     = Gate("00010111", "MAJORITY") # 3 inputs → 8 rows

A 1-input gate has a 2-bit table — there are only four of them (constant-0, identity, NOT, constant-1). A 3-input gate has an 8-bit table — 256 possible 3-input gates, of which the majority gate (00010111) is the famous one. A 4-input gate has a 16-bit table — 65536 possible gates, most of which have no name.

The necessarily-true facts

Short list of claims this representation rests on.

An $n$ -input gate is fully described by its $2^{n}$ -bit truth table. Two gates with the same truth table are interchangeable in any circuit; two gates with different truth tables differ in their behavior for at least one input combination.
There are exactly $2^{2^{n}}$ distinct $n$ -input gates. 4 one-input, 16 two-input, 256 three-input, 65536 four-input. The named ones (AND, OR, XOR, …) are a small handful of the total.
The $(a, b)$ input combination encoded as $2 a + b$ indexes the truth-table string consistently. Read the string from left to right as the outputs for inputs in order (0,0), (0,1), (1,0), (1,1). The same convention generalizes to $n$ inputs as a binary integer.
Every named gate is reproducible from its bit string. AND ↔ 0001; OR ↔ 0111; XOR ↔ 0110; NAND ↔ 1110; NOR ↔ 1000; XNOR ↔ 1001; majority ↔ 00010111. No information is lost in the representation.
Evaluation is $O (n)$ . Pack the inputs into an index in $n$ bit operations, then string-index in $O (1)$ . No branching, no special-cases.

Why this abstraction is the right one

Three reasons to like this representation:

It's data, not code. A new gate is a different value of the same parameter, not a new function. You can read gate definitions from a file, generate them programmatically, store them in a config — none of that works cleanly when each gate is a separate def.
It mirrors the hardware. Real synthesis tools represent combinational logic as truth tables (often compressed into BDDs or AIGs). Lookup-table FPGAs are literally this: each cell is a tiny RAM holding a truth table. The representation we end up with is the same one the silicon uses.
It composes uniformly. When every gate has the same calling interface — g(a, b) returns a bit — wiring gates together (the next page's job) becomes mechanical. Every node in the netlist is a Gate instance with two ports in and one port out.

Next we'll wire several of these gates together to build the one-bit and multi-bit adders, the arithmetic backbone of the CPU.