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.
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'.
(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.
(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.
Let U = {j, k, l, m, n}, X = {j, k, m} and Y = {k, m, n}. Prove : (X ∩ Y)' = X' U Y'
Here, U = {j, k, l, m, n} X = {j, k, m} Y = {k, m, n}
(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}
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
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'.
Here, U = {1, 2, 3, 4, 5, 6, 7, 8} P = {4, 5, 6} Q = {5, 6, 8}
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}
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.
