Activity 2.1.5 — DeMorgan’s Theorems & Simplification

Learning Objectives

By the end of this lesson, students will be able to:

1. State DeMorgan’s two theorems accurately
2. Apply DeMorgan’s theorems to simplify Boolean expressions
3. Use the “break the bar, change the sign” mnemonic correctly
4. Convert between NAND/NOR forms and AND/OR forms
5. Apply double negation when simplifying
6. Combine DeMorgan’s theorems with other Boolean theorems for complex simplification

Vocabulary

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{\overline{A + B} = \overline{A} \cdot \overline{B}}$$

The complement of OR equals AND of complements.

<img src=“/de/assets/images/gates/nor-gate.svg” alt=“NOR Gate” style={{ height: ‘50px’, display: ‘inline’, verticalAlign: ‘middle’ }} /> = <img src=“/de/assets/images/gates/not-gate.svg” alt=“NOT Gate” style={{ height: ‘40px’, display: ‘inline’, verticalAlign: ‘middle’ }} /> + <img src=“/de/assets/images/gates/and-gate.svg” alt=“AND Gate” style={{ height: ‘50px’, display: ‘inline’, verticalAlign: ‘middle’ }} /> (with inverted inputs)

DeMorgan’s Second Theorem: $$\boxed{\overline{A \cdot B} = \overline{A} + \overline{B}}$$

The complement of AND equals OR of complements.

<img src=“/de/assets/images/gates/nand-gate.svg” alt=“NAND Gate” style={{ height: ‘50px’, display: ‘inline’, verticalAlign: ‘middle’ }} /> = <img src=“/de/assets/images/gates/not-gate.svg” alt=“NOT Gate” style={{ height: ‘40px’, display: ‘inline’, verticalAlign: ‘middle’ }} /> + <img src=“/de/assets/images/gates/or-gate.svg” alt=“OR Gate” style={{ height: ‘50px’, display: ‘inline’, verticalAlign: ‘middle’ }} /> (with inverted inputs)

Key insight: Notice the symmetry: when you complement the result, you also swap the operation. AND becomes OR, OR becomes AND.

Visual: DeMorgan’s Transformation Steps

Theorem 1: $\overline{A + B} \rightarrow \overline{A} \cdot \overline{B}$

flowchart LR
    NOR["NOR Gate\n\overline{A+B}"] --> STEP1["Break the bar\nover OR"]
    STEP1 --> STEP2["Change + to ·\n(OR to AND)"]
    STEP2 --> STEP3["Invert each term\nA→\overline{A}, B→\overline{B}"]
    STEP3 --> RESULT["AND of complements\n\overline{A} · \overline{B}"]

Theorem 2: $\overline{A \cdot B} \rightarrow \overline{A} + \overline{B}$

flowchart LR
    NAND["NAND Gate\n\overline{AB}"] --> STEP1["Break the bar\nover AND"]
    STEP1 --> STEP2["Change · to +\n(AND to OR)"]
    STEP2 --> STEP3["Invert each term\nA→\overline{A}, B→\overline{B}"]
    STEP3 --> RESULT["OR of complements\n\overline{A} + \overline{B}"]

The “Break the Bar, Change the Sign” Mnemonic

When applying DeMorgan’s theorems, follow these steps:

1. Find the long bar — Identify the main grouping bar (or parenthesis) over the expression
2. Break the bar — Draw breaks at each major operation under the bar
3. Change the sign — Replace AND with OR, and OR with AND
4. Invert each term — Apply the complement (’) to each variable or expression

Example 1: Apply DeMorgan’s to $\overline{A + B}$

Example 2: Apply DeMorgan’s to $\overline{A \cdot B}$

Part 2: Truth Table Proofs

Let’s verify DeMorgan’s theorems with truth tables.

Proof of $\overline{A + B} = \overline{A} \cdot \overline{B}$

Since $\overline{A + B}$ and $\overline{A} \cdot \overline{B}$ have identical values in all rows, the theorem is proven.

Proof of $\overline{A \cdot B} = \overline{A} + \overline{B}$

Again, the columns match perfectly, proving the theorem.

Key insight: DeMorgan’s theorems are dual statements. The first theorem $\overline{A + B} = \overline{A}\overline{B}$ is the dual of the second $\overline{AB} = \overline{A} + \overline{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:

A ----+
      |   _____
B ----+--|     \
      |  | NAND  )--- Z
C ----+--|_____/
      |
      (|)
      |
D ----+

Step 1: Identify the gate type (NAND) and its inputs

• Gate is NAND: AND followed by bubble
• Inputs: A, B, and $\overline{C}$

Step 2: Apply DeMorgan’s $$Z = \overline{A \cdot B \cdot \overline{C}} = \overline{A} + \overline{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 = \overline{A} + \overline{B} + C$

Equivalent Circuit:

A ----+
      (|)
      |
      |   _____
      +--|     \
      |  | OR    )--- Z
B ----+--|_____/
      |
      (|)
      |
C ----+
      (|)
      |
      +----+

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 = \overline{A}$$ ( NAND with both inputs = A gives complement of A )

AND gate from NAND: $$(A \uparrow B) \uparrow (A \uparrow B) = \overline{\overline{AB}} = AB$$ (Two NANDs: first creates NAND, second inverts the NAND)

OR gate from NAND (using DeMorgan’s): $$\overline{A} \uparrow \overline{B} = \overline{\overline{A \cdot B}} = A + B$$ (Create complements first, then NAND)

OR gate directly: $$(A \uparrow A) \uparrow (B \uparrow B) = \overline{A} \uparrow \overline{B} = A + B$$

NOR is Universal

Similarly, NOR gates can implement any function:

NOT gate from NOR: $$A \downarrow A = \overline{A}$$

OR gate from NOR: $$(A \downarrow B) \downarrow (A \downarrow B) = \overline{\overline{A + B}} = A + B$$

AND gate from NOR (using DeMorgan’s): $$\overline{A} \downarrow \overline{B} = \overline{\overline{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 $\overline{\overline{A} + \overline{B}}$

Step 1: Identify the outer operation — OR under the complement Step 2: Apply DeMorgan’s theorem for OR: $$\overline{\overline{A} + \overline{B}} = \overline{\overline{A}} \cdot \overline{\overline{B}}$$

Step 3: Apply double negation: $$= A \cdot B$$

Result: $\overline{\overline{A} + \overline{B}} = AB$

Verification by truth table:

Worked Example 2: Simplify $\overline{AB + CD}$

Step 1: This is a NOR-type structure: complement of OR of products Step 2: Apply DeMorgan’s: $$\overline{AB + CD} = \overline{AB} \cdot \overline{CD}$$

Step 3: Apply DeMorgan’s again to each term: $$= (\overline{A} + \overline{B}) \cdot (\overline{C} + \overline{D})$$

Result: $\overline{AB + CD} = (\overline{A} + \overline{B})(\overline{C} + \overline{D})$

This is in Product of Sums (POS) form!

Worked Example 3: Simplify $Z = \overline{\overline{A + B} \cdot C}$

Step 1: Identify the structure — AND of NAND output with C, all inverted Step 2: Recognize this as: $Z = \overline{\overline{A + B} \cdot C}$ Step 3: Apply DeMorgan’s for AND: $$Z = \overline{\overline{A + B}} + \overline{C}$$

Step 4: Apply double negation: $$Z = (A + B) + \overline{C}$$

Step 5: Rearrange: $$Z = A + B + \overline{C}$$

Result: $Z = A + B + \overline{C}$

Worked Example 4: Simplify $\overline{A + B + C} + \overline{AB}$

Step 1: Apply DeMorgan’s to first term: $$\overline{A + B + C} = \overline{A} \cdot \overline{B} \cdot \overline{C}$$

Step 2: Apply DeMorgan’s to second term: $$\overline{AB} = \overline{A} + \overline{B}$$

Step 3: Combine: $$Z = \overline{A}\overline{B}\overline{C} + \overline{A} + \overline{B}$$

Step 4: Simplify using absorption: $$Z = \overline{A} + \overline{B} \quad [\overline{A} + \overline{A}\overline{B}\overline{C} = \overline{A} \text{ by absorption}]$$

Result: $Z = \overline{A} + \overline{B}$

Worked Example 5: Prove $(A + B)(\overline{A} + B) = B$

Step 1: Expand using distributive: $$(A + B)(\overline{A} + B) = A\overline{A} + A\overline{B} + B\overline{A} + BB$$

Step 2: Simplify using complement theorem: $$= 0 + A\overline{B} + B\overline{A} + B$$

Step 3: Simplify using absorption: $$A\overline{B} + B = B(\overline{A} + 1) = B(1) = B$$

So: $Z = B$

Alternative using DeMorgan’s: $$(A + B)(\overline{A} + B) = \overline{\overline{A + B} + \overline{\overline{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: $\overline{Z} = \overline{AB + CD}$ Step 2: Apply DeMorgan’s: $$\overline{Z} = \overline{AB} \cdot \overline{CD} = (\overline{A} + \overline{B})(\overline{C} + \overline{D})$$

Step 3: Complement both sides again (apply DeMorgan’s): $$Z = \overline{(\overline{A} + \overline{B})(\overline{C} + \overline{D})} = \overline{\overline{A} + \overline{B}} + \overline{\overline{C} + \overline{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: $\overline{Z} = (\overline{A} + \overline{B})(\overline{C} + \overline{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 + \overline{B})(\overline{A} + B) + \overline{A\overline{B} + \overline{A}B}$

Step 1: Simplify the first product using distributive: $$(A + \overline{B})(\overline{A} + B) = A\overline{A} + AB + \overline{A}\overline{B} + B\overline{B}$$

Step 2: Apply complement theorems: $$= 0 + AB + \overline{A}\overline{B} + 0 = AB + \overline{A}\overline{B}$$

Step 3: Recognize this is XOR complement (XNOR): $= \overline{A \oplus B}$

Step 4: Simplify the second term using DeMorgan’s: $$\overline{A\overline{B} + \overline{A}B} = \overline{A\overline{B}} \cdot \overline{\overline{A}B} = (\overline{A} + B)(A + \overline{B})$$

Step 5: Notice this equals the first term by symmetry.

Step 6: Let $P = AB + \overline{A}\overline{B}$ $$Z = P + \overline{P} = 1 \quad [A + \overline{A} = 1 \text{ (Complement theorem)}]$$

Result: $Z = 1$ (always true)

This circuit implements a tautology — it always outputs 1!

Example: Simplify $Z = \overline{(\overline{A}B + C)D}$

Step 1: Identify the outer inversion — complement of a product Step 2: Apply DeMorgan’s: $$Z = \overline{(\overline{A}B + C)D} = \overline{\overline{A}B + C} + \overline{D}$$

Step 3: Apply DeMorgan’s to the first term: $$\overline{\overline{A}B + C} = \overline{\overline{A}B} \cdot \overline{C} = (A + \overline{B}) \cdot \overline{C}$$

Step 4: Combine: $$Z = (A + \overline{B})\overline{C} + \overline{D}$$

Step 5: Distribute: $$Z = A\overline{C} + \overline{B}\overline{C} + \overline{D}$$

Result: $Z = A\overline{C} + \overline{B}\overline{C} + \overline{D}$

Practice Problem — Basic DeMorgan’s

Problem 1: Apply DeMorgan’s theorem to each expression.

a) $\overline{A + B + C}$ b) $\overline{ABC}$ c) $\overline{\overline{A} + B}$ d) $\overline{AB + C}$

Practice Problem — Double Application

Problem 2: Simplify $[(A + B)’ + C]’$

Practice Problem — Simplification with DeMorgan’s

Problem 3: Simplify $(A + B)(\overline{A} + B)(A + \overline{B})$

Practice Problem — NAND/NOR Implementation

Problem 4: Show how to implement $Z = A + B$ using only NAND gates.

A ---+---\     +------+
     |    \   |      |
     |     )--+   +--|---+
     |    /   |   |  |   |
     +--------+   |  |   |
                  |  |   |   +--- Z
B ---+------+   +--+---+   |
     |      |       |   +--+
     +------+       +------+

Practice Problem — Complex Simplification

Problem 5: Simplify $(\overline{A}\overline{B} + AB)’$

Summary

DeMorgan’s Theorems

”Break the Bar, Change the Sign” Steps

1. Find the main grouping bar
2. Break the bar at each major operation
3. Change the operation (AND ↔ OR)
4. Invert each term/variable

Universal Gate Equivalences

Double Negation

$$(\overline{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: $(\overline{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)’ = \overline{A}\overline{B} + AB$

Custom activity — adapted from PLTW Digital Electronics