Some solutions for Assignment 5 paper-and-pencil exercises.
 -- S. Tanimoto


Chapter 6 problems:
10. The problem about the maid and the butler.

(a)
MSJ: The maid stole the jewelry
BG: The butler was guilty
MMC: The maid milked the cows
BGC: The butler got his cream


MSJ -> ~ BG
MSJ V MMC
MMC -> BGC
BG -> BGC

(b)
~(BG -> BGC)
~(~BG V BGC)
BG ^ ~BGC
Two clauses:  BG, ~BGC

(c)
Premises and negation of conclusion, in clause form:
P1: ~MSJ V ~BG
P2: MSJ V MMC
P3: ~MMC V BGC
P4: BG
P5: ~BGC

Proof:
P6: P1 & P4: ~MSJ
P7: P2 & P6: MMC
P8: P3 & P7: BGC
P9: P5 & P8: []
 QED

13.
(a) { b/x, a/y }
(b) not unifiable
(c) { g(z)/y, f(g(z))/x }
(d) not unifiable
(e) not unifiable

14. 
The premises:
Forall x S(x) -> L(x)
~(exists x)(~S(x))
Conclusion:
Forall x L(x)

In clause form:
P1: ~S(x) V L(x)
P2: S(x)

Neg. of conclusion
(exists x) ~L(x)
In clause form:
P3:  ~L(a)
 Here the symbol a is a skolem constant.

Resolution:
P4: P1 & P2 with unifier { }: L(x)
P5: P3 & P4 with unifier { a/x }: []
 QED

15. 
P1: (Forall x) (H(x) ^ K(x)) -> M(x)
P2: (Forall y) C(y) -> H(y)
P3: (Forall z) C(z) -> K(z)
C: (Forall w) C(w) -> M(w)

Negation of conclusion:
~((Forall w) C(w) -> M(w))

Clause form:
P1: ~H(x) V ~K(x) V M(x)
P2: ~C(y) V H(y)
P3: ~C(z) V K(z)

~C: Exists w ~(C(w) -> M(w))
    Exists w ~(~C(w) V M(w))
    Exists w C(w) ^ ~M(w)
    C(a) ^ ~M(a)
P4: C(a)
P5: ~M(a)

Proof:
P6: P1 & P2 with unifier { y/x }: ~C(y) V ~K(y) V M(y)
P7: P4 & P6 with unifier { a/y }: ~K(a) V M(a)
P8: P5 & P7 with unifier { }: ~K(a)
P9: P3 & P8 with unifier { a/z }: ~C(a)
P10: P4 & P9 with unifier { }: []
 QED

Chapter 5, problem 2.

(a) There are four distinct pieces, and each piece has no symmetries.
Therefore all four rotations of pieces by multiples of 90 degrees will
lead to distinct orientations.
  Let's give counts for the number of states involving 0 pieces, 1 piece,
2 pieces, 3 pieces and 4 pieces.

0 pieces: There is only one state, corresponding to the empty board.
1 piece: There are 4 places to put the piece, 4 pieces to choose from,
 and 4 orientations, or 64 different states.
2 pieces: There are 4 places to put the first piece and 4 pieces to
choose from as well as 4 orientations for that piece.  Then there
are 3 remaining places to put the second piece and 3 pieces to choose
from with 4 different orientations.  This seems to be 64 * 36 states, but
we have actually counted each one twice, since there should be no
distinction between the first and second pieces placed. So the
actual number of 2-piece states is 64 * 18 = 1152.
3 pieces: There are 4 ways to choose the empty square, then 
4 * 4 possibilities to select and orient the first piece, and then
3 * 4 ways to select and orient the second piece, and then
2 * 4 ways to select and orient the third piece. 
4 * 4 * 4 * 3 * 4 * 2 * 4 = 6144.
4 pieces:  There are no squares to leave blank.  We have
4! ways to order the pieces and 4 orientations for each of
4! * 4^4 or 24 * 256 = 6144.
The total number of states is therefore:
1 + 1152 + 6144 + 6144 = 13441.

(b)
This is the maximum number of states.
If all four squares are identical and have only one pattern (e.g.,
dots) on all four sides, then the choices of pieces and the orientations
become irrelevant.  The only way left to differentiate states are
according to which places are taken on the board.  The numbers of
possibilities for 0 pieces, 1 piece, etc. are:
1, 4, 6, 4, 1 for a total of 16 states.

(c) Allowing flipping will increase the number of orientations
from 4 to 8.  This results in a number of states equal to

1 + 128 + 4608 + 12288 + 98308 = 115329

(d)
 Here are the quadraminos and the number of distinct orientations
for each one.  The total number of distinct boards is then 19.
This increases the number of states by a factor of 19
for a total of 2,191,251.

             x  x
 xxxx  xxx  xx  xx  xx
       x    x   x   xx

  Q1   Q2   Q3  Q4  Q5

  2    8    4   4   1

3. The maximum distance is 4.  There is one link in the path
for each piece placement.  To compute the shortest path, we
consider only correct placements.