What is De Morgan's law?

De Morgan's law states that:

• The negation ($NOT$) of conjunction ($AND$) is equivalent to the disjunction ($OR$) of the negation of the individual propositions.

or

• The negation ($NOT$) of disjunction ($OR$) is equivalent to the conjunction ($AND$) of the negation of the individual propositions.

Mathematically, if $p$ and $q$ are two propositions, then De Morgan's law states:

or

Named after a British mathematician Augustus De Morgan, this law can be extended to any number of propositions connected by logical operators. Such as the following expression shows De Morgan's law applied over four propositions:

Proof by the truth table

We can prove De Morgan's law by comparing the truth values for its left and right-hand sides. Let's try to make a truth table for $\overline{p+q} = \overline{p}.\overline{q}$. 

The second last column of the above table represents the truth values of De Morgan's law's left-hand side (L.H.S), while the last column shows the corresponding truth values for the right-hand side (R.H.S).

We can see that both L.H.S and R.H.S are equivalent to each other, which proves the validity of De Morgan's law.

De Morgan's law in sets

De Morgan's law is also applicable in the set theory as follows:

• The complement of the union ($\cup$) of sets is equivalent to the intersection ($\cap$) of the complement of the individual sets.

or

• The complement of the intersection ($\cap$) of sets is equivalent to the union ($\cup$) of the complement of the individual sets.

Mathematically, if $A$ and $B$ are two sets, then De Morgan's law states:

or

Proof of De Morgan's law for sets

Consider $A$ and $B$ are two sets. Suppose De Morgan's law for these sets is as follows:

Let's take it's L.H.S:

Suppose $x$ is an element that belongs to the resultant set of $(A \cup B)'$. Hence, we can say that:

If $x$ is in $(A \cup B)'$, then it's obvious that $x$ won't be in it's complement:

If $x$ is not in the union of $A$ and $B$, then $x$ is neither in $A$ nor in $B$:

If $x$ is not in $A$ and $B$ , then it's obvious that $x$ will be in their complements:

If $x$ is in both$A'$ and $B'$, then it will also be in their intersection:

From this, we can say that:

Now, on the R.H.S, suppose that $y$ is an element that belongs to the resultant set of $A' \cap B'$:

If $y$ is in the intersection of $A'$ and $B'$ , then it's obvious that $y$ will be in both $A'$ and $B'$ :

If $y$ is in $A'$ and $B'$ , then it won't be in their complements:

If $y$ is neither in $A$ nor in $B$ , then it's obvious that $y$ won't be in their union:

If $y$ is not in $(A \cup B)$ , then it will definately be in $(A \cup B)'$:

From this, we can say that:

From $(1) \textnormal{ and } (2)$ we can deduce that: