Table of Contents

Last modified on June 17th, 2024

De Morgan’s laws are fundamental principles in set theory and boolean algebra. They are attributed to the British mathematician and logician Augustus De Morgan.

In set theory, the laws establish the relations between union, intersection, and complements of sets, while in Boolean algebra, they relate the operations of conjunction (AND, denoted by ∧), disjunction (OR, denoted by ∨), and negation or complement (NOT, denoted by ¬).

The first De Morgan’s law (or De Morgan’s law of union) states that the complement of the union of two sets is the intersection of the complements of each set.

Mathematically, if A and B are two sets, then

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

If A = {a, b, c, d}, B = {b, c, d, e}, and U = {a, b, c, d, e, f, g}, then we have

(A ∪ B) = {a, b, c, d} ∪ {b, c, d, e} = {a, b, c, d, e}

A’ = U – A = {a, b, c, d, e, f, g} – {a, b, c, d} = {e, f, g}

B’ = U – B = {a, b, c, d, e, f, g} – {b, c, d, e} = {a, f, g}

Now, (A ∪ B)’ = U – (A ∪ B) = {a, b, c, d, e, f, g} – {a, b, c, d, e} = {f, g}

A’ ∩ B’ = {e, f, g} ∩ {a, f, g} = {f, g}

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

Let us consider an element ‘x’ such that x ∈ (A ∪ B)’

⇒ x ∉ (A ∪ B)

⇒ x ∉ A or x ∉ B

⇒ x ∈ A’ and x ∈ B’

⇒ x ∈ A’ ∩ B’

Thus, (A ∪ B)’ ⊂ A’ ∩ B’ …..(i)

Again, considering another element, ‘y,’ where y ∈ A’ ∩ B’

⇒ y ∈ A’ and y ∈ B’

⇒ y ∉ A or y ∉ B

⇒ y ∉ (A ∪ B)

⇒ y ∈ (A ∪ B)’

Thus, A’ ∩ B’ ⊂ (A ∪ B)’ …..(ii)

From (i) and (ii), we get

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

Now, using the Venn diagram, the De Morgan’s law of union is shown

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

Hence, the first De Morgan’s law is proved.

In general, for ‘n’ sets, {A_{1}, A_{2}, …, A_{n}}, the formula is written as:

${\left( \cup ^{n}_{k=1} A_{k}\right) ^{c}=\cap ^{n}_{k=1}A_{k}^{c}}$

The second De Morgan’s law (or De Morgan’s law of intersection) states that the complement of the intersection of two sets is the union of the complements of each set.

Mathematically, if A and B are two sets, then

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

If A = {a, b, c, d}, B = {b, c, d, e}, and U = {a, b, c, d, e, f, g}, then we have

(A ∩ B) = {a, b, c, d} ∩ {b, c, d, e} = {b, c, d}

A’ = U – A = {a, b, c, d, e, f, g} – {a, b, c, d} = {e, f, g}

B’ = U – B = {a, b, c, d, e, f, g} – {b, c, d, e} = {a, f, g}

Now, (A ∩ B)’ = U – (A ∩ B) = {a, b, c, d, e, f, g} – {b, c, d} = {a, e, f, g}

A’ ∪ B’ = {e, f, g} ∪ {a, f, g} = {a, e, f, g}

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

Let us consider an element ‘x’ such that x ∈ (A ∩ B)’

⇒ x ∉ (A ∩ B)

⇒ x ∉ A and x ∉ B

⇒ x ∈ A’ or x ∈ B’

⇒ x ∈ A’ ∪ B’

Thus, (A ∩ B)’ ⊂ A’ ∪ B’ …..(i)

Again, let us consider another element, ‘y,’ where y ∈ A’ ∪ B’

⇒ y ∈ A’ or y ∈ B’

⇒ y ∉ A and y ∉ B

⇒ y ∉ (A ∩ B)

⇒ y ∈ (A ∩ B)’

Thus, A’ ∪ B’ ⊂ (A ∩ B)’ …..(ii)

From (i) and (ii), we get

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

Now, using the Venn diagram, the De Morgan’s law of intersection is shown

Similarly, the complement of sets A’ and B’ and their union set A’ ∪ B’ are shown using the Venn diagram.

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

Hence, the second De Morgan’s law is proved.

In general, for ‘n’ sets, {A_{1}, A_{2}, …, A_{n}}, the formula is written as

${\left( \cap ^{n}_{k=1} A_{k}\right) ^{c}=\cup ^{n}_{k=1}A_{k}^{c}}$

It states that the complement of OR of two or more variables is the AND of the complement of each variable.

Mathematically, if A and B are two variables, then

**(A + B)’ = A’ ⋅ B’**

Here,

- + is the OR operator between variables,
- ⋅ is AND operator between variables, and
- ‘ is a complement operation on the variables

**Proof**

Here, we will use the following truth table:

These two logic gate circuits are shown:

It states that the complement of AND of two or more variables is the OR of the complement of each variable.

Mathematically, if A and B are two variables, then

**(A ⋅ B)’ = A’ + B’ **

Here,

- + is the OR operator between variables,
- ⋅ is AND operator between variables, and
- ‘ is a complement operation on the variables

**Proof**

To prove this theorem, we will use the following truth table:

These two logic gate circuits are shown:

Since the complement of a set is similar to negation and union is similar to an OR statement, there are equivalent forms of De Morgan’s Laws in logic.

It states that if p and q are two propositions, the negation of the conjunction of the propositions is equivalent to the disjunction of the negations of those propositions.

**∼(p ∧ q) ⟺ ∼p ∨ ∼q**

Here,

- ∧ is the conjunction of statements,
- ∨ is the disjunction of statements,
- ~ is the negation of the statement, and

≡ is the equivalence of statements.

Here, we will use a truth table of the propositions p and q:

p | q | ∼p | ∼q | p ∧ q | ∼(p ∧ q) | ∼p ∨ ∼q |

T | T | F | F | T | F | F |

T | F | F | T | F | T | T |

F | T | T | F | F | T | T |

F | F | T | T | F | T | T |

It states that if p and q are two propositions, the negation of the disjunction of the propositions is equivalent to the conjunction of the negations of those propositions.

**∼(p ∨ q) ⟺ ∼p ∧ ∼q**

Here,

- ∨ is the disjunction of statements,
- ∧ is the conjunction of statements,
- ~ is the negation of the statement, and
- ≡ is the equivalence of statements.

Here, we use the following truth table of the propositions p and q:

p | q | ∼p | ∼q | p ∨ q | ∼(p ∨ q) | ∼p ∧ ∼q |

T | T | F | F | T | F | F |

T | F | F | T | T | F | F |

F | T | T | F | T | F | F |

F | F | T | T | F | T | T |

Thus, De Morgan’s laws are used in electronic engineering to develop logic gates. They enable the design of digital circuits using only NAND or NOR gates, which are often more cost-effective and simpler to fabricate.

Here is a summary of all the De Morgan’s Laws formulas:

**If A = {7, 11, 15} and B = {5, 10, 15}, and the universal set U = {1, 2, 3, …, 15}, using De Morgan’s law prove that (A ∩ B)’ = A’ ∪ B’**

Solution:

Given A = {7, 11, 15}, B = {5, 10, 15}, and U = {1, 2, 3, …, 15}

Here,

A ∩ B = {7, 11, 15} ∩ {5, 10, 15} = {15}

A’ = U – A = {1, 2, 3, …, 15} – {7, 11, 15} = {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14}

B’ = U – B = {1, 2, 3, …, 15} – {5, 10, 15} = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}

Now,

(A ∩ B)’

= U – (A ∩ B)

= {1, 2, 3, …, 15} – {15}

= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} …..(i)

Also, A’ ∪ B’

= {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14} ∪ {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}

= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} …..(ii)

From (i) and (ii), (A ∩ B)’ = A’ ∪ B’, verified.

**Simplify the boolean expression [(A + B)’ + C]’**

Solution:

Given [(A + B)’ + C]’

By applying De Morgan’s law,

[(A + B)’]’ ⋅ C’

= (A + B) ⋅ C’

Last modified on June 17th, 2024