# 程序代写代做代考 Homework

Homework

(
(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
) (
CMSC

250
Spring

2017
Homework

#2
Posted:

02-07-2017
Due:

02-14-2017
Student’s first and

last

name:

only):

Student’s

UID:

Student’s

Section:

University Honor

Pledge:
I
pledge on my honor that
I
have not given or
any

unauthorized

assistance

on

this

assignment/examination.
Print the text of the University Honor Pledge

below
:
Signature:

)

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

TO

PROBLEM

(1)

BELOW

THIS

LINE
)

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

YOUR

TO

PROBLEM

(1)

BELOW

THIS

LINE
)

(
02-14-2017 – CMSC 250
) (
5
) (
Problem (2): Half Adders and
Full
(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

TO

PROBLEM

(2)

BELOW

THIS

LINE
)

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

YOUR

TO

PROBLEM

(2)

BELOW

THIS

LINE
)

(
02-14-2017 – CMSC 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 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
) (
) (
Either find an infinite domain where the statement is false OR show that there is NO such domain.

In either
) (
) (
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 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 i th 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? )

Posted in Uncategorized