Problem 5 (Validity and Entailment) A. Show that (a) is not valid, while (b) and (c) are valid. In each case, carefully justify your answer (based only on the semantics of the symbols involved, i.e., without syntactically trans- forming the formulas). a. Entity(A) b. 3x.x-God c.yx.(A#A) P(x) d. Though (b) is valid, why doesn't it establish the actual existence of a God (as various religions might interpret this term)? B. Which of the following entailments hold? Again justify your answers as above. b.(PA),-(A-B)) -P(B)? c. Vx -P(x) - P(A) P(B)? d. (grads only) Vmo_3x0 This means we can't provide axioms that will allow us to prove any equality between lambda-expressions (and hence between S-expressions) that is true (i.e., the expressions denote the same function a fact established by Alonzo Church (e.g., see http://www.joachim-breitner.de/various/ChurchTalk2011.pdf) and related to Gdel's first incompleteness theorem, the undecidability (semidecidability) of logic, and the halting problem for Turing machines 4 Problem 5 (Validity and Entailment) A. Show that (a) is not valid, while (b) and (c) are valid. In each case, carefully justify your answer (based only on the semantics of the symbols involved, i.e., without syntactically trans- forming the formulas). a. Entity(A) b. 3x.x-God c.yx.(A#A) P(x) d. Though (b) is valid, why doesn't it establish the actual existence of a God (as various religions might interpret this term)? B. Which of the following entailments hold? Again justify your answers as above. b.(PA),-(A-B)) -P(B)? c. Vx -P(x) - P(A) P(B)? d. (grads only) Vmo_3x0 This means we can't provide axioms that will allow us to prove any equality between lambda-expressions (and hence between S-expressions) that is true (i.e., the expressions denote the same function a fact established by Alonzo Church (e.g., see http://www.joachim-breitner.de/various/ChurchTalk2011.pdf) and related to Gdel's first incompleteness theorem, the undecidability (semidecidability) of logic, and the halting problem for Turing machines 4