Boolean Logic

The gates NOT, AND, OR, NAND, NOR and XOR, truth tables, De Morgan’s laws and two-gate circuits, every output worked out row by row.

Key ideas

A truth table lists every combination of inputs: n inputs give 2ⁿ rows, written in order from 00…0 to 11…1.
AND gives 1 only when every input is 1; OR gives 0 only when every input is 0; NOT turns its one input round.
NAND is AND followed by NOT and NOR is OR followed by NOT; each is a universal gate, able to build every other gate.
XOR gives 1 when its two inputs are different (with more inputs, when an odd number of them are 1).
Work out an expression in the order: brackets, then NOT, then AND, then OR.
Two expressions are equal only if their output columns agree in every row of the truth table.
In a circuit, find the first gate’s output for each row, then use it as an input of the next gate.

Outputs for 00, 01, 10, 11	AND 0, 0, 0, 1; OR 0, 1, 1, 1; XOR 0, 1, 1, 0
The inverted gates	NAND 1, 1, 1, 0; NOR 1, 0, 0, 0
De Morgan’s laws	NOT (A AND B) = NOT A OR NOT B; NOT (A OR B) = NOT A AND NOT B
Always the same	A OR NOT A = 1; A AND NOT A = 0; NOT (NOT A) = A; A OR (A AND B) = A
Written as symbols	A + B is A OR B; A · B is A AND B
Rows giving 1, gate of n inputs	AND, NOR: just one; OR, NAND: all but one; XOR: half of them

Putting NOT on each part without changing AND to OR (or OR to AND).
Mixing up NOR (1 only when every input is 0) with XOR (1 when the inputs differ).
Writing 6 rows for three inputs: there are 2 × 2 × 2 = 8.
Doing OR before AND: A OR B AND C means A OR (B AND C).

For A = 0 and B = 1, find (a) NOT (A AND B) (b) NOT A OR NOT B (c) NOT (A OR B) (d) NOT A AND NOT B.

Working: (a) and (b) are always equal, and so are (c) and (d): De Morgan’s laws

Answer: (a) 1; (b) 1; (c) 0; (d) 0