DeMorgan’s Law - Proof & Examples

# DeMorgan’s Law

De Morgan’s is a common law that is applicable in different branches of mathematics like set theory, boolean algebra, in computer engineering etc. It is nothing but a pair of rules for translation.

These rules allow via negation the disjunctions and conjunctions completely in each other terms:

(X $\cup$ Y)’ = X’ $\cap$ Y’
(X $\cap$ Y)’ = X’ $\cup$ Y’

Where X’ and Y’ are complements respectively of the sets X and Y, ‘$\cup$’ stands for union operation and ‘$\cap$’ stands for intersection operation.

In words we can say that according to the De Morgan’s law when the complement of the union of given two sets is taken then it is equal to the intersection of the complements of the given sets and when the compliment of the intersection of given two sets is taken then it is equal to the union of the complements of the given sets.

## Proof

We will prove that (X $\cap$ Y)' = X' $\cup$ Y'and the other can be proved similarly:

Now to prove this we will prove two things:

i) (X $\cap$ Y)' $\subseteq$ X' $\cup$ Y'

ii) X' $\cup$ Y' $\subseteq$ (X $\cap$ Y)'

Suppose y $\epsilon$ (X $\cap$ Y)'

$\rightarrow$ y  $\notin$ X $\cap$ Y

$\rightarrow$ y $\notin$ X or y $\notin$ Y

$\rightarrow$ y $\epsilon$ X' or y $\epsilon$ N'

$\rightarrow$ y $\epsilon$ X' $\cup$ Y'

Since there exist a y $\epsilon$ (X $\cap$ Y)' such that y $\epsilon$ X' $\cup$ Y'

$\rightarrow$ (X $\cap$ Y)' $\subseteq$ X' $\cup$ Y'....(i)

Now consider z $\epsilon$ X' $\cup$ Y'

$\rightarrow$ z $\epsilon$ X' or z $\epsilon$ Y'

$\rightarrow$ z $\notin$ X or z $\notin$ Y

$\rightarrow$ z $\notin$ X $\cap$ Y

$\rightarrow$ z $\epsilon$ (X $\cap$ Y)'

Since there exist a z $\epsilon$ X' $\subseteq$ Y' such that z $\epsilon$ (X $\cap$ Y)'

$\rightarrow$ X' $\cup$ Y'$\subseteq$ (X $\cap$ Y)'...(ii)

From (i) and (ii) we get that

(X $\cap$ Y)' = X' $\cup$ Y' that is the De Morgan's law for intersection.

Similarly we can prove the De Morgan's law of union as well.

When we are given more than two sets we get generalize our laws as below:

[$\cup_{i = 1}^n (A_i)$]' = $\cap_{i = 1}^n$ [$(A_i)'$]

[$\cap_{i = 1}^n (A_i)$]' = $\cup_{i = 1}^n$ [$(A_i)'$]

## Examples

Below is an example on application or use of De Morgan’s laws.
Example 1: Let U = {1, 3, 5, 7, 9, 2, 6, 4, 8, 10}, A = {3, 2, 7, 5 ,8, 9}, and B = {2, 5, 4, 8, 10}

Prove De Morgan’s law of intersection here.

Solution:

Here A = {3, 2, 7, 5 ,8, 9}

B = {2, 5, 4, 8, 10}

A $\cap$ B = {2, 5, 8}

A’ = {1, 4, 6, 10}

B’ = {1, 3, 6, 7, 9}

According to De Morgan’s law of intersection (X $\cup$ Y)’ = X’ $\cap$ Y’

Left hand side

= (A $\cap$ B)’

= {2, 5, 8}’

= {1, 3, 4, 6, 7, 9, 10} … (i)

Right hand side

= A’ $\cup$ B’

= {1, 4, 6, 10} $\cup$ {1, 3, 6, 7, 9}

= {1, 3, 4, 6, 7, 9, 10} … (ii)

From (i) and (ii) we get that

Left hand side = right hand side

=> (A $\cap$ B)’ = A’ $\cup$ B’

Hence proved.

Example 2: If A = {a, b, c, d, e, f}, B = {b, d, f} and C = {f, b, c}
Prove that (B $\cap$ C)' = B' $\cup$ C'

Solution:

A = {a, b, c, d, e, f} (universal set)
B = {b, d, f} and
C = {f, b, c}

B $\cap$ C = Common elements of B and C = {b, f}

(B $\cap$ C)' = A - {b, f} = {a, c, d, e}  .....(1)

Again

B' = A - B = {a, c, e} and

C' = A - C = {a, d, e}

B' $\cup$ C' = Combine elements of B' and c' = {a, c, d, e}  ....(2)
From (1) and (2), we get

(B $\cap$ C)' = B' $\cup$ c'