MA-351 Homework 5

Due at 9:50 in class, Tuesday December 3, 2002


Solutions may be submitted in person in class, or you may email an ASCII text, html, or postscipt/pdf-formatted document to me (kaltofen@math.ncsu.edu).
Note my office hours on my schedule.

  1. 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.
  2. 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?