De Morgan's Law

De Morgan’s laws are two key transformation rules in Boolean algebra and set theory. They show how the union and intersection of sets relate to their complements. These laws help simplify complex expressions, making calculations and Boolean operations easier to handle.

According to De Morgan’s Laws:
 

• The complement of the union of two sets is the same as the intersection of their individual complements.
• The complement of the intersection of two sets is the same as the union of their individual complements.

These relationships can be clearly understood with the help of Venn diagrams. In this lesson, we will explore the statements of De Morgan’s laws, see how they are proven, and understand their applications with examples.

For example,

Let:

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


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

A ∪ B = {1, 2, 3, 4, 5, 6}

Its complement \((A ∪ B)’ = ∅\)
 

A’ = {5, 6}
 

B’ = {1, 2}
 

Now,

\(A' \cap B' = \{ \} = \varnothing \)
 

So,

\(\ (A \cup B)' = A' \cap B' \ \)

This verifies the first De Morgan’s law.
 

De Morgan’s laws are used in both Boolean algebra and set theory to simplify expressions involving unions, intersections, and complements. Let A and B be two subsets of a universal set U. The complements of A and B are written as A’ and B’ respectively. The symbol ∩ represents intersection, and ∪ means union.
Using these notations, De Morgan’s laws are stated as follows:

1. De Morgan’s Law of Union
The complement of the union of two sets A and B is equal to the intersection of their complements.
In symbolic form:
 

\((A ∪ B)’ = A’ ∩ B’\)

This rule can be extended to multiple sets. For a collection of sets \(\ \{A_1, A_2, \ldots, A_n\} \ \):

\(\ \left( \bigcup_{i=1}^{n} A_i \right)' = \bigcap_{i=1}^{n} A_i' \ \)

In the Venn diagram, the orange region shows A ∪ B, while the blue shaded region represents (A ∪ B)’.

2. De Morgan’s Law of Intersection
The complement of the intersection of sets A and B is equal to the union of their complements.
 

Symbolically:
 

\((A ∩ B)’ = A’ ∪ B’\)
 

This law also generalizes to multiple sets:

\(\ \left( \bigcap_{i=1}^{n} A_i \right)' = \bigcup_{i=1}^{n} A_i' \ \)

In the Venn diagram, the orange region indicates A ∩ B, while the blue area shows (A ∩ B)’.

In set theory, De Morgan’s laws show that when taking the complement of a union or intersection, the operations switch places. These laws can be proven using mathematical reasoning or truth tables.

1. Proof of \((A ∪ B)’ = A’ ∩ B’\)

Let \(R = (A ∪ B)’\) and \(S = A’ ∩ B’\).

To show \(R = S\), we must prove both \(R ⊂ S\)  and \(S ⊂ R\).
 

Step 1: Proving \(R ⊂ S\)
 

Take any element \(y ∈ R.\)
 

\(y ∈ (A ∪ B)’\)
 

⇒ \(y ∉ (A ∪ B)\)
 

⇒ \( y ∉ A\) and \(y ∉ B\)
 

⇒ \(y ∈ A’\) and \(y ∈ B’\)
 

⇒ \(y ∈ A’ ∩ B’\)
 

⇒ \(y ∈ S\)
 

Thus, \(R ⊂ S. …(1)\)

Step 2: Proving \( S ⊂ R\)
 

Take any element \(z ∈ S\).
 

\(z ∈ A’ ∩ B’\)
 

⇒ \(z ∈ A’\) and \(z ∈ B’\)
 

⇒ \(z ∉ A \) and \(z ∉ B\)
 

⇒ \(z ∉ (A ∪ B)\)
 

⇒ \(xz ∈ (A ∪ B)’\)
 

⇒\( z ∈ R\)
 

Thus, \(S ⊂ R. …(2)\)
 

From (1) and (2), we conclude:
 

\((A ∪ B)’ = A’ ∩ B’\)

2. Proof of \((A ∩ B)’ = A’ ∪ B’\)
 

Let\( G = (A ∩ B)’ \) and \(H = A’ ∪ B’\).


To show G = H, we again prove \( G ⊂ H\) and \(H ⊂ G\).

 

Step 1: Proving \(G ⊂ H\)
 

Take any element \( y ∈ G\).
 

\(y ∈ (A ∩ B)’\)
 

⇒ \(y ∉ (A ∩ B)\)
 

⇒ \( y ∉ A \) or \(y ∉ B\)
 

⇒ \(y ∈ A’\) or \(y ∈ B’\)
 

⇒ \(y ∈ A’ ∪ B’\)
 

⇒ \(y ∈ H\)
 

Thus, \(G ⊂ H. …(1)\)
 

\( G ⊂ H. …(1)\)
 

Step 2: Proving \(H ⊂ G\)
 

Take any element \(z ∈ H\).
 

\(z ∈ A’ ∪ B’\)
 

⇒\( z ∈ A’ or z ∈ B’\)
 

⇒ \(z ∉ A or z ∉ B\)
 

⇒ \(z ∉ (A ∩ B)\)
 

⇒ \(z ∈ (A ∩ B)’\)
 

⇒ \(z ∈ G\)
 

Thus, \(H ⊂ G. …(2)\)
 

Combining (1) and (2), we get:
 

\((A ∩ B)’ = A’ ∪ B’.\)

De Morgan’s laws describe how logical operations behave under negation. In Boolean algebra, they are written as: 

• \(¬(A • B) = ¬A + ¬B\)
• \(¬(A + B) = ¬A • ¬B\)
   

Here, A and B are binary input variables that take values 0 or 1. Logical operations such as\( AND (A • B)\), \(OR (A + B)\), and NOT (negation) are represented using truth tables. These laws can be proved using these truth tables.

1. First De Morgan’s Law

Statement:
When two or more variables are OR’ed and then negated, the result is equal to the AND of their complements.

\(⇁(A+B)=⇁A⇁B\)
 

Truth Table Proof

The last two columns are identical, proving:

\(¬(A+B)=¬A⋅¬B\)

2. Second De Morgan’s Law

Statement:
When two or more variables are AND’ed and then negated, the result is equal to the OR of their complements.

\(¬(A⋅B)=¬A+¬B\)

Truth Table Proof

Again, the last two columns match, proving:

\(¬(A⋅B)=¬A+¬B\)

Let us learn more about De Morgan’s formulas in set theory, boolean algebra, and logic.

In set theory:
 

• \((A ∪ B)’ = A’ ∩ B’\) (The complement of the union of two sets is the intersection of their complements.)
  
   
• \((A ∩ B)’ = A’ ∪ B’ \)(The complement of the intersection of two sets is the union of their complements.)

Where:
 

• \(∪\) = Union (OR in sets)
• ∩ = Intersection (AND in sets)
• ’ = Complement (NOT in sets)

In Logic: 
 

• \(\ \sim (a \land b) \equiv \sim a \lor \sim b \ \)(The negation of “A AND B” is equivalent to “NOT A OR NOT B”)
   
• \(\ \sim (a \lor b) \equiv \sim a \land \sim b \ \) (The negation of “A OR B” is equivalent to “NOT A  AND NOT B.”)
   

Where:
 

•  ∼ → NOT (negation)
• ∧ = AND
• ∨ = OR

De Morgan's law helps simplify complex logical expressions in math, programming, and circuits. Regular practice makes applying the rules faster and more accurate.
 

• Know that \(¬(A ∧ B) = ¬A ∨ ¬B\) an\(¬(A ∨ B) = ¬A ∧ ¬B\).
  
   
• Verify the law by creating truth tables for AND, OR, and NOT operations.
  
   
• Rewrite complex logical expressions using De Morgan's Law for easier simplification.
  
   
• Draw logic diagrams to see how AND/OR gates transform into equivalent forms.
  
   
• Practice rewriting conditional statements in programming to strengthen understanding.
  
   
• Parents can introduce basic logic diagrams to show how AND/OR gates change when the law is applied.
  
   
• Children can practice rewriting conditional statements in coding, while parents or teachers give small exercises.

De Morgan’s law is widely used in several fields, mainly computer science. Here are some real-world uses of De Morgan’s law:
 

• Circuit design: Engineers use De Morgan’s law to simplify AND-OR logic and convert it into equivalent NAND or NOR circuits. 
  
   
• Computer programming: Logical conditions used in programming can be rewritten to make the code more efficient.
  
   
• Search engines: De Morgan’s law helps simplify complex search conditions for better accuracy.
  
   
• Database queries: Simplifies complex NOT, AND, OR conditions in SQL queries for faster data retrieval.
  
   
• Digital security systems: Helps design logic for alarms and access controls by simplifying security rules.