Take a look at this Venn diagram:
You can see that the shaded area is exactly the area not in $A\cup B$, so this is the Venn diagram for ${(A\cup B)}^{c}$. Now consider the Venn diagrams for ${A}^{c}$ and ${B}^{c}$:
You can see from the diagrams that ${A}^{c}\cap {B}^{c}={(A\cup B)}^{c}$. This is a general and useful fact, one of De Morgan’s laws.
(De Morgan’s laws for sets). Let $A\mathrm{,}B\mathrm{\subseteq}\mathrm{\Omega}$ and let ${A}^{c}$ and ${B}^{c}$ denote the complement with respect to $\mathrm{\Omega}$. Then
${(A\cup B)}^{c}={A}^{c}\cap {B}^{c}$, and
${(A\cap B)}^{c}={A}^{c}\cup {B}^{c}$.
These follow from De Morgan’s laws in logic. The left hand side of the first of these is the set of all $x\in \mathrm{\Omega}$ such that
$$\mathrm{\neg}(x\in A\vee x\in B)$$ |
and the right hand side is the set of all $x\in \mathrm{\Omega}$ such that
$$\mathrm{\neg}(x\in A)\wedge \mathrm{\neg}(x\in B).$$ |
Since $\mathrm{\neg}(p\vee q)$ is logically equivalent to $(\mathrm{\neg}p\wedge \mathrm{\neg}q)$ (Theorem 1.6.3), the two sets have the same elements and so are equal. The second equality follows from the other logical De Morgan law. ∎
De Morgan’s laws also work for unions and intersections of more than two sets.
For any sets ${A}_{\mathrm{1}}\mathrm{,}{A}_{\mathrm{2}}\mathrm{,}\mathrm{\dots}$
${({A}_{1}\cup {A}_{2}\cup \mathrm{\cdots})}^{c}={A}_{1}^{c}\cap {A}_{2}^{c}\cap \mathrm{\cdots}$, and
${({A}_{1}\cap {A}_{2}\cap \mathrm{\cdots})}^{c}={A}_{1}^{c}\cup {A}_{2}^{c}\cup \mathrm{\cdots}$