Every instruction the CPU runs — every add, cmp and and from the assembly level — ends up as signals flowing through gates: tiny circuits that take a few bits in and produce one bit out. A modern processor has billions of them. This level builds everything from gates: adders and the ALU, multiplexers and decoders, then memory and registers.
From voltages to bits
A digital circuit uses just two voltage ranges. Near 0 volts means 0; near the supply voltage — around 1 volt in a modern CPU — means 1. Anything in between is forbidden. This gap is what makes digital logic robust: a signal that has picked up some noise is still clearly 0 or 1, and each gate outputs clean levels again.
A gate computes a fixed function of its inputs. How gates are built from transistors belongs to the device level below. At this level, a gate is just a function, described by its truth table: one row per combination of inputs.
The basic gates
Toggle A and B and watch every gate respond at once. The truth table under the circuit highlights the current row:
| A | B | NOT A | A AND B | A OR B | A XOR B | A NAND B | A NOR B | A XNOR B |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
Every basic gate fed by the same two switches. Toggle A and B and watch the truth table follow. NAND and NOR are universal: every other gate can be built from either one.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
| Gate | Output is 1 when… | Symbol in algebra |
|---|---|---|
| NOT | the input is 0 | A̅ (or ¬A) |
| AND | both inputs are 1 | A·B, or AB |
| OR | at least one input is 1 | A + B |
| XOR | exactly one input is 1 | A ⊕ B |
| NAND | not both are 1 | ¬(AB) |
| NOR | neither is 1 | ¬(A + B) |
| XNOR | the inputs are equal | ¬(A ⊕ B) |
The small circle on NOT, NAND, NOR and XNOR is an inversion bubble: it means "and then invert".
How many functions are there?
A function of n inputs is completely described by its truth table, which has 2ⁿ rows, each with an output of 0 or 1. So there are 2^(2ⁿ) possible functions: 16 functions of two inputs. List the rows in the order 00, 01, 10, 11, and each function has a 4-bit name made of its output column: AND is 0001, OR is 0111, XOR is 0110, NAND is 1110, NOR is 1000. The other eleven include the constants 0000 and 1111, "just A", "just B", and a few like "A and not B".
With three inputs there are 256 functions, and with four there are 65,536. Truth tables grow quickly, which is why we also need an algebra.
Boolean algebra
Boolean algebra, named after George Boole (1815–1864), is algebra with variables that are only 0 or 1. AND works like multiplication, OR like addition (except that 1 + 1 = 1), and NOT is written with a bar (A̅), or ¬ in front of a group. Most rules look familiar; a few don't:
| Law | AND form | OR form |
|---|---|---|
| identity | 1·A = A | 0 + A = A |
| null | 0·A = 0 | 1 + A = 1 |
| idempotent | A·A = A | A + A = A |
| inverse | A·A̅ = 0 | A + A̅ = 1 |
| commutative | AB = BA | A + B = B + A |
| associative | (AB)C = A(BC) | (A + B) + C = A + (B + C) |
| distributive | A(B + C) = AB + AC | A + BC = (A + B)(A + C) |
| absorption | A(A + B) = A | A + AB = A |
| De Morgan | ¬(AB) = A̅ + B̅ | ¬(A + B) = A̅·B̅ |
Two rules have no equivalent in school algebra: idempotence (A + A = A) and the second distributive law (OR distributes over AND). De Morgan's laws are the ones you'll use most: to invert an AND, invert the inputs and use an OR, and vice versa. That's also true in code: !(a && b) is !a || !b.
From a truth table to a circuit
Any function can be built directly from its truth table:
- For every row whose output is 1, write the AND of the inputs, inverting the ones that are 0 in that row. That's a product term.
- OR all the product terms together.
The result is a sum of products. Take the majority function of three inputs, which is 1 when at least two inputs are 1. It outputs 1 on the rows 011, 101, 110 and 111, so:
M = A̅BC + AB̅C + ABC̅ + ABC
| A | B | C | M |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
M is 1 when at least two inputs are 1. Written straight from the truth table: one AND gate per row that outputs 1 (A'BC, AB'C, ABC', ABC), all ORed together. It works for any function, but it's rarely the smallest circuit.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
Three inverters, one 3-input AND per product term, and a 4-input OR. The method always works, but it rarely gives the smallest circuit.
Equivalent circuits
Boolean algebra can shrink it. Because ABC = ABC + ABC + ABC (idempotence), the term ABC can be paired with each of the other three:
- A̅BC + ABC = BC(A̅ + A) = BC
- AB̅C + ABC = AC
- ABC̅ + ABC = AB
so M = AB + AC + BC:
| A | B | C | M |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
The same function as AB + AC + BC: three 2-input ANDs and one OR instead of three NOTs, four 3-input ANDs and a 4-input OR. Boolean algebra proves the two circuits equivalent; compare their truth tables.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
It has the same truth table, but uses three 2-input ANDs and one 3-input OR, instead of three inverters, four 3-input ANDs and a 4-input OR. Fewer gates means less area, less power, and a shorter path for the signal. Chip design tools do this kind of simplification automatically, on millions of gates.
One gate is enough
NAND is universal: you can build NOT, AND and OR — and therefore any function — from NAND gates alone.
| A | B | NOT A | A AND B | A OR B |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
NAND is universal: tie both inputs together and it's NOT; follow it with a NOT and it's AND; feed it two inverted inputs and it's OR (De Morgan). So any circuit can be built from NAND gates alone — and NOR works the same way.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
- NOT: a NAND with both inputs tied together: ¬(AA) = A̅.
- AND: a NAND followed by that NOT.
- OR: by De Morgan, A + B = ¬(A̅·B̅), which is a NAND of the two inverted inputs.
NOR is universal too, by the mirror-image argument. Among the two-input gates, only NAND and NOR have this property. They're also the natural gates of CMOS, the technology of every modern chip. A CMOS NAND or NOR needs 4 transistors, while AND and OR need 6, because they're a NAND or NOR followed by an inverter. So hardware often thinks in NANDs and NORs, even when the designer wrote AND and OR.
Gates in your code
These gates are exactly what C's bitwise operators and the x86 logic instructions compute — 64 of them side by side, one per bit:
| C | x86 | Gate, per bit |
|---|---|---|
a & b | and | AND |
a | b | or | OR |
a ^ b | xor | XOR |
~a | not | NOT |
The logical operators &&, || and ! are different. They treat a whole value as true or false and, for && and ||, skip evaluating the right side when they can, so they usually compile to conditional jumps rather than to a single logic instruction.
Takeaways
- A gate computes one bit from a few input bits. Its truth table lists the output for every input combination.
- Two inputs allow 16 functions; n inputs allow 2^(2ⁿ).
- Boolean algebra — especially De Morgan's laws — rewrites circuits without changing what they compute.
- Any function can be built as a sum of products from its truth table, then simplified into an equivalent circuit with fewer gates.
- NAND (and NOR) alone can build everything, and they're the natural gates of CMOS.