MA-351 Homework 5

Due at 9:50 in class, Tuesday December 4, 2001


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 equiv b) and (a equiv c) and XOR(a,b,c)

    where equiv is the equivalence operator and XOR(a,b,c) is ``parity'': (a xor b) xor c, where xor is the exclusive-or of two Boolean values.
    1. Find the CNF (with k clauses, where k is to be determinend) 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 input variables a,b such the output variable u is true. Is this CNF satisfiable?