DeMorgan's Law

• Introduction
• How Can De Morgan's Laws Be Defined?
• Statement of De Morgan's Law
• Example of De Morgan's Law
• De Morgan's Law Proof
• Boolean Algebra: De Morgan's Law
• The Formula of De Morgan's Law
• De Morgan's Theorem Applications
• Solved Examples
• Practice Problems
• Frequently Asked Questions

Introduction

De Morgan's laws represent a fundamental set of rules in Boolean algebra and set theory, facilitating the manipulation of intersections, unions, and complements of sets. These laws establish conditions for transforming expressions, aiding in the simplification of complex Boolean expressions and calculations.

According to De Morgan's Laws:

• The complement of the combined sets' union equals the intersection of their individual complements. 
• Likewise, the complement of the combined sets' intersection equals the union of their individual complements.

In this article, we'll explore Demorgan's laws, their statements, proofs, and practical applications, and provide illustrative De Morgan's law examples using Venn diagrams for clear visualization.

How Can De Morgan's Laws Be Defined?

Demorgan's laws comprise two fundamental principles frequently applied in set theory. They state that: 

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

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

A set is a collection of distinct, well-defined objects forming a group. To simplify set operations like finding the complement, union, and intersection of sets, we employ De Morgan's laws.

Statement of De Morgan's Law

De Morgan's laws, applicable in both boolean algebra and set theory, involve the manipulation of sets within a universal set. Let `A` and `B` be subsets of the universal set `U`. `A'` represents the complement of `A`, and `B'` represents the complement of `B`. The symbols '`∩`' and '`∪`' denote intersection and union, respectively. De Morgan's laws can be stated as follows:

De Morgan's Law of Union

The complement of the union of the sets `A` and `B` is equal to the intersection of the complements of `A` and `B`. This principle, known as De Morgans Law of Union, is represented as \( (A \cup B)' = A' \cap B' \). This law can be extended to `n` sets, where if we have sets \(\{A_1, A_2, ..., A_n\}\), the formula becomes \(\biggl( \bigcup\limits_{i=1}^{n} A_i \biggr)' = \bigcap\limits_{i=1}^{n} A_i'\).

In the provided Venn diagram, the shaded red area represents the union of sets `A` and `B`, denoted as \(A \cup B\), while the green area represents the complement of this union, denoted as \((A \cup B)'\).

De Morgan's Law of Intersection

The complement of the intersection of the sets `A` and `B` is equal to the union of the complements of `A` and `B`. This principle, known as De Morgan's Law of Intersection, is represented as \( (A \cap B)' = A' \cup B' \). This law can be extended to n sets, where if we have sets \(\{A_1, A_2, ..., A_n\}\), the formula becomes \(\biggl( \bigcap\limits_{i=1}^{n} A_i \biggr)' = \bigcup\limits_{i=1}^{n} A_i'
\).

In the provided Venn diagram, the shaded red area represents the intersection of sets `A` and `B`, denoted as \(A \cap B\), while the green area represents the complement of this intersection, denoted as \((A \cap B)'\).

Example of De Morgan's Law

Let’s illustrate DeMorgans Laws using the sets `A` and `B` within the universal set \(U = \{1, 2, 3, 4, 5, 6, 7\}\). Let

• \(U = \{1, 2, 3, 4, 5, 6, 7\}\)
• \(A = \{1, 2, 3\}\)
• \(B = \{3, 4, 5\}\)

Example `1`: Using the sets `U`, `A` and `B`, prove De Morgan’s law of union \( (A \cup B)' = A' \cap B' \).

Solution:

Given:

\(U = \{1, 2, 3, 4, 5, 6, 7\}\)

\(A = \{1, 2, 3\}\)

\(B = \{3, 4, 5\}\)

`A = \{1, 2, 3\}`

`B = \{3, 4, 5\}`

`(A \cup B) = \{1, 2, 3, 4, 5\}`

`(A \cup B)' = \{6, 7\}`

`A' = \{4, 5, 6, 7\}`

`B' = \{1, 2, 6, 7\}`

`A' \cap B' = \{6, 7\}`

`\text{Thus, } (A \cup B)' = A' \cap B'`

This proves the De Morgan’s law of union \( (A \cup B)' = A' \cap B' \).

Example `2`: Using the sets `U`, `A` and `B`, prove De Morgan’s law of union `(A \cap B)' = A' \cup B'`.

Solution:

Given:

\(U = \{1, 2, 3, 4, 5, 6, 7\}\)

\(A = \{1, 2, 3\}\)

\(B = \{3, 4, 5\}\)

`A = \{1, 2, 3\}`

`B = \{3, 4, 5\}`

`(A \cap B) = \{3\}`

`(A \cap B)' = \{1, 2, 4, 5, 6, 7\}`

`A' = \{4, 5, 6, 7\}`

`B' = \{1, 2, 6, 7\}`

`A' \cup B' = \{1, 2, 4, 5, 6, 7\}`

`\text{Hence, } (A \cap B)' = A' \cup B'`

This proves the De Morgan’s law of intersection \( (A \cap B)' = A' \cup B' \).

De Morgan's Law Proof

De Morgan laws in set theory demonstrates that the complementation of sets results in the interchange of intersection and union operations. This principle can be verified through both mathematical proofs and truth tables.

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

To demonstrate the first De Morgan's theorem or law of Union, we start by defining sets `P` and `Q`. Let `P` represent the complement of the union of sets `A` and `B`, \(P = (A \cup B)'\). And `Q` represents the intersection of the complements of sets `A` and `B`, \(Q = A' \cap B' \) . Our goal is to prove \(P = Q\). To do this, we need to prove that `P` is a subset of `Q`, \(P \subset Q\) and `Q` is a subset of `P`, \(Q \subset P\).

Assume we select an element `y` that is in `P`, denoted as \(y \in P\).

`\Rightarrow y \in (A \cup B)'`

`\Rightarrow y \notin (A \cup B)`

`\Rightarrow y \notin A \text{ or } y \notin B`

`\Rightarrow y \in A' \text{ and } y \in B'`

`\Rightarrow y \in A' \cap B'`

`\Rightarrow y \in Q`

Thus, we conclude that \( P \subset Q \) (`P` is a subset of `Q`) `…(1)`

Let's consider an arbitrary element, denoted as `z`, which is a member of the set `Q`. This implies that `z` belongs to `Q`, \(z \in Q\).

`\Rightarrow z \in A' \cap B'`

`\Rightarrow z \in A' \text{ and } z \in B'`

`\Rightarrow z \notin A \text{ or } z \notin B`

`\Rightarrow z \notin (A \cup B)`

`\Rightarrow z \in (A \cup B)'`

`\Rightarrow z \in P`

Thus, we conclude that \( Q \subset P \) (`Q` is a subset of `P`) `...(2)`

We conclude from statements `(1)` and `(2)` that `Q` equals `P`.
Hence `(A \cap B)' = A' \cup B'`. Therefore, this theorem is proved.

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

To demonstrate the second De Morgan's theorem or law of Intersection, we start by defining sets `S` and `T`. Let `S` represent the complement of the intersection of sets `A` and `B`, \(S = (A \cap B)'\). And `T` represents the union of the complements of sets `A` and `B`, \(T = A' \cup B' \) . Our goal is to prove \(S = T\). To do this, we need to prove that `S` is a subset of `T`, \(S \subset T\) and `T` is a subset of `S`, \(T \subset S\).

Assume we select an element `y` that is in `S`, denoted as \(y \in S\).

`\Rightarrow y \in (A \cap B)'`

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

`\Rightarrow y \notin A \text{ and } y \notin B`

`\Rightarrow y \in A' \text{ or } y \in B'`

`\Rightarrow y \in A' \cup B'`

`\Rightarrow y \in T`

Thus, we conclude that \( S \subset T \) (`S` is a subset of `T`) `...(1)`

Let's consider an arbitrary element, denoted as `z`, which is a member of the set `T`. This implies that `z` belongs to `T`, \(z \in T\).

`\Rightarrow z \in A' \cup B'`

`\Rightarrow z \in A' \text{ or } z \in B'`

`\Rightarrow z \notin A \text{ and } z \notin B`

`\Rightarrow z \notin (A \cap B)`

`\Rightarrow z \in (A \cap B)'`

`\Rightarrow z \in S`

Thus, we conclude that \( T \subset S \) (`T` is a subset of `S`) `...(2)`

We conclude from statements `(1)` and `(2)` that `T` equals `S`. 

Hence   \( (A \cap B)' = A' \cup B' \). Therefore, this theorem is proved.

Boolean Algebra: De Morgan's Law

De Morgan's laws in Boolean algebra can be stated as:

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

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

Boolean algebra employs logic gates which operate on logical operations, with `A` and `B` serving as input binary variables. Digital input and output conditions are represented by "`0s`" and "`1s`". Truth tables are utilized to define operations like `AND` \( (A \cdot B)\), `OR` \( (A + B)\), and `NOT` (negation) based on these conditions. Through logic operations and truth tables, we can state and prove De Morgan's laws.

De Morgan's First Law

When multiple input variables `(A, B)` are combined with an `OR` operation and then negated, the outcome is equivalent to the `AND` operation of the complements of each individual input variable.

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

This can be demonstrated using a truth table, given below.

From the provided table, it's evident that the columns for \( \overline{A + B} \) and \( \overline{A} \cdot \overline{B} \) are identical.

De Morgan's Second Law

When multiple input variables `(A, B)` are combined with `AND` operation and then negated, the outcome is equivalent to the `OR` operation of the complements of each individual input variable.

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

This can be demonstrated using a truth table, given below.

From the provided table, it's evident that the columns for \( \overline{A \cdot B} \) and \( \overline{A} + \overline{B} \) are identical.

To simplify, the `OR` operation corresponds to the union operation of sets, while the `AND` operation corresponds to the intersection operation of sets.

The Formula of De Morgan's Law

De Morgan's laws finds application in both set theory and Boolean algebra, playing a crucial role in mathematical reasoning. These laws establish relationships between complementation, union, and intersection operations. The formulations are as follows:

In set theory:

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

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

For generalized formulas involving infinite unions and intersections:

\(\biggl( \bigcup\limits_{i=1}^{n} A_i \biggr)' = \bigcap\limits_{i=1}^{n} A_i'\)
\(\biggl( \bigcap\limits_{i=1}^{n} A_i \biggr)' = \bigcup\limits_{i=1}^{n} A_i'\)

In Boolean algebra:

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

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

De Morgan's Theorem Applications

• Circuit Design: De Morgan's theorem is extensively used in designing digital circuits. By applying De Morgan's theorem, complex logic expressions can be simplified, leading to more efficient circuit designs with fewer components.
   
• Boolean Algebra Manipulation: In Boolean algebra, De Morgan's theorem facilitates the manipulation and simplification of logical expressions involving `AND`, `OR`, and `NOT` operations. It allows for the transformation of expressions into alternative forms that might be easier to analyze or implement.
   
• Computer Science: De Morgan's theorem is fundamental in computer science, especially in the design and analysis of algorithms. It helps in simplifying Boolean expressions used in programming, which in turn enhances efficiency and readability of code.
   
• Set Operations: De Morgan's theorem has applications in set theory, particularly in understanding relationships between unions, intersections, and complements of sets. It enables the transformation of set expressions, aiding in proofs and establishing relationships between different sets.
   
• Error Detection and Correction: De Morgan's theorem is applied in error detection and correction techniques in communication systems. By simplifying logical expressions, it helps in designing efficient error detection and correction codes.

Solved Examples

Example `1`: Let \( U = \{6, 8, 2, 9, 4, 11, 24, 17\} \), \( A = \{4, 24, 8\} \), and \( B = \{24, 17, 4\} \). Show that \( (A \cup B)' = A' \cap B' \).

Solution:

Given that:

\( U = \{6, 8, 2, 9, 4, 11, 24, 17\} \) 

\( A = \{4, 24, 8\} \)

\( B = \{24, 17, 4\} \)

We want to show that \( (A \cup B)' = A' \cap B' \).

LHS:

\(A \cup B = \{4, 24, 8, 17\}\)

\((A \cup B)' = U - (A \cup B) = \{6, 2, 9, 11\}\)

RHS:

\(A' = U - A = \{6, 2, 9, 11, 17\}\)

\(B' = U - B = \{6, 8, 2, 9, 11\}\)

\(A' \cap B' = \{6, 2, 9, 11\}\)

Since the LHS equals the RHS, \( (A \cup B)' = A' \cap B' \) is proved.

Example `2`: Let \( U = \{m, n, o, p, q, r, s, t\} \), \( A = \{n, o, p\} \), and \( B = \{q, r, o\} \). Prove De Morgan’s Second Law.

Solution:

Given that:

\( U = \{m, n, o, p, q, r, s, t\} \) 

\( A = \{n, o, p\} \)

\( B = \{q, r, o\} \)

We know, De Morgan’s second law is \( (A \cap B)' = A' \cup B' \).

LHS:

\(A \cap B = \{o\}\)

\((A \cap B)' = U - (A \cap B) = \{m, n, p, q, r, s, t\}\)

RHS:

\(A' = U - A = \{m, q, r, s, t\}\)

\(B' = U - B = \{m, n, p, s, t\}\)

\(A' \cup B' = \{m, n, p, q, r, s, t\}\)

Since the LHS equals the RHS, \( (A \cap B)' = A' \cup B' \) is proved.

Example `3`: Simplify the expression:  \( \overline{\overline{A}B+CD} \)

Solution:

Given that:

\( \overline{\overline{A}B+CD} \)

Apply De Morgan's Law \( \overline{P+Q} = \overline{P} \cdot \overline{Q} \).

Using De Morgan's Law, \( \overline{\overline{A}B+CD} \) can be rewritten as \( \overline{\overline{A}B} \cdot \overline{CD} \).

Also, \( \overline{P \cdot Q} = \overline{P} + \overline{Q} \)

Thus, \( \overline{\overline{A}B} \cdot \overline{CD} \) = \((\overline{\overline{A}} + \overline{B}) \cdot (\overline{C} + \overline{D}) \)

As \(\overline{\overline{A}} = A\) we have \((A+ \overline{B}) \cdot (\overline{C} + \overline{D}) \).

Therefore,  \( \overline{\overline{A}B+CD} = (A+ \overline{B}) \cdot (\overline{C} + \overline{D}) \).

Practice Problems

Q`1`. Simplify the expression: \( \overline{A + (B \cdot C)} \)

1. \( \overline{A} + \overline{B} \cdot \overline{C} \)
2. \( \overline{A} + \overline{B} + \overline{C} \)
3. \( \overline{A} \cdot \overline{B} \cdot \overline{C} \)
4. \( \overline{A} \cdot \overline{B} + \overline{A} \cdot \overline{C} \)

Answer: d

Q`2`. Simplify the expression: \( \overline{(A + B + C)} \cdot \overline{(D + E)} \)

1. \( \overline{A} \cdot \overline{B} \cdot \overline{C} \cdot \overline{D} \cdot \overline{E} \)
2. \( \overline{A} \cdot \overline{B} \cdot \overline{C} \cdot \overline{D} + \overline{A} \cdot \overline{B} \cdot \overline{C} \cdot \overline{E} \)
3. \( \overline{A} \cdot \overline{B} \cdot \overline{C} + \overline{D} \cdot \overline{E} \)
4. \( \overline{A} + \overline{B} + \overline{C} + \overline{D} + \overline{E} \)

Answer: a

Q`3`. Simplify the expression: \( \overline{(A \cdot B)} \cdot \overline{(C + D)} \)

1. \( \overline{A} \cdot \overline{C} \cdot \overline{D} + \overline{B} \cdot \overline{C} \cdot \overline{D} \)
2. \( \overline{A} \cdot \overline{B} \cdot \overline{C} \cdot \overline{D} \)
3. \( \overline{A} \cdot (\overline{B} + \overline{C}) \cdot \overline{D} \)
4. \( \overline{A} \cdot \overline{B} \cdot \overline{C} + \overline{A} \cdot \overline{B} \cdot \overline{D} \)

Answer: a

Frequently Asked Questions

Q`1`. What is De Morgan's Law?

Answer: De Morgan's Law is a fundamental principle in Boolean algebra that describes the relationship between negations of logical `OR` and logical `AND` operations. It states that the negation of a logical `OR` operation is equivalent to the logical `AND` operation of the negations of the operands, and vice versa.

Q`2`. How do I apply De Morgan's Law in practice?

Answer: To apply De Morgan's Law, simply negate the terms inside the brackets and switch the operation. For example, \( \overline{A + B} \) becomes \( \overline{A} \cdot \overline{B} \), and \( \overline{A \cdot B} \) becomes \( \overline{A} + \overline{B} \).

Q`3`. What are the benefits of using De Morgan's Law?

Answer: De Morgan's Law provides a simple and systematic method for simplifying complex Boolean expressions. By applying this law, you can transform expressions into more manageable forms, making them easier to analyze and understand.

Q`4`. Can I apply De Morgan's Law multiple times in a single expression?

Answer: Yes, you can apply De Morgan's Law multiple times within a single expression to simplify it further. Each application of the law helps break down the expression into simpler components, facilitating easier analysis.

Q`5`. Does De Morgan's Law apply to other logical operators besides `AND` and `OR`?

Answer: While De Morgan's Law specifically applies to the negation of logical `AND` and `OR` operations, similar principles can be extended to other logical operators, such as `NAND` and `NOR`. These extensions are known as generalized De Morgan's Laws and are widely used in digital logic design and computer science.