Boolean algebra and De Morgan's laws
You already know how to describe a circuit with a
truth table. But a
table only describes a circuit — it doesn't help you improve it. Two
very different-looking logic expressions can have exactly the same truth table, which
means they do the same job. If one uses five gates and the other uses two, you'd always rather
build the two-gate version: it is cheaper, uses less power,
takes up less silicon, and the signal reaches the output faster
(fewer gates to pass through means less delay).
Boolean algebra is the set of rules that lets us shuffle a logic expression into
an equivalent — but simpler — one, without ever having to draw the truth table. It is
ordinary algebra's cousin: instead of numbers we manipulate the values
1 (true) and 0 (false), and instead of
+ and \times we use
OR, AND and NOT. Learn a handful of identities
and you can collapse a tangle of gates into something tidy — the everyday work of a hardware
engineer.
The notation
Writing "AND", "OR" and "NOT" out in full gets clumsy fast, so Boolean algebra borrows the look
of ordinary arithmetic. There are a few common notations; the one used at A-level is:
- AND is written like multiplication:
A \cdot B (or just AB). Think "both".
- OR is written like addition:
A + B. Think "either".
- NOT is written with a bar over the top:
\overline{A} (say "A bar" or "not A").
The multiply/add resemblance is a genuinely useful memory aid, because several Boolean
rules look just like arithmetic — A \cdot 1 = A mirrors
x \times 1 = x, and A + 0 = A mirrors
x + 0 = x. Just don't push the analogy too far: as we'll see,
A + A = A in Boolean algebra, which is emphatically not true
of ordinary numbers.
The identities you can lean on
Here is the toolkit. Every one of these can be checked by writing out the (tiny) truth table —
do a couple yourself to convince yourself they're real, not magic. They come in matched pairs:
anything true for AND has an OR twin with
0 and 1 swapped (this mirroring is called
duality).
- Identity:
A \cdot 1 = A and
A + 0 = A — combining with the "neutral" value changes nothing.
- Annulment (domination):
A \cdot 0 = 0 and
A + 1 = 1 — a 0 forces an AND to
0; a 1 forces an OR to
1.
- Idempotent:
A \cdot A = A and
A + A = A — a value combined with itself is just itself.
- Complement:
A \cdot \overline{A} = 0 and
A + \overline{A} = 1 — something and its opposite can't both be
true, but one of them always is.
- Double negation:
\overline{\overline{A}} = A — flip twice and you're back where you
started.
- Commutative:
A \cdot B = B \cdot A and
A + B = B + A — order doesn't matter.
- Associative:
(A \cdot B) \cdot C = A \cdot (B \cdot C) and
(A + B) + C = A + (B + C) — grouping doesn't matter.
- Distributive:
A \cdot (B + C) = A \cdot B + A \cdot C — multiply out just like
in ordinary algebra (and its dual,
A + B \cdot C = (A + B)\cdot(A + C)).
- Absorption:
A + A \cdot B = A and
A \cdot (A + B) = A — the extra term is "absorbed" and vanishes.
You don't need to memorise these like times tables — but you should recognise each one when it
shows up, so you can spot the moment a messy expression can be shrunk. The two most surprising
(and most useful) are idempotent and absorption: they are what
let whole terms simply disappear.
It looks too good to be true, so let's prove it with the other laws — no truth table needed:
A + A\cdot B = A\cdot 1 + A\cdot B = A\cdot(1 + B) = A\cdot 1 = A
Read left to right: rewrite A as A\cdot 1
(identity), factor out the common A (distributive),
note 1 + B = 1 (annulment — an OR with a
1 is always 1), and finish with identity
again. The intuition: if A is already true the whole thing is true;
if A is false, A\cdot B is false too — so
B never gets a say. It was dead weight all along.
De Morgan's laws — the star of the show
All the rules above let you tidy up. De Morgan's laws do something more
powerful: they let you push a NOT through a bracket, turning an AND into an OR (or the
other way round). This is the single most examined idea in A-level Boolean algebra, and it's the
key trick for redesigning circuits (for example, building any circuit out of nothing but NAND
gates). The two laws are:
- The negation of an AND is the OR of the negations:
\overline{A \cdot B} = \overline{A} + \overline{B}
- The negation of an OR is the AND of the negations:
\overline{A + B} = \overline{A} \cdot \overline{B}
In words: NOT(A AND B) = (NOT A) OR (NOT B), and
NOT(A OR B) = (NOT A) AND (NOT B). There's a neat two-step recipe hiding in there. To
move a bar across a bracket you:
- flip the operator — every AND becomes an OR, every OR becomes an AND; and
- negate each term — put a bar on each thing inside.
An everyday sanity check: "it is not the case that (it's raining and
I'm outside)" says exactly the same as "it's not raining or
I'm not outside" — as long as at least one of the two things fails, the joint
claim fails. Same logic, flipped operator, both terms negated.
The most reliable way to believe a Boolean identity is still the truth table. Here the
two sides of the first law, \overline{A \cdot B} and
\overline{A} + \overline{B}, are built up column by column — press
play and watch their two output columns come out identical, row for row. That
matching pair of columns is the proof.
Because the final two columns agree on every one of the four rows, the two expressions are
interchangeable: anywhere a circuit computes \overline{A \cdot B} you
may substitute \overline{A} + \overline{B}, and vice-versa. (Try the
same construction for the second law yourself — it works the same way.)
A worked simplification, step by step
Let's put the whole toolkit to work. Suppose a circuit has been designed to compute
Y = \overline{\overline{A} + \overline{B}} + A\cdot B
As drawn, that's several gates: two NOTs, an OR, a big NOT over the top, another AND, and a
final OR. Watch it melt away, one law at a time.
| Step |
Expression |
Law used |
| Start |
\overline{\overline{A} + \overline{B}} + A\cdot B |
— |
| 1 |
\overline{\overline{A}}\cdot\overline{\overline{B}} + A\cdot B |
De Morgan on \overline{\overline{A}+\overline{B}} (flip OR→AND, negate each term) |
| 2 |
A\cdot B + A\cdot B |
Double negation (\overline{\overline{A}}=A, \overline{\overline{B}}=B) |
| 3 |
A\cdot B |
Idempotent (X + X = X) |
Six-or-so gates reduced to a single AND gate:
Y = A \cdot B
Same behaviour, a fraction of the hardware. That is the whole point of Boolean algebra — and the
thrill of it is watching a fearsome expression collapse to something you could have drawn in
your sleep.
Simplify Y = A + \overline{A}\cdot B. This one has a famous shortcut,
but let's grind it out honestly:
A + \overline{A}\cdot B = (A + \overline{A})\cdot(A + B) = 1\cdot(A + B) = A + B
Distribute (the OR-over-AND dual), use complement
(A + \overline{A} = 1), then identity. So
A + \overline{A}\cdot B = A + B — the bar on the
A inside simply washes out. A tidy little surprise worth
remembering.
Verify with a program
A simplification is only correct if the truth tables match on every row. Rather
than trust the algebra, we can have a computer check all four input combinations for us. This
program evaluates the original expression
Y = \overline{\overline{A} + \overline{B}} + A\cdot B and the claimed
simplification A\cdot B side by side, and reports whether they agree
everywhere. Press Run.
// Boolean values as 1/0. In TS, && / || / ! work on truthy 1/0 and we
// fold the result back to a clean 1 or 0 with `? 1 : 0`.
const NOT = (x: number): number => (!x ? 1 : 0);
const AND = (x: number, y: number): number => (x && y ? 1 : 0);
const OR = (x: number, y: number): number => (x || y ? 1 : 0);
// The original tangle: NOT(NOT A OR NOT B) OR (A AND B)
const original = (A: number, B: number): number =>
OR(NOT(OR(NOT(A), NOT(B))), AND(A, B));
// The claimed simplification: A AND B
const simplified = (A: number, B: number): number => AND(A, B);
console.log("A B | original simplified match?");
console.log("----+-----------------------------");
let allMatch = true;
for (const A of [0, 1]) {
for (const B of [0, 1]) {
const o = original(A, B);
const s = simplified(A, B);
const ok = o === s;
if (!ok) allMatch = false;
console.log(A + " " + B + " | " + o + " " + s + " " + (ok ? "yes" : "NO"));
}
}
console.log("----+-----------------------------");
console.log(allMatch ? "All rows match - the simplification is valid." : "MISMATCH - not equivalent!");
Every row matches, so the algebra checked out. This "generate both truth tables and compare"
trick is exactly how you'd verify any simplification — by hand for two inputs, or by a
loop like this for more.
Watch out
By far the commonest exam slip is doing half of De Morgan's law. Remember, to
move a bar across a bracket you must do both of these together:
- flip the operator (AND ↔ OR), and
- negate every term (put a bar on each one).
Forget the first and you write the plain wrong
\overline{A \cdot B} = \overline{A} \cdot \overline{B} (operator not
flipped). Forget the second and you write
\overline{A + B} = \overline{A} \cdot B (only one term negated).
Both are wrong. The correct pair is always
\overline{A \cdot B} = \overline{A} + \overline{B} and
\overline{A + B} = \overline{A} \cdot \overline{B}.
And a golden rule for every simplification, not just De Morgan's: a simplification is
only valid if it preserves the truth table. If in doubt, write out both
tables (or run a check like the program above) — if a single row disagrees, you've made a
mistake somewhere, no matter how convincing the algebra looked. Simpler must still mean
the same.
Augustus De Morgan (1806–1871) was a British mathematician and a friend of
George Boole, whose Laws of Thought (1854) founded the algebra of
true and false. De Morgan's laws capture a symmetry Boole's system hinted at, and for decades
they were treated as pure logic with no practical use. Then, in 1937, a young engineer named
Claude Shannon pointed out in his master's thesis that this century-old
true/false algebra described electrical switching circuits perfectly — every AND, OR
and NOT is a real arrangement of switches. Every phone, laptop and games console you have ever
touched runs on the algebra you're learning here.