Page 53 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Digital Circuits and Logic Design

Notes
x
2. (xy• ) =+ y
Theorem (1) says that when the OR sum of two variables is inverted, this is the same as inverting
each variable individually and then ANDing these inverted variables. Theorem (2) says that
when the AND product of two variables is inverted, this is the same as inverting each variable
individually and then ORing them. Each of DeMorgan’s theorems can be readily proven by
checking for all possible combinations of x and y.

Although these theorems have been stated in terms of single variables x and y, they are equally
valid for situations where x and/or y are expressions that contain more than one variable. For
example, let’s apply them to the expression

(AB + C ) as shown below:
(AB + C ) = (AB ) C
·
Note that here we treated AB as x and C as y. The result can be further simplified since we have
a product AB that is inverted. Using theorem (2), the expression becomes
AB C = (A + ) B C
•
·
Notice that we can replace B by B, so that we finally have
(A + ) B C = AC + BC
•
This final result contains only inverter signs that invert a single variable.
When using DeMorgan’s theorems to reduce an expression, we may break an inverter sign at
any point in the expression and change the operator at that point in the expression to its opposite
(+ is changed to •, and vice versa). This procedure is continued until the expression is reduced to
one in which only single variables are inverted. Two or more examples are given below:
.
1. z = A + B C 2. w = (A + BC ) (D + EF )
•
= A · B C) = (A + BC ) + (D + EF )
·(
= A •( B + C) = (ABC• ) + (D EF )
•
= A •( B + C) = [A • (B + C )]+ [D • (E + F )]
= AB + AC + DE + DF
DeMorgan’s theorems are easily extended to more than two variables. For example, it can be
proved that
y
z
x ++ = xy z· ·
y
xy z = x ++ z
·
·
and so on for more variables. Again, realize that any one of these variables can be an expression
rather than a single variable.
3.3.1 Implications of DeMorgan’s Theorems
Let us examine these theorems (1) and (2) from the standpoint of logic circuits. First, consider
theorem (1),
x + y = xy·
The left-hand side of the equation can be viewed as the output of a NOR gate whose inputs are
x and y. The right-hand side of the equation, on the other hand, is the result of first inverting both
x and y and then putting them through an AND gate. These two representations are equivalent
and are illustrated in Figure 3.8 (a).

48 LOVELY PROFESSIONAL UNIVERSITY