CS 327: Artificial Intelligence

Assigned on Monday, 2/17.
Due on paper in class on Monday, 2/24.

Propositional Logic

On this webpage, '^' stands for AND, 'v' stands for OR, and '~' stands for NOT.

Problem 1: Resolution

Using the resolution algorithm, show that the following knowledge base entails S:

P ^ Q
P v Q => R
W => ~(~Z)
~R v W
S v Q
P ^ Z => S v ~R

Problem 2: Minesweeper

(This is a version of textbook problem 7.11)
Minesweeper, the well-known computer game, is closely related to the wumpus world. A minesweeper world is a rectangular grid of N squares with M invisible mines scattered among them. Any square may be probed by the agent; instant death follows if a mine is probed. Minesweeper indicates the presence of mines by revealing, in each probed square, the number of mines that are directly or diagonally adjacent. The goal is to have probed every unmined square. Minesweeper is installed on any Windows system. If you haven't played it before, give it a try.

(a) Let X_i,j be true if square [i,j] contains a mine. Write down the assertion that there are exactly two mines adjacent to [1,1] as a sentence involving some logical combination of X_i,j propositions.

(b) Write down the assertion that there are exactly five mines adjacent to [2,2] as a sentence involving some logical combination of X_i,j propositions. This can get somewhat long, so you do not to need to write down the entire answer. You should write enough of it with annotations to make the pattern clear.

(c) Explain precisely how an agent can use DPLL to try to prove that a given square contains a mine, ignoring the global constraint that there are M mines in total on the board.

(d) Instead of trying to incorporate the global constraint of M mines into your assertion, describe instead how the DPLL algorithm can be modified to take this into account.