First De Morgan’s Law
First De Morgan’s law states that “The complement of the union of two sets is equal to the intersection of the complements of each set.”
Let A and B be two sets, then mathematically First De Morgan’s Law is given as:
(A ∪ B)’ = A’ ∩ B’
Where
- U represents the Union operation between sets,
- ∩ represents intersection operation between sets, and
- ‘ represents complement operation on a set.
It is also called De Morgan’s Law of Union.
Detail the Proof of De Morgan’s Law
Step | Explanation |
---|---|
Step 1: State the Law | De Morgan’s Law includes two parts: ¬(A ∪ B) = ¬A ∩ ¬B and ¬(A ∩ B) = ¬A ∪ ¬B. |
Step 2: Choose an Element | Let’s prove ¬(A ∪ B) = ¬A ∩ ¬B. Assume an element x that is not in A ∪ B. |
Step 3: Understand the Assumption | If x is not in A ∪ B, then x is neither in A nor in B. |
Step 4: Apply the Definition | By the definition of complement, if x is not in A and not in B, then x is in ¬A and in ¬B. |
Step 5: Conclude the Proof | Since x is in both ¬A and ¬B, x is in ¬A ∩ ¬B. Thus, we’ve shown ¬(A ∪ B) = ¬A ∩ ¬B. |
Proof Using Algebra of Sets
We need to prove, (A ∪ B)’ = A’ ∩ B’
Let X = (A ∪ B)’ and Y = A’ ∩ B’
Let p be any element of X, then p ∈ X ⇒ p ∈ (A ∪ B)’
⇒ p ∉ (A ∪ B)
⇒ p ∉ A or p ∉ B
⇒ p ∈ A’ and p ∈ B’
⇒ p ∈ A’ ∩ B’
⇒ p ∈ Y
∴ X ⊂ Y . . . (i)
Again, let q be any element of Y, then q ∈ Y ⇒ q ∈ A’ ∩ B’
⇒ q ∈ A’ and q ∈ B’
⇒ q ∉ A or q ∉ B
⇒ q ∉ (A ∪ B)
⇒ q ∈ (A ∪ B)’
⇒ q ∈ X
∴ Y ⊂ X . . . (ii)
From (i) and (ii) X = Y
(A ∪ B)’ = A’ ∩ B’
Also Read – Proof of De-Morgan’s laws in boolean algebra
Proof Using Venn Diagram
Venn Diagram for (A ∪ B)’
Venn Diagram for A’ ∩ B’
From both Diagrams, we can clearly say,
(A ∪ B)’ = A’ ∩ B’
That is the First De Morgan’s Law.
De Morgan’s Law – Theorem, Proofs, Formula & Examples
De Morgan’s law is the most common law in set theory and Boolean algebra as well as set theory. In this article, we will learn about De Morgan’s law, De Morgan’s law in set theory, and De Morgan’s law in Boolean algebra along with its proofs, truth tables, and logic gate diagrams. The article also includes the solved De Morgan’s Law Example and FAQs on De Morgan’s law. Let us learn about De Morgan’s law.
Table of Content
- What is De Morgan’s Law
- De Morgan’s Law in Set Theory
- First De Morgan’s Law
- Second De Morgan’s Law
- Proof Using Algebra of Sets
- De Morgan’s Law in Boolean Algebra
- De Morgan’s Law Formula
- Solved Examples on De Morgan’s Law
- Logic Applications of De Morgan’s Law