664
Boolean Algebra and Computer Logic
We have had some experience in simplifying Boolean expressions by applying the properties of Boolean algebra. However, we had no procedure to use. We
simply had to guess, attacking each problem individually. What we want now is
a mechanical procedure that we can use without having to be clever or insightful.
Unfortunately, we won’t develop the ideal procedure. However, we already know
how to select the canonical sum-of-products form from the equivalence class of
expressions for a given truth function. In this section we will discuss two procedures to reduce a canonical sum-of-products form to a minimal sum-of-products
form. Therefore, we can minimize within the framework of a sum-of-products
form and reduce, if not completely minimize, the number of elements and connections required.
example 19
The Boolean expression
x 1 x 2 x 3 + x 1 ′x 2 x 3 + x 1 ′x 2 x 3 ′
is in sum-of-products form. An equivalent minimal sum-of-products form is
x 2 x 3 + x 2 x 1 ′
Implementing a network for this form would require two AND gates, one OR gate,
and an inverter. Using one of the distributive laws of Boolean algebra, this expression reduces to
x 2 (x 3 + x 1 ′)
which requires only one AND gate, one OR gate, and an inverter, but it is no longer in sum-of-products form. Thus, a minimal sum-of-products form may not be
minimal in an absolute sense.
■
PraCtiCe 15 Use properties of Boolean algebra to reduce the following expressions as indicated:
a. x 1 x 2 + x 1 ′x 2 to x 2
b. x 1 + x 1 ′x 2 to x 1 + x 2
There are two extremely useful equivalences in minimizing a sum-of- products
form. They are
x 1 x 2 + x 1 ′x 2 = x 2
and
x 1 + x 1 ′x 2 = x 1 + x 2
The equivalence x 1 x 2 + x 1 ′x 2 = x 2 means, for example, that the expression
x 1 ′x 2 x 3 ′x 4 + x 1 ′x 2 ′x 3 ′x 4 reduces to x 1 ′x 3 ′x 4 . Thus, when we have a sum of two products
that differ in only one factor, we can eliminate that factor. However, the canonical
Boolean Algebra and Computer Logic
We have had some experience in simplifying Boolean expressions by applying the properties of Boolean algebra. However, we had no procedure to use. We
simply had to guess, attacking each problem individually. What we want now is
a mechanical procedure that we can use without having to be clever or insightful.
Unfortunately, we won’t develop the ideal procedure. However, we already know
how to select the canonical sum-of-products form from the equivalence class of
expressions for a given truth function. In this section we will discuss two procedures to reduce a canonical sum-of-products form to a minimal sum-of-products
form. Therefore, we can minimize within the framework of a sum-of-products
form and reduce, if not completely minimize, the number of elements and connections required.
example 19
The Boolean expression
x 1 x 2 x 3 + x 1 ′x 2 x 3 + x 1 ′x 2 x 3 ′
is in sum-of-products form. An equivalent minimal sum-of-products form is
x 2 x 3 + x 2 x 1 ′
Implementing a network for this form would require two AND gates, one OR gate,
and an inverter. Using one of the distributive laws of Boolean algebra, this expression reduces to
x 2 (x 3 + x 1 ′)
which requires only one AND gate, one OR gate, and an inverter, but it is no longer in sum-of-products form. Thus, a minimal sum-of-products form may not be
minimal in an absolute sense.
■
PraCtiCe 15 Use properties of Boolean algebra to reduce the following expressions as indicated:
a. x 1 x 2 + x 1 ′x 2 to x 2
b. x 1 + x 1 ′x 2 to x 1 + x 2
There are two extremely useful equivalences in minimizing a sum-of- products
form. They are
x 1 x 2 + x 1 ′x 2 = x 2
and
x 1 + x 1 ′x 2 = x 1 + x 2
The equivalence x 1 x 2 + x 1 ′x 2 = x 2 means, for example, that the expression
x 1 ′x 2 x 3 ′x 4 + x 1 ′x 2 ′x 3 ′x 4 reduces to x 1 ′x 3 ′x 4 . Thus, when we have a sum of two products
that differ in only one factor, we can eliminate that factor. However, the canonical