search
Search
Publish
menu
menu search toc more_vert
Robocat
Guest 0reps
Thanks for the thanks!
close
Comments
Log in or sign up
Cancel
Post
account_circle
Profile
exit_to_app
Sign out
help Ask a question
Share on Twitter
search
keyboard_voice
close
Searching Tips
Search for a recipe: "Creating a table in MySQL"
Search for an API documentation: "@append"
Search for code: "!dataframe"
Apply a tag filter: "#python"
Useful Shortcuts
/ to open search panel
Esc to close search panel
to navigate between search results
d to clear all current filters
Enter to expand content preview
icon_star
Doc Search
icon_star
Code Search Beta
SORRY NOTHING FOUND!
mic
Start speaking...
Voice search is only supported in Safari and Chrome.
Navigate to
A
A
share
thumb_up_alt
bookmark
arrow_backShare
Twitter
Facebook

De Morgan's Laws

Probability and Statistics
chevron_right
Probability Theory
schedule Mar 9, 2022
Last updated
local_offer Arthur
Tags

De Morgan's law states that given two sets $S$ and $T$:

$$(S\, \cap\, T)^C = S^C \,\cup\,T^C$$

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:

$$x \in (S\,\cap\,T)^C \Leftrightarrow x \notin {S\,\cap\,T} \Leftrightarrow x \notin {S} \space {or}\space {x} \notin {T} \Leftrightarrow x \in {S^C} \space {or}\space {x} \in {T^C} \Leftrightarrow x \in {S^C}\, \cup\, {T^C} $$

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:

$$\begin{align*} S \rightarrow {S^C} \\ S^C \rightarrow {S} \\ T \rightarrow {T^C} \\ T^C \rightarrow {T} \end{align*} $$

This gives us:

$$\begin{gather*} (S^C \, \cap \, T^C)^C = S\,\cup\,T \\ S^C \, \cap \, T^C = (S\,\cup\,T)^C \end{gather*} $$

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:

$$(\bigcap_n S_n)^C = \bigcup_n S_n^C$$

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:

$$(\bigcup_nS_n)^C=\bigcap_nS_n^C$$

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$:

$$(S\, \cap\, T)^C = S^C \,\cup\,T^C$$

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

robocat
Published by Arthur Yanagisawa
Edited by 0 others
Did you find this page useful?
thumb_up
thumb_down
Ask a question or leave a feedback...