DeMorgan's Theorem | De Morgan's Proof

In set theory, De Morgan's theorem has a great importance. This is quite a useful theorem in the field of logic and Boolean algebra also.
The statements defined by this theorem are known as De Morgan's laws or rules. De Morgan's theorem was introduced by a 19$^{th}$-century mathematician Augustus De Morgan who defined a couple of important laws for the set operations.This theorem is widely applicable in Boolean algebra and electronics. De Morgan's theorem relates union (conjunction), intersection (disjunction) and complement (negation) all together. Here, we are going to study about De Morgan's laws and their proofs in detail.

There are three basic operations in set theory - union, intersection and complement. De Morgan's Laws are all about relations among these set operations.
Let us recall these set operations first.
1) Union: Union of two finite sets is defined as the set which has all the elements of both sets, such as A $\cup$ B = {x : x $\in$ A or x $\in$ B}

2) Intersection: Intersection of two finite sets denotes the set that contains the elements that are common to both the sets, such as A $\cap$ B = {x : x $\in$ A and x $\in$ B}

3) Complement: Complement of a finite set is the set of all the element except for the elements of that particular set. i.e., $\bar{A}$ or A$^{c}$ = {x : x $\notin$ A} = U - A, where A is the universal set.

De Morgan's Theorem defines two laws or rules which are as follows:
First Law
It states that the complement of union of two finite sets is equal to the intersection of complements of the sets separately.Let us consider two sets P and Q, then according to De Morgan's law:

$(A \cup B)^{c}=A^{c} \cap B^{c}$

Second Law
It states that the complement of intersection of two finite sets equals to the union of complements of the sets separately.
Let us consider two sets P and Q, then according to De Morgan's law:

$(A \cap B)^{c}=A^{c} \cup B^{c}$

Generalization of De Morgan's Theorem
De Morgan's theorem is also generalized to be defined on n number of finite sets. Let us consider n finite sets A$_{1}$, A$_{2}$, A$_{3}$, ..., A$_{n}$.
Then generalization of De Morgan's theorem is given by the statement:

$(\bigcup_{i=1}^{n}A_{i})^{c}=\bigcap_{i=1}^{n}A_{i}^{c}$

And

$(\bigcap_{i=1}^{n}A_{i})^{c}=\bigcup_{i=1}^{n}A_{i}^{c}$

Undoubtedly, De Morgan's laws are the most important tools used while simplifying set operations and also while dealing with logic gates in computers.

The two De Morgan's laws can be proved as illustrated below:
Proof of First De Morgan's Law
In order to prove first law which is $(A \cup B)^{c}=A^{c} \cap B^{c}$, we have to prove that if an element belongs to $(A \cup B)^{c}$ and same element must belong to $A^{c} \cap B^{c}$.

Let us consider that $x \in (A \cup B)^{c}$, then from the definition of complement,
$x \notin A \cup B$
$x \in (A \cup B)^{c}$
$(x \in A \cup x \in B)^{c}$ .........(by the definition of union)
$(x \in A)^{c} \cap (x \in B)^{c}$ ...(by the definition of complement)
$(x \notin A) \cap (x \notin B)$
$(x \in A^{c}) \cap (x \in B^{c})$
$x \in (A^{c} \cap B^{c})$
Since $x \in (A \cup B)^{c} \Rightarrow x \in (A^{c} \cap B^{c})$
Hence, $(A \cup B)^{c}=A^{c} \cap B^{c}$
Therefore, first law of De Morgan is proved.

Proof of First De Morgan's Law
Similarly, to prove this law which is given by the statement $(A \cap B)^{c}=A^{c} \cup B^{c}$, we shall assume an element belonging to $(A \cap B)^{c}$ , to prove that same element belongs to $A^{c} \cup B^{c}$.

Let us assume that $x \in (A \cap B)^{c}$, then from complement definition, we have
$x \notin A \cap B$
$x \in (A \cap B)^{c}$
$(x \in A \cap x \in B)^{c}$ .........(intersection definition)
$(x \in A)^{c} \cup (x \in B)^{c}$ ...(by complement definition)
$(x \notin A) \cup (x \notin B)$
$(x \in A^{c}) \cup (x \in B^{c})$
$x \in (A^{c} \cup B^{c})$
Since $x \in (A \cap B)^{c} \Rightarrow x \in (A^{c} \cup B^{c})$
Hence, $(A \cap B)^{c}=A^{c} \cup B^{c}$
Therefore, first law of De Morgan is proved.