ic
Section 8.2 Logic Networks
643
Each term in the sum will be a product of the form abg where a is either x 1 or x 1
′, b is either x 2 or x 2
′, and g is either x 3 or x 3
′. If the input value of
x i , i = 1, 2, 3, in the row we are working on is 1, then x i itself is used; if the input
value of x i in the row we are working on is 0, then x i ′ is used. These values will
force abg to be 1 for that row and 0 for all other rows. Thus, we have
row 1: x 1 x 2 x 3
row 3: x 1 x 2
′x 3
row 4: x 1 x 2
′x 3
′
row 7: x 1
′x 2
′ x 3
The final expression is
(x 1 x 2 x 3 ) + (x 1 x 2
′ x 3 ) + (x 1 x 2
′x 3
′) + (x 1 ′x 2
′x 3 )
The procedure described in Example 13 always leads to an expression that is
a sum of products, called the canonical sum-of-products form, or the disjunctive normal form, for the given truth function. The only case not covered by
this procedure is when the function has a value of 0 everywhere. Then we use an
expression such as
x 1 x 1
′
which is also a sum (one term) of products. Therefore, we can find a sum-ofproducts expression to represent any truth function. A pseudocode description
of the algorithm is given in the accompanying box. For this algorithm, the input
is a truth table representing a truth function on n variables x 1 , x 2 , … , x n ; the
output is a Boolean expression in disjunctive normal form with the same truth
function.
algoRitHm Sum-Of-PROductS
Sum-Of-Products (truth table; integer n)
//the truth table represents a truth function with n arguments;
//result is the canonical sum-of-products expression for this truth function
Local variables:
sum
//sum-of-products expression
product
//single term in sum, a product
i
//index for the columns of the table
row
//index for the rows of the table
sum = empty