Understand and prove De Morgan's laws and their applications.
Understanding De Morgan's Laws
De Morgan's Laws are fundamental rules in set theory and logic that describe how complements interact with unions and intersections of sets. These laws provide a way to express the complement of a union in terms of intersections of complements, and vice versa. They are essential tools for simplifying complex set expressions and are widely used in mathematics, computer science, and engineering.
1. Preliminaries: Sets and Operations
Before diving into De Morgan's Laws, let's recall some basic set concepts:
Universal Set (U): The set containing all elements under consideration.
Complement of a Set (A'): The set of all elements in U that are not in A.
Union (A \cup B): The set of elements that are in A or B or both.
Intersection (A \cap B): The set of elements that are in both A and B.
Difference (A - B): The set of elements in A but not in B.
Notation reminder: The complement of a set \( A \) is denoted by \( A' \) or \( \overline{A} \).
2. Statements of De Morgan's Laws
For any two sets \( A \) and \( B \) within a universal set \( U \), De Morgan's Laws state:
\[(A \cup B)' = A' \cap B'\] \[(A \cap B)' = A' \cup B'\]
In words:
The complement of the union of two sets is the intersection of their complements.
The complement of the intersection of two sets is the union of their complements.
3. Intuitive Explanation Using Venn Diagrams
Consider the universal set \( U \) represented by a rectangle, and two sets \( A \) and \( B \) as overlapping circles inside it.
In the diagram above:
\( A \cup B \) is the area covered by both circles.
\( (A \cup B)' \) is everything outside both circles.
\( A' \cap B' \) is the intersection of the areas outside \( A \) and outside \( B \), which is also everything outside both circles.
This visual confirms the first De Morgan's Law. A similar argument holds for the second law.
4. Proofs of De Morgan's Laws
Proof Using Element Method
We prove the first law; the second follows similarly.
To prove: \( (A \cup B)' = A' \cap B' \)
Proof: Let \( x \in U \).
\( x \in (A \cup B)' \) means \( x \notin A \cup B \).
By definition of union, \( x \notin A \cup B \) means \( x \notin A \) and \( x \notin B \).
Therefore, \( x \in A' \) and \( x \in B' \), so \( x \in A' \cap B' \).
Hence, \( (A \cup B)' \subseteq A' \cap B' \).
Conversely, if \( x \in A' \cap B' \), then \( x \in A' \) and \( x \in B' \), so \( x \notin A \) and \( x \notin B \), which implies \( x \notin A \cup B \), so \( x \in (A \cup B)' \).
Thus, \( A' \cap B' \subseteq (A \cup B)' \).
Combining both, \( (A \cup B)' = A' \cap B' \).
Proof of Second Law
Similarly, to prove \( (A \cap B)' = A' \cup B' \), consider \( x \in (A \cap B)' \). Then \( x \notin A \cap B \), so \( x \notin A \) or \( x \notin B \), which means \( x \in A' \) or \( x \in B' \), hence \( x \in A' \cup B' \). The converse follows similarly.
5. Important Related Concepts
Power Set: The set of all subsets of a set \( S \). If \( n(S) = k \), then \( n(\mathcal{P}(S)) = 2^k \).
Subset: A set \( A \) is a subset of \( B \) (denoted \( A \subseteq B \)) if every element of \( A \) is also in \( B \).
Symmetric Difference: \( A \oplus B = (A - B) \cup (B - A) \).
6. Applications of De Morgan's Laws
De Morgan's Laws are used to:
Simplify expressions involving complements, unions, and intersections.
Convert logical expressions in Boolean algebra.
Design digital circuits by transforming AND/OR gates with NOT gates.
Prove other set identities and properties.
7. Common Mistakes to Avoid
Confusing union and intersection when taking complements.
Forgetting that the complement is always relative to the universal set \( U \).
Assuming \( (A \cup B)' = A' \cup B' \) or \( (A \cap B)' = A' \cap B' \), which is incorrect.
8. Connection to Board Exam Patterns
Questions on De Morgan's Laws often appear as:
Prove or verify De Morgan's Laws using element method or Venn diagrams.
Simplify set expressions using De Morgan's Laws.
Find complements of unions or intersections.
Apply laws to solve problems involving power sets and subsets.
Understanding these laws thoroughly helps in solving both theoretical and applied problems efficiently.
Worked Examples
Example 1: Verify \( (A \cup B)' = A' \cap B' \) using element method
Given: \( U = {1, 2, 3, 4, 5, 6} \), \( A = {1, 2, 3} \), \( B = {3, 4, 5} \).
Find: \( (A \cup B)' \) and \( A' \cap B' \), and verify equality.
Solution:
Calculate \( A \cup B = {1, 2, 3, 4, 5} \).
Complement \( (A \cup B)' = U - (A \cup B) = {6} \).
Calculate complements: \( A' = U - A = {4, 5, 6} \), \( B' = U - B = {1, 2, 6} \).
Find intersection \( A' \cap B' = {6} \).
Since \( (A \cup B)' = A' \cap B' = {6} \), the law is verified.
Difficulty: ★☆☆☆☆ (Basic)
Example 2: Find \( (A \cap B)' \) given \( U = {1, 2, 3, 4, 5, 6, 7} \), \( A = {1, 3, 5} \), \( B = {3, 4, 5, 6} \)
Solution:
Calculate \( A \cap B = {3, 5} \).
Complement \( (A \cap B)' = U - {3, 5} = {1, 2, 4, 6, 7} \).
Calculate complements: \( A' = U - A = {2, 4, 6, 7} \), \( B' = U - B = {1, 2, 7} \).
Find union \( A' \cup B' = {1, 2, 4, 6, 7} \).
Since \( (A \cap B)' = A' \cup B' \), the law holds.
Difficulty: ★☆☆☆☆ (Basic)
Example 3: Simplify \( (A \cup B \cup C)' \) using De Morgan's Laws
Given: Sets \( A, B, C \subseteq U \).
Solution:
Using De Morgan's Law extended to three sets:
\[ (A \cup B \cup C)' = A' \cap B' \cap C' \]
This is a direct extension of the two-set law.
Difficulty: ★★☆☆☆ (Intermediate)
Example 4: If \( A \subseteq B \), prove \( A \cup B = B \)
Proof:
Since \( A \subseteq B \), every element of \( A \) is in \( B \).
Therefore, \( A \cup B \) contains all elements of \( B \) and possibly more from \( A \), but since \( A \subseteq B \), no new elements are added.
Hence, \( A \cup B = B \).
Difficulty: ★☆☆☆☆ (Basic)
Example 5: Find the number of subsets of \( S = {1, 2, 3, 4, 5} \) and verify the power set cardinality formula
Solution:
Number of elements in \( S \) is \( n(S) = 5 \).
Number of subsets \( = 2^{n(S)} = 2^5 = 32 \).
This includes the empty set and the set \( S \) itself.
Difficulty: ★☆☆☆☆ (Basic)
Example 6: Given \( A = {1, 2, 5, 6} \), \( B = {1, 2, 3} \), find \( (A \times B) \cap (B \times A) \)
Solution:
Cartesian product \( A \times B = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (5,1), (5,2), (5,3), (6,1), (6,2), (6,3)} \).
Cartesian product \( B \times A = {(1,1), (1,2), (1,5), (1,6), (2,1), (2,2), (2,5), (2,6), (3,1), (3,2), (3,5), (3,6)} \).
Find intersection \( (A \times B) \cap (B \times A) \) = pairs common to both:
\( (1,1) \) and \( (2,2) \) are common (since both appear in \( A \times B \) and \( B \times A \)).
\( (1,2) \) is in \( A \times B \) but \( (1,2) \notin B \times A \) (since first element is from \( B \) in \( B \times A \)).
\( (2,1) \) is in both.
Therefore, \( (A \times B) \cap (B \times A) = {(1,1), (2,2), (2,1), (1,2)} \).
Difficulty: ★★☆☆☆ (Intermediate)
Formula Bank
Complement of union: \( (A \cup B)' = A' \cap B' \)
Complement of intersection: \( (A \cap B)' = A' \cup B' \)
Power set cardinality: If \( n(S) = k \), then \( n(\mathcal{P}(S)) = 2^k \)
Subset definition: \( A \subseteq B \iff \forall x (x \in A \Rightarrow x \in B) \)
Symmetric difference: \( A \oplus B = (A - B) \cup (B - A) \)
Set difference: \( A - B = {x : x \in A \text{ and } x \notin B} \)
Union and intersection subset relations: If \( A \subseteq C \), then \( (A \cap B) \subseteq (C \cap B) \) and \( (A \cup B) \subseteq (C \cup B) \)
Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
