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.
- 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)).
- 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.)
- 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.
- 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.)
- 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?
- 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?
- 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.)
- 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?