Chapter 06 of 32

De Morgan's Theorems

Of all the laws in Boolean algebra, two are used more than any others in real design work: De Morgan's theorems. They tell you how to remove (or introduce) a NOT bar that sits over an AND or an OR. Every time you complement an expression, convert an AND-OR circuit into NAND gates, read a datasheet with active-low signals, or clean up a messy if condition in a program, you are using De Morgan.

The theorems are named after the British mathematician Augustus De Morgan (1806–1871), who stated them in his work on formal logic in the 1840s and 1850s (the same identities later became standard laws of set theory). In the previous chapter, Boolean Algebra Laws, they appeared as one line in a table. Here we study them properly: what they say, why they are true, how to apply them to big expressions without making mistakes, and how they explain the gate equivalences you met in Universal Gates: NAND & NOR.

De Morgan's theorems: the complement of a sum equals the product of the complements, (A + B)′ = A′B′; and the complement of a product equals the sum of the complements, (AB)′ = A′ + B′.

Notation: A′ means NOT A, AB means A AND B, A + B means A OR B. Every identity and example in this chapter was checked by enumerating all input combinations with a Python script.


The Two Theorems

Theorem 1: Complement of a Sum

(A + B)′ = A′ · B′

In words: "NOT (A OR B)" is the same as "(NOT A) AND (NOT B)". Think of a sentence: "It is not true that I drink tea or coffee" means "I drink neither tea nor coffee": no tea and no coffee.

Theorem 2: Complement of a Product

(A · B)′ = A′ + B′

"NOT (A AND B)" is the same as "(NOT A) OR (NOT B)". "It is not true that the door is locked and the alarm is on" means at least one of them is off: the door is unlocked or the alarm is off.

The famous shortcut for both: break the bar, change the sign. When you split a long bar into short bars over each variable, + becomes · and · becomes +.

Proof by Truth Table

With two variables there are only 4 rows, so we can check every case. This is called perfect induction.

A

B

A + B

(A + B)′

A′B′

AB

(AB)′

A′ + B′

0

0

0

1

1

0

1

1

0

1

1

0

0

0

1

1

1

0

1

0

0

0

1

1

1

1

1

0

0

1

0

0

Columns 4 and 5 match in every row, and so do columns 7 and 8. Both theorems are proved.

Algebraic Proof (Why It Is True)

A truth table proves the result but does not explain it. Here is an algebraic argument. In Boolean algebra, the complement of X is the unique value Y with X + Y = 1 and X · Y = 0. So to show that A′B′ is the complement of A + B, we check both conditions:

Condition 1:  (A + B) + A′B′ = A + (B + A′B′)
                             = A + (B + A′)        redundant literal: X + X′Y = X + Y
                             = (A + A′) + B
                             = 1 + B = 1           ✓

Condition 2:  (A + B) · A′B′ = AA′B′ + BA′B′
                             = 0 · B′ + A′ · 0     complement law: XX′ = 0
                             = 0                   ✓

Therefore (A + B)′ = A′B′.

Theorem 2 is the dual of Theorem 1 (swap + and ·), so by the duality principle it is true as well.

The Set-Theory View

If you have seen sets in discrete mathematics, the same laws hold there: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. Outside the union of two circles is the region outside both circles. Boolean algebra and set algebra are two models of the same structure, so every law transfers.


Generalised De Morgan's Theorems

The theorems extend to any number of variables. You can prove this by repeated use of the two-variable form, for example (A + B + C)′ = ((A + B) + C)′ = (A + B)′C′ = A′B′C′.

(A + B + C + ... + Z)′ = A′ · B′ · C′ · ... · Z′
(A · B · C · ... · Z)′ = A′ + B′ + C′ + ... + Z′

Here is a short Python program that checks the three-variable versions for all 8 input combinations:

from itertools import product

print("A B C | (A+B+C)' A'B'C' | (ABC)' A'+B'+C'")
ok = True
for a, b, c in product([0, 1], repeat=3):
    nor  = 1 - (a | b | c)          # (A + B + C)'
    and_ = (1 - a) & (1 - b) & (1 - c)  # A'B'C'
    nand = 1 - (a & b & c)          # (ABC)'
    or_  = (1 - a) | (1 - b) | (1 - c)  # A' + B' + C'
    ok = ok and nor == and_ and nand == or_
    print(f"{a} {b} {c} |    {nor}       {and_}    |   {nand}       {or_}")
print("Both theorems hold for all 8 rows:", ok)

Output:

A B C | (A+B+C)' A'B'C' | (ABC)' A'+B'+C'
0 0 0 |    1       1    |   1       1
0 0 1 |    0       0    |   1       1
0 1 0 |    0       0    |   1       1
0 1 1 |    0       0    |   1       1
1 0 0 |    0       0    |   1       1
1 0 1 |    0       0    |   1       1
1 1 0 |    0       0    |   1       1
1 1 1 |    0       0    |   0       0
Both theorems hold for all 8 rows: True

Notice the pattern: (A + B + C)′ is 1 in only one row (all inputs 0), and (ABC)′ is 0 in only one row (all inputs 1). Keep this picture in mind; it returns as minterms and maxterms in the next chapter.

Complementing Any Expression

The most useful general form says: to complement any Boolean expression,

  1. change every + into · and every · into +,

  2. complement every literal (A becomes A′, A′ becomes A),

  3. change constants 0 ↔ 1,

  4. keep the original grouping by adding brackets. The order of evaluation must not change.

Step 4 is where most mistakes happen. In AB + C, the AND is done first. After complementing, the operation that was done first must still be done first, so the result is (A′ + B′)C′, with brackets. Writing A′ + B′C′ would be wrong.


Worked Examples

Example 1: Complement an SOP Expression

Find F′ for F = A′B + CD′.

F′ = (A′B + CD′)′
   = (A′B)′ · (CD′)′           Theorem 1 on the outer +
   = (A + B′) · (C′ + D)       Theorem 2 on each product

An SOP (sum of products) becomes a POS (product of sums). This conversion is exactly how a K-map POS answer is produced later in Karnaugh Maps.

Example 2: A Nested Expression

Find F′ for F = (A + B′C)(D′ + E).

F′ = [(A + B′C)(D′ + E)]′
   = (A + B′C)′ + (D′ + E)′    Theorem 2 on the outer product
   = A′(B′C)′ + DE′            Theorem 1 on each sum
   = A′(B + C′) + DE′          Theorem 2 on B′C

Work from the outside in: remove the outermost bar first, then deal with each piece.

Example 3: Remove the Bars and Simplify

Simplify F = ((A + B)′C)′.

F = ((A + B)′ · C)′
  = ((A + B)′)′ + C′          Theorem 2
  = A + B + C′                involution: (X′)′ = X

Example 4: Complement, then Simplify

Simplify F = (AB′ + C)′.

F = (AB′)′ · C′               Theorem 1
  = (A′ + B) C′               Theorem 2
  = A′C′ + BC′                distributive law (SOP form)

Example 5: The Double-Bar Trick

Show that ((A′B′)′ · (C′D′)′)′ = A′B′ + C′D′.

Let X = (A′B′)′ and Y = (C′D′)′.
F = (X · Y)′ = X′ + Y′        Theorem 2
  = ((A′B′)′)′ + ((C′D′)′)′
  = A′B′ + C′D′               involution

This looks like a trick, but it is the exact algebra behind NAND-NAND circuits, as we see next.


De Morgan and Logic Gates

Read the theorems as statements about gates:

  • (AB)′ = A′ + B′: a NAND gate is the same as an OR gate with inverted inputs. This drawing is called a negative-OR or bubbled-OR.

  • (A + B)′ = A′B′: a NOR gate is the same as an AND gate with inverted inputs, a negative-AND or bubbled-AND.

Gate

Standard symbol reads as

Equivalent (De Morgan) symbol

When the equivalent symbol is clearer

NAND

(AB)′

A′ + B′ (OR with bubbles on inputs)

Output is 1 if any input is 0 (active-low inputs)

NOR

(A + B)′

A′B′ (AND with bubbles on inputs)

Output is 1 only if all inputs are 0

AND

AB

(A′ + B′)′ (NOR with bubbles on inputs)

Rarely needed

OR

A + B

(A′B′)′ (NAND with bubbles on inputs)

Explains why OR = NAND of inverted inputs

Bubble Pushing: AND-OR to NAND-NAND

Take F = AB + CD, a two-level AND-OR circuit. Put two bubbles (two inversions, which cancel) on each wire between the AND gates and the OR gate:

Step 1  AND-OR circuit:
        A, B ──► AND ──► AB ──┐
                              ├──► OR ──► F
        C, D ──► AND ──► CD ──┘

Step 2  Put a bubble at each AND output and a bubble at each OR input.
        Two bubbles on the same wire cancel, so F is unchanged.
        AND with an output bubble  = NAND
        OR with input bubbles      = NAND   (De Morgan: X′ + Y′ = (XY)′)

Step 3  NAND-NAND circuit:
        F = ( (AB)′ · (CD)′ )′
          = ((AB)′)′ + ((CD)′)′       Theorem 2
          = AB + CD                   ✓

The rule that falls out of this: any SOP expression can be built directly as a two-level NAND-NAND circuit, by replacing every gate with a NAND (single literals going straight into the OR level must be complemented). By the dual argument, any POS expression can be built as NOR-NOR:

F = (A + B)(C + D)
  = ( (A + B)′ + (C + D)′ )′      Theorem 1 read backwards: XY = (X′ + Y′)′
  = NOR( NOR(A, B), NOR(C, D) )

The full design procedure, with gate counts, is in Universal Gates: NAND & NOR. Here the point is that De Morgan is the reason it works.

Active-Low Signals

Many chip pins are active-low: the signal does its job when it is 0 (written with a bar, for example CS′ for chip select). Suppose a memory chip must be enabled when either of two active-low requests R1′ or R2′ is asserted. "Enable if R1 or R2" is R1 + R2 = (R1′ · R2′)′, which is a single NAND gate fed by the two active-low pins. Its output is an active-high enable: 1 when at least one request is asserted. Drawing it as a bubbled-OR makes the intent ("either request") obvious to the reader.


De Morgan in Programming

Programmers use De Morgan all the time to simplify conditions. In C, C++, Java and JavaScript, ! is NOT, && is AND and || is OR:

!(a && b)   is the same as   !a || !b
!(a || b)   is the same as   !a && !b

Example: "keep looping until x or y becomes zero"
while (!(x == 0 || y == 0))   →   while (x != 0 && y != 0)

Example: "reject if NOT (age at least 18 and has ID)"
if (!(age >= 18 && hasId))   →   if (age < 18 || !hasId)

Notice that the complement of a comparison flips it completely: the opposite of age ≥ 18 is age < 18, not age ≤ 18.


Complement vs Dual

Students often confuse these two operations because both swap + and ·.

Operation

What changes

F = A + BC′ becomes

Equal to F′?

Complement (De Morgan)

+ ↔ ·, 0 ↔ 1, and every literal is complemented

A′(B′ + C)

Yes, always

Dual

+ ↔ ·, 0 ↔ 1, literals unchanged

A(B + C′)

Not in general

The two are linked: the dual of F equals F′ with every variable complemented, that is Fd(A, B, C) = F′(A′, B′, C′). A function that equals its own dual is called self-dual; the 3-input majority function AB + BC + CA is the classic example.


Common Mistakes

  • Breaking the bar without changing the sign. (A + B)′ is not A′ + B′. Try A = 1, B = 0: the left side is 0, the right side is 1.

  • Losing the grouping. (AB + C)′ = (A′ + B′)C′, not A′ + B′C′. Add brackets around every sum you create.

  • Complementing only some literals. Every literal inside the bar flips, including ones that were already complemented: (A′B)′ = A + B′.

  • Applying De Morgan to a bar that covers only part of the expression. In A + (BC)′ only BC is under the bar, so the result is A + B′ + C′; A is untouched.

  • Confusing complement with dual. The dual does not complement the variables.

  • Treating XOR like OR. De Morgan is about AND and OR. For XOR the rule is different: (A ⊕ B)′ = A′ ⊕ B = A ⊕ B′ (the XNOR), not A′ ⊕ B′.


Interview and GATE-Style Questions

Q1. Find the complement of F = X + YZ′.

F′ = X′ · (YZ′)′ = X′(Y′ + Z). In SOP form: X′Y′ + X′Z.

Q2. A NAND gate is equivalent to which gate with inverted inputs?

An OR gate, because (AB)′ = A′ + B′. Similarly, a NOR gate is an AND gate with inverted inputs, because (A + B)′ = A′B′.

Q3. Simplify ((A′B′)′ · (C′D′)′)′.

By Theorem 2 and involution, it equals A′B′ + C′D′. Equivalently it is ((A + B)(C + D))′, because (A′B′)′ = A + B and (C′D′)′ = C + D.

Q4. Is (A + B)′ = A′ + B′? Prove or disprove.

False. Counterexample A = 1, B = 0: (1 + 0)′ = 0 but 1′ + 0′ = 0 + 1 = 1. The correct identity is (A + B)′ = A′B′.

Q5. Rewrite the C condition !(x > 5 && y <= 3) without the outer NOT.

x <= 5 || y > 3. The && becomes ||, and each comparison is replaced by its exact opposite.

Q6. Find the dual and the complement of F = A + BC.

Dual: A(B + C). Complement: A′(B′ + C′). They differ only in whether the variables are complemented, which confirms Fd(A, B, C) = F′(A′, B′, C′).

Q7. How many 2-input NAND gates implement F = AB + CD, and why?

Three: two NANDs produce (AB)′ and (CD)′, and a third NAND combines them: ((AB)′(CD)′)′ = AB + CD by De Morgan.


Summary

  • (A + B)′ = A′B′ and (AB)′ = A′ + B′. Shortcut: break the bar, change the sign.

  • They generalise to any number of variables and to any expression: swap + and ·, complement every literal, swap 0 and 1, and keep the grouping with brackets.

  • Complementing an SOP gives a POS, and vice versa.

  • In gates: NAND = bubbled-OR, NOR = bubbled-AND. This is why AND-OR maps to NAND-NAND and OR-AND maps to NOR-NOR.

  • The complement is not the dual: the dual leaves literals alone.

  • Next, Canonical Forms: SOP & POS uses these ideas to write any function as a sum of minterms or a product of maxterms, the starting point for every simplification method.