De Morgan’s Law: Theorem, Proofs, Examples

De Morgan’s Law is a collection of boolean algebra transformation rules that are used to connect the intersection and union of sets using complements. De Morgan’s Law states that two conditions must be met. These conditions are typically used to simplify complex expressions. This makes performing calculations and solving complicated boolean expressions easier.

According to De Morgan’s Law logic, the complement of the union of two sets is equal to the intersection of their separate complements. Furthermore, the complement of two sets intersecting is equal to the sum of their separate complements. Venn diagrams make it simple to visualise these laws. We will study Demorgan’s Law’s statements, how to prove them, how to apply them, and De Morgan’s law example in this article. 

State De Morgan’s Law: Definition

Set theory is an algorithm of set types and sets operations. For a better understanding of the multiple set operations and their inter-relationship, De Morgan’s laws are the best tool. De Morgan’s Law describes the relationship between three fundamental operations of sets: the complement of sets, the union of sets and the intersection of sets.

De Morgan’s Law states that the complement of the union of two sets is the intersection of their complements, and also, the complement of intersection of two sets is the union of their complements.

Depending on the inter-relation between the set-union and set-intersection, there are two types of De Morgan’s law that exists in set theory. They are explained below:

De Morgan’s First Law

It states that the complement of the union of any two sets is equal to the intersection of the complement of that sets. This De Morgan’s theorem gives the relation of the union of two sets with their intersection of sets by using the set complement operation.

Consider any two sets \(A\) and \(B,\) the mathematical relation of De Morgan’s first law is given by

\({(AUB)^\prime } = {A^\prime } \cap {B^\prime }\)

De Morgan’s Logic Second Law

It states that the complement of the intersection of any two sets is equal to the union of the complement of that sets. 

This type of De Morgan’s law gives the relation of the intersection of two sets with their union of sets by using the set complement operation.

Consider any two sets A and B, the mathematical relation of De Morgan’s second law is given by

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

Union of Sets:

The union of sets (\(A\) and \(B\)) is the set containing all the elements in both sets \(A\) and \(B.\) The mathematical symbol used for the union of sets is “”.

The union of set \(A\) and set \(B\) is denoted by \(A∪B,\) mathematically. We can represent the union of two sets in the pictorial form by using Venn diagrams. The union of given sets \(A\) and \(B\) is represented in Venn diagrams by shading all portions of the sets \(A\) and \(B\) as shown below:

Example:
The union of sets \(A = \{ 5,10,15,20\} \) and \(B = \left\{ {10,\,20,30,40} \right\}\) given by

The union of two sets is \(A \cup B = \{ 5,10,15,20\} \cup \{ 10,20,30,40\} \)

\(A \cup B = \{ 5,10,15,20,30,40\} \)

It can be represented in the Venn diagram as shown below:

Intersection of Sets

The intersection of sets is the set containing the common elements of both sets \(A\) and \(B.\) The mathematical symbol used for the union of sets is \(“∩”.\)Intersection of sets \(A, B\) is denoted by \(A∩B,\) mathematically. We can represent the intersection of two sets in the pictorial form by using Venn diagrams. The intersection of given sets \(A\) and \(B\) is represented in Venn diagrams by shading the intersected (common) portion of the sets \(A\) and \(B\) as shown below:

Example:
The intersection of sets \(A = \{ 5,10,15,20\} \) and \(B = \{ 10,20,30,40\} \) given by

The union of two sets is \(A \cap B = \{ 5,10,15,20\} \cap \{ 10,20,30,40\} \)

\(A \cap B = \{ 10,20\} \)

It can be represented in the Venn diagram as shown below:

Complement of a Set

Complement of any set is the set obtained by removing all the elements of a given set from the universal set. Universal set contains all the elements of given sets.

The complement of set \(A\) is denoted by \(A’\) and is given by the difference of universal set \(\left( \cup \right)\) and the given set \(A.\)

\({A^\prime } = U – A\)

The complement of set \(A\) is denoted by using the Venn diagram as follows:

The rectangular portion shows the universal set \(U,\) and the circular portion denotes the set \(A.\) The shaded portion with blue colour indicates the complement of set \(A.\)

Proof of De Morgan’s First Law

There are two proofs given for De Morgan’s Law, and one is a mathematical approach and the other by using Venn diagram.

De Morgan’s first law tells that, \({(AUB)^\prime } = {A^\prime } \cap {B^\prime }\) 

Mathematical Approach:

Let us consider \(P = {(AUB)^\prime }\,{\rm{and}}\,Q = {A^\prime } \cap {B^\prime }\)

Let \(x\) be any element of \(P,\) then \(x \in P \Rightarrow x \in {(AUB)^\prime }\)

\( \Rightarrow x \notin (AUB)\)

\( \Rightarrow x \notin A\,{\rm{or}}\,x \notin B\)

\( \Rightarrow x \in {A^\prime }\,{\rm{and}}\,x \in {B^\prime }\)

\( \Rightarrow x \in {A^\prime } \cap {B^\prime }\)

\( \Rightarrow x \in Q\)

Therefore, \(P \subset Q…….(i)\)

Again, let \(y\) be an arbitrary element of \(Q\) then)\(y \in Q \Rightarrow y \in {A^\prime } \cap {B^\prime }\)

\( \Rightarrow y \in {A^\prime }\,{\rm{and}}\,y \in {B^\prime }\)

\( \Rightarrow y \notin A\,{\rm{or}}\,y \notin B\)

\( \Rightarrow y \notin (AUB)\)

\( \Rightarrow y \in {(AUB)^\prime }\)

\( \Rightarrow y \in P\)

Therefore, \(Q \subset P……..\left( {ii} \right)\) Now combine \((i)\) and \((ii)\) we get; \(P = Q.\) i.e. \({(AUB)^\prime } = {A^\prime } \cap {B^\prime }\)

Venn Diagram Method
Consider two sets, \(A\) and \(B.\) the Union of sets is represented by shading the complete portion of two sets.

The Venn diagram of \((AUB)’\) shows all the region of Union except \(A\) and \(B.\)

We know that the complement of two sets, \(A\) and \(B,\) are shown by shading all region of union except the given set.

The intersection of the complement of two sets shown in the below Venn diagram.

Thus, by using the Venn diagrams, we can say that, \({(AUB)^\prime } = {A^\prime } \cap {B^\prime }\)

Proof of De Morgan’s Second Law

There are two proofs given for De Morgan’s Law, and one is a mathematical approach and the other by using Venn diagram.

De Morgan’s second law states that \({(A \cap B)^\prime } = {A^\prime } \cup {B^\prime }\) 

Mathematical Approach:

Let us consider \(P = {(A \cap B)^\prime }\) and \(Q = {A^\prime }U{B^\prime }\)

Let \(x\) be any element of \(P,\) then \(x \in P \Rightarrow x \in {(A \cap B)^\prime }\)

\( \Rightarrow x \notin (A \cap B)\)

\( \Rightarrow x \notin A\,{\rm{and}}\,x \notin B\)

\( \Rightarrow x \in {A^\prime }\,{\rm{or}}\,x \in {B^\prime }\)

\( \Rightarrow x \in {A^\prime }U{B^\prime }\)

\( \Rightarrow x \in Q\)

Therefore, \(P \subset Q…….\left( i \right)\)

Again, let \(y\) be an arbitrary element of \(Q\) then \(y \in Q \Rightarrow y \in {A^\prime }U{B^\prime }\)

\( \Rightarrow y \in {A^\prime }\,{\rm{or}}\,y \in {B^\prime }\)

\( \Rightarrow y \notin A\,{\rm{and}}\,y \notin B\)

\( \Rightarrow y \notin (A \cap B)\)

\( \Rightarrow y \in {(A \cap B)^\prime }\)

\( \Rightarrow y \in P\)

Therefore, \(Q \subset P \ldots ..(ii)\) Now combine \((i)\) and \((ii)\) we get; \(P = Q.\) i.e. \({(A \cap B)^\prime } = {A^\prime }U{B^\prime }\)

Venn Diagram Method:

The Venn diagram of \(A∩B\) is shown by shading the common portion.

The Venn diagram for the complement of \(A∩B\) is shown by shading the all-region excluding the common part of sets given as below:

We know that the complement of two sets, \(A\) and \(B,\) are shown by shading all region of union except the given set.

The union of the complement of two sets is shown below:

From the above Venn diagrams, we can say that \({(A \cap B)^\prime } = {A^\prime } \cup {B^\prime }\)

Solved Examples on De Morgan’s Law

Let us look at De Morgan’s Law logic:

Q.1. Set \(U = \{ 0,1,2,3,4,5,6,7,8,9,10\} \) set \(A = \{ 2,4,6,8\} ,\) and set \(B = \{ 1,3,5,6,7,9\} .\) Prove that \({(A \cap B)^\prime } = {A^\prime } \cup {B^\prime }.\)
Ans: Given: \(U = \{ 0,1,2,3,4,5,6,7,8,9,10\} \) set \(A = \{ 2,4,6,8\} ,\) and set \(B = \{ 1,3,5,6,7,9\} .\)
Intersection of the sets contains the common elements of both sets.
\( \Rightarrow A \cap B = \{ 6\} \)
\( \Rightarrow {(A \cap B)^\prime } = U – (A \cap B)\)
\( \Rightarrow {(A \cap B)^\prime } = \{ 0,1,2,3,4,5,7,8,9,10\} ………\left( 1 \right)\)
\({A^\prime } = U – A = \{ 0,1,3,5,7,9,10\} \)
Similarly, \({B^\prime } = U – B = \{ 0,2,4,8,10\} \)
\({A^\prime } \cup {B^\prime } = \{ 0,1,3,5,7,9,10\} \cup \{ 0,2,4,8,10\} = \{ 0,1,2,3,4,5,7,8,9,10\} …….\left( 2 \right)\)
From \((1,) (2)\)
\({(A \cap B)^\prime } = {A^\prime } \cup {B^\prime }.\)
Hence, proved.

Q.2. If \(U = \{ a,b,c,d,e\} \) and set \(A = \{ a,b,d\} \) and \(B = \{ b,d,e\} .\) Prove De Morgan’s law of intersection.
Ans: We need to prove that \({(A \cap B)^\prime } = {A^\prime } \cup {B^\prime }.\)
Given: \(U = \{ a,b,c,d,e\} \) and set \(A = \{ a,b,d\} \) and \(B = \{ b,d,e\} \)
\( \Rightarrow A \cap B = \{ b,d\} \)
\( \Rightarrow {(A \cap B)^\prime } = U – (A \cap B)\)
\( \Rightarrow {(A \cap B)^\prime } = \{ a,c,e\} ……..\left( 1 \right)\)
\({A^\prime } = U – A = \{ a,b,c,d,e\} – \{ a,b,d\} = \{ c,e\} \)
\({B^\prime } = U – B = \{ a,b,c,d,e\} – \{ b,d,e\} = \{ a,c\} \)
\({A^\prime } \cup {B^\prime } = \{ c,e\} \cup \{ a,c\} = \{ a,c,e\} …….\left( 2 \right)\)
From \(1 (2),\)
\({(A \cap B)^\prime } = {A^\prime } \cup {B^\prime }.\)

Q.3. Let \(U = \{ 1,2,3,4,5,6\} ,A = \{ 2,3\} \) and \(B = \{ 3,4,5\} ,\) prove that \({(AUB)^\prime } = {A^\prime } \cap {B^\prime }\)
Ans: Given, \(U = \{ 1,2,3,4,5,6\} ,A = \{ 2,3\} \) and \(B = \{ 3,4,5\} ,\)
\(A \cup B = \{ 2,3\} \cup \{ 3,4,5\} = \{ 2,3,4,5\} \)
\({(AUB)^\prime } = U – (A \cup B) = \{ 1,2,3,4,5,6\} – \{ 2,3,4,5\} = \{ 1,6\} ……..\left( 1 \right)\)
\({A^\prime } = U – A = \{ 1,2,3,4,5,6\} – \{ 2,3\} = \{ 1,4,5,6\} \)
\({B^\prime } = U – B = \{ 1,2,3,4,5,6\} – \{ 3,4,5\} = \{ 1,2,6\} \)
\({A^\prime } \cap {B^\prime } = \{ 1,4,5,6\} \cap \{ 1,2,6\} = \{ 1,6\} …….(2)\)
From \((1,) (2)\)
\({(AUB)^\prime } = {A^\prime } \cap {B^\prime }\).
Hence, proved.

Q.4. \(U = \{ a,b,c,d,e\} \) and set \(A = \{ a,b,d\} \) and \(B = \{ b,d,e\} .\) Prove De Morgan’s law of union.
Ans: We need to prove that \({(AUB)^\prime } = {A^\prime } \cap {B^\prime }.\)
Given: \(U = \{ a,b,c,d,e\} \) and set \(A = \{ a,b,d\} \) and \(B = \{ b,d,e\} \)
\( \Rightarrow A \cup B = \{ a,b,d\} \cup \{ b,d,e\} = \{ a,b,d,e\} \)
\( \Rightarrow {(A \cup B)^\prime } = U – (A \cup B)\)
\( \Rightarrow {(A \cup B)^\prime } = \{ c\} …….(1)\)
\({A^\prime } = U – A = \{ a,b,c,d,e\} – \{ a,b,d\} = \{ c,e\} \)
\({B^\prime } = U – B = \{ a,b,c,d,e\} – \{ b,d,e\} = \{ a,c\} \)
\({A^\prime } \cap {B^\prime } = \{ c,e\} \cap \{ a,c\} = \{ c\} …….(2)\)
From \((1)\) and \((2),\)
\({(AUB)^\prime } = {A^\prime } \cap {B^\prime }.\)

Q.5. Universal set contains all possible outcomes when a dice is thrown. Set \(A\) contains even number outcomes and set \(B\) contains odd number outcomes. Prove that, \({(AUB)^\prime } = {A^\prime } \cap {B^\prime }.\)
Ans: When a dice is thrown, the possible outcomes are \(1, 2, 3, 4, 5, 6.\)
Given: \(U = \left\{ {1,2,3,4,5,6} \right\}A,\left\{ {2,4,6} \right\}\) and \(B = \left\{ {1,3,5} \right\}\)
\(A \cup B = \{ 2,4,6\} \cup \{ 1,3,5\} = \{ 1,2,3,4,5,6\} \)
\({(AUB)^\prime } = U – (A \cup B) = \{ 1,2,3,4,5,6\} – \{ 1,2,3,4,5,6\} = \emptyset ……(1)\)
\({A^\prime } = U – A = \{ 1,2,3,4,5,6\} – \{ 2,4,6\} = \{ 1,3,5\} \)
\({B^\prime } = U – B = \{ 1,2,3,4,5,6\} – \{ 1,3,5\} = \{ 2,4,6\} \)
\({A^\prime } \cap {B^\prime } = \{ 1,3,5\} \cap \{ 2,4,6\} = \emptyset …….\left( 2 \right)\)
From \((1,) (2):\)
\({(AUB)^\prime } = {A^\prime } \cap {B^\prime }.\)
Hence, proved.

Applications of De Morgan’s Law

De Morgan’s law may be found in both elementary and Boolean algebra. This law is commonly used in most engineering sectors to develop hardware and simplify operations since it helps to minimise difficult statements. Some of the De Morgan’s law example are stated below:

• In computer programming, Demorgan’s law is used. This law helps in the reduction of the number of lines of logical statements expressed in codes. As a result, it helps in overall code optimization. Furthermore, these laws make SAS code verification considerably easier and faster.
• De Morgan’s Law in Digital Electronics: The use of De Morgan’s law in electronic engineering for the development of logic gates may be observed. Only the NAND (AND negated) or NOR (OR negated) gates are required to produce this mathematical equation. As a result, the hardware is less expensive. NAND, NOT, and NOR gates are also easy to implement in practise.

Summary About De Morgan’s Law

In this article, we have studied Demorgan’s law, which gives the relation of the complement of union and the intersection of two sets. This article discussed the union, intersection and complement of sets. This article has also given the Mathematical proof of De Morgan’s laws. It also discussed the proof of De Morgan’s law by using Venn diagrams visually.

Frequently Asked Questions (FAQs) – De Morgan’s Law

Q.1. What is De Morgan’s first law?
Ans: It states that the complement of the union of any two sets is equal to the intersection of the complement of that sets.

Q.2. What is De Morgan’s Second law?
Ans: It states that the complement of the intersection of any two sets is equal to the union of the complement of that sets.

Q.3. Why De Morgan’s law is used?
Ans: De Morgan’s law is used for a better understanding of the multiple set operations and their inter-relationship in set theory.

Q.4. What are the fundamental operations of the set used for De Morgan’s law?
Ans: The fundamental operations like the union of sets, the intersection of sets and the complement of sets are used in De Morgan’s law.

Q.5. What are De Morgan’s laws?
Ans: The De Morgans’ Laws are:
1. \({(AUB)^\prime } = {A^\prime } \cap {B^\prime }\)
2. \({(AUB)^\prime } = {A^\prime } \cap {B^\prime }.\)