Answers to Selected Problems in Chapter 2, COSC3410

Answers to Selected Problems on Boolean Algegra and Logic Gates

(See Chapter 2 of Mano's Digital Design (2nd ed.))

2-13 Express the complement of the following functions in sum of minters:
(a) F(A, B, C, D) = S(0, 2, 6, 11, 13, 14), F'(A, B, C, D) = S(1, 3, 4, 5, 7, 8, 9, 10, 12, 15).

(b) F(x, y, z) = P(0, 3, 6, 7) = S(1, 2, 4, 5), F'(x, y, z) = S(0, 3, 6, 7).

2-14 Convert the following to the other canonical form:
(a) F(x, y, z) = S(1, 3, 7) = P(0, 2, 4, 5, 6)

(b) F(A, B, C, D) = P(0, 1, 2, 3, 4, 6, 12) = S(5, 7, 8, 9, 10, 11, 13, 14, 15)

2-15 The sum of all the minterms of a Boolean function of n variables is equal to 1.
(a) Prove the above statement for n=3.
a'b'c' + a'b'c + a'bc' + a'bc + ab'c' + ab'c + abc' + abc = a'b' + a'b + ab' + ab = a' + a = 1.

(b) Suggest a general procedure for a general proof.
(Hint) For n > 3. If E represents the sum of all minterms of a function of n variables, then the sum of all minterms of a function of n+1 variables will be E(z'+z), which is equal to 1. This is obviously so for n = 4. Use induction for any n > 4.

2-19 By substituting the Boolean expression equivalent of the binary operations as defined in Table 2-8, show the following:
(a) The inhibition operation is neither commutative nor associative.
(Hint) y/x = x'y, x/y = xy', and x'y xy' because these represent two different minterms of a function of two variables. Thus it is not commutative. Similarly, (z/y)/x = (y'z)/x = x'y'z z/(y/x) = z/(x'y) = (x'y)'z = (x+y')z = xz + y'z = x'y'z + xy'z + xyz. Hence it is not associative.

2-22 Show that a positive logic NAND gate is a negative logic NOR gate and vice versa.
(Hint) To change a positive-logic gate to a negative-logic gate is to complement all inputs and output of the gate at the same time. A positive-logic NAND gate implements the function (xy)'. Hence a negative-logic NAND gate implements ((x'y')')' = (x+y)', which is NOR function.

2-23 An integrated-circuit logic family has NAND gates with fan-out of 5 and buffer gates with fan-out of 10. Show how the output signal of a single NAND gate can bee applied to 50 other NAND-gate inputs without overloading the output gate. Use buffers to satisfy the fan-out requirements.
(Hint) Feed the output of the NAND gate to 5 buffer gates, and use the output of the buffer gates to feed other gates.

COSC 3410 Answers to Selected Problems, Chapter | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

visits since 2/18/98. RETURN to J. C. Huang's home page.

2-13 Express the complement of the following functions in sum of minters:	(a) F(A, B, C, D) = S(0, 2, 6, 11, 13, 14), F'(A, B, C, D) = S(1, 3, 4, 5, 7, 8, 9, 10, 12, 15). (b) F(x, y, z) = P(0, 3, 6, 7) = S(1, 2, 4, 5), F'(x, y, z) = S(0, 3, 6, 7).
2-14 Convert the following to the other canonical form:	(a) F(x, y, z) = S(1, 3, 7) = P(0, 2, 4, 5, 6) (b) F(A, B, C, D) = P(0, 1, 2, 3, 4, 6, 12) = S(5, 7, 8, 9, 10, 11, 13, 14, 15)
2-15 The sum of all the minterms of a Boolean function of n variables is equal to 1.	(a) Prove the above statement for n=3. a'b'c' + a'b'c + a'bc' + a'bc + ab'c' + ab'c + abc' + abc = a'b' + a'b + ab' + ab = a' + a = 1. (b) Suggest a general procedure for a general proof. (Hint) For n > 3. If E represents the sum of all minterms of a function of n variables, then the sum of all minterms of a function of n+1 variables will be E(z'+z), which is equal to 1. This is obviously so for n = 4. Use induction for any n > 4.
2-19 By substituting the Boolean expression equivalent of the binary operations as defined in Table 2-8, show the following:	(a) The inhibition operation is neither commutative nor associative. (Hint) y/x = x'y, x/y = xy', and x'y xy' because these represent two different minterms of a function of two variables. Thus it is not commutative. Similarly, (z/y)/x = (y'z)/x = x'y'z z/(y/x) = z/(x'y) = (x'y)'z = (x+y')z = xz + y'z = x'y'z + xy'z + xyz. Hence it is not associative.
2-22 Show that a positive logic NAND gate is a negative logic NOR gate and vice versa.	(Hint) To change a positive-logic gate to a negative-logic gate is to complement all inputs and output of the gate at the same time. A positive-logic NAND gate implements the function (xy)'. Hence a negative-logic NAND gate implements ((x'y')')' = (x+y)', which is NOR function.
2-23 An integrated-circuit logic family has NAND gates with fan-out of 5 and buffer gates with fan-out of 10. Show how the output signal of a single NAND gate can bee applied to 50 other NAND-gate inputs without overloading the output gate. Use buffers to satisfy the fan-out requirements.	(Hint) Feed the output of the NAND gate to 5 buffer gates, and use the output of the buffer gates to feed other gates.