Logic gates and boolean algebra: from truth tables to adders

Digital electronics rests on a single decision: every wire is either high or low, and nothing in between is allowed. Once you accept that restriction, the entire subject becomes a small set of rules about how one wire's state determines another's — and those rules are simple enough to fit on a postcard. What follows is that postcard, plus the two or three insights that turn it from memorisation into understanding.

Seven gates, but really only three

Every logic family gives you seven named gates, and most courses ask you to learn all seven. It helps to notice that four of them are just the other three with the output flipped.

On a schematic the inversion is that small bubble on a gate's output. A NAND is drawn exactly as an AND with a bubble, which is the diagram telling you what the name already says. XOR is the one genuinely new idea in the list — "one or the other, but not both" — and it turns out to be the most useful gate of all.

The truth table is the specification

A truth table lists every possible combination of inputs and what comes out. That makes it the complete description of a circuit: two circuits with identical truth tables are interchangeable, no matter how differently they are drawn or how many gates each uses. This is the fact the whole of logic design is built on, because it means you can redraw a circuit to be cheaper or faster and prove the redrawing is safe.

The table has 2ⁿ rows for n inputs. Two inputs give four rows, three give eight, ten would give 1,024. That doubling is why engineers stop enumerating rows past about four inputs and switch to algebra.

De Morgan's laws

Two identities do most of the useful work in boolean algebra:

In words: break the bar, change the sign. Negating a whole expression turns every AND into an OR and every OR into an AND, with each term negated. It is worth checking on a truth table once so you believe it — take A = 1, B = 0: NOT(1 AND 0) is 1, and (NOT 1) OR (NOT 0) is 0 OR 1, also 1.

This is not an academic curiosity. It is how "not (logged in and verified)" becomes "not logged in, or not verified" in a piece of code, and it is how a designer with only NOR gates in stock builds an AND.

Why NAND is universal

Here is the fact that makes the subject click. Every circuit that can be built at all can be built from NAND gates alone.

Since any boolean function can be written with AND, OR and NOT, and all three come from NAND, any function at all comes from NAND. NOR is universal for exactly the same reason. This is not a party trick — it matters commercially, because a chip fabricated with one gate type repeated millions of times is dramatically simpler to design, verify and manufacture than one using seven different cells.

How a processor adds

Add two single bits and there are only four cases: 0+0=0, 0+1=1, 1+0=1, and 1+1=10 in binary — zero, carry one. Look at the sum column and it is exactly XOR. Look at the carry column and it is exactly AND. So two gates sharing two inputs add two bits, and that circuit is called a half adder.

It is called half because real addition has three inputs per column: the two digits and a carry from the column to the right. Chain two half adders and OR their carries and you get a full adder. String eight full adders together, each passing its carry to the next, and you have an 8-bit adder — the arithmetic unit of a processor, built from nothing but the gates above.

Simplifying: Karnaugh maps in one example

Circuits derived straight from a truth table are usually bigger than they need to be. A Karnaugh map is a rearranged truth table where adjacent cells differ by one variable, so redundant terms become visually obvious as groups.

Take a three-input function that is true for input rows 001, 011, 101 and 111. Written out term by term that is four three-variable products. But look at the pattern: it is true whenever C is 1, regardless of A and B. The whole circuit reduces to a wire — F = C. Four gates saved, and on a real chip that is silicon area and power saved millions of times over.

Seeing it work

Reading truth tables is a poor substitute for watching signals move. Our logic gate simulator lights each wire as it carries a 1 and fills in the truth table as you flip the switches, with all eleven circuits discussed here — the seven gates, both adders, a multiplexer and a majority vote. Trying the full adder with all three inputs high, and tracing why both output lamps come on, is worth more than a page of notes.