De Morgan's Laws
Start your free 7-days trial now!
De Morgan's law states that given two sets $S$ and $T$:
This reads, the complement of the union of sets $S$ and $T$ is the intersection of their respective complements. Visually it looks like the below:
The logic behind this law is as follows:
In English this reads from left to right:
If $x$ is a member of the complement set of $S$ intersect $T$
Then $x$ is not a member of $S$ intersect $T$
Hence either $x$ is not a member of set $S$ or is not a member of set $T$
Same as saying $x$ is a member of the complement of $S$ or $T$
Shortened to $x$ is a member of the union of $S$ complement and $T$ complement.
Syntactic substitution
We can also come up with a second law, using syntactic substitution of the first law:
This gives us:
General form
In the above we dealt with the specific scenario of two sets S and T, however, the law holds for multiple sets and can be represented using the below general form:
Complement of intersection of sets
Given $n$ sets, the complement of their intersection is equivalent to the union of each set's complement $S^C$. This is represented mathematically as follows:
Complement of union of sets
Given $n$ sets, the complement of their union is equivalent to the intersection of each set's complement $S^C$. This is represented mathematically as follows:
Example
Given the following information on what sports students of a class play:
Sport | Number of students |
|---|---|
Basketball | 10 |
Tennis | 13 |
Both basketball and tennis | 4 |
Other | 15 |
We can represent this visually as follows:
Remember De Morgan's law states that given two sets $S$ and $T$:
We can see in this example that indeed:
Left-hand side:
$(\text{Basketball} \,\cap\, \text{Tennis})^C$ is all students other than those that play both basketball and tennis.
This gives us 15 (other) + 10 (only basketball) + 13 (only tennis) = 38.
Right-hand side:
$\text{Basketball}^C$ = all students other than those play basketball = 15 (other) + 13 (just tennis)
$\text{Tennis}^C$ = all students other than those that play tennis = 15 (other) + 10 (just basketball)
Taking the union (distinct students) of $\text{Basketball}^C$ and $\text{Tennis}^C$, we get 15 (other) + 13 (just tennis) + 10 (just basketball) = 38 so indeed we see LHS = RHS (right-hand side).
