Boolean Algebra and De Morgan's Laws
Four lines of algebra turn a three-gate circuit into a piece of wire — and De Morgan drawn as two schematics.
Skip to the animationA Boolean expression and a circuit are the same object, so the identities of Boolean algebra are claims about hardware — and simplifying an expression deletes gates you would otherwise have to build, power and wait for.
Expression and circuit are one thing
Each operator in an expression is a gate. F = A·B + A·B′ is three gates and five wires. Apply the distributive law, then the complement law, and it reduces to F = A — a piece of wire. The original circuit was computing A the slow way.
This is why the algebra is worth doing rather than merely knowing: every term eliminated is a gate not built, and gates cost area, power and propagation delay.
The identities, in dual pairs
| Law | OR form | AND form |
|---|---|---|
| Identity | A + 0 = A | A · 1 = A |
| Null | A + 1 = 1 | A · 0 = 0 |
| Idempotent | A + A = A | A · A = A |
| Complement | A + A′ = 1 | A · A′ = 0 |
| Commutative | A + B = B + A | A · B = B · A |
| Distributive | A + B·C = (A+B)(A+C) | A·(B + C) = A·B + A·C |
| Absorption | A + A·B = A | A · (A + B) = A |
| Redundancy | A + A′·B = A + B | A · (A′ + B) = A · B |
Duality: exchange + with · and 0 with 1, and a valid law becomes another valid law. That is a structural symmetry of Boolean algebra, and it halves what there is to remember.
The OR-form distributive law, A + B·C = (A+B)(A+C), has no counterpart in ordinary arithmetic and is the one that most often looks wrong at first glance. It is correct here because there are only two values.
De Morgan's laws
(A · B)′ = A′ + B′— "not both" is the same claim as "at least one is not".(A + B)′ = A′ · B′— "neither" is the same claim as "not this and not that".
As a circuit rule: push a bubble through a gate and the gate changes shape, AND becoming OR and vice versa. This is what lets any inversion be moved anywhere in an expression.
The practical consequence is that any two-level AND-OR circuit converts to NAND-NAND by adding bubbles that cancel in pairs. Since NAND is the cheapest gate in CMOS — an AND is a NAND *followed by* an inverter, so it costs more — real chips are built almost entirely from it.
Canonical forms
Any function has two standard spellings that can be read straight off a truth table, which guarantees you can always start:
- 1Sum of products (SOP) — one AND term (a *minterm*) for each row where the output is 1, all ORed together.
- 2Product of sums (POS) — one OR term (a *maxterm*) for each row where the output is 0, all ANDed together.
Neither canonical form is minimal, and reducing them by hand is exactly what the K-map exists to systematise.
The numbers you will be asked for
- De Morgan
(A·B)′ = A′ + B′ · (A+B)′ = A′·B′
Move an inversion through a gate and the gate changes.
- Absorption
A + A·B = A
The most useful law in practice.
- Redundancy
A + A′·B = A + B
The one most often missed in exams.
- Consensus
A·B + A′·C + B·C = A·B + A′·C
The third term is implied by the other two.
- Duality
swap + ↔ · and 0 ↔ 1
Turns any valid law into another valid law.
Advantages and disadvantages
Advantages
- Simplification is free — it costs paper and saves silicon.
- Duality halves the number of identities to learn.
- De Morgan converts any circuit to a single gate type.
- Canonical forms can be written mechanically from a truth table.
Disadvantages
- Algebraic simplification has no guaranteed procedure — you may not spot the shortest form.
- Minimising a large function by hand is impractical, which is why K-maps and Quine-McCluskey exist.
- It ignores propagation delay, so an algebraically minimal circuit is not always the fastest.
- It says nothing about glitches, which arise from timing rather than logic.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.