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