PHIL 110 – Introduction to logic and reasoning Assignment 3 Distributed on Canvas: Wed. Jul. 27 Due at the beginning of class: Wed. Aug. 3 Value: 11.67% Please read carefully. This assignment is out of 45 points (+2 bonus points) and is worth 11.67% of your final mark. On separate paper, answer each of the following questions. You can type up or hand-write your work. If you write up your work by hand, please write clearly. You must submit a hard copy of your work at the beginning of class. Electronic submissions via email will not be accepted. Make sure to include your name, student ID, and tutorial number on the front page of your assignment. Failure to do so will result in a loss of marks. Note: It should be remembered that the assignments are not just assessment tests. They also have a pedagogical function, in that they’re designed to push you to look into things which you might not already have looked at sufficiently closely. Question about Language (10 pts.) Suppose we have an FOL with constants a, b, c, d, e, variables x, y, z, predicate symbols Px, Qx, Rxy, x = y, the regular connectives ¬, ∧,∨, →,↔, and the quantifiers ∀ and ∃. For each of the following, indicate whether they are simple terms, mere well-formed formulas (wffs), atomic sentences, complex (non-atomic) sentences, or none of these. a. ∀x((Rba ∧ Qec) → ∃y(y = x ↔ Pd)) None b. [∃x∃y(Px ∧ Rxa) ∧ Qx] Mere wff c. ∀a (Pa → Qa) None d. Rax Mere wff e. ∃z (Qz ∧ Rad) Complex sentence f. ∀x(Pa → Qa) Complex sentence g. e Simple term h. a = c atomic sentence i. (a = c ∧ b = c) Complex sentence j. ∀x∃x(Lx → Txx) None Translations (10 pts.) Consider the following symbolization key: UD: Everything Cxy: x cares for y Oxy: x owns y Px: x is a pet Sx: x is a student 2 1. (5 pts.) Translate the following English sentences in FOL: i. Some students have no pet. ∃x(Sx ∧ ∀y(Py → ¬Oxy)) ii. No student owns every pet. ∀x(Sx → ¬∀y(Py → Oxy)) iii. Some pets aren’t owned by any student. ∃x(Px ∧ ∀y(Sy → ¬Oyx) iv. Every student who owns a pet cares for it. ∀x(Px → ∀y((Sy ∧ Oyx) → Cyx)) v. Every pet is owned and cared for by some student. ∀x(Px → ∃y((Sy ∧ Oyx) ∧ Cyx)) 2. (5 pts.) Given the symbolization key above, translate the following FOL sentences in English: i. ∀x(Px → ∀y(Oyx → Cxy)) Every pet cares for each of their owners. ii. ∃x(Px ∧ ∃y(Oyx ∧ ¬Cyx)) Some pet isn’t cared for by their owner. iii. ∀y(Sy → ∀z(Pz → ¬Oyz)) No student owns any pet. iv. ∀x(Sx → ¬∀y(Py → Oxy)) No student owns every pet. v. ∃x(Px ∧ ∃y((Sy ∧ Oyx) ∧ ¬Cxy)) Some pet doesn’t care for some of their student owner. Explanation (5 pts.) Show that ∨E is sound in t. For the sake of contradiction, suppose that there is a proof p in t whose first invalid step derives the sentence P from an application of ∨E to sentences (P ∨ Q) and ¬Q. Let A1…Ak, (P ∨ Q), and ¬Q be the assumptions in force at step P. Since we’re assuming that this is the first invalid step, we’re assuming that P is not a tautological consequence of A1…Ak, (P ∨ Q), and ¬Q. Now consider the joint truth table for A1…Ak, (P ∨ Q), ¬Q, and P. Since we’re assuming that P is not a tautological consequence of A1…Ak, (P ∨ Q), and ¬Q, there must be