Problem 1: Short answers? Yes! (18 pts)

1.1

Draw a high-level diagram of a 4-input multiplexor. Be sure to include a function table and label all inputs and outputs clearly.

Answer: See notes for correct picture; circuit has four inputs: $I_0$, $I_1$, $I_2$, $I_3$. The proper output is determined by the (decimal) value of the two select inputs: $S_0$, $S_1$. The function table is given below:

$S_1$	$S_0$	output
0	0	$I_0$
0	1	$I_1$
1	0	$I_2$
1	1	$I_3$

1.2

Prove or Disprove: (P' or Q) (R or P') = (RQ or P')

Answer: True Proof: matching truth tables works. Or, use Boolean identities on the left hand side of the equation above to get:

$$(P'R\; {\rm or}\; P'\; {\rm or}\; P'Q \; {\rm or}\; RQ)\; = \... ...1 \; {\rm or} \; Q) \; {\rm or}\; RQ)\; = (P'\; {\rm or} \;RQ )$$

Remember, we have commutativity and associativity of or and and; also, the 'or' of 1 with anything else is 1.

1.3

Draw two different gate representations for the following logical expresssion (not ((not A) and B)).

Answer: The trick here is to us DeMorgan's law, which permits you to derive an equivalent expression: (A or (not B)). Thus, in one expression you can use one OR gate and one inverter. In the other, as originally written, you use an AND gate, and two inverters.

1.4

Write down the truth table for a four-output decoder, being sure to label your inputs and outputs appropriately. You need not draw the circuit. A four output decoder has two inputs, and will output a one in the output position corresponding to the decimal equivalent of the two-bit binary input. Note that a diagram of a 4 output decoder with enable would receive full credit, because it is a 4 output decoder.

$B_1$	$B_0$	$D_3$	$D_2$	$D_1$	$D_0$
0	0	0	0	0	1
0	1	0	0	1	0
1	0	0	1	0	0
1	1	1	0	0	0

1.5

Write expressions for the following quantities, being sure to justify your answer for full credit:

• the number of lines in a truth table for a combinational circuit having 6 inputs.

  Answer: Given 6 variables, each with two values, gives you $2^6$ rows.

• the number of of possible combinational circuits having 6 inputs and one (1) output. (Hint: to avoid double jeopardy, you may assume that V is the number of rows in a 6 input truth table.)

  Answer: You need the number of rows in the truth table to get this right; so, rather than make the two pieces coupled, you can use the variable V for the number of rows in the truth table, as we shall do here at first. We have V rows in the truth table and one output, call it W. There are two possible output values associated with each row of the truth table; this gives $2^{V}$ possible outputs, since V is the number of rows. Substituting from the first part gives us $2^{2^6}$ possible one output combinational circuits given 6 inputs.

1.6

Why are 2-input strict encoders rarely, if ever, produced for sale as ready-made combinational circuits? Explain your asnwer for full credit.

Answer: The easiest way to see this is to design the part. Since it is a strict encoder, exactly one bit in the input can be non-zero. The truth table is shown below:

$D_1$	$D_0$	W
0	1	0
1	0	1

A Boolean expression which satisfies this truth table is $W=D_1$, meaning that no gates are involved; the output merely corresponds to the value of input $D_1$, and anyone can connect that input directly to the output-no such part is ever needed.