# Homework Two

1: The three wise men puzzle is as follows:

A certain king wishes to test his three wise men. He arranges them in a circle so that they can see and hear each other and tells them that he will put a white or black spot on each of their foreheads but that at least one spot will be white. In fact all three spots are white. He then repeatedly asks them, ``Do you know the color of your spot?'' What do they answer?

The solution is that they answer, ``No,'' the first two times the question is asked and answer ``Yes'' thereafter.

This is a variant form of the puzzle. The traditional form is:

A certain king wishes to determine which of his three wise men is the wisest. He arranges them in a circle so that they can see and hear each other and tells them that he will put a white or black spot on each of their foreheads but that at least one spot will be white. In fact all three spots are white. He then offers his favor to the one who will first tell him the color of his spot. After a while, the wisest announces that his spot his white. How does he know?

The intended solution is that the wisest reasons that if his spot were black, the second would see a black and a white and would reason that if his spot were black, the third would have seen two black spots and reasoned from the king's announcement that his spot was white. This traditional version requires the wise men to reason about how fast their colleagues reason, and we don't wish to try to formalize this.

Axiomatize this in first order logic using an accessibility relation R(w,w',m,t) which says that at world w, the wise man m considers the world w' possible at time t. Use disjoint sorts for people, natural numbers (for times), colors, and worlds.

Your solution should imply that the third wise man know the color of his spot it white at time 3. (or 2 if you start from 0)

Hint: McCarthy's solution

2: Axiomatize the following in a SNARK theory

Tony, Mike and John belong to the Alpine Club. Every memeber of the club who is not a skier is a mountain climber. Mountain climbers do not like rain, and anyone who does not like snow is not a skier. Mike dislikes whatever Tony likes, and likes whatever Tony dislikes. Tont likes rain and snow.

Prove there is a memeber of the Alpine club who is a mountain climber but not a skier.

3: Suppose we have a dinner party with n married couples. According to social customs, husbands may not sit next to, nor opposite their wives. Show that we must have four couples for an acceptable party. That is, show that less than four couples implies that a social convention is broken.

Consider a domain consisting of people, books, and copies of books (volumes). Let L be a sorted first-order language with "person", "book", and "volume" as sorts, and with the following nonlogical symbols:

Constants: Sam, Barbara, Tolstoy, Joyce Predicates: Owns(p,v): Person p owns volume v Author(p,b): Person p wrote book b Copy(v,b): Volume v is a copy of book B.

Express each of the following as a sentence in L: Put this in a SNARK theory.

1. Sam owns a copy of every book that is either by Tolstoy or Joyce.

2. All the volumes that Barbara owns are copies of books by Tolstoy.

3. If Barbara owns a copy of a book, then Sam owns a copy of the same book.

4. There is some book that Sam owns but Barbara doesn't.

5. Every author owns a copy of each of his own books.

For 6. --- 9. , define your own vocabulary (functions, predicates, etc.)

6. Only one person is a vegetarian.

7. No person is acquainted with all vegetarians.

8. The best score in History is better than the best score in Biology.

9. Nobody except amateur bakers owns bread machines.

10. All Swiss speak the same languages.

T Costello