MA-351 Homework 5

Due at 9:50 in class, Tuesday November 16, 1999


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 xor b) and (a xor c) and U(a,b,c)

    where xor is the exclusive-or operator and U(a,b,c) is ``exactly one'': (a or b or c) and ((not a) or (not b)) and ((not a) or (not c)) and ((not b) or (not c)).
    1. Find the CNF (with k clauses) 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 implies b); t := (a and s); u := (t and (not b)); find a CNF that is satsifiable iff there is a Boolean value assignment for the inputs a,b such the output u is true. Is this CNF satisfiable?