EECS 391/491 PS#6 FAQ

EECS 391/491: PROBLEM SET #6 FAQ

Overall

There is no need to typeset any problem this time.

Problem 6.2

For example, the sentence "A or B" can be determined to be true if only A is known to be true and B is unknown.

Problem 6.3 (7.5 of R&N)

This question is asking you to compute the number of possible worlds (aka models) in which each of the sentences are true. (See the first two sentences of paragraph 3 on page 201 of R&N.)

Problem 6.4 (7.7 of R&N)

You can verify these with a truth table. "De Morgan follows from De Morgan" is unacceptable.

Problem 6.6 (7.11 of R&N)

If you've never played the game before, there are numerous on-line versions. I found a nice one at

http://gameswizard.com/j_jvmine.html

(a) As an example, the assertion that there are exactly three mines adjacent to [1,1] would be

X_1,2 ^ X_2,2 ^ X_2,1

Note that cells in this world are numbered from 1, so that [1,1] is the lower left corner cell. Specifically, there is no [0,0] cell.

(b) You are to do this for a general cell (not just [1,1]). However, you can use words or symbols to represent the formula implicitly rather than explicitly.

To understand the difference between implicit and explicit, examine the following example from C++. An explicit definition of an array is
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
An implicit definition of the same array is
for (i=0; i<10; i++) {
  a[i] = i+1;
}
Implicit mathematical definitions of the same array are as follows:
1, 2, ..., 10                            // symbols
The integers between 1 and 10, inclusive // verbally

(f) This might be a little hard, even if you've played Minesweeper before. Here's a hint (though it's not an Nx1 board):

12221  COULD BE  12221  OR  12221
*****            X-XX-      -XX-X

where * denotes "don't know," X denotes a bomb, and - denotes no bomb.

Problem 6.7 (7.13 of R&N)

Equation (7.4) is on page 228 and Equation (7.5) is on page 229. In general, the numbered Equation (X.Y), like the numbered Figure X.Z, appear consecutively in Chapter X.

Problem 6.8 (7.17 of R&N)

The DPLL algorithm is described on pp. 221-222 of R&N. The first step is conversion to CNF.

Problem 6.9

I do not intend to post this code. Merely typing it in will help you to learn the alogorithm. (Also, this is more fair to students not using C++.) However, that is not to say one can't use cut-and-paste plus a little editiing to drastically speed up the process. ...