Artificial Intelligence: Solution Set 2

Problem 1

A. If a child of a MAX node N attains the maximum possible value, then no further children of N need be expanded. If a child of a MIN node N attains the minimum possible value, then no further children of N need be expanded. Example: Suppose the maximum is 5.

                   N (MAX)
                  / \
                 /   \
                5  
Any further branches of N can be pruned.

B. One example is shown below. If no pruning takes place, then every child except the last of every AND node must evaluate to TRUE, and every child except the last of every OR node must evaluate to FALSE. Therefore the only possible trees with no pruning are the one shown and the one that is identical except that the very last leaf is TRUE.

Problem 2

A. Every color is either red or blue.

1. XB V XR
2. YB V YR
3. ZB V ZR
No two neighboring countries have the same color.
4. ~(XR & YR)
5. ~(XB & YB)
6. ~(YR & ZR)
7. ~(YB & ZB)

B. Express the fact that X and Z have the same color. 8. (XR & ZR) V (XB & ZB).

C. Using propositional resolution, prove (B) from (A).

Statements (1), (2), and (3) are already in CNF. The CNF equivalents of (4) through 7 are

4.  ~XR V ~YR
5.  ~XB V ~YB
6.  ~YR V ~ZR
7.  ~YB V ~ZB
The CNF equivalent of the negation of (8) is
8. ~XR V ~ZR
9. ~XB V ~ZB.
The resolution proof can then proceed as follows.
10. XR V ~YB (from 1 and 5)
11. XR V YR  (from 10 and 2)
12. XR V ~ZR (from 11 and 6)
13. XR V ZB  (from 12 and 3)
14. XR V ~XB (from 13 and 9)
15. XR V XR  (from 14 and 1)
16. XR       (from 15)
17. ~YR      (from 16 and 4)
18. YB       (from 17 and 2)
19. ~ZB      (from 18 and 7)
20. ZR       (from 19 and 3)
21. ~XR      (from 20 and 8)
22. null     (from 21 and 16)