MA-351 Homework 5

Due at 9:50am in class, Thursday December 2, 2004


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.

  1. DMM §3.6, Problem 13, page 168. Note that your coloring also needs to include the country "11" surrounding countries 1-10.
  2. Consider the Boolean expression

    (a implies b) and (b implies c) and (not a)

    where implies is implication: (not a) or b.
    1. 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.
    2. 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.
  3. For the Boolean straight-line program s := (a or b); t := (not a) and (not b); u := (s equiv t) 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?