Homework assignment 6
CSCI 3650
Summer 2001

Due: Monday, June 18
  1. Page 946 problem 36.4-5. (Disjunctive normal form uses a definition where a formula is a disjunction of clauses, and each clause is a conjunction of literals. Just think about how you might decide whether a disjunctive normal form formula is satisfiable.)

  2. Page 946 problem 36.4-6. (Here, you have a black box that only gives yes or no answers. It tells you whether any given formula is satisfiable. Show how to use the box to get a satisfying assignment of values to the variables for any given satisfiable formula. You will want to ask many questions. Be sure that your algorithm runs in polynomial time, assuming that the black box answers questions in one unit of time.)

  3. Page 961 problem 36.5-6.

  4. Page 962 Problem 36-2.