# 程序代写代做代考 Homework

Homework

CMSC 250 Spring 2017

Homework #2
Posted: 02-07-2017

Due: 02-14-2017

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:

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.

02-14-2017 – CMSC 250 3

02-14-2017 – CMSC 250 4

02-14-2017 – CMSC 250 5

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

2. How many AND gates are in a Full-Adder? How many OR gates are in a Full-Adder? How many NOT gates

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

02-14-2017 – CMSC 250 6

02-14-2017 – CMSC 250 7

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

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