ic
Section 8.3 Minimization
663
37. A multiplexor is a control circuit with 2
n
input lines (numbered 0 through 2
n
− 1), n selector lines, and
exactly one output line. The signal on the output line is to match the signal on one of the input lines; the
selector lines determine which of the input line signals will be propagated to the output line. Signals on
the n selector lines determine an n-bit binary number, which can range in value from 0 to 2
n
− 1; hence
the numeric value on the selector lines identifies exactly one input line. The arithmetic-logic unit of a computer processor contains circuits for various operations (addition, subtraction, comparison, and so forth),
and when an arithmetic or comparison operation is to be done, the ALU may activate all these circuit. A
multiplexor then picks out the one desired result.
a. Write a truth function for a multiplexor where n = 1; that is, there are 2 input lines, 1 selector line and,
of course, one output line.
b. Draw the logic network (as simple as possible).
38. A decoder is a control circuit with n input lines and 2
n
output lines (numbered 0 through 2
n
− 1). The pattern of n bits on the input lines represents a binary number between 0 and 2
n
− 1. A decoder activates the
output line with the corresponding identification number by putting a 1 output on that line and 0 outputs
on all other output lines. A decoder in a computer can, for example, read input lines that represent a binary
memory address and then activate the line to that memory cell for a read operation.
a. Write truth functions for a decoder where n = 2, that is, there are 2 input lines and 2
2
= 4 output lines
(hence four truth functions).
b. Draw the logic network that incorporates all four truth functions.
39. At the beginning of this chapter, you were
. . . hired by Rats R Us to build the control logic for the production facilities for a new anticancer
chemical compound being tested on rats. The control logic must manage the opening and closing
of two valves, A and B, downstream of the mixing vat. Valve A is to open whenever the pressure
in the vat exceeds 50 psi (pounds per square inch) and the salinity of the mixture exceeds 45 g/L
(grams per liter). Valve B is to open whenever valve A is closed and the temperature exceeds 53°C
and the acidity falls below 7.0 pH (lower pH values mean more acidity).
How many and what type of logic gates will be needed in the circuit?
Answer this question by finding the canonical sum-of-products form for the logic circuits to control A
and B.
S e c t i o n 8 . 3 MiniMiz ation
Minimization Process
Remember from Section 8.2 that a given truth function is associated with an
equivalence class of Boolean expressions. If we want to design a logic network
for the function, the ideal would be to have a procedure that chooses the simplest
Boolean expression from the class. What we consider simple will depend on the
technology employed in building the network, what kind of logic elements are
available, and so on. At any rate, we probably want to minimize the total number
of connections that must be made and the total number of logic elements used. (As
we discuss minimization procedures, keep in mind that other factors may influence the economics of the situation. If a network is to be built only once, the time
spent on minimization is costlier than building the network. But if the network
is to be mass-produced, then the cost of minimization time may be worthwhile.)
Section 8.3 Minimization
663
37. A multiplexor is a control circuit with 2
n
input lines (numbered 0 through 2
n
− 1), n selector lines, and
exactly one output line. The signal on the output line is to match the signal on one of the input lines; the
selector lines determine which of the input line signals will be propagated to the output line. Signals on
the n selector lines determine an n-bit binary number, which can range in value from 0 to 2
n
− 1; hence
the numeric value on the selector lines identifies exactly one input line. The arithmetic-logic unit of a computer processor contains circuits for various operations (addition, subtraction, comparison, and so forth),
and when an arithmetic or comparison operation is to be done, the ALU may activate all these circuit. A
multiplexor then picks out the one desired result.
a. Write a truth function for a multiplexor where n = 1; that is, there are 2 input lines, 1 selector line and,
of course, one output line.
b. Draw the logic network (as simple as possible).
38. A decoder is a control circuit with n input lines and 2
n
output lines (numbered 0 through 2
n
− 1). The pattern of n bits on the input lines represents a binary number between 0 and 2
n
− 1. A decoder activates the
output line with the corresponding identification number by putting a 1 output on that line and 0 outputs
on all other output lines. A decoder in a computer can, for example, read input lines that represent a binary
memory address and then activate the line to that memory cell for a read operation.
a. Write truth functions for a decoder where n = 2, that is, there are 2 input lines and 2
2
= 4 output lines
(hence four truth functions).
b. Draw the logic network that incorporates all four truth functions.
39. At the beginning of this chapter, you were
. . . hired by Rats R Us to build the control logic for the production facilities for a new anticancer
chemical compound being tested on rats. The control logic must manage the opening and closing
of two valves, A and B, downstream of the mixing vat. Valve A is to open whenever the pressure
in the vat exceeds 50 psi (pounds per square inch) and the salinity of the mixture exceeds 45 g/L
(grams per liter). Valve B is to open whenever valve A is closed and the temperature exceeds 53°C
and the acidity falls below 7.0 pH (lower pH values mean more acidity).
How many and what type of logic gates will be needed in the circuit?
Answer this question by finding the canonical sum-of-products form for the logic circuits to control A
and B.
S e c t i o n 8 . 3 MiniMiz ation
Minimization Process
Remember from Section 8.2 that a given truth function is associated with an
equivalence class of Boolean expressions. If we want to design a logic network
for the function, the ideal would be to have a procedure that chooses the simplest
Boolean expression from the class. What we consider simple will depend on the
technology employed in building the network, what kind of logic elements are
available, and so on. At any rate, we probably want to minimize the total number
of connections that must be made and the total number of logic elements used. (As
we discuss minimization procedures, keep in mind that other factors may influence the economics of the situation. If a network is to be built only once, the time
spent on minimization is costlier than building the network. But if the network
is to be mass-produced, then the cost of minimization time may be worthwhile.)