De Morgan

Cheatsheet Content

De Morgan's Theorem De Morgan's theorems are a pair of transformation rules in Boolean algebra that relate conjunction and disjunction through negation. They are fundamental in digital logic design and set theory. Statement of Theorems Theorem 1: The complement of a conjunction (AND operation) is the disjunction (OR operation) of the complements. $\overline{A \cdot B} = \overline{A} + \overline{B}$ Theorem 2: The complement of a disjunction (OR operation) is the conjunction (AND operation) of the complements. $\overline{A + B} = \overline{A} \cdot \overline{B}$ Proof for Two Variables (A, B) Theorem 1: $\overline{A \cdot B} = \overline{A} + \overline{B}$ $A$ $B$ $A \cdot B$ $\overline{A \cdot B}$ $\overline{A}$ $\overline{B}$ $\overline{A} + \overline{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 Since the columns for $\overline{A \cdot B}$ and $\overline{A} + \overline{B}$ are identical, Theorem 1 is proven for two variables. Theorem 2: $\overline{A + B} = \overline{A} \cdot \overline{B}$ $A$ $B$ $A + B$ $\overline{A + B}$ $\overline{A}$ $\overline{B}$ $\overline{A} \cdot \overline{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 the columns for $\overline{A + B}$ and $\overline{A} \cdot \overline{B}$ are identical, Theorem 2 is proven for two variables. Proof for Three Variables (A, B, C) Theorem 1: $\overline{A \cdot B \cdot C} = \overline{A} + \overline{B} + \overline{C}$ $A$ $B$ $C$ $A \cdot B \cdot C$ $\overline{A \cdot B \cdot C}$ $\overline{A}$ $\overline{B}$ $\overline{C}$ $\overline{A} + \overline{B} + \overline{C}$ 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 The columns for $\overline{A \cdot B \cdot C}$ and $\overline{A} + \overline{B} + \overline{C}$ are identical, confirming Theorem 1 for three variables. Theorem 2: $\overline{A + B + C} = \overline{A} \cdot \overline{B} \cdot \overline{C}$ $A$ $B$ $C$ $A + B + C$ $\overline{A + B + C}$ $\overline{A}$ $\overline{B}$ $\overline{C}$ $\overline{A} \cdot \overline{B} \cdot \overline{C}$ 0 0 0 0 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 The columns for $\overline{A + B + C}$ and $\overline{A} \cdot \overline{B} \cdot \overline{C}$ are identical, confirming Theorem 2 for three variables.