Problem Set 2

Assigned: Feb. 9.
Due: Feb. 23.

Problem 1

Show the results of applying alpha-beta pruning to the following game tree. What is the best move for MAX at the top level?

Problem 2

Convert the following sentences in the propositional logic to clausal form.
(B ^ C) => A
D => B^C
E <=> (~A V ~D)
(E ^ ~C) => (D^F).

Answer

1.  A V ~B V ~C.
2a. ~D V B
2b. ~D V C.
3a. ~E V ~A V ~D.
3b. A V E.
3c. D V E.
4a. ~E V C V D.
4b. ~E V C V F.

Problem 3

Trace the action of the Davis-Putnam algorithm applied to the clauses in problem 2. Assume that, when the algorithm encounters a branch point, it selects the first atom in alphabetical order, and that it tries "TRUE" before "FALSE".
F = TRUE (pure literal).  Delete 4b.
Try A=TRUE.
   Set S1:
     2a. ~D V B
     2b. ~D V C.
     3a. ~E V ~D.
     3c. D V E.
     4a. ~E V C V D.

B and C are pure literals.  Set B=TRUE, C=TRUE
     
     3a. ~E V ~D
     3c.  D V E.

   Try D=TRUE.
    Set S2:
      3a. ~E

      E is a pure literal. Set E=FALSE.  Succeed.

      Solution: A=TRUE, B=TRUE, C=TRUE, D=TRUE, E=FALSE, F=TRUE.