Use the following convention for logic symbols: | (for disjunction), & (for conjunction), ~ (for negation), = (for implication), <= (for equivalence), E (for existential quantification, e.g., (E x, y) (loves(x, y))), and A (for universal quantification, e.g., (A x, y)(loves(x, y))). You may assume the normal order of operations as described in your text, but you may use parentheses to override this order or to make things more clear.
1. (20 pts) Problem 9.4 from the text (which we repeat here for those who do not have the text). For each pair of atomic sentences, give the most general unifier if it exists:
(a) P(A, B, B), P(x, y, z). (b) Q(y, G(A, B)), Q(G(x, x), y). (c) R(x,A,z) , R(B,y,z) (d) Older (Father(y), y), Older (Father(x), John). (e) Knows(Father(y),y), Knows(x,x).
2. (80 pts) Consider the following sentences:
John likes all kinds of food. Apples are food. Chicken is food. Anything anyone eats and isn’t killed by is food. If you are killed by something, you are not alive. Bill eats peanuts and is still alive. * Sue eats everything Bill eats.
(a) Translate these sentences into formulas in first-order logic. (b) Convert the formulas of part (a) into CNF (also called clausal form). (c) Prove that John likes peanuts using resolution. (d) Use resolution to answer the question, “What food does Sue eat?” (e) Use resolution to answer (d) if, instead of the axiom marked with an asterisk above, we had: If you don’t eat, you die. If you die, you are not alive. Bill is alive.
