CS475/575 Assignment #4.

Do the following exercises from the textbook.

1. Exercise 7.5 a,c
2. Exercise 7.8 c,g,h
3. Exercise 8.6 b,c,g
4. Exercise 9.4
5. Convert into CNF:
   • ((Exists x)P(x) v (Exists x)Q(x)) => (Exists x)(P(x) v Q(x))
6. Use resolution refutation to prove that the following formula is a tautology:
   [(ForAll x)(p(x)=>q(x))] => [{(ForAll x)p(x)} => {(ForAll x)q(x)}]
7. Exercise 9.19
8. Suppose that you wanted to describe the task of writing a program as a planning problem. Assignment statements of the form

   < variable1 > = < variable2 > ;

   might be represented by the following operator:

   assign-val(Var1, Var2):
   Preconditions: holds(Var1, Value1) & holds(Var2, Value2)
   Effects: holds(Var1, Value2) & ¬ holds(Var1, Value1)

   Suppose you have the following planning problem:

   Initial State: holds(v1, a) & holds(v2, b)
   Goal State: holds(v1, b) & holds(v2, a)

   You may assume that in addition to variables v1 and v2, another variable, v3, is also available for use.

   • Draw a partial-order plan that solves this problem using only the operator assign-val. (Of course you will need to use it more than once.) Be sure to make it clear in your diagram which arcs are of which types (causal or temporal). (Make sure that each step in your plan has all of its preconditions and effects listed, and all preconditions have causal links pointed to them).
   • Is your plan a total plan? How many linearizations does it have?