# 程序代写代做代考 Homework

Homework

(

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

) (

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:

)

(

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

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

)

) (

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

) (

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