Leis de De Morgan
Teorema (Leis de De Morgan). Para quaisquer conjuntos $A$, $B$ e um universo $U$:
$$(A \cup B)^c = A^c \cap B^c, \qquad (A \cap B)^c = A^c \cup B^c.$$
Demonstração da primeira lei. Usamos dupla inclusão.
($\subset$): Seja $x \in (A \cup B)^c$. Então $x \notin A \cup B$, ou seja, $x \notin A$ e $x \notin B$. Portanto $x \in A^c$ e $x \in B^c$, logo $x \in A^c \cap B^c$.
($\supset$): Seja $x \in A^c \cap B^c$. Então $x \notin A$ e $x \notin B$. Portanto $x \notin A \cup B$, isto é, $x \in (A \cup B)^c$.
Logo $(A \cup B)^c = A^c \cap B^c$. $\square$
Demonstração da segunda lei. Análoga (exercício).
($\subset$): Seja $x \in (A \cap B)^c$. Então $x \notin A \cap B$, ou seja, $x \notin A$ ou $x \notin B$. Portanto $x \in A^c$ ou $x \in B^c$, logo $x \in A^c \cup B^c$.
($\supset$): Seja $x \in A^c \cup B^c$. Então $x \notin A$ ou $x \notin B$. Em qualquer caso, $x \notin A \cap B$, isto é, $x \in (A \cap B)^c$.
Logo $(A \cap B)^c = A^c \cup B^c$. $\square$