Boolean Algebra and Lattices - Applications

De Morgan's Laws are fundamental for manipulating Boolean expressions and understanding the duality between operations.

DefinitionDe Morgan's Laws

For elements $a, b$ in a Boolean algebra: $\neg(a \land b) = \neg a \lor \neg b$ $\neg(a \lor b) = \neg a \land \neg b$

Proof:

We prove the first law; the second follows by duality.

We show $\neg(a \land b) = \neg a \lor \neg b$ by proving each side is the complement of $a \land b$ .

Part 1: Show $(\neg a \lor \neg b) \land (a \land b) = 0$ .

$(\neg a \lor \neg b) \land (a \land b) = [(\neg a \lor \neg b) \land a] \land b$ (by associativity and commutativity)

$= [(\neg a \land a) \lor (\neg b \land a)] \land b$ (by distributivity)

$= [0 \lor (\neg b \land a)] \land b = (\neg b \land a) \land b$ (by complement law and identity)

$= a \land (\neg b \land b) = a \land 0 = 0$ (by associativity, complement law, and zero law)

Part 2: Show $(\neg a \lor \neg b) \lor (a \land b) = 1$ .

$(\neg a \lor \neg b) \lor (a \land b) = [\neg a \lor \neg b \lor a] \land [\neg a \lor \neg b \lor b]$ (by distributivity)

$= [(\neg a \lor a) \lor \neg b] \land [\neg a \lor (\neg b \lor b)]$ (by associativity and commutativity)

$= [1 \lor \neg b] \land [\neg a \lor 1] = 1 \land 1 = 1$ (by complement law and identity)

Since $\neg a \lor \neg b$ satisfies both conditions for being the complement of $a \land b$ , and complements are unique in Boolean algebras, we have: $\neg(a \land b) = \neg a \lor \neg b$

The second law follows symmetrically or by applying duality. $\square$

ExampleCircuit Simplification

De Morgan's laws enable converting between NAND/NOR implementations:

$\neg(a \land b \land c) = \neg a \lor \neg b \lor \neg c$

So a 3-input NAND gate equals a 3-input NOR gate with inverted inputs. This flexibility helps optimize circuits for available gate types and power consumption.

ExampleSet Theory Application

For sets: $\overline{A \cap B} = \overline{A} \cup \overline{B}$ and $\overline{A \cup B} = \overline{A} \cap \overline{B}$

To find elements NOT in both $A$ and $B$ : take elements not in $A$ OR not in $B$ .

Remark

De Morgan's laws extend to infinite collections in set theory: $\overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i}$ and $\overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i}$ . In logic, they connect conjunction/disjunction with negation, enabling conversion between DNF and CNF. In probability, they relate events: $P(A \cup B) = 1 - P(\overline{A} \cap \overline{B})$ . The laws reveal the duality structure underlying Boolean algebra, where AND and OR are dual operations.