CS 4804 Homework #3

1. (42 points) Encode the following statements in predicate logic using a consistent vocabulary (which you must define):
   • Every prime number other than 2 is odd.
   • Every even number greater than 2 can be expressed as the sum of two primes.
   • Fermat's last theorem: There does not exist non-zero integers "x", "y", and "z" such that x^k+y^k=z^k holds for k>=3.
   • Nobody knows all the troubles I had gotten myself into.
   • Nobody knows any of the troubles I had gotten myself into.
   • Everybody knows some trouble I had gotten myself into.
   • If there is somebody who knows all the troubles I had gotten myself into, then that somebody is God.
   
   
2. (18 points) Convert the following predicate logic statements into clause form (here FA indicates "Forall", "EX indicates there exists", "NEG" indicates negation, and "AND" indicates conjunction):
   • (FA x) (FA y) ((P(x) AND Q(y)) => (EX z) (R(x,y,z)))
   • (EX x) (FA y) (EX z) (P(x) => (Q(y) => R(z)))
   • (FA x) (P(x) => (EX y) (Q(x,y))) AND (FA x) (NEG P(x) => NEG (EX y) (Q(x,y)))
   
   
3. (20 points) Using predicate logic, from the statement: "the father of an elephant is an elephant", prove that "the father of the father of an elephant is an elephant". Define suitable predicates yourself; explain what they mean; encode the statements as clauses; and prove using resolution-refutation.
   
   
4. (20 points) "Island Paradise is inhabited by two tribes. Members of Tribe1 always tell the truth when asked a question. Members of Tribe2 always lie when asked a question. The correct answer to "Is today Sunday?" is "Yes". Person StraightFace says "Yes" when this question is posed." Prove that StraightFace belongs to Tribe1. Define suitable predicates yourself; explain what they mean; encode the statements as clauses; and prove using resolution-refutation.