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 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-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 THISLINE
)
(
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 THISLINE
)
(
02-14-2017–CMSC 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-2017–CMSC 250) (10) (CONTINUE YOUR ANSWER TO PROBLEM (4) BELOW THIS LINE) (02-14-2017–CMSC 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?)
Reviews
There are no reviews yet.