Practical no-
DeMorgan’s Theorems
AIM
To study and verify DeMorgan’s Theorems using Boolean algebra and truth tables,
demonstrating the equivalence between NAND and negative-OR logic, and between NOR
and negative-AND logic
TOOLS USED
Software/Simulation: Logic Gate Simulator (TinkerCAD / Logisim)
Concepts: Boolean Algebra, Logic Gates, DeMorgan’s Laws
Components: AND, OR, NOT, NAND, NOR gates
THEORY
DEMORGAN’S THEOREM
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.
Figure 1: Implementation of 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.
Figure 2: Implementation of DeMorgan’s SecondTheorem
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.
DeMorgan’s First Theorem states that the NAND gate can be replaced with the OR
function having inverted inputs i.e. Invert-OR logic.
