DeMorgan's theorem

The single most useful identity in digital design — what a NOT bar over a whole AND or OR really means. "Break the bar, change the sign."

Built from first principles. Augustus De Morgan, 1806–1871.

Before you start

What you need first

Derived gates — NAND/NOR are inverted AND/OR.
Theorems & simplification — and the truth-table check.

What you'll be able to do

State and apply the two DeMorgan identities.
Prove an identity with a truth table.
Push a NOT bar through a nested expression, outside-in.

When the bar sits over a whole group

So far NOT applied to a single variable — A′ means "flip A." But what does a bar over a whole expression like (A·B)′ equal in terms of A and B?

DeMorgan's rule: push a NOT bar into a group — the operator flips (AND↔OR) and every variable picks up its own bar.

Without it, (A·B)′ is just a NAND you can't compare with anything. With it, (A·B)′ = A′ + B′ — now you can simplify, translate, and mix it with other gates.

The two identities

$$ (A\cdot B)' = A' + B' $$

$$ (A + B)' = A'\cdot B' $$

The complement of an AND is the OR of the complements.
The complement of an OR is the AND of the complements.

Shortest form: "break the bar, change the sign." Remove a bar from over a group → every AND becomes OR (and vice-versa), and each variable gets its own bar.

Proof by truth table (identity #1)

Claim: (A·B)′ = A′ + B′. Compare the two columns for every row:

A	B	A·B	(A·B)′	A′	B′	A′+B′
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Columns (A·B)′ and A′+B′ match on every row → the two expressions are the same function. ✓ The same method proves any Boolean identity.

Why DeMorgan matters

1. Reformulating. The same condition, two phrasings. A door alarm: "not both doors closed" (D1·D2)′ equals "at least one door open" D1′ + D2′ — same circuit, suits different readers.

2. Bubble-pushing. Need a NAND-only build? A+B = (A′·B′)′, so an OR becomes NANDs. The inversion bubbles slide around a schematic, obeying DeMorgan.

3. Behind the scenes. A synthesis tool rarely builds your literal AND/OR. It applies DeMorgan over and over to rewrite logic into NAND/NOR — the gates silicon makes cheapest. You design how people think; the tool rewrites for the chip. DeMorgan guarantees both are the same circuit.

📐 Worked example

Push the bar, outside-in

1Bar over an AND of three — each AND flips, each variable gets a bar:

$$ (A\cdot B\cdot C)' = A' + B' + C' $$

2Outer AND, inner OR — work outside-in:

$$ \begin{aligned} \big((A+B)\cdot C\big)' &= (A+B)' + C' \\ &= A'\cdot B' + C' \end{aligned} $$

3Mixed, with a double-bar that cancels:

$$ \begin{aligned} (A\cdot B' + C)' &= (A\cdot B')'\cdot C' \\ &= (A' + B)\cdot C' \end{aligned} $$

Method: each time you break a bar over a group, flip the operator inside and give every variable its own bar; double bars cancel ($(B')' = B$).

✏️ Try it yourself

(a) (A+B)′ (b) (X·Y)′ (c) (A+B+C)′ as a product (d) ((A·B′)+C)′

(a) A′·B′. (b) X′+Y′. (c) A′·B′·C′. (d) outer: (A·B′)′·C′; inner: (A·B′)′ = A′+B → (A′+B)·C′.

Recap — the whole topic on one screen

Idea	What you own now
Identity #1	(A·B)′ = A′ + B′
Identity #2	(A+B)′ = A′·B′
Rule of thumb	break the bar, change the sign (work outside-in)
Why it's everywhere	reformulating · NAND/NOR builds · synthesis tools

Next topic

From English to a Boolean expression

You now have the operators, the gates, and the algebra. Last in this theme: a repeatable method to turn a real-world requirement into correct logic — DeMorgan included.

→ From English to Boolean