*chevron_left*Probability Theory

# De Morgan's Laws

*chevron_right*

*schedule*Mar 9, 2022

*toc*Table of Contents

*expand_more*

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).