THE DIGITAL LOGIC LEVEL - Structured Computer Organization - page 238

3. A missionary lost in Southern California stops at a fork in the road. He knows that two
motorcycle gangs inhabit the area, one of which always tells the truth and one of which
always lies. He wants to know which road leads to Disneyland. What question should
he ask?
4. Use a truth table to show that X =( X AND Y ) OR ( X AND NOT Y ).
5. There exist four Boolean functions of a single variable and 16 functions of two vari-
ables. How many functions of three variables are there? Of n variables?
6. There exist four Boolean functions of a single variable and 16 functions of two vari-
ables. How many functions of four variables are there?

7. Show how the AND function can be constructed from two NAND gates.
8. Using the three-variable multiplexer chip of Fig. 3-12, implement a function whose
output is the parity of the inputs, that is, the output is 1 if and only if an even number
of inputs are 1.
9. Put on your thinking cap. The three-variable multiplexer chip of Fig. 3-12 is actually
capable of computing an arbitrary function of four Boolean variables. Describe how,
and as an example, draw the logic diagram for the function that is 0 if the English word
for the truth-table row has an even number of letters, 1 if it has an odd number of let-
ters (e.g., 0000 = zero = four letters → 0; 0111 = seven = five letters → 1; 1101 = thir-

0). Hint : If we call the fourth input variable D , the eight input
lines may be wired to V cc , ground, D ,or D .
10. Draw the logic diagram of a 2-bit encoder, a circuit with four input lines, exactly one
of which is high at any instant, and two output lines whose 2-bit binary value tells
which input is high.
11. Draw the logic diagram of a 2-bit demultiplexer, a circuit whose single input line is
steered to one of the four output lines depending on the state of the two control lines.
12. What does this circuit do?

teen = eight letters →

A
B

C

D

13. A common chip is a 4-bit adder. Four of these chips can be hooked up to form a 16-bit
adder. How many pins would you expect the 4-bit adder chip to have? Why?
14. An n -bit adder can be constructed by cascading n full adders in series, with the carry
into stage i , C i , coming from the output of stage i 1. The carry into stage 0, C 0 ,is0.

If each stage takes T nsec to produce its sum and carry, the carry into stage i will not be
valid until iT nsec after the start of the addition. For large n the time required for the

−