644
Boolean Algebra and Computer Logic
for row = 1 to 2
n
do
if truth value for row is 1 then
initialize product;
for i = 1 to n do
if x i = 1 then
put x i in product
else
put x i
′ in product
end if
end for
sum = sum + product
end if
end for
if sum is empty then
sum = x 1 x 1
′
end if
write (“The canonical sum-of-products expression for this truth function is”, sum)
end Sum-Of-Products
Because any expression has a corresponding network, any truth function has
a logic network representation. Furthermore, the AND gate, OR gate, and inverter
are the only devices needed to construct the network. Thus, we can build a network for any truth function with only three kinds of parts—and lots of wire! Later
we will see that it is necessary to stock only one kind of part.
Given a truth function, the canonical sum-of-products form just described
is one expression that has this truth function, but it is not the only possible one.
A method for obtaining a different expression for any truth function is given in
Exercise 25 at the end of this section.
example 14
The network for the canonical sum-of-products form of Example 13 is shown in
Figure 8.11. We have drawn the inputs to each AND gate separately because it
looks neater, but actually a single x 1 , x 2 , or x 3 input can be split as needed.
figure 8.11