DeMorgan’s First Law

DeMorgan’s laws involve the complement of the union of sets or the complement of the intersection of sets.

Complement of the union of sets

Let’s investigate the union of two arbitrary sets, $A$ and $B$. If we want to compute the complement of this union, that is, $\overline{ (A\cup B) }$, its intuitive to explore if it can be computed by taking the union of $\overline A$ and $\overline B$, that is, $\overline{(A\cup B)} \overset{?}= \overline{A} \cup \overline{B}$. We can delve into this further with the following example.

Let’s assume that $\mathbb{U}=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, $A=\{2, 4, 6\}$, and $B=\{1, 3, 5, 7\}$. From this we can derive the following:

$\overline{A} = \{0, 1, 3, 5, 7, 8, 9\}$

$\overline{B} = \{0, 2, 4, 6, 8, 9\}$

$A\cup B = \{1, 2, 3, 4, 5, 6, 7\}$

$\overline{(A\cup B)} = \{0, 8, 9\}$

$\overline{A} \cup \overline{B} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$

Therefore, we can conclude that $\overline{(A\cup B)} \ne \overline{A} \cup \overline{B}$.

Here, DeMorgan’s first law can help us find a solution. According to DeMorgan’s first law, considering that $A$ and $B$ are arbitrary sets, $\overline{(A\cup B)} = \overline{A} \cap \overline{B}$.

Let’s see the argument for why this is true. We first show that $\overline{(A\cup B)} \sube (\overline{A} \cap \overline{B})$.