De Morgan’s Laws

De Morgan’s Laws

Augustus De Morgan (1806 – 1871) was a British mathematician. He was born on 27^th June 1806 in Madurai, Tamilnadu, India. His father was posted in India by the East India Company. When he was seven months old, his family moved back to England. De Morgan was educated at Trinity College, Cambridge, London. He formulated laws for set difference and complementation. These are called De Morgan’s laws.

1. De Morgan’s Laws for Set Difference

These laws relate the set operations union, intersection and set difference.

Let us consider three sets A, B and C as A = {−5, −2,1, 3}, B = {−3,−2, 0, 3, 5} and C = {−2,−1, 0, 4,5}.

Now, B ∪C = {-3,-2,-1, 0, 3, 4,5}

 A − (B ∪C) = { −5,1 }  ... (1)

Then,

 A − B = {-5, 1} and A − C = { −5, 1, 3}

 (A−B)∪(A−C) = { −5,1, 3 } ... (2)

 (A−B)∩(A−C) = { −5,1 } ... (3)

From (1) and (2), we see that

 A−(B ∪C) ≠ (A−B)∪(A−C)

But note that from (1) and (3), we see that

A−(B ∪C) = (A−B)∩(A−C)

Thinking Corner

(A−B) ∪(A−C) ∪(A ∩ B)=____

Now,  B ∩C = { −2, 0, 5 }

A−(B ∩C) = { −5,1, 3 } ... (4)

From (3) and (4) we see that

 A−(B ∩C) ≠ (A−B)∩(A−C)

But note that from (2) and (4), we get A − (B ∩ C ) = (A − B ) ∪ (A −C)

De Morgan’s laws for set difference : For any three sets A, B and C

(i) A − (B ∪ C ) = (A − B ) ∩ (A −C) (ii) A − (B ∩ C ) = (A − B ) ∪ (A −C)

Example 1.23

Verify A − (B ∪ C ) = (A − B ) ∩ (A −C) using Venn diagrams.

Solution

From (1) and (2), we get A − (B ∪C ) = (A − B ) ∩ (A −C) . Hence it is verified.

Example 1.24

If P = {x : x∈ W and 0 < x < 10}, Q = {x : x = 2n+1, n∈ W and n<5} and R = { 2, 3, 5, 7,11, 13}, then verify P − (Q ∩ R ) = (P −Q ) ∪ (P − R)

Solution The roster form of sets P, Q and R are

P = {1,2,3,4,5,6,7,8,9} , Q = {1,3,5,7,9} and R = {2, 3, 5, 7,11, 13}

First, we find (Q ∩ R) = {  3,5,7 }

Then, P − (Q ∩ R) = { 1,2,4,6,8,9 } ... (1)

Next, P–Q = { 2,4,6,8 } and

P–R = { 1,4,6,8,9 }

and so, (P − Q) ∪ (P − R) = { 1,2, 4,6, 8,9} ... (2)

Hence from (1) and (2), it is verified that P − (Q ∩ R ) = (P −Q ) ∪ (P − R).

Finding the elements of set Q

Given, x = 2n + 1

n = 0 → x = 2(0) +1 = 0 +1 = 1

n = 1 → x = 2(1) +1 = 2 +1 = 3

n = 2 → x = 2(2) +1 = 4 +1 = 5

n = 3 → x = 2(3) +1 = 6 +1 = 7

n = 4 → x = 2(4) +1 = 8 +1 = 9

Therefore, x takes values such as 1, 3, 5, 7 and 9.

2. De Morgan’s Laws for Complementation

These laws relate the set operations on union, intersection and complementation.

Thinking Corner : Check whether A−B =A∩B′

Let us consider universal set U={0,1,2,3,4,5,6}, A={1,3,5} and B={0,3,4,5}.

Now, A ∪ B = {0,1, 3, 4,5}

Then, (A ∪ B)′ = {2,6} .....(1)

Next, A′ = {0, 2, 4, 6} and B′ = {1,2,6}

Then, A′ ∩ B′ = {2,6} .....(2)

From (1) and (2), we get (A ∪ B)′ = A′ ∩ B′

Also, A ∩ B = {3, 5},

Thinking Corner (A− B) ∪ (B − A′ ) = ____

 (A ∩ B)′ = {0,1,2, 4, 6} .....(3)

A′ = { 0,2,4,6 } and B′ = { 1,2,6 }

A′ ∪ B′ = { 0,1,2, 4,6 } .....(4)

From (3) and (4), we get (A ∩ B)^′ = A′ ∪ B′

De Morgan’s laws for complementation : Let ‘U’ be the universal set containing finite sets A and B. Then (i) (A ∪ B)′ = A′ ∩ B′ (ii) (A ∩ B)′ = A′ ∪ B′

Example 1.25

Verify (A ∪ B)′ = A′ ∩ B′ using Venn diagrams.

Solution

From (1) and (2), it is verified that (A ∪ B)′ = A′ ∩ B′

Example 1.26

If U = {x : x ∈ ℤ, − 2 ≤ x ≤ 10}, A = {x : x = 2 p + 1, p ∈ ℤ, − 1 ≤ p ≤ 4}, B = {x : x = 3q + 1, q ∈ ℤ, − 1 ≤ q < 4}, verify De Morgan’s laws for complementation.

Solution

Given U = {−2, −1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} ,

A= {−1, 1, 3, 5, 7, 9} and B = {−2, 1, 4, 7,10}

Thinking Corner  A ∩ (A ∪ B)′ =____

Law (i) (A ∪ B)′ = A′ ∩ B′

Now, A ∪ B = {-2,-1,1, 3, 4,5,7,9,10}

 (A ∪ B)′ = {0,2,6, 8} ..... (1)

Then, A′ = {-2, 0, 2, 4, 6, 8,10} and B′ = {-1, 0,2, 3,5,6, 8,9}

 A′ ∩ B′ = {0, 2, 6, 8} ..... (2)

From (1) and (2), it is verified that (A∪B)′ =  A′ ∩ B ′

Law (ii) (A ∩ B)′ =A′ ∪B′

Now, A ∩ B = {1,7}

 (A ∩ B)′ = {-2,-1, 0,2, 3, 4,5,6, 8,9,10}     ..... (3)

Then, A′ ∪ B′ = {-2,-1, 0,2, 3, 4,5,6, 8,9,10}      ..... (4)

From (3) and (4), it is verified that (A∩B)′ = A′ ∪ B′

Thinking Corner (A ∪ B)′ ∪ (A′ ∩ B) =___