Complement Law Proof using De Morgan's Law

In boolean algebra, De Morgan's law is a pair of transformation valid rules of inference. The rule explains the conjunctions and disjunctions in terms of negation. The rule can be given as 'the complement of the union of two sets is the same as the intersection of their complements and the complement of the intersection of two sets is the same as the union of their complements.' Refer the below tutorial to know about Complement law Proof using De Morgan's Law.

Complement law:

De Morgan's Law states that, 'The complement of the union of two sets is equal to the intersection of their complements and the complement of the intersection of two sets is equal to the union of their complements'.

De Morgan’s Law:

For any two finite sets A and B; (i) (A U B)' = A' ∩ B' (De Morgan's Law of Union). (ii) (A ∩ B)' = A' U B' (De Morgan's Law of Intersection).
Proof of De Morgan’s Law :
Case 1:

(A U B)' = A' ∩ B' Let us consider P = (A U B)' and Q = A' ∩ B' Let 'x' 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 'y' 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) Now combining (i) and (ii) we get, P = Q i.e. (A U B)' = A' ∩ B' Hence, it is proved.

Case 2:

(A ∩ B)' = A' U B' Let us consider 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 Therefore, M ⊂ N …………….. (i) 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 Therefore, N ⊂ M …………….. (ii) Now combining (i) and (ii) we get, M = N i.e. (A ∩ B)' = A' U B' Hence, De Morgan's Law is proved.

Example 1:

Let U = {j, k, l, m, n}, X = {j, k, m} and Y = {k, m, n}. Prove : (X ∩ Y)' = X' U Y'

Solution:

Here, U = {j, k, l, m, n} X = {j, k, m} Y = {k, m, n}

Step 1:

(X ∩ Y) = {j, k, m} ∩ {k, m, n} = {k, m} Therefore, (X ∩ Y)' = {j, l, n} ……………….. (i) X = {j, k, m} Therefore, X' = {l, n} Y = {k, m, n} Therefore, Y' = {j, l}

Step 2:

X' ∪ Y' = {l, n} ∪ {j, l} Therefore, X' ∪ Y' = {j, l, n} ……………….. (ii) Combining (i) and (ii) we get, (X ∩ Y)' = X' U Y' Hence, the De Morgan's Law is Proved

Example 2:

Let U = {1, 2, 3, 4, 5, 6, 7, 8}; P = {4, 5, 6} and Q = {5, 6, 8}. Prove De Morgan's Law (P ∪ Q)' = P' ∩ Q'.

Solution:

Here, U = {1, 2, 3, 4, 5, 6, 7, 8} P = {4, 5, 6} Q = {5, 6, 8}

Step 1:

P ∪ Q = {4, 5, 6} ∪ {5, 6, 8} = {4, 5, 6, 8} Therefore, (P ∪ Q)' = {1, 2, 3, 7} ……………….. (i) P = {4, 5, 6} Therefore, P' = {1, 2, 3, 7, 8} Q = {5, 6, 8} Therefore, Q' = {1, 2, 3, 4, 7}

Step 2:

P' ∩ Q' = {1, 2, 3, 7, 8} ∩ {1, 2, 3, 4, 7} Therefore, P' ∩ Q' = {1, 2, 3, 7} ……………….. (ii) Combining (i) and (ii) we get; (P ∪ Q)' = P' ∩ Q' Hence, De Morgan's Law is proved.