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

## What is De Morgan’s Law

De Morgan’s law is the law that gives the relation between union, intersection, and complements in set theory. In Boolean algebra, it gives the relation between AND, OR, and complements of the variable, and in logic, it gives the relation between AND, OR, or Negation of the statement. With the help of De Morgan’s Law, we can optimize various boolean circuits involving logic gates which help us perform the same operation but with very few apparatus.

## De Morgan’s Law in Set Theory

De Morgan’s law in the set theory defines the relationship between the union, intersection, and complements of the sets, and is given for both complement of union and intersection of two sets. In set theory, there are two De Morgan’s Laws that are:

- First De Morgan’s Law
- Second De Morgan’s Law

Let’s understand these laws in detail as below:

## 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

represents the Union operation between sets,Urepresents 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**

**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’

Proof of De-Morgan’s laws in boolean algebraAlso Read –

**Proof Using Venn Diagram**

**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.

## Second De Morgan’s Law

Second De Morgan’s law states that **“The complement of intersection of two sets is equal to the union 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

represents the Union operation between sets,Urepresents intersection operation between sets, and∩represents complement operation on a set.‘

It is also called ** De Morgan’s Law of Intersection**.

**Proof Using Algebra of Sets**

**Proof Using Algebra of Sets**

Second De Morgan’s law: (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 and p ∉ B

⇒ p ∈ A’ or 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’ or q ∈ B’

⇒ q ∉ A and q ∉ B

⇒ q ∉ (A ∩ B)

⇒ q ∈ (A ∩ B)’

⇒ q ∈ X

∴ Y ⊂ X ————–(ii)

From (i) and (ii) X = Y

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

**Proof Using Venn Diagram**

**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 Second De Morgan’s Law.

## De Morgan’s Law in Boolean Algebra

De Morgan’s Law Boolean Algebra defines the relation between the OR, AND, and the complements of variables, and is given for both the complement of AND and OR of two values. In Boolean Algebra there are two De Morgan’s Laws that are:

- First De Morgan’s Law
- Second De Morgan’s Law

Let’s understand these laws in detail as below:

## First De Morgan’s Law in Boolean Algebra

First De Morgan’s law states that **“The complement of OR of two or more variables is equal to the AND of the complement of each variable.”**

Let A and B be two variables, then mathematically First De Morgan’s Law is given as:

(A + B)’ = A’ . B’Where

- + represents the OR operator between variables,
represents AND operator between variables, and.represents complement operation on variable.‘

### First De Morgan’s Law Logic Gates

In context to logic gates and Boolean Algebra, De Morgan’s Law states that “Both the logic gate circuits i.e., NOT gate is added to the output of OR gate, and NOT gate is added to the input of AND gate, are equivalent. These two logic gate circuits are given as follows:

### First De Morgan’s Law Truth Table

The truth table for first De Morgan’s Law is given as follows:

A | B | A + B | (A + B)’ | A’ | B’ | A’. B’ |
---|---|---|---|---|---|---|

1 | 1 | 1 | 1 | |||

1 | 1 | 1 | ||||

1 | 1 | 1 | ||||

1 | 1 | 1 |

## Second De Morgan’s Law in Boolean Algebra

Second De Morgan’s law states that **“The complement of AND of two or more variables is equal to the OR of the complement of each variable.”**

Let A and B be two variables, then mathematically Second De Morgan’s Law is given as:

(A . B)’ = A’ + B’Where

- + represents the OR operator between variables,
represents AND operator between variables, and.represents complement operation on variable.‘

### Second De Morgan’s Law Logic Gates

In context to logic gates and Boolean Algebra, De Morgan’s Law states that “Both the logic gate circuits i.e., NOT gate is added to the output of AND gate, and NOT gate is added to the input of OR gate, are equivalent. These two logic gate circuits are given as follows:

### Second De Morgan’s Law Truth Table

The truth table for the second De Morgan’s Law is given as follows:

A | B | A . B | (A. B)’ | A’ | B’ | A’ + B’ |
---|---|---|---|---|---|---|

1 | 1 | 1 | 1 | |||

1 | 1 | 1 | 1 | |||

1 | 1 | 1 | 1 | |||

1 | 1 | 1 |

### De Morgan’s Law Logic

In De Morgan’s law for logic the below prepositions are tautology:

∼ (a ∧ b) ≡ ∼ a ∨ ∼ b

∼ (a ∨ b) ≡ ∼ a ∧ ∼ bWhere,

represetns the conjuction of statemetns,∧represents the disjunction of statements,∨represetns the negation of statement, and~represents the equivalence of statements.≡

## De Morgan’s Law Formula

Let’s compile all the formulas for De Morgan’s Law, in the following list.

For set theory:

- (A ∪ B)’ = A’ ∩ B’
- (A ∩ B)’ = A’ ∪ B’
For Boolean Algebra:

- (A + B)’ = A’ . B’
- (A . B)’ = A’ + B’
For Logic:

- ∼ (a ∧ b) ≡ ∼ a ∨ ∼ b
- ∼ (a ∨ b) ≡ ∼ a ∧ ∼ b

## Solved Examples on De Morgan’s Law

**Problem 1: Given that U = {2, 3, 7, 8, 9}, A = {2, 7} and B = {2, 3, 9}. Prove De Morgan’s Second Law.**

**Solution:**

U = {2, 3, 7, 8, 9}, A = {2, 7} and B = {2, 3, 9}

To Prove: (A ∩ B)’ = A’ ∪ B’

(A ∩ B) = {2}

(A ∩ B)’ = U – (A ∩ B) = {2, 3, 7, 8, 9} – {2}

(A ∩ B)’ = {3, 7, 8, 9}A’ = U – A = {2, 3, 7, 8, 9} – {2, 7}

A’ = {3, 8, 9}

B’ = U – B = {2, 3, 7, 8, 9} – {2, 3, 9}

B’ = {7, 8}

A’ ∪ B’ = {3, 8, 9} ∪ {7, 8}

A’ ∪ B’ = {3, 7, 8, 9}

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

**Problem 2:****Given that U = {1, 4, 6, 8, 9}, A = {1, 9} and B = {4, 6, 9}. Prove De Morgan’s First Law.**

**Solution:**

U = {1, 4, 6, 8, 9}, A = {1, 9} and B = {4, 6, 9}

To Prove: (A ∪ B)’ = A’ ∩ B’

(A ∪ B) = {1, 4, 6, 9}

(A ∪ B)’ = U – (A ∪ B) = {1, 4, 6, 8, 9} – {1, 4, 6, 9}

(A ∪ B)’ = {8}A’ = U – A = {1, 4, 6, 8, 9} – {1, 9}

A’ = {4, 6, 8}

B’ = U – B = {1, 4, 6, 8, 9} – {4, 6, 9}

B’ = {1, 8}

A’ ∩ B’ = {4, 6, 8} ∩ {1, 8}

A’ ∩ B’ = {8}

(A ∪ B)’ = A’ ∩ B’Hence Proved

**Problem 3: Simplify the Boolean Expression: Y = [(A + B).C]’**

**Solution:**

Y = [(A + B).C]’

Applying De Morgan’s law (A . B)’ = A’ + B’

Y = (A + B)’ + C’

Applying De Morgan’s law (A + B)’ = A’. B’

Y = A’. B’ + C’

**Problem 4: Simplify the Boolean Expression: X = [(A + B)’ + C]’**

**Solution:**

X = [(A + B)’ + C]’

Applying De Morgan’s law (A + B)’ = A’. B’

X = [(A + B)’]’ . C’

X = (A + B). C’

**Check this sources for more:**

Topic for Interlinking | Related to |
---|---|

Boolean Algebra | De Morgan’s Law Boolean Algebra |

Set Theory | De Morgan’s Law in Set Theory |

Logical Gates | De Morgan’s Law Logic |

Discrete Mathematics | De Morgan’s Law Discrete Math |

Java Programming Examples | De Morgan’s Law Java |

## Showcase Examples of De Morgan’s Law

Context | Example |
---|---|

Logic Puzzles | : If it is not true that “It is raining and cold,” what can we infer? Puzzle: We can infer that “It is not raining or it is not cold.” This uses De Morgan’s Law to simplify the negation of a conjunction into a disjunction.Application of De Morgan’s Law |

Programming | : Checking if a number is neither positive nor even in a programming language. Scenario: Code Snippet (Pseudocode)`if !(number > 0 and number % 2 == 0)` can be simplified using De Morgan’s Law to `if (number <= 0 or number % 2 != 0)` . This demonstrates how De Morgan’s Law helps in simplifying conditional statements. |

Mathematical Proofs | : Prove that the complement of the intersection of two sets A and B is equal to the union of their complements. Statement: According to De Morgan’s Law, (A ∩ B)’ = A’ ∪ B’. This shows how De Morgan’s Law is used to simplify expressions in set theory.Application of De Morgan’s Law |

## De Morgan’s Law Practical Examples

### Example 1: Pizza Toppings

Imagine you’re at a pizza party, and you’re told you can choose any toppings except for both mushrooms and olives together.

: This means if you don’t want both mushrooms and olives (Not (Mushrooms and Olives)), you can either not have mushrooms (Not Mushrooms) or not have olives (Not Olives) on your pizza. So, you could have a pizza with just mushrooms, just olives, or neither!**Using De Morgan’s Law**

### Example 2: Library Books

Your teacher says you cannot bring books about wizards or dragons into the classroom.

: This means if you’re not allowed books about wizards or dragons (Not (Wizards or Dragons)), you can’t bring books about wizards (Not Wizards) and you can’t bring books about dragons (Not Dragons). So, books about space or animals are still okay!**Using De Morgan’s Law**

### Example 3: Playing Outside

Your mom says you can’t play outside if it’s raining and cold at the same time.

: This means if you’re not going out because it’s raining and cold (Not (Raining and Cold)), you wouldn’t go out if it’s just raining (Not Raining) or just cold (Not Cold). But if it’s sunny and warm, you’re good to go!**Using De Morgan’s Law**

### Example 4: Choosing a Movie

Your friend says they don’t want to watch a movie that is scary or boring.

: This means if your friend doesn’t want a movie that’s scary or boring (Not (Scary or Boring)), they don’t want a scary movie (Not Scary) and they don’t want a boring movie (Not Boring). So, a funny or exciting movie would be perfect!**Using De Morgan’s Law**

## Logic Applications of De Morgan’s Law

Application Area | Description |
---|---|

Logical Reasoning | In logical puzzles or arguments, De Morgan’s Law helps simplify complex negations. For instance, negating “All apples are red” to “Not all apples are red” implies “Some apples are not red.” |

Computer Science | De Morgan’s Law is crucial in optimizing conditional statements in programming. It allows programmers to simplify complex logical conditions, making code more efficient and readable. |

Electronic Circuit Design | In digital electronics, De Morgan’s Law is used to design and simplify circuits. For example, it helps in converting AND gates into OR gates (and vice versa) using NOT gates, facilitating the creation of more efficient circuit layouts. |

## De Morgan’s Law – FAQs

**State De Morgan’s first law statement in set theory.**

**State De Morgan’s first law statement in set theory.**

The De Morgan’s first law in set theory states that ” The complement of union of two sets is equal to the intersection of their individual complements”.

**State De Morgan’s second law statement in Boolean algebra.**

**State De Morgan’s second law statement in Boolean algebra.**

The De Morgan’s second law in Boolean algebra states that ” The complement of AND of two or more variables is equal to the OR of the complement of each variable”.

**Write the formula for De Morgan’s law in set theory.**

**Write the formula for De Morgan’s law in set theory.**

The formula for De Morgan’s law in set theory:

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

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

**Write the formula for De Morgan’s law in Boolean algebra.**

**Write the formula for De Morgan’s law in Boolean algebra.**

The formula for De Morgan’s law in Boolean algebra:

(i) (A + B)’ = A’ . B’

(ii) (A . B)’ = A’ + B’

**Write some applications of De Morgan’s law.**

**Write some applications of De Morgan’s law.**

Some of the applications of De Morgan’s law is to minimize the complex Boolean expression and to simply it.

**How to prove De Morgan’s law?**

**How to prove De Morgan’s law?**

The De Morgan’s law in the set theory can be proved by the Venn diagrams and De Morgan’s law in the Boolean algebra can be proved by truth tables.