CSC 173, Fall 2006
Assignment 6: Logic
Solve the following problems. In each case, explain your answer (i.e.,
show how you derived your answer). An answer without an explanation will
not be considered valid.

(20 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? Prove/explain your answer in each case.)

(10 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)).

(20 points)
Draw circuit diagrams for three different 2bit adders (adders that take
two 2bit inputs and compute a 2bit output and a carry bit): a
ripplecarry adder, a carrylookahead (divideandconquer adder), and a
sumofproducts (disjunctivenormalform, without trying to eliminate
any literals or terms) adder. For each of the
adders, give the total number of gates and the depth (the number of
gates on the longest path).

(Extra Credit: up to 15 points)
Determine, for each of the three classes of adders mentioned in the
previous questions, a general formula 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 bigO question: I'm looking for an exact answer.)

(15 points)
Minimize the following expression using a Karnaugh map
(i.e., remove as many literals and terms as
possible): (ABCD)(ABCD) (ABCD) (ABCD) (ABCD). Express the result in product of sums
notation. (Hint: You will want to directly generate the product of sums
notation from the Karnaugh map). Also, minimize the expression using
algebraic laws with the result in sum of products (as opposed to product
of sums) notation. Show that the two are equivalent (derive one
algebraically from the other).

(10 points)
Translate the following statements into prenex CNF form (all quantifiers
on the outside, insides written as a logical product of sums):

A[student(A) (dorm_resident(A) B[class(B) takes(A,B)])

AB [(C[takes(A,C) takes(B,C)]) classmates(A,B)]

(10 points)
Suppose big(N) is interpreted to mean N > 2 and works(A,B,C,N) is
interpreted to mean A^{N} + B^{N} = C^{N}.
State Fermat's last theorem
in predicate calculus, first in whatever form seems most intuitive, then
in prenex CNF. (Fermat's last theorem holds that the equation
A^{N} + B^{N}
= C^{N} has no solutions over the nonzero integers for N > 2. It was
posed around 1630, but wasn't solved [by Andrew Wiles] until 1995.)

(15 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: 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: In class, Thursday November 30.
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.
Back to the grading page
Back to the course home page
Last Change: 21 November 2006