Demorgan's Law: A Practical Guide To Applying The Theory

De Morgan's Law, named after Augustus De Morgan, is a set of two postulates widely used in set theory and Boolean algebra. The laws state that the AND and OR operations are interchangeable through negation. In other words, the complement of the union of two sets is equal to the intersection of their individual complements, and vice versa. This can be expressed as:

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

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

De Morgan's Law is useful for simplifying complex expressions and calculations, and it has applications in various fields, including engineering, computer programming, and mathematics.

De Morgan's Law in Set Theory

De Morgan's Law is a set of two postulates used in set theory to simplify mathematical expressions. The law gives the relationship between the union, intersection, and complements of sets.

First De Morgan's Law

The complement of the union of two sets is equal to the intersection of the complements of each set.

Let A and B be two sets, then mathematically, the First De Morgan's Law is given as:

A ∪ B)’ = A’ ∩ B’

Here, U represents the union operation between sets, ∩ represents the intersection operation between sets, and ‘ represents the complement operation on a set.

This is also known as De Morgan's Law of Union and can be proven using algebra of sets, Venn diagrams, and truth tables.

Second De Morgan's Law

The complement of the intersection of two sets is equal to the union of the complements of each set.

Let A and B be two sets, then mathematically, the Second De Morgan's Law is given as:

A ∩ B)’ = A’ ∪ B’

Here, U represents the union operation between sets, ∩ represents the intersection operation between sets, and ‘ represents the complement operation on a set.

This is also known as De Morgan's Law of Intersection and can be proven using algebra of sets, Venn diagrams, and truth tables.

Applications of De Morgan's Law

De Morgan's Law is used in various fields, including elementary algebra, Boolean algebra, computer programming, and electronic engineering. It is particularly useful for simplifying complex expressions and optimizing code. In electronic engineering, the law is applied to develop logic gates and create cheaper hardware.

De Morgan's Law in Boolean Algebra

De Morgan's Law is a pair of transformation rules in Boolean algebra and set theory that relates the intersection and union of sets through complements. The rules are used to reduce expressions into a simpler form, making calculations easier and complex Boolean expressions more manageable.

De Morgan's Law is named after Augustus De Morgan, a 19th-century British mathematician. The law is often stated as "union and intersection interchange under complementation". In other words, the complement of the union of two sets is equal to the intersection of their individual complements, and the complement of the intersection of two sets is equal to the union of their individual complements.

In Boolean algebra, De Morgan's Law can be expressed as:

• The negation of the conjunction of two variables is equal to the disjunction of the individual variables' negations: $\overline{A \cdot B} = \overline{A} + \overline{B}$
• The negation of the disjunction of two variables is equal to the conjunction of the individual variables' negations: $\overline{A + B} = \overline{A} \cdot \overline{B}$

Here, the overline denotes the logical NOT of what is underneath it, the dot represents the logical AND, and the plus represents the logical OR.

De Morgan's Law can be applied to simplify logical expressions in computer programs and digital circuit designs. It is also used in electrical and computer engineering to simplify circuit designs.

Proof Using Algebra of Sets

First De Morgan's Law

Let's prove (A ∪ B)’ = A’ ∩ B’.

Let X = (A ∪ B)’ and Y = A’ ∩ B’.

Let p be any element of X, then p ∈ X ⇒ p ∈ (A ∪ B)’

⇒ p ∉ A or p ∉ B

⇒ p ∈ A’ and p ∈ B’

⇒ p ∈ A’ ∩ B’

∴ X ⊂ Y . . (i)

Again, let q be any element of Y, then q ∈ Y ⇒ q ∈ A’ ∩ B’

⇒ q ∈ A’ and q ∈ B’

⇒ q ∉ A or q ∉ B

⇒ q ∈ (A ∪ B)’

∴ Y ⊂ X . . (ii)

From (i) and (ii) X = Y

A ∪ B)’ = A’ ∩ B’

Second De Morgan's Law

Let's prove (A ∩ B)’ = A’ ∪ B’.

Let X = (A ∩ B)’ and Y = A’ ∪ B’

Let p be any element of X, then p ∈ X ⇒ p ∈ (A ∩ B)’

⇒ p ∉ A and p ∉ B

⇒ p ∈ A’ or p ∈ B’

⇒ p ∈ A’ ∪ B’

∴ X ⊂ Y ————–(i)

Again, let q be any element of Y, then q ∈ Y ⇒ q ∈ A’ ∪ B’

⇒ q ∈ A’ or q ∈ B’

⇒ q ∉ A and q ∉ B

⇒ q ∈ (A ∩ B)’

∴ Y ⊂ X ————–(ii)

From (i) and (ii) X = Y

A ∩ B)’ = A’ ∪ B’

Proof Using Venn Diagram

De Morgan's Law is a collection of boolean algebra transformation rules that relate the intersection and union of sets using complements. There are two types of De Morgan's Law:

De Morgan's First Law

The complement of the union of two sets is the intersection of their complements.

Consider any two sets, A and B. De Morgan's first law is given by:

\((A \cup B)' = A' \cap B'\)

De Morgan's Second Law

The complement of the intersection of two sets is the union of their complements.

Consider any two sets, A and B. De Morgan's second law is given by:

\((A \cap B)' = A' \cup B'\)

These laws can be easily visualised using Venn diagrams. Let's consider a universal set, U, where A and B are subsets of U.

Proof of De Morgan's First Law using Venn Diagrams

The union of sets A and B is represented by shading the entire portion of both sets. The Venn diagram of \((A \cup B)'\) shows all the regions of the union except A and B.

The complement of two sets, A and B, is shown by shading all regions of the union except the given set. The intersection of the complement of the two sets is shown in the Venn diagram below:

By using the Venn diagrams, we can see that \((A \cup B)' = A' \cap B'\), thus proving De Morgan's First Law.

Proof of De Morgan's Second Law using Venn Diagrams

The Venn diagram of \(A \cap B\) is shown by shading the common portion. The Venn diagram for the complement of \(A \cap B\) is shown by shading all regions excluding the common part of the sets, as shown below:

We know that the complement of two sets, A and B, is shown by shading all regions of the union except the given set. The union of the complement of the two sets is shown below:

From the above Venn diagrams, we can say that \((A \cap B)' = A' \cup B'\), thus proving De Morgan's Second Law.

Logic Applications of De Morgan's Law

De Morgan's Law is a fundamental principle in logic, set theory, and Boolean algebra, providing rules for transforming logical expressions. It gives the relationship between union, intersection, and complements in set theory. In Boolean algebra, it provides the relationship between AND, OR, and the complements of variables. In logic, it gives the relationship between AND, OR, or the negation of a statement.

De Morgan's Law is crucial in simplifying conditional statements in programming. It allows programmers to simplify complex logical conditions, making code more efficient and readable. It is also used in electronic circuit design to create more efficient layouts by converting AND gates into OR gates and vice versa using NOT gates.

• If it is not true that "it is raining and cold," we can infer that "it is not raining or it is not cold."
• If you are checking if a number is neither positive nor even in a programming language, the statement "if !(number > 0 and number % 2 == 0)" can be simplified using De Morgan's Law to "if (number <= 0 or number % 2 != 0)."
• To prove that the complement of the intersection of two sets, A and B, is equal to the union of their complements, we can use De Morgan's Law, which states that "(A ∩ B)' = A' ∪ B'."
• In logical puzzles or arguments, De Morgan's Law helps to simplify complex negations. For example, negating "All apples are red" to "Not all apples are red" implies "Some apples are not red."

Frequently asked questions