660
Boolean Algebra and Computer Logic
25. There is also a canonical product-of-sums form (conjunctive normal form) for any truth function. This
expression has the form
( )( ) c ( )
with each factor a sum of the form
a + b + c + v
where a = x 1 or x 1 ′, b = x 2 or x 2 ′, and so on. Each factor is constructed to have a value of 0 for the input
values of exactly one of the rows of the truth function having value 0. Thus, the entire expression has
value 0 for these inputs and no others. Find the canonical product-of-sums form for the truth functions of
Exercises 11–15.
26. Consider the truth function given here. Because there are many more 1s than 0s. the canonical sum-ofproducts form might seem tedious to compute. Instead, create a Boolean sum-of-products expression using the same formula as before but on the 0 rows instead of the 1 rows. This expression will give outputs of
1s for those rows and no others, exactly the opposite of what you want. Then complement the expression
(equivalent to sticking an inverter on the end of the network).
x 1
x 2
x 3 f(x 1 , x 2 , x 3 )
1
1
1
1
1
1
0
1
1
0
1
1
1
0
0
0
0
1
1
1
0
1
0
1
0
0
1
0
0
0
0
1
a. Use this approach to create a Boolean expression for this truth function.
b. Prove that the resulting expression is equivalent to the canonical product-of-sums form described in
Exercise 25.
27. The 2’s complement of an n-bit binary number p is an n-bit binary number q such that p + q equals an
n-bit representation of zero (any carry bit to column n + 1 is ignored). Thus 01110 is the 2’s complement
of 10010 because
10010
+ 01110
(1)00000
The 2’s complement idea can be used to represent negative integers in binary form. After all, the negative
of p is by definition a number that, when added to p, results in zero.
Given a binary number p, the 2’s complement of p is found by scanning p from low-order to highorder bits (right to left). As long as bit i of p is 0, bit i of q is 0. When the first 1 of p is encountered, say at
bit j, then bit j of q is 1, but for the remaining bits, j < i ≤ n, q i = p i
′. For p = 10010, for instance, the
Boolean Algebra and Computer Logic
25. There is also a canonical product-of-sums form (conjunctive normal form) for any truth function. This
expression has the form
( )( ) c ( )
with each factor a sum of the form
a + b + c + v
where a = x 1 or x 1 ′, b = x 2 or x 2 ′, and so on. Each factor is constructed to have a value of 0 for the input
values of exactly one of the rows of the truth function having value 0. Thus, the entire expression has
value 0 for these inputs and no others. Find the canonical product-of-sums form for the truth functions of
Exercises 11–15.
26. Consider the truth function given here. Because there are many more 1s than 0s. the canonical sum-ofproducts form might seem tedious to compute. Instead, create a Boolean sum-of-products expression using the same formula as before but on the 0 rows instead of the 1 rows. This expression will give outputs of
1s for those rows and no others, exactly the opposite of what you want. Then complement the expression
(equivalent to sticking an inverter on the end of the network).
x 1
x 2
x 3 f(x 1 , x 2 , x 3 )
1
1
1
1
1
1
0
1
1
0
1
1
1
0
0
0
0
1
1
1
0
1
0
1
0
0
1
0
0
0
0
1
a. Use this approach to create a Boolean expression for this truth function.
b. Prove that the resulting expression is equivalent to the canonical product-of-sums form described in
Exercise 25.
27. The 2’s complement of an n-bit binary number p is an n-bit binary number q such that p + q equals an
n-bit representation of zero (any carry bit to column n + 1 is ignored). Thus 01110 is the 2’s complement
of 10010 because
10010
+ 01110
(1)00000
The 2’s complement idea can be used to represent negative integers in binary form. After all, the negative
of p is by definition a number that, when added to p, results in zero.
Given a binary number p, the 2’s complement of p is found by scanning p from low-order to highorder bits (right to left). As long as bit i of p is 0, bit i of q is 0. When the first 1 of p is encountered, say at
bit j, then bit j of q is 1, but for the remaining bits, j < i ≤ n, q i = p i
′. For p = 10010, for instance, the