De Morgan's Law

De Morgan's laws are a pair of transformation rules in boolean algebra and set theory that is used to relate the intersection and union of sets through complements. There are two conditions that are specified under Demorgan's law. These conditions are primarily used to reduce expressions into a simpler form. This increases the ease of performing calculations and solving complex boolean expressions.

According to De Morgan's Laws:

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

These laws can easily be visualized using Venn diagrams. In this article, we will learn about the statements of Demorgan's law, the proof of these statements, their applications, and examples.

Demorgan's laws are a set of two postulates that are widely used in set theory. They state that: (i) (A ∪ B)’ = A’ ∩ B’ and (ii) (A ∩ B)’ = A’ ∪ B’.

☛Also Check:

1. A union B Complement (First De Morgan's Law)
2. A Intersection B Complement (Second De Morgan's Law)

When we have a collection of well-defined distinct objects that form a group, this collection is known as set. When we want to simplify set operations such as taking the complement, union, and intersection of sets, we use De Morgan's laws.

De Morgan's Law Statement

Demorgan's law can be used in boolean algebra as well as in set theory to simplify mathematical expressions. Suppose we have two sets A and B that are subsets of the universal set U. A' is the complement of A and B' is the complement of B. '∩' is the symbol for intersection and '∪' is used to denote the union. Then the De Morgan's laws are given below.

De Morgan's Law of Union: The complement of the union of the two sets A and B will be equal to the intersection of A' (complement of A) and B' (complement of B). This is also known as De Morgan's Law of Union. It can be represented as (A ∪ B)’ = A’ ∩ B’. We can also generalize this law. Suppose we have n sets given by {\(A_{1}, A_{2}, ..., A_{n}\)} then formula is given by \((\bigcup_{i = 1}^{n}A_{i})^{'} = \bigcap_{i = 1}^{n} A_{i}^{'}\).

In the above Venn diagram, the orange-coloured shaded portion represents A ∪ B and the blue-coloured portion represents (A ∪ B)’.

De Morgan's Law of Intersection: The complement of the intersection of A and B will be equal to the union of A' and B'. This condition is called De Morgan's law of Intersection. It can be given by (A ∩ B)’ = A’ ∪ B’. Similarly, as above this law can be generalized by the formula \((\bigcap_{i = 1}^{n}A_{i})^{'} = \bigcup_{i = 1}^{n} A_{i}^{'}\).

In the above Venn diagram, the orange-coloured shaded portion represents A ∩ B and the blue-coloured portion represents (A ∩ B)’.

De Morgan's Law Example

Let us understand De Morgan's law with the help of a simple example. Let the universal set U = {7, 8, 9, 10, 11, 12, 13 }. The two subsets are given by A = {11, 12, 13} and B = {7, 8}.

• De Morgan's Law of Union Example: (A ∪ B) = {7, 8, 11, 12, 13}, (A ∪ B)’ = {9, 10}. A’ = {7, 8, 9, 10} and B' = { 9, 10, 11, 12, 13}. A’ ∩ B’ = {9, 10}. Thus, (A ∪ B)’ = A’ ∩ B’
• De Morgan's Law of Intersection Example: (A ∩ B) = ∅, (A ∩ B)' = {7, 8, 9, 10, 11, 12, 13 }. A’ ∪ B’ = {7, 8, 9, 10, 11, 12, 13}. Hence, (A ∩ B)’ = A’ ∪ B’

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.

Proof of (A ∪ B)’ = A’ ∩ B’:

The first De Morgan's theorem or law of Union can be proved as follows:

Let R = (A U B)' and S = A' ∩ B'. Our intention now is to prove R = S. For this, it is sufficient to prove that R ⊂ S and S ⊂ R.

Suppose we choose an element y that belongs to R. This is denoted as y ∈ R.

⇒ y ∈ (A U B)'

⇒ y ∉ (A U B)

⇒ y ∉ A and y ∉ B

⇒ y ∈ A' and y ∈ B'

⇒ y ∈ A' ∩ B'

⇒ y ∈ S

Thus, we conclude that R ⊂ S (R is a subset of S) ...(1)

Now suppose we have an arbitrary element z that belongs to set S. Then z ∈ S

⇒ z ∈ A' ∩ B'

⇒ z ∈ A' and z ∈ B'

⇒ z ∉ A and z ∉ B

⇒ z ∉ (A U B)

⇒ z ∈ (A U B)'

⇒ z ∈ R

Hence, S ⊂ R ...(2)

From (1) and (2) we infer that S = R or (A ∪ B)’ = A’ ∩ B’. Thus, this theorem is proved.

Proof of (A ∩ B)’ = A’ ∪ B’:

The second De Morgan's theorem or law of Intersection can be mathematically proved using the following steps:

Let G = (A ∩ B)' and H = A' U B'. We would now prove that G = H by proving G ⊂ H and H ⊂ G.

Let an element y belong to G. y ∈ G.

⇒ y ∈ (A ∩ B)'

⇒ y ∉ (A ∩ B)

⇒ y ∉ A or y ∉ B

⇒ y ∈ A' or y ∈ B'

⇒ y ∈ A' U B'

⇒ y ∈ H

This implies that G ⊂ H ...(1)

If z is an arbitrary element of H then z ∈ H

⇒ z ∈ A' U B'

⇒ z ∈ A' or z ∈ B'

⇒ z ∉ A or z ∉ B

⇒ z ∉ (A ∩ B)

⇒ z ∈ (A ∩ B)'

⇒ z ∈ G

Therefore, H ⊂ G ...(2)

Now when we combine (1) and (2) we can say that G = H or (A ∩ B)’ = A’ ∪ B’. Hence, we have successfully proved the second theorem.

De Morgan's laws in boolean algebra are as follows:

• \(\overline{A•B}\) = \(\overline{A}\) + \(\overline{B}\)
• \(\overline{A+B}\) = \(\overline{A}\) • \(\overline{B}\)

In boolean algebra, we make use of logic gates. These logic gates work on logic operations. Here, A and B become input binary variables. "0's" and "1's" are used to represent digital input and output conditions. Thus, using these conditions we can create truth tables to define operations such as AND (A•B), OR (A + B), and NOT (negation). By using logic operations as well as truth tables, we can state and prove De Morgan's laws as follows.

First De Morgan's Law

It that when two or more input variables (A, B) are OR’ed and then negated, the result is equal to the AND of the complements of the individual input variables. \(\overline{A + B}\) = \(\overline{A}\)•\(\overline{B}\). To prove this theorem we can use the truth table as given below:

From the above table, we can notice that the columns of \(\overline{A + B}\) and \(\overline{A}\) · \(\overline{B}\) are one and the same.

Second De Morgan's Law

It states that when two or more input variables are AND'ed and negated, then the obtained result will be equal to the OR of the complements of the individual variables. \(\overline{A•B}\) = \(\overline{A}\) + \(\overline{B}\). Using the truth table, we can prove this as follows:

For simplicity purposes, OR operation is analogous to the union of sets operation while the AND operation corresponds to the intersection operation of sets.

Demorgan's law is used both in set theory as well as in boolean algebra. These laws are critical in understanding mathematical arguments. Using these laws a relationship can be established between union and intersection via complementation. Given below are the various forms of the formulas:

In set theory,

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

Generalized Formulas for infinite unions and intersections,

• \((\bigcup_{i = 1}^{n}A_{i})^{'} = \bigcap_{i = 1}^{n} A_{i}^{'}\)
• \((\bigcap_{i = 1}^{n}A_{i})^{'} = \bigcup_{i = 1}^{n} A_{i}^{'}\)

In Boolean Algebra,

• \(\overline{A + B}\) = \(\overline{A}\)•\(\overline{B}\)
• \(\overline{A•B}\) = \(\overline{A}\) + \(\overline{B}\)

De Morgan's law is used in both elementary algebra as well as Boolean algebra. As this law helps to reduce complicated expressions it is widely utilized in most engineering industries to create hardware and simplify operations. Given below are some other applications of De morgan's law.

• De morgan's law applications can be seen in electronic engineering for developing logic gates. By using, this law equations can be constructed using only the NAND (AND negated) or NOR (OR negated) gates. This results in cheaper hardware. Further, NAND, NOT and NOR gates are easier to implement practically.
• Demorgan's law is used in computer programming. This law helps to simplify logical expressions written in codes thereby, reducing the number of lines. Thus, it helps in the overall optimization of the code. Furthermore, these laws are make verifying SAS codes much simpler and faster.

☛Related Articles:

• Boolean Algebra Calculator
• Types of Sets
• Set Operations

Important Notes on De Morgan's Law:

• The first de morgan's law is given by the formula (A ∪ B)’ = A’ ∩ B’ or \(\overline{A + B}\) = \(\overline{A}\)•\(\overline{B}\). This is also known as De Morgan's law of union.
• The second de morgan's law is written as (A ∩ B)’ = A’ ∪ B’ or \(\overline{A.B}\) = \(\overline{A}\) + \(\overline{B}\). This is also called De Morgan's law of intersection.
• The union operator is analogous to the logical OR and the intersection operator is equivalent to logical AND.
• The proof of de morgan's law can be given by truth tables (in boolean algebra) and theoretically (set theory).

Cuemath is one of the world's leading math learning platforms that offers LIVE 1-to-1 online math classes for grades K-12. Our mission is to transform the way children learn math, to help them excel in school and competitive exams. Our expert tutors conduct 2 or more live classes per week, at a pace that matches the child's learning needs.

What Does De Morgan's Law in Sets State?

There are two De Morgan's Laws in sets.

• The first De Morgan law states that the complement of the union of two sets is equal to the intersection of the respective complements.
• The second law states that the complement of the intersection of two sets is the same as the union of their individual complements.

What is the Formula for De Morgan's Law?

In set theory the formula for De Morgan's law is given by (A ∪ B)’ = A’ ∩ B’ and (A ∩ B)’ = A’ ∪ B’. Furthermore, in Boolean Algebra the formulas for these laws are \(\overline{A + B}\) = \(\overline{A}\).\(\overline{B}\) and \(\overline{A.B}\) = \(\overline{A}\) + \(\overline{B}\).

What are the Two De Morgan's Laws in Sets?

The first law is called De morgan's law of union and is given by (A ∪ B)’ = A’ ∩ B’. The second theorem is called De Morgan's Law of Intersection and is written as (A ∩ B)’ = A’ ∪ B’.

What is De Morgan's Law in Boolean Algebra?

In Boolean algebra, De Morgan's first theorem states that when two or more variables are NOR'd together, the obtained result will be equal to the AND of the inverted variables. According to the second theorem, when two or more variables are NAND'd together it is equivalent to the OR of the inverted variables.

How to Prove De Morgan's Laws?

There are several methods available to prove De Morgan's laws. We can use the mathematical approach, the boolean approach by utilizing truth tables, and the visual approach given by Venn diagrams.

What is De Morgan's Law Truth Table?

De Morgan's law truth table is used to verify both the theorems by applying "0's" and "1's" to the input variables and checking the output when certain logic operations are applied. For more information, click here.

How to Apply De Morgan's Law?

We can apply de morgan's law by using the formulas (A ∪ B)’ = A’ ∩ B’ and (A ∩ B)’ = A’ ∪ B’ to simplify expressions and reduce them to a form that makes calculations faster. If we are dealing with logic operations then we use the equivalent forms given by \(\overline{A + B}\) = \(\overline{A}\).\(\overline{B}\) and \(\overline{A.B}\) = \(\overline{A}\) + \(\overline{B}\)