De Morgan’s Laws

De Morgan’s Laws are essential rules in mathematics that relate the complement of unions and intersections in set theory, and the negation of logical operations in Boolean algebra. These laws help simplify complex expressions and are widely used in algebraic proofs, logic design, and computer science. In sets, they show how the complement of a union is the intersection of complements, and vice versa. Understanding De Morgan’s Laws is key to mastering mathematical logic and set manipulation.

1.0What is De Morgan’s Law? (De Morgan's Law Definition)

De Morgan’s Laws describe how the complement of the union and intersection of two sets relate to each other. Formally, in set theory:

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

In symbols, these laws are expressed as :

De Morgan’s law formula:

1. $(A\cup B{)}^c=A^c\cap B^c$
2. $(A\cap B{)}^c=A^c\cup B^c$

Here, A and B are sets, A^c denotes the complement of set A, ∪ is union, and ∩ is intersection.

2.0De Morgan’s Law in Sets (Demorgan Law in Sets)

In set theory, De Morgan’s Laws help us simplify expressions involving complements, unions, and intersections. These laws reveal an elegant symmetry between union and intersection under complementation.

Example (Demorgan Law Example):

Let’s consider two sets:

• A = {1, 2, 3} 
• B = {3, 4, 5} 
• Universal set U = {1, 2, 3, 4, 5, 6} 

Find $(A\cup B{)}^c$:

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

Now, find $A^c\cap B^c$ :

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

Thus, $(A\cup B{)}^c=A^c\cap B^c$, which confirms De Morgan’s first law.

3.0De Morgan’s Law in Boolean Algebra (Demorgan Law Boolean Algebra)

De Morgan’s Laws are also fundamental in Boolean algebra, where they describe the relationship between logical operators AND $(\wedge )$ and OR $(\vee )$ under negation $(\neg )$:

$\begin{array}{rl}& \neg (A\wedge B)=\neg A\vee \neg B\\ & \neg (A\vee B)=\neg A\wedge \neg B\end{array}$

These correspond exactly to the set theory laws when interpreting union as OR and intersection as AND.

4.0Visualizing De Morgan’s Laws: Venn Diagrams and Truth Tables

De Morgan's Law Venn Diagram

A Venn diagram is a great way to visualize De Morgan’s Laws in set theory.

• The shaded region representing $(A\cup B{)}^c$ is exactly the area outside both A and B.
• This area matches the intersection of $A^c$ and $B^c$.

Similarly, $(A\cap B{)}^c$ covers everything outside the overlapping part of A and B, which equals the union of $A^c$ and $B^c$.

5.0De Morgan's Law Truth Table

In Boolean algebra, the truth table confirms the equivalence by listing all truth values for A and B and their combinations.

From the table, $\neg (A\wedge B)$ and $\neg A\vee \neg B$ always have the same truth values.

6.0De Morgan’s Law Statement and Proof

Statement:

$\begin{array}{rl}& (A\cup B{)}^c=A^c\cap B^c\\ & (A\cap B{)}^c=A^c\cup B^c\end{array}$

Proof for $(A\cup B{)}^c=A^c\cap B^c$:

To prove two sets are equal, show that each is a subset of the other:

• If $x\in (A\cup B{)}^c,thenx\notin A\cup B.So,x\notin Aandx\notin B$. Thus, $x\in A^{c}andx\in B^c$, which means $x\in A^c\cap B^c$.
• If $x\in A^c\cap B^c$, then $x\in A^c$ and $x\in B^c$. So, $x\notin Aandx\notin B$, which means $x\notin A\cup B$. Hence, $x\in (A\cup B{)}^c$.

Therefore, $(A\cup B{)}^c=A^c\cap B^c$.

7.0De Morgan’s Law Formula (Recap)

8.0Applications of De Morgan's Laws

• Digital circuit design and logic gate simplification
• Set theory proofs in mathematics
• Programming: logic operations in conditions
• Database queries: transforming NOT with AND/OR
• Mathematical logic and theorem proving

9.0Solved Examples on De Morgan’s Laws 

Example 1: Given: Universal set U = {1, 2, 3, 4, 5, 6, 7, 8},

A = {1, 2, 3, 4},

B = {3, 4, 5, 6}.

Find and verify $(A\cap B{)}^c$ using De Morgan’s law.

Solution:

1. Calculate A ∩ B:

A ∩ B = {3, 4}

2. Find complement $(A\cap B{)}^c$:

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

3. Find $A^c$ and $B^c$:

$A^c=U-A=\{5,6,7,8\},B^c=U-B=\{1,2,7,8\}$

4. Find union $A^c\cup B^c$:

$A^c\cup B^c=\{1,2,5,6,7,8\}$

Since $(A\cap B{)}^c=A^c\cup B^c$, De Morgan’s law holds.

Example 2: Simplify the expression: $\neg (X\vee Y)$  using De Morgan’s Law.

Solution:

By De Morgan’s law in Boolean algebra:

$\neg (X\vee Y)=\neg X\wedge \neg Y$

So the simplified expression is:

$\neg X\wedge \neg Y$

10.0Practice Questions on De Morgan’s Laws 

1. Given U = {a, b, c, d, e, f}, A = {a, c, e}, B = {b, c, d}, verify $(A\cup B{)}^c=A^c\cap B^c$.
2. Show that $\neg (P\wedge Q)=\neg P\vee \neg Q$ using a truth table.
3. Simplify the expression $\neg (A\wedge (B\vee C))$ using De Morgan’s Laws.