[SOLVED] Homework

Homework

(
Problem (0): READINGS
(0 points)
Read the Textbook Epp Chapter on
Number Systems and Circuits for Addition
(you can skip the 1s-complement, 2s-complement stuff) as well as the chapters on
Quantifiers
and
Set Theory
.
) (
1
) (
CMSC

250
Spring

2017
Homework

#2
Posted:

02-07-2017
Due:

02-14-2017
Students first and

last

name:

Grade

(grader

only):

Students

UID:

Students

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:

)

(
02-14-2017CMSC 250
) (
2
) (
Problem (1):Middle bit Problem
(40

points)
) (
x
1
, x
0
, y
1
, y
0
are bits. We will think of
x
1
x
0
and
y
1
y
0
as two 2-bit numbers.
Let

f

(
x
1
,

x
0
,

y
1
,

y
0
)

=

z
2
z
1
z
0
,

the

binary

representation

of

x
1
x
0

+

y
1
y
0
.
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 (
z
1
) . 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 oneoutput.
) (
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 and3outputs)
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 THISLINE
)

(
02-14-2017CMSC 250
) (
3
) (
CONTINUE

YOUR

ANSWER

TO

PROBLEM

(1)

BELOW

THIS

LINE
)

(
02-14-2017CMSC 250
) (
4
) (
CONTINUE

YOUR

ANSWER

TO

PROBLEM

(1)

BELOW

THIS

LINE
)

(
02-14-2017CMSC 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 THISLINE
)

(
02-14-2017CMSC 250
) (
6
) (
CONTINUE

YOUR

ANSWER

TO

PROBLEM

(2)

BELOW

THIS

LINE
)

(
02-14-2017CMSC 250
) (
7
) (
CONTINUE

YOUR

ANSWER

TO

PROBLEM

(2)

BELOW

THIS

LINE
)

(
02-14-2017CMSC 250
) (
8
) (
Problem (3):Notation for Sets of Numbers
(15 points
)
) (
Give an infinite number of elements
x
in
Z
that are NOT in
N
(this is often written
x

Z

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

Q

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

(
02-14-2017CMSC 250
) (
9
) (
Problem (4):Domains
(25pts)
) (
For each of the following sentences do thefollowing:
) (
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 /= xy]) (BEGIN YOUR ANSWER TO PROBLEM (4) BELOW THISLINE) (02-14-2017CMSC 250) (10) (CONTINUE YOUR ANSWER TO PROBLEM (4) BELOW THIS LINE) (02-14-2017CMSC 250) (11) (Problem (5):HONORS Problem (0points)(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 stepsthis 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?)