Problem Set Number 5
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.