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.

  1. Consider the Boolean expression

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

    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 := 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?