In short: De Morgan's theorems say that inverting an AND gives an OR of inverted inputs, and inverting an OR gives an AND of inverted inputs, which is why NAND and NOR alone can build any digital circuit and why synthesis tools can freely swap gate styles.
The two theorems in plain terms
Augustus De Morgan's laws, written for Boolean variables, are:
- First theorem: ¬(A·B) = ¬A + ¬B. A NAND is the same function as an OR whose inputs are inverted.
- Second theorem: ¬(A+B) = ¬A · ¬B. A NOR is the same function as an AND whose inputs are inverted.
The memory trick used in interviews is "break the bar, change the sign": split the overbar across the operands and flip AND to OR (or OR to AND). The rule extends to any number of variables: ¬(A·B·C) = ¬A + ¬B + ¬C. It is one of the identities collected in our Boolean algebra laws guide, but it deserves its own treatment because it is the bridge between the logic you write on paper and the gates that end up on silicon.
Proof by truth table
With only two variables, exhaustive checking is the fastest proof. Compare ¬(A·B) with ¬A + ¬B across all four input rows:
| 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 |
The fourth and seventh columns match on every row, so the first theorem holds. The second theorem follows by the same method, or by applying the first to the inverted variables.
Proof by complements
A more algebraic proof relies on the fact that a Boolean value has exactly one complement: if X + Y = 1 and X·Y = 0, then Y = ¬X. Let X = A·B and Y = ¬A + ¬B. Then X + Y = AB + ¬A + ¬B = (A + ¬A + ¬B)(B + ¬A + ¬B) = 1·1 = 1 by distributivity. And X·Y = AB¬A + AB¬B = 0 + 0 = 0. Both conditions hold, so ¬A + ¬B is the complement of AB, which is the theorem. This style of proof generalises cleanly to n variables by induction, a favourite follow-up question in written interviews.
Key fact: De Morgan duality is not just a trick for two inputs. Replace every AND with OR, every OR with AND, and every literal with its complement, and you get the complement of the whole function.
Bubble pushing: the gate-level picture
Designers rarely manipulate bars on paper; they push inversion bubbles through gates. Moving a bubble from a gate's output to its inputs (or the reverse) converts the gate symbol between AND-shape and OR-shape.
Why bother with two symbols for one gate? Readability. In an active-low system, a chip-select that asserts when either of two enables is low is clearest drawn as an OR-shape with bubbled inputs, even though the cell in the library is called NAND2.
Watching the equivalence in motion
The animation below cycles through all four input combinations. Each row lights up in turn, showing that the NAND column and the "¬A + ¬B" column are identical on every row.
NAND and NOR are universal
De Morgan is what makes NAND a universal gate. Using only 2-input NANDs:
- NOT: tie the inputs together, ¬A = NAND(A, A).
- AND: a NAND followed by a NAND-as-inverter, A·B = ¬(NAND(A,B)).
- OR: invert each input first, then NAND: A + B = NAND(¬A, ¬B). This is the first theorem read right to left.
NOR is universal by the mirror-image argument using the second theorem. Practical consequence: any two-level sum-of-products expression becomes NAND-NAND with no other gate type. Take F = AB + CD. Double inversion leaves it unchanged, ¬¬(AB + CD), and De Morgan turns the inner part into ¬(AB)·¬(CD), giving F = NAND( NAND(A,B), NAND(C,D) ).
Why CMOS cares: transistors and speed
In static CMOS, the inverting gate is the natural one. A 2-input NAND uses 4 transistors (two series NMOS, two parallel PMOS); a non-inverting AND2 needs 6, because it is a NAND plus an inverter stage. The same count applies to NOR versus OR. The pull-down and pull-up networks are De Morgan duals of each other: series becomes parallel when you swap NMOS for PMOS and AND for OR. That duality is exactly the theorem implemented in silicon.
Key fact: NAND is usually preferred over NOR in CMOS because stacked PMOS devices in a NOR are slow (hole mobility is roughly 2 to 3 times lower than electron mobility), so wide NOR gates need much larger PMOS to match drive strength.
Take a 3-input NOR driving the same load as a 3-input NAND at the same delay: the NOR's three series PMOS must each be roughly 3 times wider than a minimum PMOS, so area and input capacitance both grow. That is why standard-cell libraries are rich in NAND2/NAND3/NAND4 and more sparing with NOR3/NOR4.
What synthesis tools do with it
When you write assign y = a & b | c & d; in RTL, tools such as Synopsys Design Compiler, Cadence Genus and Siemens Oasys do not literally build AND-OR. During technology mapping they apply De Morgan transforms to cover the logic network with whichever library cells give the best timing, area and power. An AOI22 cell (AND-OR-INVERT) can implement ¬(AB + CD) in a single stage of 8 transistors, and a De Morgan rewrite lets the mapper absorb inverters into neighbouring cells. Formal equivalence checkers such as Synopsys Formality and Cadence Conformal then prove the mapped netlist is logically identical to the RTL, which is a direct, large-scale application of the identity.
The same thinking shows up in active-low signal naming. If rst_n and en_n are both active low, "reset or disabled" is simply a NAND of the two active-low nets; engineers who see the bubbles correctly write less glue logic. Teams doing this at scale, such as the physical-design groups at Avecas VLSI design services, review such polarity choices routinely during netlist sign-off.
Common mistakes and interview traps
- Bar scope. ¬(A·B) is not ¬A·¬B. The bar covers the entire product, and it only splits after the operator flips.
- Forgetting double inversion. When converting AND-OR to NAND-NAND, every first-level gate and the output gate each supply one inversion; the pair cancels. Count the bubbles along every path and make sure the parity is even.
- Mixed polarity. Applying the theorem to part of an expression while leaving the rest uncomplemented silently changes the function. Verify with a truth table or an equivalence check.
- Glitch assumptions. The two forms are logically equal but not necessarily hazard-equal; their static hazards can differ, which matters in asynchronous or clock-gating paths.
Practise with the related topics in Karnaugh map simplification, where choosing groups of zeros gives a product-of-sums that you then convert with the very same theorem.
Ready to go from identities to real netlists? Explore the digital design modules on our CourseTron courses page and practise with graded gate-level exercises.
Frequently asked questions
Does De Morgan's theorem work for more than two variables?
Yes. ¬(A·B·C·…) equals ¬A + ¬B + ¬C + …, and ¬(A+B+C+…) equals ¬A·¬B·¬C·…, for any finite number of variables. The proof is a straightforward induction on the number of operands.
Why is NAND called a universal gate?
Because NOT, AND and OR can each be built from NAND gates alone, using the tied-input inverter and De Morgan's first theorem. Since AND, OR and NOT can build any Boolean function, NAND alone can too. NOR is universal for the mirror-image reason.
Is a NAND-NAND circuit smaller than AND-OR?
In static CMOS it usually is, since each NAND2 costs 4 transistors while AND2 and OR2 cost 6 each. AB + CD as AND-OR needs 6+6+6 = 18 transistors versus 12 for three NAND2s.
How do I convert an expression to NOR-only logic?
Write it as a product of sums, apply double inversion, and use the second theorem on the inner terms. Each OR term becomes a NOR, and the final AND becomes a NOR of the complemented sums.