De Morgan’s Laws

De Morgan's Laws - Definition, Explanation, and Examples

De Morgan's laws are fundamental rules in set theory that describe the relationship between union, intersection, and complements of sets. They help simplify complex set expressions, especially involving complements.

Statements of De Morgan's Laws

Let $A$ and $B$ be two sets and $U$ be the universal set.

1. The complement of the union of two sets is equal to the intersection of their complements:

$(A\cup B{)}^{\prime }=A^{\prime }\cap B^{\prime }$

2. The complement of the intersection of two sets is equal to the union of their complements:

$(A\cap B{)}^{\prime }=A^{\prime }\cup B^{\prime }$

Here, $A^{\prime }$ denotes the complement of $A$ with respect to $U$.

Explanation

- The first law means that everything not in either $A$ or $B$ is exactly the elements not in $A$ and not in $B$. - The second law means that everything not in both $A$ and $B$ is everything not in $A$ or not in $B$.

Examples

Example 1

Let

$U=\{1,2,3,4,5,6\}$ $A=\{1,2,3\}$ $B=\{3,4,5\}$

Calculate $(A\cup B{)}^{\prime }$ and $A^{\prime }\cap B^{\prime }$:

- $A\cup B=\{1,2,3,4,5\}$ - $(A\cup B{)}^{\prime }=U-(A\cup B)=\{6\}$

Find complements:

- $A^{\prime }=U-A=\{4,5,6\}$ - $B^{\prime }=U-B=\{1,2,6\}$

Calculate intersection of complements:

- $A^{\prime }\cap B^{\prime }=\{4,5,6\}\cap \{1,2,6\}=\{6\}$

Thus,

$(A\cup B{)}^{\prime }=A^{\prime }\cap B^{\prime }=\{6\}$

Example 2

Using the same sets,

Calculate $(A\cap B{)}^{\prime }$ and $A^{\prime }\cup B^{\prime }$:

- $A\cap B=\{3\}$ - $(A\cap B{)}^{\prime }=U-\{3\}=\{1,2,4,5,6\}$

Calculate union of complements:

- $A^{\prime }\cup B^{\prime }=\{4,5,6\}\cup \{1,2,6\}=\{1,2,4,5,6\}$

Therefore,

$(A\cap B{)}^{\prime }=A^{\prime }\cup B^{\prime }=\{1,2,4,5,6\}$

Summary

• De Morgan's laws provide a way to distribute complements over unions and intersections.
• These laws are very useful in simplifying set expressions and solving problems in mathematics, logic, and computer science.