DeMorgan’s Theorem

DeMorgan’s Theorem

In the previous articles, we discussed that the digital logic uses Boolean data type which comprises of only two states i.e. “0” and “1”, and which are also referred to as “LOW” and “HIGH” states, respectively. The set of rules and laws can be applied to Boolean data types to find the optimum solution. As such, a digital logic circuit can be expressed in a Boolean Algebraic equation, and, by applying Boolean rules, laws, and theorems on this equation, an optimum digital circuit can be deduced. This optimum digital circuit benefits reduced logic, size, power consumption, and cost. Augustus DeMorgan, an English Mathematician, gave two famous laws known as DeMorgan’s Theorems which imparted a major contribution to Boolean Algebra. DeMorgan’s Theorems will be explained later in this article. However, in simple words, DeMorgan’s Theorems can be used to find the equivalency of NAND and NOR gates by viewing these operations as separate NOT-AND and NOT-OR functions, respectively.

The truth table comprising of AND, NAND, OR, and NOR logic functions against two inputs is given below. These logical functions are used in DeMorgan’s Theorems and, as such, given to recall these logical operations.

The above given logical functions are denoted by equivalent Boolean notations. A “.” between operands means AND (Multiplication) operation, a “+” means OR (Sum) operation, and overline means an inversion of the operand. The equivalent Boolean notations of commonly used logical functions are shown in the following table.

DeMorgan’s Theory

DeMorgan’s Theory states two sets of laws or rules which are applicable to Boolean expressions having AND, OR, and NOT logical operations with two inputs (or more). Using these theorems, the logical operation of two variables is negated and converted into another logical operation. Such as, the logical NOR operation on two (or more) variables is equivalent to inversion of these variables and AND’ed together. Similarly, the logical NAND operation on two (or more) variables is equivalent to inversion of these variables and OR’ed, together. In other words, using DeMorgan’s theorems, the AND operator is replaced with the OR operator, and the OR operator is replaced with the AND operator.

DeMorgan’s First Theorem

According to DeMorgan’s First Theorem, the resultant of two (or more) variables AND’ed and inverted (NOT) as a whole is equivalent to the OR of the complements of individual variables. Thus, AND + NOT (NAND) operation on variables is equivalent to the sum (OR) of the individual complement of each variable. In Boolean expression, it is stated as follow:

Verification of DeMorgan’s First Theorem using Truth Table

DeMorgan’s First Theorem can be verified using a truth table as illustrated below:

DeMorgan’s First Law Implementation

The following figure shows the implementation of DeMorgan’s First Theorem. The two logic circuits are equivalent to each other as per DeMorgan’s First Theorem.

The left logic circuit forms a NAND (AND + NOT) gate. Whereas the right logic circuit, first inverts the inputs then they are OR’ed. These two logic circuits are equivalent to each other i.e. NAND = negative-OR. It can also be stated that a complement can be shifted from the output of the AND gate to the individual input of an OR gate and will be identical in logic operation as per the first theorem of DeMorgan.

DeMorgan’s Second Theorem

According to DeMorgan’s Second Theorem, the resultant of two (or more) variables OR’ed and inverted (NOT) as a whole is equivalent to the AND of the complements of individual variables. Thus, OR + NOT (NOR) operation on variables is equivalent to AND of the individual complement of each variable. In Boolean expression, it is stated as follow:

Verification of DeMorgan’s Second Theorem using Truth Table

DeMorgan’s Second Theorem can be verified using a truth table as illustrated below:

DeMorgan’s Second Law Implementation

The following figure shows an implementation of DeMorgan’s Second Theorem. The two logic circuits are equivalent to each other as per DeMorgan’s Second Theorem.

The left logic circuit forms a NOR (OR + NOT) gate. Whereas the right logic circuit, first inverts the inputs then they are AND’ed. These two logic circuits are equivalent to each other i.e. NOR = negative-AND. It can also be stated that a complement can be shifted from the output of OR gate to individual input of an AND gate and will be identical in logic operation as per the second theorem of DeMorgan.

Thus, according to DeMorgan, an AND operation on inverted inputs is equivalent to NOR (OR + NOT) operation and vice versa. Similarly, an OR operation on inverted inputs is equivalent to NAND (AND + NOT) operation and vice versa.

In the above text, DeMorgan’s theorems have been applied to two-input variables. However, theorems are equally valid for more than two inputs variables.

For three-input variables:

DeMorgan’s First Theorem:

DeMorgan’s Second Theorem:

For four-input variables:

DeMorgan’s First Theorem:

DeMorgan’s Second Theorem:

DeMorgan’s Equivalent Gates

The standard logic gates i.e. AND, NAND, OR, and NOR representing DeMorgan’s theorems can be obtained.  It has already been discussed above that the NAND (AND + NOT) operation can be replaced by the OR logic on inverted inputs. Here, firstly, AND logic is replaced with the OR, and, secondly, the inversion is applied at the inputs and outputs. Resultantly, the AND + NOT logic becomes NOT + OR. The inputs which were originally not inverted become inverted and inverted output becomes non-inverted. The same can be applied to DeMorgan’s Second Theorem to obtain equivalent logic gates.

The following table shows the standard equivalent logic gates of DeMorgan’s theorems.

Conclusion

• Augustus DeMorgan, an English Mathematician, gave two famous laws known as DeMorgan’s Theorems which are used to find the equivalency of the NAND and NOR logic gates.
• DeMorgan’s First Theorem states that the NAND gate can be replaced with the OR function having inverted inputs i.e. Invert-OR logic.
• DeMorgan’s Second Theorem states that the NOR gate can be replaced with the AND function having inverted inputs i.e. Invert-AND logic.
• According to DeMorgan’s theorems, the AND logic can be replaced with the OR logic with inversion applied at the inputs and the output. Similarly, the OR logic can be replaced with the AND logic with inversion applied at the inputs and the output.
• The AND logic can be replaced with the Inversion-NOR logic.
• The NAND logic can be replaced with the Inversion-OR logic.
• The OR logic can be replaced with the Inversion-NAND logic.
• The NOR logic can be replaced with the Inversion-AND logic.

Please follow and like us: