CSC 173, Fall 2001
Assignment 6: Logic
Solve the following problems:
-
(30 points)
Draw a truth table that shows all 16 Boolean functions of 2 variables, A
and B. Label the columns with their common names. You know most of
these:
,
,
(exclusive or),
,
,
,
NAND,
NOR,
true,
false,
A,
B,
A,
B.
What are the other two?
Which of the functions are commutative? Which are associative?
Which are complete? (You know that NAND and NOR are
complete; are any of the others?)
-
(20 points)
Prove the generalized DeMorgan's laws (equations 12.20(c) and 12.20(d)
in the book, p. 677) by
induction on k, using the basic laws (equations 12.20(a) and 12.20(b)).
-
(30 points) Draw circuit diagrams for three different 4-bit adders
(adders that take two 4-bit inputs and compute a 4-bit output and a
carry bit): a ripple-carry adder, divide-and-conquer adder (like we
did in class, and as is discussed in the book) and a product-of-sums
(conjunctive-normal-form) adder. For each of the adders, give the
total number of gates and the depth (the number of gates on the
longest path).
ATTENTION::: It is not necessary to
answer all of the above question. You still must create circuit
diagrams for 4 bit ripple carry and carry-look-ahead, but you DO NOT
need to do a 4 bit product-of-sums adder. Instead, draw a circuit
diagram for a 2 bit product-of-sums adder, and answer the following
question: How many gate would you have in a 4 bit adder? Hopefully
after answering this question you will understand why the question
has been modified. You must still answer the second part of the
question. Note, if you have already completed the assignment with a
4 bit product-of-sums adder, simply make a note that you finished
the assignment before it was modified. You can still receive full
credit.
-
(Extra Credit: up to 15 points)
Determine, for each of the three classes of adders mentioned in the
previous questions, a general forumla for the total number of gates and
the depth, as a function of the number of bits N in each operand.
(This is not a big-O question: I'm looking for an exact answer.)
-
(20 points)
Prove the following by contradiction, using resolution. (Restate the
premises and the negation of the conclusion in CNF to create a database
[set] of terms, then apply resolution to obtain new terms, until you
derive the empty term [false].)
Premise one: (A B) (C D).
Premise two:
(A B).
Conclusion: C
D.
-
(Extra Credit: up to 10 points)
Prove that it is impossible to write a program that takes two arbitrary
programs as input and tells you whether they do the same thing (i.e.
whether given the same input they either both halt, with the same
output, or both run forever.) You may take as a given that the halting
problem is undecidable.
DUE DATE: 4:30pm, Friday December 13.
NO EXTENSIONS.
What/how to turn in
Bring hard-copy answers to Marty's Guenther's office (CBS 735).
There will be a box labeled 173 assignments.
Be sure to explain your answers.
In accordance with course policy,
you are permitted to discuss the
exercises with your peers, look things up in books, etc., but you
must actually write the answers yourself, in your own words, out of your
own head: no copying.