Homework
CMSC 250 Spring 2017
Homework #2
Posted: 02-07-2017
Due: 02-14-2017
Student’s first and last name: Grade (grader only):
Student’s UID:
Student’s Section:
University Honor Pledge:
I pledge on my honor that I have not given or received
any unauthorized assistance on this assignment/examination.
Print the text of the University Honor Pledge below:
Signature:
Problem (0): READINGS (0 points)
Read the Textbook Epp Chapter on Number Systems and Circuits for Addition (you can skip the 1’s-complement,
2’s-complement stuff) as well as the chapters on Quantifiers and Set Theory.
1
02-14-2017 – CMSC 250 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) = z2z1z0, the binary representation of x1x0 + y1y0.
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.
BEGIN YOUR ANSWER TO PROBLEM (1) BELOW THIS LINE
02-14-2017 – CMSC 250 3
CONTINUE YOUR ANSWER TO PROBLEM (1) BELOW THIS LINE
02-14-2017 – CMSC 250 4
CONTINUE YOUR ANSWER TO PROBLEM (1) BELOW THIS LINE
02-14-2017 – CMSC 250 5
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.)
BEGIN YOUR ANSWER TO PROBLEM (2) BELOW THIS LINE
02-14-2017 – CMSC 250 6
CONTINUE YOUR ANSWER TO PROBLEM (2) BELOW THIS LINE
02-14-2017 – CMSC 250 7
CONTINUE YOUR ANSWER TO PROBLEM (2) BELOW THIS LINE
02-14-2017 – CMSC 250 8
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).
BEGIN YOUR ANSWER TO PROBLEM (3) BELOW THIS LINE
02-14-2017 – CMSC 250 9
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. (∀x)(∃y)[x < y < 1] 2. (∀x)(∃y)[x < y ∧ ∼BET (x, y)] 3. (∀x)(∃y)[x < y < 1 ∧ ∼BET (x, y)] 4. (∀x)(∀y)(∃z)[z = x + y]. 5. (∀x)(∀y)(∃z)[z = x + y] ∧ (∃x)(∃y)(∀z)[z 6= xy] BEGIN YOUR ANSWER TO PROBLEM (4) BELOW THIS LINE 02-14-2017 – CMSC 250 10 CONTINUE YOUR ANSWER TO PROBLEM (4) BELOW THIS LINE 02-14-2017 – CMSC 250 11 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?