DeMorgan's Law states that the complement of the union of two sets is equal to the intersection of their complements:

$\overline{A \cup B} = \overline{A} \cap \overline{B}.$

Proof:

We will prove this using set theory and logic equivalences.

---

Definitions:

1. Set complement: $\overline{A} = \{x \mid x \notin A\}$.
2. Set union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$.
3. Set intersection: $A \cap B = \{x \mid x \in A \text{ and } x \in B\}$.

To prove $\overline{A \cup B} = \overline{A} \cap \overline{B}$, we show:

1. $x \in \overline{A \cup B} \implies x \in \overline{A} \cap \overline{B}$,
2. $x \in \overline{A} \cap \overline{B} \implies x \in \overline{A \cup B}$.

---

Part 1: Show $\overline{A \cup B} \subseteq \overline{A} \cap \overline{B}$.

Assume $x \in \overline{A \cup B}$.
This means $x \notin A \cup B$.
By definition of union, $x \notin A \cup B \implies x \notin A \text{ and } x \notin B$.

Thus: $x \in \overline{A} \text{ and } x \in \overline{B}.$

Therefore, $x \in \overline{A} \cap \overline{B}$.

---

Part 2: Show $\overline{A} \cap \overline{B} \subseteq \overline{A \cup B}$.

Assume $x \in \overline{A} \cap \overline{B}$.
This means $x \in \overline{A}$ and $x \in \overline{B}$, or equivalently:
$x \notin A$ and $x \notin B$.

By definition of union: $x \notin A \text{ and } x \notin B \implies x \notin A \cup B.$

Thus, $x \in \overline{A \cup B}$.

---

Conclusion:

Since we have shown both: $\overline{A \cup B} \subseteq \overline{A} \cap \overline{B},$ and: $\overline{A} \cap \overline{B} \subseteq \overline{A \cup B},$

we conclude: $\overline{A \cup B} = \overline{A} \cap \overline{B}.$

---

Would you like details on a related example or further explanation?

---

Follow-up Questions:

1. How does DeMorgan's law apply to Boolean algebra?
2. What is the analogous form of DeMorgan's law for intersections?
3. Can you prove DeMorgan's law using a Venn diagram?
4. How does DeMorgan's law generalize for more than two sets?
5. How is DeMorgan's law used in computer science for logical negation?

Tip:

DeMorgan's laws are essential for simplifying logical expressions, particularly in programming and circuit design!