Phil 455: Homework 7 (on Syntax and Semantics of Logical Systems)

This homework won’t be due until the end of the day on Friday. Communicate with me if you need assistance or more time to complete the homework.

Symbolize in predicate logic with identity ("="): (a) Andy loves Beverly, but she loves someone else. (b) Alice loves no one other than Beverly.
Symbolize this, using predicate logic with identity and “functors” (function symbols): If the father of a person is friends with each of the father’s co-workers, then that person’s mother has at least two sisters.
Suppose we have a logical system with sentence constants like P, Q, and R, and logical operators like ⊃ and ¬. We also have variables φ and ψ in our metalanguage, that can stand in for arbitrary simple or complex sentences. Is (φ ⊃ ψ) ⊃ (¬φ ⊃ ¬ψ) a tautology? Explain your answer. (Hint: this question may be less straightforward than you first think.)
If φ is the formula Fx ⊃ ∀y(Gyx ∨ P ∨ ∃xHx), then (a) What is φ[x ← w]? (b) What is φ[x ← y]? (c) What is φ[P ← ∀xGxy]? (Hint: variables that occur free in the terms being substituted in should still be free after the substitution.)
Explain the difference between ⟦φ[x ← a]⟧_{𝓜 q} and ⟦φ⟧_{𝓜 q[x:=a]}.
Show it to be false that: If ⊨ φ ∨ ψ then ⊨ φ or ⊨ ψ.
Here is a sample demonstration that P ⊃ (Q ⊃ P) is logically valid, that is, that it’ll be true given any interpretation of the sentence constants:

Assume for reductio that some interpretation makes the whole sentence false. Then by the semantic rule for ⊃, the interpretation must make P true and Q ⊃ P false. But to achieve the latter, again by the rule for ⊃, it must make Q true and P false. But no interpretation can make P both true and false. So our assumption fails: there must be no interpretation that makes the whole sentence false.

Show that these others are also logically valid:
1. (P ⊃ Q) ∨ (Q ⊃ P)
2. P ∨ (P ⊃ Q)
3. ((P ⊃ Q) ⊃ P) ⊃ P
Here is a sample demonstration that P ∨ Q and (P ⊃ Q) ⊃ Q are semantically/logically equivalent, that is, that they’ll have the same truth-value on any interpretation:

Assume for reductio that some interpretation gives these sentences different truth-values. Either (i) it makes P ∨ Q false or (ii) it makes P ∨ Q true. In case (i), by the rule for ∨ the interpretation must make both P and Q false; but then by the rule for ⊃ it must make P ⊃ Q true, giving (P ⊃ Q) ⊃ Q a true antecedent and false consequent, thus making it false. This is contrary to our assumption that the interpretation gives (P ⊃ Q) ⊃ Q a different truth-value than P ∨ Q. In case (ii), for the interpretation to make (P ⊃ Q) ⊃ Q false, it must make P ⊃ Q true and Q false, but then it can only do the former by making P false along with Q. But then it cannot make P ∨ Q true as claimed in the description of case (ii). So our assumption fails: there must be no interpretation that gives these sentences different truth-values.

Show that these others are also logically equivalent:
1. P ⊃ (Q ∨ R) versus (P ⊃ Q) ∨ (P ⊃ R)
2. (Q ∨ R) ⊃ P versus (Q ⊃ P) ∧ (R ⊃ P)
3. P ⊃ (Q ⊃ R) versus Q ⊃ (P ⊃ R)
4. P ⊃ ¬Q versus Q ⊃ ¬P
Show that these are logically equivalent.
1. ∀x(Fx ⊃ P) versus ∃xFx ⊃ P
2. P ⊃ ∀xFx versus ∀x(P ⊃ Fx)
3. ∀x(Fx ∧ Gx) versus ∀xFx ∧ ∀xGx
4. ∃x(Fx ∨ Gx) versus ∃xFx ∨ ∃xGx
Show that these are not logically equivalent.
1. ∀x(Fx ∨ Gx) versus ∀xFx ∨ ∀xGx
2. ∃x(Fx ∧ Gx) versus ∃xFx ∧ ∃xGx
Show that Fab ⊨ ∀x(x = a ⊃ Fxb)
Show that (a) Rab ⊭ ∃xRxx; and (b) Rab ⊭ ¬∃xRxx
Show that (a) ∃x∀yRxy ⊨ ∀y∃xRxy, but that (b) ∀y∃xRxy ⊭ ∃x∀yRxy