De Morgan’s Laws are the most important rules of Set Theory and Boolean Algebra. This post will discuss in detail about what are De Morgan’s Laws, details about first law and second Law, verification of these laws and their applications.

What are De Morgan’s Laws

Augustus De Morgan was a British Mathematician who formulated laws or rules of Set Theory and Boolean Algebra that relates three basic ‘Set’ operations; Union, Intersection and Complement. De Morgan laws are a couple of theorems that are related to each other.

In Propositional Logic and Boolean Algebra, these laws are seen as rules of transformation. These laws can be proved using Venn Diagrams and Truth-tables.

Fig. 1 – Introduction to De Morgan’s Laws

De Morgan’s texts were outstanding which included Algebra, Trigonometry, Differential and Integral Calculus, Probability and Symbolic Logic. De Morgan pioneered Propositional Calculus. He devised Algorithm for approximating factorials in the 19th Century.

Fig. 2 – Augustus De Morgan

De Morgan’s Laws

The two laws stated by him are:

• De Morgan’s Law of Union or First Law
• De Morgan’s Law of Intersection or Second Law

De Morgan’s Law of Union or First Law

The first law or the Law of Union states that: If A and B are two finite sets or subsets of a Universal Subset U then, the element not in A ∪ B is not in A’ and not in B’. Conversely, it also states that an element not in A’ and not in B’ is not in A ∪ B. i.e.

(A U B)’ = A’ ∩ B’ where:

∪ denotes the Union (OR).

A’ refers to the set complement (NOT) of A in U, i.e., A’ = U\A

It can also be defined as; the complement of the union of two sets is the same as the Intersection of their complements; i.e.

Not (A or B) = Not A and Not B

De Morgan’s Law of Intersection or Second Law

The second law or the Law of Intersection states that an element not in A ∩ B is not in A’ or not in B’. Conversely, it also states that an element not in A’ or not in B’ is not in A ∩ B. i.e.

(A ∩ B) ‘ = A’ ∪ B’ where:

∩ denotes the Intersection.

It can also be defined as; the complement of the Intersection of two sets is the same as the Union of their complements; i.e.

Not (A and B) = Not A or Not B

Fig. 3, shows Venn Diagram representing logical relations between finite sets.

Fig. 3 – Venn Diagram of Finite Sets

Verification of First and Second Law

The laws can be verified or proved as shown below:

Verification of De Morgan’s Law of Union or First Law

 (A U B)’ = A’ ∩ B’

Let P = (A U B)’ and Q = A’ ∩ B’

Let x be an arbitrary element of P then x ∈ P ⇒ x ∈ (A U B)’

⇒ x ∉ (A U B)

⇒ x ∉ A and x ∉ B

⇒ x ∈ A’ and x ∈ B’

⇒ x ∈ A’ ∩ B’

⇒ x ∈ Q

Therefore, P ⊂ Q ……………. (i)

Again, let y be an arbitrary element of Q then y ∈ Q ⇒ y ∈ A’ ∩ B’

⇒ y ∈ A’ and y ∈ B’

⇒ y ∉ A and y ∉ B

⇒ y ∉ (A U B)

⇒ y ∈ (A U B)’

⇒ y ∈ P

Therefore, Q ⊂ P …………….. (ii)

Now combine (i) and (ii) we get; P = Q i.e. (A U B)’ = A’ ∩ B’. Hence proved.

Example of De Morgan’s Law of Union or First Law 

Let us consider two finite sets ‘P’ and ‘Q’ in the universal set U and

Let U = {1, 2, 3, 4, 5, 6, 7, 8}, P = {4, 5, 6} and Q = {5, 6, 8}.

Now let us verify: (P ∪ Q)’ = P’ ∩ Q’.

P ∪ Q = {4, 5, 6} ∪ {5, 6, 8}

= {4, 5, 6, 8}

Therefore, (P ∪ Q)’ = {1, 2, 3, 7}   ……………….. (i)

As we know P = {4, 5, 6} so, P’ = {1, 2, 3, 7, 8}

and Q = {5, 6, 8} so, Q’ = {1, 2, 3, 4, 7}

P’ ∩ Q’ = {1, 2, 3, 7, 8} ∩ {1, 2, 3, 4, 7}

Therefore, P’ ∩ Q’ = {1, 2, 3, 7}   ……………….. (ii)

Combining (i) and (ii) we get;

(P ∪ Q)’ = P’ ∩ Q’. Hence proved.

Fig. 4 – Venn Diagrams Representing De Morgan’s Laws

Verification of De Morgan’s Law of Intersection or Second Law

(A ∩ B)’ = A’ U B’

Let M = (A ∩ B)’ and N = A’ U B’

Let x be an arbitrary element of M then x ∈ M ⇒ x ∈ (A ∩ B)’

⇒ x ∉ (A ∩ B)

⇒ x ∉ A or x ∉ B

⇒ x ∈ A’ or x ∈ B’

⇒ x ∈ A’ U B’

⇒ x ∈ N

Therefore, M ⊂ N ……………. (i)

Again, let y be an arbitrary element of N then y ∈ N ⇒ y ∈ A’ U B’

⇒ y ∈ A’ or y ∈ B’

⇒ y ∉ A or y ∉ B

⇒ y ∉ (A ∩ B)

⇒ y ∈ (A ∩ B)’

⇒ y ∈ M

Therefore, N ⊂ M ……………. (ii)

Now combine (i) and (ii) we get; M = N i.e. (A ∩ B)’ = A’ U B’. Hence proved.

Example for De Morgan’s Law of Intersection or Second Law

If U = {j, k, l, m, n}, X = {j, k, m} and Y = {k, m, n}.

Now let us verify: (X ∩ Y)’ = X’ U Y’.

We know, U = {j, k, l, m, n}

X = {j, k, m}

Y = {k, m, n}

(X ∩ Y) = {j, k, m} ∩ {k, m, n}

= {k, m}

Therefore, (X ∩ Y)’ = {j, l, n} ………………. (i)

Again, X = {j, k, m} so, X’ = {l, n}

and Y = {k, m, n} so, Y’ = {j, l}

X’ ∪ Y’ = {l, n} ∪ {j, l}

Therefore, X’ ∪ Y’ = {j, l, n} ………………. (ii)

Combining (i)and (ii) we get;

(X ∩ Y)’ = X’ U Y’. Hence proved.

Applications of De Morgan’s Laws

These two laws are of utmost importance in various branches of mathematics and engineering.  We have seen how they can be applied in mathematics.  Similarly, they are applied both in computer and electrical engineering.

These laws are used in designing digital circuits and in verification of SAS code. These laws can also be applied in text searching by using AND, OR and NOT, collectively known as Boolean Operators.

Think of a set containing the words cats and dogs. According to De Morgan’s Laws:

Search A:  NOT (cats OR dogs)

Search B: (NOT cats) AND (NOT dogs)

Limitation of De Morgan’s Laws

The laws relate conjunction and inclusive dis-junction through Negation.

Also Read:
Ohms Law – Voltage, Current & Resistance Relation, When Not Applicable
Kirchhoff’s Laws of Current & Voltage – Application, Advantage, Limitation
Electromagnetic Induction – Theory, Application, Advantage, Disadvantage