10. De Morgan's Theorems and Simplification Examples

De Morgan's theorems are perhaps the most important tools for transforming Boolean expressions, particularly when converting between OR-based and AND-based implementations.

De Morgan's First Theorem (NOR transformation)

The complement of a logical sum is equal to the logical product of the complements.

$$\overline{A + B} = \overline{A} \cdot \overline{B}$$ (A NOR gate is equivalent to inverted inputs connected to an AND gate.)

De Morgan's Second Theorem (NAND transformation)

The complement of a logical product is equal to the logical sum of the complements.

$$\overline{A \cdot B} = \overline{A} + \overline{B}$$ (A NAND gate is equivalent to inverted inputs connected to an OR gate.)

Simplification Example

Simplify the expression $Y = A\overline{B}C + A\overline{B}\overline{C} + A B C$.

1. Factor out common terms in the first two terms: $$Y = A\overline{B}(C + \overline{C}) + A B C$$
2. Apply the Complement Law ($C + \overline{C} = 1$): $$Y = A\overline{B}(1) + A B C = A\overline{B} + A B C$$
3. Factor out A: $$Y = A(\overline{B} + B C)$$
4. Apply the Distributive Law variant (or Consensus Theorem variant: $\overline{B} + B C = \overline{B} + C$): $$Y = A(\overline{B} + C)$$

The simplified circuit is much smaller: instead of 3 AND gates and 1 OR gate (plus an inverter), we need 2 AND gates and 1 OR gate.