Due: Oct 11.

1. P V ~Q V R

2. P V R V X

3. ~P V ~R V W

4. ~P V Q V ~W

5. ~P V Q V W

6. ~Q V X

7. ~Q V ~X V Y

8. ~Q V ~Y

** Answer: **

Initial set of clauses S0: 1. P V ~Q V R

2. P V R V X

3. ~P V ~R V W

4. ~P V Q V ~W

5. ~P V Q V W

6. ~Q V X

7. ~Q V ~X V Y

8. ~Q V ~Y Initial valuation V0: All atoms unbound. Call 1. dp1(ATOMS,S0,V0) No singleton clauses, no pure literals Try V[P]=TRUE. Propagate: Delete clauses 1, 2, delete ~P from 3,4,5 Set S1: 3. ~R V W

4. Q V ~W

5. Q V W

6. ~Q V X

7. ~Q V ~X V Y

8. ~Q V ~Y V1: V[P]=TRUE. Call 2. dp1(ATOMS,S1,V1) ~R is a pure literal. Set V[R]=FALSE. Delete 3. 4. Q V ~W

5. Q V W

6. ~Q V X

7. ~Q V ~X V Y

8. ~Q V ~Y No singleton clauses, no pure literals. Try V[Q]=TRUE. Propagate: Delete 4, 5, delete ~Q from 6,7,8. Set S2: 6. X

7. ~X V Y

8. ~Y V2: V[P]=TRUE, V[Q]=TRUE, V[R]=FALSE. Call 3. dp1(ATOMS,S2,V2) 6 is a singleton clause. Set V[X]=TRUE. Delete 6, delete ~X from 7 7. Y 8. ~Y. 7 is a singleton clause. Set V[Y]=TRUE. Delete 7, delete ~Y from 8. 8 is the empty clause. Fail call 3. Return to call 2. In call 2: try V[Q]=FALSE. Delete 6,7,8. Delete Q from 4,5. Set S3: 4. ~W. 5. W. V3: V[P]=TRUE, V[Q]=FALSE, V[R]=FALSE. Call 4. dp1(ATOMS,S3,V3) 4 is a singleton clause. Set V[W]=FALSE. Delete W from 5. 5 is the empty clause. Fail call 4. Return to call 2 Fail call 2. Return to call 1 Try V[P] = FALSE. Propagate. Delete 3, 4, 5, delete P from 1, 2. Set S5: 1. ~Q V R

2. R V X

6. ~Q V X

7. ~Q V ~X V Y

8. ~Q V ~Y Valuation V5: V[P]=FALSE. ~Q is a pure literal. Set V[Q]=FALSE. Delete 1,6,7,8. 2. R V X R is a pure literal. Set V[R]=TRUE. Delete 2. No clauses return. Succeed! Return valuation V[P]=TRUE, V[Q]=FALSE, V[R]=TRUE. V[W], V[X], and V[Y] may be assigned arbitrarily.

m(P,Q) --- Person P has met person Q.Express the following statements in L:

s(P,C) --- Person P is a student in class C.

t(P,C) --- Person P is the teacher of class C.

a,b --- Constants naming people Amy, and Barney .

d,e,f --- Constants naming classes Data Structures, English, French.

- A. Amy has not met the teacher of the English class.

**Answer**Either forall(P) t(P,e) => ~m(a,P)

or exists(P) t(P,e) ^ ~m(a,P)

is correct, as "the teacher of the English class" is presumably unique. - B. There is a class in which all the students have met one another.

**Answer**exists(C) forall(P1,P2) s(P1,C) ^ s(P2,C) => m(P1,P2). - C. There is a class in which some of the students have not met one
another.

**Answer**exists(C,P1,P2) s(P1,C) ^ s(P2,C) ^ ~m(P1,P2). - D. Everyone has met himself/herself (by definition).

**Answer**forall(P) m(P,P).

(Note: This is a little problematic since it implies that every class has met itself. If you assume that every class has at least one student, then this problem can be fixed as follows:

forall(X) [~exists(P) s(P,X)] => m(P,P).

i.e. everything that doesn't have students enrolled in it has met itself. Since the only entities are people and classes, this means that every person has met him/herself.) - E. Amy has met all the students in Data Structures that Barney has.

**Answer**forall(P) s(P,d) ^ m(b,P) => m(a,P). - F. None of the students in English have met any of the students in
French.

**Answer**~[exists(P1,P2) s(P1,e) ^ s(P2,f) ^ m(P1,P2)]. - G. All of the teachers of classes that Amy is taking have met one another.

**Answer**forall(P1,P2,C1,C2) s(a,C1) ^ s(a,C2) ^ t(P1,C1) ^ t(P2,C2) => m(P1,P2). - H. The only people that Barney has met and Amy hasn't are students
in English.

**Answer:**forall(P) m(b,P) ^ ~m(a,P) => s(P,e).