MA-351 Homework 5
Due at 10:15am in class, Tuesday December 5, 2006
Solutions may be submitted in person in class or put in my mailbox,
or you may email an
ASCII text,
Html,
or postscipt/pdf-formatted document to me.
Note my office hours on my
schedule.
-
Consider the Boolean expression
(a implies b) and (b implies c) and b
where implies is implication: (not a) or b.
-
Using the truth table method discussed in class,
find the CNF (with k clauses, where k is to be
determinend) that is equivalent to this expression.
-
Draw the graph corresponding to the CNF that has
a clique of size k iff the CNF is satisfiable.
For a satisfying assignment, identify the clique.
-
For the Boolean straight-line program
s := (a or b); t := s and (not b); u := t and (not a)
find a CNF that is satsifiable iff there is a Boolean value
assignment for the input variables
a,b such the output variable u is true.
Is this CNF satisfiable?