[SOLVED] CMSC 250 Homework #2

Problem (1): Middle bit Problem (40 points)

x1, x0, y1, y0 are bits. We will think of x1x0 and y1y0 as two 2-bit numbers. Let f (x1 , x0 , y1 , y0 ) = z2 z1 z0 , the binary representation of x1 x0 + y1 y0 .
For example f (0, 1, 1, 1) = 100.

1. Write the truth table for the function f. It will have four inputs and three outputs (note that the largest value is 11 + 11 = 110 (all in base 2)).
2. Look at the MIDDLE column (z1) . Write a formula that is 1 iff the middle column is 1 DO NOT SIMPLIFY. (HINT: first, for every row that makes the middle column 1, write a small formula that is 1 ONLY on that row.)
3. Draw a circuit that represents the MIDDLE column. You can only use AND, OR, and NOT gates. The AND and OR gates can have unbounded inputs, but only one output.
4. Though experiment: Imagine that you take the Truth Table for the 2-bit adder (that is, takes two 2-bit numbers and adds them) and use it to make a circuit (with 4 inputs and 3 outputs). Also imagine that (unlike the last problem) your AND and OR gates have only 2 inputs. (NOTE- A PRIOR VERSION HAD (with 2 inputs and 3 outputs) THAT WAS A TYPO.)

   How many AND gates would it have? How many OR gates would it have? How many NOT gates would it have?

   Do not simplify- just do it straightforwardly. Explain how you got these numbers.

   Problem (2): Half Adders and Full Adders (20 points)

   For this problem all AND, OR gates are 2-input and 1-output, all NOT gates are 1-input. (NOTE- the Half Adder in the Textbook uses 2-inputs 2-output gates. The one on the slides uses 2-input, 1-output gates. Hence use the one on the slides.)

   1. How many AND gates are in a Half-Adder? How many OR gates are in a Half-Adder? How many NOT gates are in a Half-Adder?
   2. How many AND gates are in a Full-Adder? How many OR gates are in a Full-Adder? How many NOT gates are in a Full-Adder?
   3. If you build a 2-bit adder from Half-adders and Full-adders (as we did in class) then How many AND gates are in the 2-bit Adder? How many OR gates are in the 2-bit Adder? How many NOT gates are in the 2-bit Adder? (For your thought, not to hand in- how does it compare to the 2-bit adder obtained via truth table in the last question.)
   4. If you build an n-bit adder from Half-adders and Full-adders (as we did in class) then how many AND gates are in the n-bit Adder? How many OR gates are in the n-bit Adder? How many NOT gates are in the n-bit Adder? (The answers are functions of n.)

      Problem (3): Notation for Sets of Numbers (15 points)

      1. Give an infinite number of elements x in Z that are NOT in N (this is often written x Z N).

      2. Give an infinite number of element x in Q that are NOT in N (this is often written x Q N).

      3. Give an infinite number of element x in R that are NOT in Q (this is often written x R Q).

      Problem (4): Domains (25 pts)
      For each of the following sentences do the following:

      Either find an infinite domain where the statement is true OR show that there is NO such domain. In either case explain your answer.

      Either find an infinite domain where the statement is false OR show that there is NO such domain. In either case explain your answer.

      Let BET (x, y) mean x < y (z)[x < z < y]. So we are saying that x < y and there is a z inBETween x and y. 1.

      2. 3. 4. 5.

      (x)(y)[x < y < 1]
      (x)(y)[x < y BET (x, y)] (x)(y)[x < y < 1 BET (x, y)] (x)(y)(z)[z = x + y]. (x)(y)(z)[z = x + y] (x)(y)(z)[z = xy]

      Problem (5): HONORS Problem (0 points) (Do not hand in.)

      The n-bit adder that we designed in class takes two n bit numbers and outputs the sum. The number of steps this computation takes is roughly n since the ith bit depends on the i 1st carry.

      Design a circuit that takes two n bit numbers and outputs the sum in roughly n/2 steps. (It might have a much bigger circuit.) Can you obtain an even faster circuit?