Activity 2.1.5 — DeMorgan's Theorems & Simplification¶
Learning Objectives¶
By the end of this lesson, students will be able to:
- State DeMorgan's two theorems accurately
- Apply DeMorgan's theorems to simplify Boolean expressions
- Use the "break the bar, change the sign" mnemonic correctly
- Convert between NAND/NOR forms and AND/OR forms
- Apply double negation when simplifying
- Combine DeMorgan's theorems with other Boolean theorems for complex simplification
Vocabulary¶
Vocabulary (click to expand)
| Term | Definition |
|---|---|
| DeMorgan's Theorems | Two fundamental theorems relating AND and OR operations through complementation |
| NAND Gate | An AND gate followed by an inverter; output is the complement of AND |
| NOR Gate | An OR gate followed by an inverter; output is the complement of OR |
| Universal Gates | NAND and NOR gates that can be used to implement any Boolean function |
| Duality | The principle that every Boolean expression remains valid when swapping 0↔1 and AND↔OR |
| Bubble Pushing | A technique for applying DeMorgan's theorems by moving bubbles and changing gate symbols |
| Double Negation | The principle that two inversions cancel: $(A')' = A$ |
Part 1: Understanding DeMorgan's Theorems¶
Augustus DeMorgan (1806-1871) was a British mathematician who developed two fundamental theorems that relate complementation to AND and OR operations. These theorems are essential for circuit simplification and for understanding NAND/NOR logic.
The Two Theorems¶
DeMorgan's First Theorem: $$\boxed{(A + B)' = A' \cdot B'}$$
The complement of OR equals AND of complements.
DeMorgan's Second Theorem: $$\boxed{(A \cdot B)' = A' + B'}$$
The complement of AND equals OR of complements.
Key insight: Notice the symmetry: when you complement the result, you also swap the operation. AND becomes OR, OR becomes AND.
The "Break the Bar, Change the Sign" Mnemonic¶
When applying DeMorgan's theorems, follow these steps:
- Find the long bar — Identify the main grouping bar (or parenthesis) over the expression
- Break the bar — Draw breaks at each major operation under the bar
- Change the sign — Replace AND with OR, and OR with AND
- Invert each term — Apply the complement (') to each variable or expression
Example 1: Apply DeMorgan's to $(A + B)'$
| Step | Action |
|---|---|
| Original | $(A + B)'$ |
| Find bar | Bar over (A + B) |
| Break bar | Split between A and B |
| Change sign | + becomes · |
| Invert terms | A becomes A', B becomes B' |
| Result | $A' \cdot B'$ |
Example 2: Apply DeMorgan's to $(A \cdot B)'$
| Step | Action |
|---|---|
| Original | $(A \cdot B)'$ |
| Find bar | Bar over (A · B) |
| Break bar | Split between A and B |
| Change sign | · becomes + |
| Invert terms | A becomes A', B becomes B' |
| Result | $A' + B'$ |
Part 2: Truth Table Proofs¶
Let's verify DeMorgan's theorems with truth tables.
Proof of $(A + B)' = A' \cdot B'$¶
| A | B | A + B | (A + B)' | A' | B' | A' · B' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Since $(A + B)'$ and $A' \cdot B'$ have identical values in all rows, the theorem is proven.
Proof of $(A \cdot B)' = A' + B'$¶
| 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 |
Again, the columns match perfectly, proving the theorem.
Key insight: DeMorgan's theorems are dual statements. The first theorem $(A + B)' = A'B'$ is the dual of the second $(AB)' = A' + B'$. Each can be derived from the other by applying the duality principle.
Part 3: Bubble Pushing Technique¶
Bubble pushing is a visual method for applying DeMorgan's theorems directly on circuit diagrams. This technique is especially useful when analyzing complex circuits with multiple inversions.
Bubble Pushing Rules¶
Rule 1: A bubble indicates inversion (NOT operation) Rule 2: When pushing a bubble through a gate, change the gate's operation (AND ↔ OR) Rule 3: When pushing a bubble to an input, the input becomes inverted Rule 4: Two bubbles in series cancel each other
Worked Example — Bubble Pushing¶
Original Circuit:
Step 1: Identify the gate type (NAND) and its inputs - Gate is NAND: AND followed by bubble - Inputs: A, B, and C'
Step 2: Apply DeMorgan's $$Z = (A \cdot B \cdot C')' = A' + B' + C$$
Step 3: Draw equivalent circuit using only AND, OR, and NOT - Replace NAND with OR gate (apply bubble to inputs) - The result is Z = A' + B' + C
Equivalent Circuit:
Key insight: NAND gates can be replaced with OR gates if you complement all inputs. This is the foundation of NAND-NAND logic implementation.
Part 4: NAND and NOR as Universal Gates¶
One of the most important applications of DeMorgan's theorems is showing that NAND and NOR gates are universal gates — they can implement any Boolean function by themselves.
NAND is Universal¶
Using only NAND gates, you can create:
NOT gate from NAND: $$A \uparrow A = A'$$ ( NAND with both inputs = A gives complement of A )
AND gate from NAND: $$(A \uparrow B) \uparrow (A \uparrow B) = (AB)' ' = AB$$ (Two NANDs: first creates NAND, second inverts the NAND)
OR gate from NAND (using DeMorgan's): $$A' \uparrow B' = (A \cdot B)' ' = A + B$$ (Create complements first, then NAND)
OR gate directly: $$(A \uparrow A) \uparrow (B \uparrow B) = A' \uparrow B' = A + B$$
NOR is Universal¶
Similarly, NOR gates can implement any function:
NOT gate from NOR: $$A \downarrow A = A'$$
OR gate from NOR: $$(A \downarrow B) \downarrow (A \downarrow B) = (A + B)' ' = A + B$$
AND gate from NOR (using DeMorgan's): $$A' \downarrow B' = (A + B)' ' = A \cdot B$$
Key insight: Because NAND and NOR are universal, you only need one type of gate to build any digital circuit. This simplifies manufacturing and reduces cost.
Part 5: Applying DeMorgan's to Simplify Expressions¶
Worked Example 1: Simplify $(A' + B')'$¶
Step 1: Identify the outer operation — OR under the complement Step 2: Apply DeMorgan's theorem for OR: $$(A' + B')' = (A')' \cdot (B')'$$
Step 3: Apply double negation: $$= A \cdot B$$
Result: $(A' + B')' = AB$
Verification by truth table:
| A | B | A' | B' | A'+B' | (A'+B')' | AB |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Worked Example 2: Simplify $(AB + CD)'$¶
Step 1: This is a NOR-type structure: complement of OR of products Step 2: Apply DeMorgan's: $$(AB + CD)' = (AB)' \cdot (CD)'$$
Step 3: Apply DeMorgan's again to each term: $$= (A' + B') \cdot (C' + D')$$
Result: $(AB + CD)' = (A' + B')(C' + D')$
This is in Product of Sums (POS) form!
Worked Example 3: Simplify $Z = [(A + B)' \cdot C]'$¶
Step 1: Identify the structure — AND of NAND output with C, all inverted Step 2: Recognize this as: $Z = [(A + B)' \cdot C]'$ Step 3: Apply DeMorgan's for AND: $$Z = (A + B)' ' + C'$$
Step 4: Apply double negation: $$Z = (A + B) + C'$$
Step 5: Rearrange: $$Z = A + B + C'$$
Result: $Z = A + B + C'$
Worked Example 4: Simplify $(A + B + C)' + (AB)'$¶
Step 1: Apply DeMorgan's to first term: $$(A + B + C)' = A' \cdot B' \cdot C'$$
Step 2: Apply DeMorgan's to second term: $$(AB)' = A' + B'$$
Step 3: Combine: $$Z = A'B'C' + A' + B'$$
Step 4: Simplify using absorption: $$Z = A' + B' \quad \text{[A' + A'B'C' = A' by absorption]}$$
Result: $Z = A' + B'$
Worked Example 5: Prove $(A + B)(A' + B) = B$¶
Step 1: Expand using distributive: $$(A + B)(A' + B) = AA' + AB' + BA' + BB$$
Step 2: Simplify using complement theorem: $$= 0 + AB' + BA' + B$$
Step 3: Simplify using absorption: $$AB' + B = B(A' + 1) = B(1) = B$$
So: $Z = B$
Alternative using DeMorgan's: $$(A + B)(A' + B) = [(A + B) + (A' + B)']' \quad \text{[DeMorgan's in reverse]}$$
This gets complicated, so algebraic expansion is cleaner.
Part 6: Converting Between Forms¶
DeMorgan's theorems allow you to convert between SOP and POS forms.
SOP to POS Using DeMorgan's¶
Given: $Z = AB + CD$
Step 1: Complement both sides: $Z' = (AB + CD)'$ Step 2: Apply DeMorgan's: $$Z' = (AB)' \cdot (CD)' = (A' + B')(C' + D')$$
Step 3: Complement both sides again (apply DeMorgan's): $$Z = [(A' + B')(C' + D')]' = (A' + B')' + (C' + D')'$$
Step 4: Simplify using double negation: $$Z = (A + B) + (C + D)$$
Result: $Z = (A + B)(C + D)$ — Wait, that's POS form!
Actually, let's verify: $AB + CD$ in POS is $(A + B)(C + D)$... let's check: $(A + B)(C + D) = AC + AD + BC + BD$
This is NOT the same as $AB + CD$. So the direct conversion doesn't work that way.
Correct approach: For $Z = AB + CD$: - Complement: $Z' = (A' + B')(C' + D')$ — this is POS - The SOP form $Z = AB + CD$ is already minimal
Key insight: Not all expressions have a simpler POS equivalent. Simplification depends on the specific function.
Part 7: Complex Simplification Examples¶
Example: Simplify $Z = (A + B')(A' + B) + (AB' + A'B)'$¶
Step 1: Simplify the first product using distributive: $$(A + B')(A' + B) = AA' + AB + A'B' + BB'$$
Step 2: Apply complement theorems: $$= 0 + AB + A'B' + 0 = AB + A'B'$$
Step 3: Recognize this is XOR complement (XNOR): $= (A \oplus B)'$
Step 4: Simplify the second term using DeMorgan's: $$(AB' + A'B)' = (AB')' \cdot (A'B)' = (A' + B)(A + B')$$
Step 5: Notice this equals the first term by symmetry.
Step 6: Let P = AB + A'B' $$Z = P + P' = 1 \quad \text{[Complement theorem: A + A' = 1]}$$
Result: $Z = 1$ (always true)
This circuit implements a tautology — it always outputs 1!
Example: Simplify $Z = [(A'B + C)D]'$¶
Step 1: Identify the outer inversion — complement of a product Step 2: Apply DeMorgan's: $$Z = [(A'B + C)D]' = (A'B + C)' + D'$$
Step 3: Apply DeMorgan's to the first term: $$(A'B + C)' = (A'B)' \cdot C' = (A + B') \cdot C'$$
Step 4: Combine: $$Z = (A + B')C' + D'$$
Step 5: Distribute: $$Z = AC' + B'C' + D'$$
Result: $Z = AC' + B'C' + D'$
Practice Problem — Basic DeMorgan's¶
Problem 1: Apply DeMorgan's theorem to each expression.
a) $(A + B + C)'$ b) $(ABC)'$ c) $(A' + B)'$ d) $(AB + C)'$
Show Solution
a) $(A + B + C)'$ = $A' \cdot B' \cdot C'$ (Extend DeMorgan's: complement of OR is AND of complements)
b) $(ABC)'$ = $A' + B' + C'$ (Complement of AND is OR of complements)
c) $(A' + B)'$ = $(A')' \cdot B'$ = $A \cdot B'$
d) $(AB + C)'$ = $(AB)' \cdot C'$ = $(A' + B') \cdot C'$
Practice Problem — Double Application¶
Problem 2: Simplify $[(A + B)' + C]'$
Show Solution
Step 1: Let P = $(A + B)'$ $$Z = [P + C]'$$
Step 2: Apply DeMorgan's: $$Z = P' \cdot C'$$
Step 3: Substitute P: $$Z = [(A + B)' ]' \cdot C'$$
Step 4: Apply double negation to $(A + B)'$: $$Z = (A + B) \cdot C'$$
Result: $Z = (A + B)C' = AC' + BC'$
Verification: We can also think of this as applying DeMorgan's twice directly: $[(A + B)' + C]' = (A + B)'' \cdot C' = (A + B)C'$
Practice Problem — Simplification with DeMorgan's¶
Problem 3: Simplify $(A + B)(A' + B)(A + B')$
Show Solution
Step 1: Multiply first two terms: $$(A + B)(A' + B) = AA' + AB' + BA' + BB = 0 + AB' + A'B + 0 = AB' + A'B$$
This is XOR: $A \oplus B$
Step 2: Multiply result with third term: $$(AB' + A'B)(A + B')$$
Step 3: Distribute: $$= AB'A + AB'B' + A'BA + A'BB'$$ $$= A(1) + A(0) + A'(0) + A'(0)$$ $$= A$$
Result: $Z = A$
Verification: When A = 0: first two terms give $0 \oplus 0 = 0$, times $(0 + 1) = 1$, result = 0. When A = 1: first two terms give $1 \oplus 1 = 0$, times $(1 + 0) = 1$, result = 0. Wait...
Let me recalculate more carefully. Actually:
$(A + B)(A' + B) = B + AB'$ using absorption-like logic. Let's use distributive: $(A + B)(A' + B) = AA' + AB + A'B + BB = 0 + AB + A'B + 0 = B(A + A') = B$
Ah! The answer is B. Then: $B(A + B') = AB + BB' = AB + 0 = AB$
So: $Z = AB$
Practice Problem — NAND/NOR Implementation¶
Problem 4: Show how to implement $Z = A + B$ using only NAND gates.
Show Solution
Strategy: Use DeMorgan's theorem: $A + B = (A' \cdot B')'$
Circuit: 1. NAND gate 1: inputs A, A → output A' (NAND as inverter) 2. NAND gate 2: inputs B, B → output B' (NAND as inverter) 3. NAND gate 3: inputs A', B' → output $(A' \cdot B')' = A + B$
Diagram:
A ---+---\ +------+
| \ | |
| )--+ +--|---+
| / | | | |
+--------+ | | |
| | | +--- Z
B ---+------+ +--+---+ |
| | | +--+
+------+ +------+
Verification: Using DeMorgan's in reverse, NAND of A' and B' equals OR of A and B.
Practice Problem — Complex Simplification¶
Problem 5: Simplify $(A'B' + AB)'$
Show Solution
Step 1: Recognize this as complement of sum of products Step 2: Apply DeMorgan's: $$(A'B' + AB)' = (A'B')' \cdot (AB)'$$
Step 3: Apply DeMorgan's to each term: $$= (A + B) \cdot (A' + B')$$
Step 4: Expand using distributive: $$= AA' + AB' + BA' + BB'$$ $$= 0 + AB' + A'B + 0$$ $$= AB' + A'B$$
Result: $(A'B' + AB)' = AB' + A'B = A \oplus B$ (XOR)
Intuition: The complement of XNOR is XOR. $A'B' + AB$ is XNOR (true when A = B), so its complement is XOR (true when A ≠ B).
Summary¶
DeMorgan's Theorems¶
| Theorem | Expression | Gate Interpretation |
|---|---|---|
| First | $(A + B)' = A' \cdot B'$ | NOR = NAND of complements |
| Second | $(A \cdot B)' = A' + B'$ | NAND = NOR of complements |
"Break the Bar, Change the Sign" Steps¶
- Find the main grouping bar
- Break the bar at each major operation
- Change the operation (AND ↔ OR)
- Invert each term/variable
Universal Gate Equivalences¶
| Function | NAND Implementation | NOR Implementation |
|---|---|---|
| NOT | $A \uparrow A$ | $A \downarrow A$ |
| AND | $(A \uparrow B) \uparrow (A \uparrow B)$ | $(A \downarrow A) \downarrow (B \downarrow B)$ |
| OR | $(A \uparrow A) \uparrow (B \uparrow B)$ | $(A \downarrow B) \downarrow (A \downarrow B)$ |
Double Negation¶
$$(A')' = A$$ Two inversions cancel. Use this to simplify expressions after applying DeMorgan's.
Key Reminders¶
- DeMorgan's relates complementation to AND/OR operations
- Always apply the theorem completely: change operation AND complement all terms
- NAND and NOR are universal — can implement any Boolean function alone
- Bubble pushing is a visual technique for applying DeMorgan's on schematics
- Two bubbles in series cancel: $(A')' = A$
- When simplifying with DeMorgan's, apply the theorem first, then simplify the result
- Verify simplified expressions with truth tables when possible
- The complement of XOR is XNOR: $(A \oplus B)' = A'B' + AB$
Custom activity — adapted from PLTW Digital Electronics