De-Morgan's Laws

According to De Morgan's First Law, the intersection of two sets' complements is the complement of the union of those sets. According to De Morgan's second law, the union of two sets' complements is the complement of the intersection of those two sets. We refer to these two laws as De Morgan's Law. The formula for De Morgan's first law is (AUB)' = A'∩B'.The intersection and union of sets are related by complements in these laws.

In this article, we will cover the concept of the De-Morgan's Law. This concept falls under the broader category of sets relation and function, a crucial Chapter in class 11 Mathematics. It is not only essential for board exams but also for competitive exams like the Joint Entrance Examination (JEE Main), and other entrance exams such as SRMJEE, BITSAT, WBJEE, BCECE, and more. Over the last ten years of the JEE Main exam (from 2013 to 2023), a total of one question has been asked on this concept, including one in 2022.

What is De Morgan's law?

In set theory, the relationship between union, complements, and intersection is provided by De Morgan's law. It provides the relationship between AND, OR, and the variable's complements in Boolean algebra; in logic, it provides the relationship between AND, OR, or the statement's negation. De Morgan's Law allows us to optimize different boolean circuits that use logic gates to do the same task with a minimum amount of equipment.

De Morgan's Law Statement

First Law:

The complement of the union of two sets is equal to the intersection of the complements of each set, according to the first application of De Morgan's law. If A and B are two sets, then First De Morgan's Law can be expressed mathematically as follows:
(A ∪ B)' = A' ∩ B'
Where
U stands for the Union operation between sets,' for the complement operation on a set, and ∩ for the intersection operation between sets.
Another name for it is De Morgan's Law of Union.
Second Law:

"The complement of intersection of two sets is equal to the union of the complements of each set," according to the second De Morgan's law.
If A and B are two sets, then First De Morgan's Law can be expressed mathematically as follows:
(A ∩ B)' = A' ∪ B'
Where
U stands for the Union operation between sets,' for the complement operation on a set, and ∩ for the intersection operation between sets.
Another name for it is the Law of Intersection by De Morgan.

Proof of De Morgan's Law

In set theory, Demorgan's law proves that the intersection and union of sets get interchanged under complementation. We can prove De Morgan's law both mathematically and by taking the help of truth tables.

1. (A ∪ B)′ = A′ ∩ B′

Let x be any element in (A ∪ B)’

x ∈ (A ∪ B)’ ⇔ x ∉ (A ∪ B)

⇔ x ∉ A and x ∉ B (As x does not belong to A ∪ B, it cannot belong to both A and B)

⇔ x ∈ A’ and x ∈ B’

⇔ x ∈ (A’ ∩ B’)

∴ x ∈ (A ∪ B)’ ⇔ x ∈ (A’ ∩ B’)

So, any element that belongs to (A ∪ B)’ also belongs to (A’ ∩ B’), and vice versa

So, these sets have exactly the same elements, hence they are equal

2. (A ∩ B)′ = A′ ∪ B′

Let x be any element in (A ∩ B)’

x ∈ (A ∩ B)’ ⇔ x ∉ (A ∩ B)

⇔ x ∉ A or x ∉ B (as x ∉ (A ∩ B), means it is not common in A and B, and thus either it is not in A or not in B)

⇔ x ∈ A’ or x ∈ B’

⇔ x ∈ (A’ ∪ B’)

∴ x ∈ (A ∩ B)’ ⇔ x ∈ (A’ ∪ B’)

So, any element that belongs to (A ∩ B)’ also belongs to (A’ ∪ B’), and vice versa

So, these sets have exactly the same elements, hence they are equal

Solved Examples Based On the De-Morgan's Law:

Example 1: If

1)

2)

3)

4)

Solution:

Using De-Morgan's Law:

P' = (A ∪ B)′ = A′ ∩ B′

Hence, the answer is the option 4.

Example 2: Which of the following is not a property of a union of sets?

1)

2)

3)

4)

Solution:

As we learned

UNION OF SETS -

Let A and B be any two sets. The union of A and B is the set which consists of all the elements of A and all the elements of B, the common elements being taken only once. The symbol ‘∪’ is used to denote the union.

Symbolically, we write A U B = {x: x ∈ A or x ∈ B}.

De Morgans’s Law -

(A ∪ B)′ = A′ ∩ B′

Hence, option 3 is incorrect.

Hence, the answer is the option 3.

Example 3:

1)

2)

3)

4)

Solution:

P' = (A∩B∩C)'

= ((A∩B) ∩ C)'

= (A∩B)' ∪ C' ------{De-Morgans Law}

= A'∪B'∪C'.

Hence, the answer is the option 2.

Example 4: If the set

1) {1,3,5,7,9}

2) {5,7}

3) {5}

4) {1,5,9}

Solution:

As we learned

De Morgans’s Law:

(A ∪ B)′ = A′ ∩ B′

The intersection of A' and B' is {5}.

Hence, the answer is the option 3.

Example 5: If A - B = X and A - C = Y. then the simplification of A - (B U C) is

1)

2)

3)

4)

Solution:

As we have learned,

So,

Hence, the answer is the option 1.

Summary

De Morgan's Laws provide a way to simplify complex logical and set expressions by transforming them into an equivalent form. These laws are particularly useful in various fields such as computer science, digital logic design, and mathematics for simplifying expressions and proving equivalences. They demonstrate the duality in logic and set operations, showing how operations are interconnected through complementation.