De Morgan's Theorem

Statement of the Theorem

De Morgan’s theorem describes how to distribute a complement (NOT) over an AND or OR operation:

$\overline{a \cdot b} = \bar{a} + \bar{b}$

$\overline{a + b} = \bar{a} \cdot \bar{b}$

In words:

• The complement of a product equals the sum of the complements: $\overline{a \cdot b} = \bar{a} + \bar{b}$.
• The complement of a sum equals the product of the complements: $\overline{a + b} = \bar{a} \cdot \bar{b}$.

For the general form with $n$ variables:

$\overline{a \cdot b \cdot c \cdot \ldots} = \bar{a} + \bar{b} + \bar{c} + \ldots$

$\overline{a + b + c + \ldots} = \bar{a} \cdot \bar{b} \cdot \bar{c} \cdot \ldots$

Truth Table Verification

For two variables, both forms can be verified exhaustively:

a	b	$\overline{a \cdot b}$	$\bar{a} + \bar{b}$	$\overline{a + b}$	$\bar{a} \cdot \bar{b}$
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

The columns for $\overline{a \cdot b}$ and $\bar{a} + \bar{b}$ are identical, confirming the first form. The columns for $\overline{a + b}$ and $\bar{a} \cdot \bar{b}$ are identical, confirming the second form.

Inductive Extension to More Variables

The theorem extends to any number of variables by induction. For three variables:

$\overline{a + b + c} = \overline{(a + b) + c} = \overline{a + b} \cdot \bar{c} = (\bar{a} \cdot \bar{b}) \cdot \bar{c} = \bar{a} \cdot \bar{b} \cdot \bar{c}$

The key step applies the two-variable form treating $(a + b)$ as a single variable combined with $c$.

Similarly for the AND form:

$\overline{a \cdot b \cdot c} = \overline{(a \cdot b) \cdot c} = \overline{a \cdot b} + \bar{c} = (\bar{a} + \bar{b}) + \bar{c} = \bar{a} + \bar{b} + \bar{c}$

Practical Rule for Application

To apply De Morgan’s theorem to a Boolean expression:

1. Change all ANDs to ORs (and vice versa).
2. Complement each individual variable (put a bar over every literal).
3. Complement the entire expression (put a bar over the whole thing).

Example: Apply De Morgan to $a + b \cdot c$.

Step 1: change OR to AND, AND to OR: $a \cdot (b + c)$ Step 2: complement each variable: $\bar{a} \cdot (\bar{b} + \bar{c})$ Step 3: complement the whole: $\overline{\bar{a} \cdot (\bar{b} + \bar{c})}$

So $\overline{a + b \cdot c} = \overline{\bar{a} \cdot (\bar{b} + \bar{c})}$. We can then simplify the right-hand side further by applying De Morgan again:

$\overline{\bar{a} \cdot (\bar{b} + \bar{c})} = \overline{\bar{a}} + \overline{\bar{b} + \bar{c}} = a + (b \cdot c)$

Which returns us to the original, confirming correctness.

More usefully, De Morgan can simplify: $\overline{a + b \cdot c} = \bar{a} \cdot \overline{b \cdot c} = \bar{a} \cdot (\bar{b} + \bar{c})$.

Worked Algebraic Example

Simplify $\overline{a \cdot b + a \cdot (b + c) + b \cdot (b + c)}$.

Step 1: Apply De Morgan to the whole expression (impossible directly because it’s a sum of three terms). Instead, simplify inside first.

Inside: $a \cdot b + a \cdot (b + c) + b \cdot (b + c)$

Simplify each term algebraically before applying De Morgan:

$a \cdot b + a \cdot \overline{b + c} + b \cdot \overline{b + c}$

Apply De Morgan: $\overline{b + c} = \bar{b} \cdot \bar{c}$.

$= a \cdot b + a \cdot \bar{b} \cdot \bar{c} + b \cdot \bar{b} \cdot \bar{c}$

Note $b \cdot \bar{b} = 0$, so the third term vanishes:

$= a \cdot b + a \cdot \bar{b} \cdot \bar{c}$

Factor $a$: $= a \cdot (b + \bar{b} \cdot \bar{c})$

Using the distributive law $x + \bar{x} \cdot y = x + y$ (proved in the Boolean Algebra note):

$= a \cdot (b + \bar{c})$

Bubble Logic: Gate Equivalences

De Morgan’s theorem has an elegant interpretation in terms of gate symbols. The “bubble” on a gate input or output represents complementation.

Rule 1: Two Bubbles Cancel

Two bubbles in series (an input bubble feeding into an output bubble along the same wire) cancel and have no logical effect:

$\overline{\overline{x}} = x$

Rule 2: AND with Inverted Inputs = NOR

An AND gate with bubbles on all inputs:

$\overline{\bar{a} \cdot \bar{b}} = \bar{\bar{a}} + \bar{\bar{b}} = a + b$

So an AND gate with inverted inputs is functionally a NOR gate (and equivalently, a NOR gate with inverted inputs is an AND gate).

Rule 3: OR with Inverted Inputs = NAND

An OR gate with bubbles on all inputs:

$\overline{\bar{a} + \bar{b}} = \bar{\bar{a}} \cdot \bar{\bar{b}} = a \cdot b$

So an OR gate with inverted inputs is functionally a NAND gate.

Rule 4: Bubble Through a Gate

Moving a bubble from output to inputs changes the gate type:

• NAND: AND gate followed by bubble → bubble input OR gate: $\overline{a \cdot b} = \bar{a} + \bar{b}$
• NOR: OR gate followed by bubble → bubble input AND gate: $\overline{a + b} = \bar{a} \cdot \bar{b}$

Example 1: Implementing $f = a \cdot b + c \cdot d$ Using Only NAND Gates

The expression $f = a \cdot b + c \cdot d$ is in SOP form: two AND terms OR-ed together.

Direct implementation uses two AND gates and one OR gate.

NAND-only implementation: Apply De Morgan by double-complementing:

$f = a \cdot b + c \cdot d$ $f = \overline{\overline{a \cdot b + c \cdot d}}$ $f = \overline{\overline{a \cdot b} \cdot \overline{c \cdot d}}$

The outer complement tells us to use a NAND gate. Its inputs are $\overline{a \cdot b}$ and $\overline{c \cdot d}$, each of which is the output of a NAND gate. So the circuit is: three NAND gates. Two NAND gates feed into a third NAND gate.

Gate 1: NAND of $a$ and $b$ produces $\overline{a \cdot b}$. Gate 2: NAND of $c$ and $d$ produces $\overline{c \cdot d}$. Gate 3: NAND of the two intermediate signals produces $\overline{\overline{a \cdot b} \cdot \overline{c \cdot d}} = a \cdot b + c \cdot d$.

Example 2: Implementing $f = (a + b) \cdot (c + d)$ Using Only NOR Gates

The expression $f = (a + b) \cdot (c + d)$ is in POS form: two OR terms AND-ed together.

NOR-only implementation: Double-complement and apply De Morgan:

$f = (a + b) \cdot (c + d)$ $f = \overline{\overline{(a + b) \cdot (c + d)}}$ $f = \overline{\overline{a + b} + \overline{c + d}}$

Now the outer complement is a NOR gate. Its inputs are $\overline{a + b}$ and $\overline{c + d}$, each produced by a NOR gate. So three NOR gates in total.

Gate 1: NOR of $a$ and $b$ produces $\overline{a + b}$. Gate 2: NOR of $c$ and $d$ produces $\overline{c + d}$. Gate 3: NOR of the two intermediate signals produces $\overline{\overline{a + b} + \overline{c + d}} = (a + b) \cdot (c + d)$.

Summary of Gate Transformations

Original gate	With bubbles on inputs	Equivalent gate
AND	Bubbles on both inputs	NOR
OR	Bubbles on both inputs	NAND
NAND	Bubbles on both inputs	OR
NOR	Bubbles on both inputs	AND

These transformations are the foundation of bubble pushing: a technique for converting a circuit from one gate type to another while preserving the logic function. They are essential when a designer must implement a circuit using only one type of gate (e.g., NAND-only or NOR-only designs, which are common in CMOS).