646
Boolean Algebra and Computer Logic
and
x 1 x 3 + x 2
′
for example, are equivalent Boolean expressions.
Clearly, equivalence of Boolean expressions is an equivalence relation on the
set of all Boolean expressions in n variables. Each equivalence class is associated
with a distinct truth function. Given a truth function, algorithm Sum-Of-Products
produces one particular member of the class associated with that function, namely, the canonical sum-of-products form. However, if we are trying to design the
logic network for that function, we want to find a member of the class that is as
simple as possible. We would rather build the network of Figure 8.12 than the one
for Practice 11(b).
How can we reduce a Boolean expression to an equivalent, simpler expression? We can use the properties of a Boolean algebra because they express the
equivalence of Boolean expressions. If P is a Boolean expression containing the
subexpression (x 1 + x 2 )(x 1 + x 3 ), for example, and Q is the expression obtained
from P by replacing (x 1 + x 2 )(x 1 + x 3 ) with the equivalent expression x 1 + (x 2 x 3 ),
then P and Q are equivalent and Q is simpler than P.
example 16
Using the properties of Boolean algebra, we can reduce
x 1 x 2 x 3 + x 1 x 2
′x 3 + x 1 x 2
′x 3
′ + x 1
′x 2
′x 3 + x 1
′x 2
′x 3
′
to
x 1 x 3 + x 2
′
as follows:
x 1 x 2 x 3 + x 1 x 2
′x 3 + x 1 x 2
′x 3
′ + x 1
′x 2
′x 3 + x 1
′x 2
′x 3
′
= x 1 x 2 x 3 + x 1 x 2
′x 3 + x 1 x 2
′x 3 + x 1 x 2
′x 3
′ + x 1
′x 2
′x 3 + x 1
′x 2
′x 3
′
(idempotent)
= x 1 x 3 x 2 + x 1 x 3 x 2
′ + x 1 x 2
′x 3 + x 1 x 2
′x 3
′ + x 1
′x 2
′x 3 + x 1
′x 2
′x 3
′
(1b)
= x 1 x 3 (x 2 + x 2
′) + x 1 x 2
′(x 3 + x 3
′) + x 1
′x 2
′(x 3 + x 3
′)
(3b)
= x 1 x 3 # 1 + x 1 x 2
′ # 1 + x 1
′x 2
′ # 1
(5a)
= x 1 x 3 + x 1 x 2
′ + x 1
′x 2
′
(4b)
= x 1 x 3 + x 2
′x 1 + x 2
′x 1
′
(1b)
= x 1 x 3 + x 2
′(x 1 + x 1
′)
(3b)
= x 1 x 3 + x 2
′ # 1
(5a)
= x 1 x 3 + x 2
′
(4b)
Unfortunately, one must be fairly clever to apply Boolean algebra properties to
simplify an expression. In Section 8.3 we will discuss more systematic approaches
to this minimization problem that require less ingenuity. For now, we should say
Boolean Algebra and Computer Logic
and
x 1 x 3 + x 2
′
for example, are equivalent Boolean expressions.
Clearly, equivalence of Boolean expressions is an equivalence relation on the
set of all Boolean expressions in n variables. Each equivalence class is associated
with a distinct truth function. Given a truth function, algorithm Sum-Of-Products
produces one particular member of the class associated with that function, namely, the canonical sum-of-products form. However, if we are trying to design the
logic network for that function, we want to find a member of the class that is as
simple as possible. We would rather build the network of Figure 8.12 than the one
for Practice 11(b).
How can we reduce a Boolean expression to an equivalent, simpler expression? We can use the properties of a Boolean algebra because they express the
equivalence of Boolean expressions. If P is a Boolean expression containing the
subexpression (x 1 + x 2 )(x 1 + x 3 ), for example, and Q is the expression obtained
from P by replacing (x 1 + x 2 )(x 1 + x 3 ) with the equivalent expression x 1 + (x 2 x 3 ),
then P and Q are equivalent and Q is simpler than P.
example 16
Using the properties of Boolean algebra, we can reduce
x 1 x 2 x 3 + x 1 x 2
′x 3 + x 1 x 2
′x 3
′ + x 1
′x 2
′x 3 + x 1
′x 2
′x 3
′
to
x 1 x 3 + x 2
′
as follows:
x 1 x 2 x 3 + x 1 x 2
′x 3 + x 1 x 2
′x 3
′ + x 1
′x 2
′x 3 + x 1
′x 2
′x 3
′
= x 1 x 2 x 3 + x 1 x 2
′x 3 + x 1 x 2
′x 3 + x 1 x 2
′x 3
′ + x 1
′x 2
′x 3 + x 1
′x 2
′x 3
′
(idempotent)
= x 1 x 3 x 2 + x 1 x 3 x 2
′ + x 1 x 2
′x 3 + x 1 x 2
′x 3
′ + x 1
′x 2
′x 3 + x 1
′x 2
′x 3
′
(1b)
= x 1 x 3 (x 2 + x 2
′) + x 1 x 2
′(x 3 + x 3
′) + x 1
′x 2
′(x 3 + x 3
′)
(3b)
= x 1 x 3 # 1 + x 1 x 2
′ # 1 + x 1
′x 2
′ # 1
(5a)
= x 1 x 3 + x 1 x 2
′ + x 1
′x 2
′
(4b)
= x 1 x 3 + x 2
′x 1 + x 2
′x 1
′
(1b)
= x 1 x 3 + x 2
′(x 1 + x 1
′)
(3b)
= x 1 x 3 + x 2
′ # 1
(5a)
= x 1 x 3 + x 2
′
(4b)
Unfortunately, one must be fairly clever to apply Boolean algebra properties to
simplify an expression. In Section 8.3 we will discuss more systematic approaches
to this minimization problem that require less ingenuity. For now, we should say