Boolean Algebra and Logic Gates

Boolean algebra is simply ordinary algebra on just two numbers, 1 for true and 0 for false, so that logic becomes arithmetic. It's named after George Boole, who first wrote logic this way in the mid-1800s. What it's good for is enormous: a circuit can do this arithmetic with electricity, and that's what every computer chip is doing. The formulas look odd at first, but each is tiny: $x \cdot y$ (AND, 1 only if both are 1), $x + y - xy$ (OR, 1 if at least one is 1), $1 - x$ (NOT, flip the bit) and $x + y - 2xy$ (XOR, 1 if exactly one is 1). That's the entire toolkit. Every chip you've ever used is built out of these few pieces.

Swap T and F for the bits 1 and 0, and every connective becomes a small formula. AND is the easiest to see: $xy$ is 1 only when both are 1, and a single 0 wipes the product out. OR is $x + y - xy$: adding $x + y$ almost works, but it gives 2 when both are 1, so we subtract the overlap $xy$. NOT just flips, $1 - x$. A logic gate is a circuit that computes one of these: AND, OR, NOT, XOR, and NAND ($1 - xy$).

From a truth table to a circuit. Can every truth table be built out of gates? Yes, and here's a recipe. For each row where the output should be 1, AND together the inputs, negating the ones that are 0 in that row. That term is 1 on that row and nowhere else. Then OR all those terms together, so the result is 1 on exactly the rows you wanted. This sum of products form shows that any truth table can be built from AND, OR and NOT gates.

Adding bits. Think about adding two bits $x$ and $y$ in binary. The answer can be 0, 1 or 2, and 2 is $10_2$, so you need two output bits: a sum bit and a carry bit. The sum bit is 1 when exactly one input is 1, and the carry is 1 only when both are:

• sum $= x \oplus y$,
• carry $= x \cdot y$.

That's a half adder. It's "half" because it ignores any carry coming in from the column to the right, the same carry you write above the digits when adding by hand. A full adder also takes a carry in, and chaining full adders adds numbers of any length, the way a processor's arithmetic unit does.

NAND alone is universal. NOT $x$ is NAND($x$, $x$), since $1 - x \cdot x = 1 - x$ for a bit. AND is a NAND followed by a NOT, and OR comes from De Morgan's laws. That's why chips are often made almost entirely of NAND gates.

Every processor is built from billions of logic gates, and the adder you design here, repeated 64 times, is the heart of a CPU's arithmetic unit.