Computer Science 111

*Due by 5 PM, Friday March 3, 2000*

**1.** Exercise 13, page 166 of the text.
There are fancy ways to do this, but there is one
very simple way; try to find it.

**2.** Exercise 15, page 167. As usual, feel free to
use AND and OR gates that have more than two inputs.
Any correct solution will get full credit, but there
is a pretty solution that needs just four gates.

**3.** Exercise 19, page 167. Remember that the idea
of a multiplexor is to make the single output
equal to one of the inputs, according to the setting
of the selector wires. Again, gates
with more than two inputs are OK.

**extra credit:** We've seen that the set
of AND, OR, and NOT gates is *universal* in
the sense that we can build any Boolean logic
function using only those gates.
The NAND gate you designed in
question 1 is similarly universal. Prove this by
showing how to make AND, OR, and NOT gates using
only NANDs. Assume that you can use constant 0
and 1 inputs if you need them.