Logic Gates & Boolean Algebra
Every computation a computer performs — adding numbers, comparing values, deciding branches — reduces to one thing: manipulating individual bits using simple logic gates. Understanding gates means understanding the physical foundation of every CPU, GPU, and microcontroller ever built.
Why Binary?
A transistor is a voltage-controlled switch — it is either on (conducting, high voltage ≈ 3.3 V) or off (not conducting, ≈ 0 V). This maps naturally to two states: 1 and 0, true and false, HIGH and LOW.
Designing electronics for ten stable voltage levels (decimal) would require much more precision and would be far more sensitive to noise. Binary is maximally noise-resistant: the difference between a 0 and a 1 can be hundreds of millivolts, and anything below a threshold is confidently read as LOW.
The Basic Gates: AND, OR, NOT, XOR
A logic gate takes one or two binary inputs and produces a binary output according to a deterministic rule captured in a truth table.
AND and XOR Truth Tables
The truth tables for all basic gates with two inputs A and B:
| A | B | AND | OR | XOR | NOT A |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Derived Gates: NAND, NOR, XNOR
Adding a NOT stage to any gate inverts its output, producing a new gate:
Boolean Algebra
Boolean algebra (George Boole, 1854) is the mathematics of logic — rules that let you manipulate and simplify expressions involving AND, OR, and NOT, just like ordinary algebra simplifies arithmetic expressions.
These identities let a designer reduce a complex circuit specification — which might use dozens of gates — to the minimal equivalent, cutting silicon area and power consumption.
De Morgan's Laws
Augustus De Morgan's two laws are the most practically important Boolean identities in digital design:
In plain English:
- Negating an AND is the same as OR-ing the negated inputs.
- Negating an OR is the same as AND-ing the negated inputs.
De Morgan's laws are why NAND and NOR gates can each implement any Boolean function: you can build AND, OR, and NOT using only NANDs (or only NORs). In practice, CMOS circuits implement NAND and NOR more efficiently than AND and OR, so designers deliberately convert circuits to use only NAND/NOR.
Truth-table test (A=1, B=0): NOT(1·0) = NOT 0 = 1. Right side: (NOT 1)+(NOT 0) = 0+1 = 1. ✓
Building an Adder
Binary addition mirrors decimal addition: you add each column of bits and carry the overflow to the next column. Two gates handle single-bit addition:
Half Adder
Adds two single bits A and B. Outputs: Sum (the result bit) and Carry (the overflow into the next position).
Full Adder
A half adder cannot accept a carry-in from a previous bit position. A full adder takes three inputs (A, B, and Carry-in) and produces Sum and Carry-out. It is built from two half adders and an OR gate:
Chain 8 full adders together in a ripple-carry adder and you can add two 8-bit numbers — every carry "ripples" through to the next stage. To add two 64-bit integers (an everyday CPU operation), you chain 64 full adders, plus a final carry-out overflow bit.
The Arithmetic Logic Unit (ALU)
An ALU is the computational core of a CPU. It takes two operands and an operation selector (a few bits that choose what to compute) and routes them through the appropriate gate network:
- Arithmetic: ADD, SUBTRACT, INCREMENT, DECREMENT
- Bitwise logical: AND, OR, XOR, NOT
- Shift operations: LEFT SHIFT (÷2ⁿ), RIGHT SHIFT (×2ⁿ)
- Comparison: EQUAL, GREATER-THAN (via subtraction + sign bit)
The operation selector drives a multiplexer — a circuit that selects one of many inputs to pass through — channelling the operands to the correct logic block and routing the result to the output.
A modern CPU core contains many ALUs, floating-point units (FPUs), and SIMD units that apply one operation to many values simultaneously — but they are all fundamentally built from the same AND, OR, NOT, and XOR gates you now understand.
NAND: The Universal Gate
NAND (and NOR) are called functionally complete — any Boolean function can be implemented using only NAND gates:
In CMOS transistor technology, NAND is also the cheapest gate to fabricate — it requires only 4 transistors (2 PMOS in parallel + 2 NMOS in series), compared to 6 for an AND gate (which is NAND + NOT). This is why real chips are designed in NAND logic, synthesised automatically by EDA tools.
Gates in Silicon
Each logic gate in a modern chip is built from a complementary pair of MOSFET transistors (CMOS technology). In a 2-input NAND in CMOS:
- Two PMOS transistors (P-type, "pull-up network") connect the output to the supply voltage in parallel — if either input is LOW, the output is pulled HIGH.
- Two NMOS transistors (N-type, "pull-down network") connect the output to ground in series — only if both inputs are HIGH is the path to ground complete, pulling the output LOW.
The Apple M4 chip (2024) contains approximately 28 billion transistors in a 3 nm process node — 3 nanometres being roughly 10 silicon atoms. Each of those ~28 billion transistors participates in a logic gate that obeys the same truth tables on this page.
The path from Shannon's 1937 switching circuit theory to a 3 nm chip containing 28 billion gates is 87 years of engineering, but the underlying Boolean algebra has not changed by a single axiom.