Part I: Translating English to first-order logic:
1. --- 5. are taken from Davis, pp. 92-93, Exercise 3.
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:

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.

11. --- 14., (and also 1. - 3. of part III) continue the family tree example discussed in class. The predicates parent, married, male, and female, are taken as primitive, with the following interpretations:
parent(x,y) is true iff x is the parent of y;
female(x) is true iff x is female;
male(x) is true iff x is male;
married(x,y) is true iff x is married to y.

You may also assume the following definitions:
(forall x,y) (child(x,y) <==> parent(y,x))
(forall x,y) (mother(x,y) <==> parent(x,y) & female(x))
(forall x,y) (father(x,y) <==> parent(x,y) & male(x))
(forall x,y) (sibling(x,y) <==> (exists z,w)(mother(z,x) & mother(z,y) & father(w,x) & father(w,y))) ( corrected 2-5-99)
(forall x,y) (brother(x,y) <==> sibling(x,y) & male(x))
(forall x,y) (sister(x,y) <==> sibling(x,y) & female(x))
(forall x,y) (aunt(x,y) <==> (exists(w) ((sister(x,w) & parent(w,y)) v (exists z)(married(x,z) & brother(z,w) & parent(w,y))))
(and similarly for uncle)

11. Define grandparent.

12. Define sister-in-law.

13. Define first cousin.

14. Define mth cousin n times removed.

Note that first cousins have grandparents in common; second cousins have great-grandparents in common; third cousins have great-great-grandparents in common and so on. If A and B are mth cousins and C is an n-times descendant of B, then A and C are mth cousins n times removed. For example, if A and B have great-grandparents in common, then A and B are second cousins. A's children are B's second cousins once removed; A's grandchildren are B's second cousins twice removed and so on.
Hint: 1. Define mth cousin first, then define mth cousin n times removed in terms of your definition of mth cousin. 2. Use recursive definitions for your definition of mth cousin, and for your definition of mth cousin n times removed.

Part II: Translating first-order logic into English

These problems are taken from Genesereth and Nilsson, p. 43

1. (forall x) Hesitates(x) ==> Lost(x)

2. ~ (exists x) Business(x) & Like(x, Showbusiness)

3. ~ (forall x) Glitters(x) ==> Gold(x)

4. (forall x) Glitters(x) ==> ~ Gold(x)

Which of 3. or 4. represents the well-known adage?

5. (exists x)(forall y) Loves(x,y)

6. (forall y)(exists x) Loves(x,y)

7. (exists y)(forall x) Loves(x,y)

8. (forall x)(exists y) Loves(x,y)

For each of 9. and 10., give an interpretation which makes the sentence true

9. ((exists x)P(x)) <==> Q(x)

10. (exists x)(P(x) <==> Q(x))

Part III: Inference in first-order logic (natural deduction)

1.-3. refer to the family tree example discussed in class. Assume the family tree of the British Royal Family. (For the purposes of this example, it is necessary only to know that Queen Elizabeth II and her husband Prince Philip are parents of Charles and Andrew; that Charles and Diana are parents of William and Harry; and that Andrew and Sarah are parents of Beatrice and Eugenie.)

1. From the assumptions above, and the definitions previously provided, prove that Philip is William's grandfather. (Assume that a grandfather is a male grandparent.)

2. From the assumptions above, and the definitions previously provided, prove that Beatrice and Harry are first cousins.

3. From the definitions previously provided, prove that first cousins have parents who are siblings.

4. From (forall x)(P(x) & Q(x)) prove (forall x)P(x) & (forall x)Q(x). Does the converse hold?

5. From (forall x)P(x) v (forall x)Q(x) prove (forall x)(P(x) v Q(x)). Does the converse hold?

6. From:
(forall x)(P(X) v Q(x))
(exists x) ~ Q(x) (corrected 2-5-99)
(forall x) (S(x) ==> ~P(x))
Prove: (exists x) ~S(x)

7. Davis, p. 93, Exercise 4 (both parts). They are given below, for those who haven't managed to get Davis's book yet.

Consider the following "proof" of sentence 4. (in part I) from 1. and 2. (in part I). Sam owns all books by Joyce (from 1.) and Barbara owns only books by Tolstoy (from 2.). Therefore, any book by Joyce is owned by Sam but not by Barbara. Therefore Sam owns some book that Barbara doesn't.

a. What background assumptions does this proof rely on? Express these as sentences in first-order logic.

b. Using natural deduction, give a proof of sentence 4. from 1., 2., and the additional assumptions in a.