Homework 6

Due in class, 15 March, 2012
  1. Chapter 13, Problem 9 on page 324
  2. Use the method on page 315 to convert the formula

    (x1 or x2) and ((not x1) or x2) and (x1 or (not x2))

    to a linear program. Ignore the integer constraint and find a cost function that will make the simplex algorithm find the satisfying assignment. What other solutions might be found by other cost functions?
  3. Now add the clause ((not x1) or (not x2)) and explore what happens.