4.3 De Morgan's Laws: Pushing a Complement Through AND/OR
State both of De Morgan's laws precisely, apply the two-step complement-and-swap procedure to invert a multi-term Boolean expression, and use the laws to justify NAND/NOR-based circuit conversions.
De Morgan's laws describe exactly what happens when you complement (invert) an entire AND or OR expression, rather than a single variable: (A + B)' = A'B' and (AB)' = A' + B'. These two identities are arguably the single most practically important pair of laws in this entire module, because they are the precise mathematical tool that explains why NAND and NOR gates are each universal (Module 3.8's OR-from-NAND and AND-from-NOR constructions both depend directly on De Morgan's laws), why a circuit built from AND/OR gates can be systematically redrawn using only NAND (or only NOR) gates, and why complementing a large multi-term Boolean expression is a mechanical procedure rather than something you have to re-derive from a truth table every time.
Core Concept: Complementing Flips the Operator
The spec states both laws directly: (A + B)' = A'B' and (A B)' = A' + B'. Read the first one in words: the complement of an OR is the AND of the complements — inverting 'A or B' gives you 'not A and not B'. Read the second: the complement of an AND is the OR of the complements — inverting 'A and B' gives you 'not A or not B'. Notice the pattern in both: the operator itself changes (OR becomes AND, or AND becomes OR) at exactly the same moment every variable inside gets individually complemented — these two things always happen together, never one without the other.
This pairing of 'invert every variable' with 'swap the operator' is what makes De Morgan's laws a single unified rule rather than two unrelated facts to memorize separately — once you internalize that complementing an AND/OR expression always does both of these things simultaneously, you can apply the rule to expressions of any size, not just the two-variable case the spec states explicitly.
• (A + B)' = A'B' — complement of OR = AND of the complements. • (AB)' = A' + B' — complement of AND = OR of the complements. • The operator always flips (OR ↔ AND) at the same time every variable is individually complemented. • The two laws are mirror images of each other, exactly like NAND and NOR are mirror images in Module 3.
Step-by-Step: The Two-Rule Procedure for Any Expression
The spec distills the general procedure for complementing any Boolean expression into exactly two steps: 1) complement every variable, and 2) change OR to AND, and AND to OR. Applying this to the spec's own three-variable example, (A + B + C)', gives A'B'C': every one of the three variables is individually complemented, and the single OR joining them becomes a single AND joining the complemented variables — the two-variable law generalizes directly to any number of OR'd (or AND'd) terms by the same two-step rule.
For expressions that mix AND and OR (not just a single flat OR or AND of variables), the same two rules still apply, but they must be applied at every level of the expression's structure, innermost first: complementing (A + B·C)' requires first treating the whole thing as an OR of two things (A, and B·C), applying De Morgan's OR rule to get A' · (B·C)', and then applying the AND rule again to the inner (B·C)' term to get A' · (B' + C') — nested applications of the exact same two-step procedure, worked from the inside out or the outside in consistently.
• Rule 1: Complement every individual variable in the expression. • Rule 2: Swap every OR for AND, and every AND for OR. • Spec's example: (A + B + C)' = A'B'C' — three OR'd variables become three AND'd complements. • For nested/mixed expressions, apply both rules at every level of the expression's structure.
Practical and Real-World Application: NAND/NOR Circuit Conversion
De Morgan's laws are the exact tool Module 3.8 used to complete the proof that NAND alone can build OR: the identity (A'·B')' = A+B is a direct instance of De Morgan's AND law (AB)'=A'+B', read right-to-left with A and B replaced by A' and B'. This is not a coincidence — De Morgan's laws are precisely what makes it possible to systematically redraw any AND/OR/NOT circuit using only NAND gates (or only NOR gates), which is exactly the practical, manufacturing-driven motivation behind NAND-only and NOR-only IC design discussed in that earlier topic.
Beyond gate conversion, De Morgan's laws are also the standard tool for simplifying negated conditions in both circuit design and software: a condition like 'NOT (temperature is high OR pressure is high)' is far easier to reason about and implement once rewritten, via De Morgan's law, as 'temperature is NOT high AND pressure is NOT high' — the same transformation programmers apply constantly when simplifying negated compound conditionals in code, which is ultimately governed by the same Boolean algebra taught here.
Common Mistake and the Tricky Concept
The single most common mistake is applying only one of the two required steps — complementing every variable but forgetting to swap the operator, or swapping the operator but forgetting to complement the variables. Either partial application produces a wrong, unequal expression: (A+B)' complemented-variables-only (without swapping the operator) would incorrectly give A'+B', which is actually the complement of AND, not of OR — a completely different function that happens to look deceptively similar.
A second, subtler trap appears with nested expressions: forgetting to apply the rule recursively at every level, and instead only inverting the outermost operator while leaving an inner sub-expression's variables un-complemented. The correct approach, as shown above with (A + B·C)', requires pushing the complement all the way through the expression's full structure, one level at a time, until every individual variable (not just the outermost grouping) has been complemented.
De Morgan's Two Laws
Both laws generalize to any number of variables: (A+B+C)' = A'B'C', and (ABC)' = A'+B'+C'. Apply the two-step procedure recursively, innermost level first, for nested/mixed expressions.
(A + B)' = A'B' (complement of OR = AND of complements)
(A B)' = A' + B' (complement of AND = OR of complements)
General procedure for complementing any expression:
1. Complement every variable.
2. Change OR ↔ AND.Code Examples
This is the spec's own stated example, extending the two-variable law to three OR'd variables. Every variable gets individually complemented, and the single OR joining all three becomes a single AND — exactly the two-step procedure applied without any nested structure to worry about.
(A+B+C)' = A'B'C' Because the original expression mixes OR (at the outer level) and AND (at the inner level), De Morgan's rule must be applied twice, once per level, working from the outside in: first treat A and B·C as the two OR'd terms and complement/swap at that level, then apply the rule again to the still-uncomplemented inner (B·C)' term.
(A + B·C)' = A'(B' + C')
(A + B + C)' = A'B'C'
Step 1: complement every variable → A', B', C'
Step 2: change OR to AND → join with AND instead of OR
Result: A'B'C'(A + B·C)'
= A' · (B·C)' [outer OR-complement rule: (X+Y)' = X'Y', with X=A, Y=B·C]
= A' · (B' + C') [inner AND-complement rule applied to (B·C)']
Result: A'(B' + C')NAND-from-De Morgan's Law
De Morgan's AND-law, read as (X·Y)' = X'+Y' with X=A', Y=B', gives (A'B')'=A+B.
(A' · B')' = A + B
A ──[NOT]── A' ──┐
D──o── (A'·B')' = A+B
B ──[NOT]── B' ──┘
This is exactly the identity Module 3.8 used to build OR from NAND gates.Important Rules
(A + B)' = A'B' — complement of OR equals the AND of the individually complemented variables.
(AB)' = A' + B' — complement of AND equals the OR of the individually complemented variables.
General procedure: complement every variable AND swap every OR↔AND — both steps always happen together.
Apply the procedure recursively, level by level, for expressions with nested/mixed AND and OR.
NAND/NOR Circuit Redesign and Negated Conditions
De Morgan's laws are the exact mathematical justification behind converting AND/OR-based circuits into all-NAND or all-NOR implementations (as used directly in Module 3.8's proof that NAND can build OR), and they are the standard tool — in both hardware design and everyday software — for simplifying negated compound conditions, such as rewriting 'NOT (A OR B)' into the equivalent, easier-to-implement 'NOT A AND NOT B'.
Complementing every variable in (A+B)' but forgetting to also swap the OR to an AND, incorrectly producing A'+B'.
Always perform both steps together: complement every variable AND swap the operator, giving the correct result (A+B)' = A'B'.
The spec's tricky problem states the procedure as two required steps: '1. Complement every variable. 2. Change OR ↔ AND.' Performing only the first step produces A'+B', which is actually the complement of AND (a different, unequal expression), not the complement of OR.
[tricky-problem] According to the spec, what two steps must you always perform together when complementing a Boolean expression built from AND/OR? A. Complement only the first variable, and leave the operator unchanged. B. Complement every variable, and change OR to AND (or AND to OR). C. Change every AND to OR, but leave all variables uncomplemented. D. Complement the whole expression only if it contains more than two variables.
B. Complement every variable, and change OR to AND (or AND to OR). — The spec states the procedure precisely: '1. Complement every variable. 2. Change OR ↔ AND.' Both steps are required and always occur together — omitting either one produces an incorrect, unequal expression, as shown by the common-mistake example in this lesson.
[interview] Which earlier proof in this course directly depends on De Morgan's AND-law, (AB)' = A' + B'? A. The idempotent-law-based proof that A NAND A = A' (Module 3.4) B. The Module 3.8 proof that OR can be built from NAND gates alone, via the identity (A'·B')' = A + B C. The truth table for the XOR gate (Module 3.6) D. The identity law A + 0 = A (Module 4.2)
B. The Module 3.8 proof that OR can be built from NAND gates alone, via the identity (A'·B')' = A + B — Module 3.8's construction of OR from NAND gates relies on (A'·B')' = A+B, which is exactly De Morgan's AND-complement law (XY)'=X'+Y' applied with X=A' and Y=B'. The NOT-from-NAND construction instead relies on the idempotent law, not De Morgan's law.
Apply De Morgan's laws to simplify (A'+B+C')'. Show both required steps explicitly.
(A'+B+C')' = (A')'·B'·(C')' = A·B'·C, using the two-step rule (complement every term, swap OR to AND) and the involution law (A')'=A from Module 4.2 to simplify the doubly-complemented terms.
The outer expression is an OR of three terms — A', B, and C' — so apply the OR-complement rule and remember to also complement each of those three terms individually, including the already-complemented ones.