Every logic gate is a number
Micro-lessons
The half-adder looks like two arbitrary gate choices. It isn’t — and seeing why turns “which gate?” into a counting problem with exactly one answer. Full page →
The setup
Adding two single bits needs two output bits, because 1 + 1 = 10 in binary. Call them sum (the units column) and carry (the next column over). Fill in the table and read each output column top to bottom:
| a | b | sum | carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
The sum column is 0110 — that’s XOR. The carry column is 0001 — that’s AND. But why those two, and could anything else have worked?
The move: a gate is its output column
A 2-input gate is pinned down completely by what it emits on the four input rows. Stack those four output bits and you get a 4-bit string — a number from 0 to 15. There are exactly 2⁴ = 16 two-input gates in existence, and each one is a number. Click any of them:
| a | b | out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The output column, read top to bottom, is the binary for 6. That number is the gate.
The sum column is the pattern 0110 = the number 6, and exactly one of the sixteen gates is 6: XOR. The carry is 0001 = 1 = AND. No taste, no design preference — the truth table names the gates.
The payoff: it’s field arithmetic
Look at what those two forced gates actually compute:
- XOR(a, b) = (a + b) mod 2 — addition, dropping the overflow.
- AND(a, b) = a · b — multiplication.
Those are exactly addition and multiplication in 𝔽₂, the two-element field. So the half-adder isn’t merely “a bit adder” — handed (a, b) it computes their sum and product in 𝔽₂ at once, in a single gate-delay. The carry is the product bit.
Once XOR = + and AND = × click into place, a mountain of bit-twiddling turns back into ordinary linear algebra over 𝔽₂ — which is precisely why this pair runs error-correcting codes, CRCs, and AES.
Say it, don’t just nod
XNOR outputs 1 when its inputs are equal. Which 4-bit pattern is it, and which number 0–15?
Equal inputs are 00 and 11, so the outputs are 1,0,0,1 = 1001 = 9.
And a bonus pattern: XNOR (9) is the bit-flip of XOR (6), and 6 + 9 = 15. Flipping every output of gate n always lands on gate 15 − n — the sixteen gates pair up into eight complementary couples.