Problem Set 4
Assigned: Oct. 4
Due: Oct 11.
Trace the execution of the Davis-Putnam algorithm over the following set
of clauses. When the algorithm must "guess" at a binding, it should choose
the first unbound atom in alphabetical order, and should try TRUE before
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
Let U be a universe of people and classes. Let L be the first-order language
with the following symbols:
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.
- B. There is a class in which all the students have met one another.
- C. There is a class in which some of the students have not met one
- D. Everyone has met himself/herself (by definition).
- E. Amy has met all the students in Data Structures that Barney has.
- F. None of the students in English have met any of the students in
- G. All of the teachers of classes that Amy is taking have met one another.
- H. The only people that Barney has met and Amy hasn't are students