Proof of De Morgan’s Law in Boolean Algebra | Demorgan’s Law Definition, Statement and Proof

According to Demorgan’s Law Complement of Union of Two Sets is the Intersection of their Complements and the Complement of Intersection of Two Sets is the Union of Complements. The Law can be expressed as such ( A ∪ B) ‘ = A ‘ ∩ B ‘. By referring to the further modules you can find Demorgan’s Law Statement, Proof along with examples.

For any two finite sets A and B, we have

(i) (A U B)’ = A’ ∩ B’ (which is a De Morgan’s law of union).

(ii) (A ∩ B)’ = A’ U B’ (which is a De Morgan’s law of intersection).

De Morgan’s Laws Statement and Proof

A Set is a well-defined collection of objects or elements. You can perform various operations on sets such as Complement, Union, and Intersection. These Operations and usage can be further simplified by a set of simple laws called Demorgan’s Laws.

Any Set that includes all the elements related to a particular context is called a universal set. Let us assume a Universal Set U such that A and B are Subsets of it.

De Morgan’s Law Proof: (A∪B)’= A’∩ B’   

As per Demorgan’s First Law, the Complement of Union of Two Sets A and B is equal to the Intersection of Complements of Sets A and B.

(A∪B)’= A’∩ B’

Let P = (A U B)’ and Q = A’ ∩ B’

Consider x to be an arbitrary element of P then x ∈ P ⇒ x ∈ (A U B)’

⇒ x ∉ (A U B)

⇒ x ∉ A and x ∉ B

⇒ x ∈ A’ and x ∈ B’

⇒ x ∈ A’ ∩ B’

⇒ x ∈ Q

Therefore, P ⊂ Q …………….. (i)

Let us consider y to be an arbitrary element of Q then y ∈ Q ⇒ y ∈ A’ ∩ B’

⇒ y ∈ A’ and y ∈ B’

⇒ y ∉ A and y ∉ B

⇒ y ∉ (A U B)

⇒ y ∈ (A U B)’

⇒ y ∈ P

Therefore, Q ⊂ P …………….. (ii)

Combining (i) and (ii) we get; P = Q i.e. (A U B)’ = A’ ∩ B’

De Morgan’s Law Proof: (A ∩ B)’ = A’ U B’

Let us consider Sets M = (A ∩ B)’ and N = A’ U B’

Let x be an arbitrary element of M then x ∈ M ⇒ x ∈ (A ∩ B)’

⇒ x ∉ (A ∩ B)

⇒ x ∉ A or x ∉ B

⇒ x ∈ A’ or x ∈ B’

⇒ x ∈ A’ U B’

⇒ x ∈ N

Thus, M ⊂ N …………….. (i)

Again, let y be an arbitrary element of N then y ∈ N ⇒ y ∈ A’ U B’

⇒ y ∈ A’ or y ∈ B’

⇒ y ∉ A or y ∉ B

⇒ y ∉ (A ∩ B)

⇒ y ∈ (A ∩ B)’

⇒ y ∈ M

Thus, N ⊂ M …………….. (ii)

Combining (i) and (ii) we get; M = N i.e. (A ∩ B)’ = A’ U B’

Examples of De Morgan’s Law

1. If U = {a,b,c, d, e}, X = {b, c, d} and Y = {b, d, e}. Prove that De Morgan’s law: (X ∩ Y)’ = X’ U Y’?

Solution:

Given Sets are U = {a,b,c, d, e}, X = {b, c, d} and Y = {b, d, e}

Firstly find the (X ∩ Y) = {b, c, d} ∩ {b, d, e}

= { b,d}

(X ∩ Y)’ = U – (X ∩ Y)

= {a,b,c, d, e} – { b,d}

= {a,c,e}

X’ =  U – X

= {a,b,c, d, e} – {b, c, d}

= {a,e}

Y’ = U – Y

= {a,b,c, d, e} – {b, d, e}

= {a,c}

X’ U Y’ = {a,e} U {a,c}

= {a,c,e}

Hence Prooved (X ∩ Y)’ = X’ U Y’

2. Let U = {1, 2, 3, 4, 5, 6, 7, 8}, A = {2, 3, 4} and B = {5, 6, 8}. Show that (A ∪ B)’ = A’ ∩ B’?

Solution:

Given Sets are U = {1, 2, 3, 4, 5, 6, 7, 8}, A = {4, 5, 6} and B = {5, 6, 8}
(A ∪ B) = {4, 5, 6} ∪ {5, 6, 8}

= {4, ,5, 6, 8}

(A ∪ B)’ = U – (A ∪ B)

= {1, 2, 3, 4, 5, 6, 7, 8} – {4, ,5, 6, 8}

= {1, 2, 3,7}

A’ = U – A

= {1, 2, 3, 4, 5, 6, 7, 8} – {4, 5, 6}

= {1, 2, 3, 7, 8}

B’ = U – B

= {1, 2, 3, 4, 5, 6, 7, 8} – {5, 6, 8}

= {1, 2, 3, 4, 7}

A’ ∩ B’ = {1, 2, 3, 7, 8} ∩ {1, 2, 3, 4, 7}

= {1, 2, 3, 7}

Hence Prooved (A ∪ B)’ = A’ ∩ B’

 

Leave a Comment

Scroll to Top