Digital Logic

Original interactive lesson for this course.

Every digital circuit — from a single flip-flop to a whole CPU — is built out of a handful of logic gates, each computing a single boolean function of its inputs. A truth table just lists every possible input combination and the output for each.

The basic gates

Gate	Symbol	$Y=$	1 iff
BUFFER	pass-through	$Y=A$	$A=1$
NOT	inverter	$Y=\overline{A}$	$A=0$
AND	$\cdot$	$Y=A\cdot B$	both inputs are 1
OR	$+$	$Y=A+B$	either input is 1
NAND	AND then NOT	$Y=\overline{A\cdot B}$	not both inputs are 1
NOR	OR then NOT	$Y=\overline{A+B}$	neither input is 1
XOR	"exactly one"	$Y=A\oplus B$	inputs differ
XNOR	"match"	$Y=\overline{A\oplus B}$	inputs are the same

NAND and NOR are called universal gates — every other gate (including NOT, AND, and OR themselves) can be built from nothing but NAND gates, or from nothing but NOR gates. That's not just a party trick: it's why a real chip fab only needs to mass-produce one or two gate shapes.

Lab: build gates from a deck

Below, drag gates out of the deck on the left (search it if the list is long), drop them on the canvas, and wire them up — drag from an output dot to an input dot. Click an input card's circle to toggle it between 0 and 1 and watch the value propagate live. Once you think the circuit is right, click Check: it tests your circuit against the entire truth table, not just the wiring, so a circuit that's connected but logically wrong will still fail.

Exercise 1 — NOT, using only a NAND gate

A NAND gate with both inputs tied to the same signal degenerates into a NOT gate: $\overline{A\cdot A}=\overline{A}$. Drag a single NAND onto the canvas, connect A's output to both of its inputs, then connect its output to Y.

Exercise 2 — XOR, using only AND, OR, and NAND

XOR isn't one of the universal gates, but it's easy to build from ones that are: $A\oplus B = (A+B)\cdot\overline{A\cdot B}$ — "at least one is on, AND they're not both on." Drag out one OR, one NAND, and one AND; wire both A and B into the OR and into the NAND, then feed the OR's output and the NAND's output into the AND, and the AND's output into Y.

If a check fails, the two revealed cases (after two attempts) show exactly which input combination your circuit gets wrong — a fast way to tell "not wired yet" (output shows ?) from "wired, but the wrong gate" (output is a confident, wrong 0 or 1).