1. For a term u, let ux t be the expression obtained from u by replacing the variable x by the term t. Restate this definition without using any form of the word “replace” or its synonyms. Suggestion: Use recursion on u. (Observe that from the new definition it is clear that ux t is itself a term.) 


2. To which axiom groups, if any, do each of the following formulas belong? (a) [( ∀ x Px → ∀ y Py)→ P z]→[∀ x Px →( ∀ y Py → P z)]. (b) ∀ y[∀ x(Px → Px) → (Pc → Pc)]. (c) ∀ x ∃ y Pxy → ∃ y Pyy. 


3. (a) Let A be a structure and let s : V → |A|. Define a truth assignment v on the set of prime formulas by v(α) = T iff |=A α[s].

Show that for any formula (prime or not), v(α) = T iff |=A α[s]. Remark: This result reflects the fact that ¬ and → were treated in Chapter 2 the same way as in Chapter 1. (b) Conclude that if tautologically implies ϕ, then logically implies ϕ.


4. Give a deduction (from ∅) of ∀ x ϕ→ ∃ x ϕ. (Note that you should not merely prove that such a deduction exists. You are instead asked to write out the entire deduction.) 


5. Find a function f such that if a formula ϕ has a deduction of length n from a set , and if x does not occur free in , then ∀ x ϕ has a deduction from of length f (n). The more slowly your function grows, the better. 


6. (a) Show that if ! α → β, then ! ∀ x α → ∀ x β. (b) Show that it is not in general true that α→β |= ∀ x α→∀ x β. 


7. (a) Show that ! ∃ x(Px → ∀ x Px). (b) Show that {Qx, ∀ y(Qy → ∀ z Pz)} ! ∀ x Px. 


8. (Q2b) Assume that x does not occur free in α. Show that ! (α → ∃ x β) ↔ ∃ x(α → β). Also show that, under the same assumption, we have Q3a: ! ( ∀ x β → α) ↔ ∃ x(β → α). 


9. (Re-replacement lemma) (a) Show by example that (ϕx y )y x is not in general equal to ϕ. And that it is possible both for x to occur in (ϕx y )y x at a place where it does not occur in ϕ, and for x to occur in ϕ at a place where it does not occur in (ϕx y )y x . (b) Show that if y does not occur at all in ϕ, then x is substitutable for y in ϕx y and (ϕx y )y x = ϕ. Suggestion: Use induction on ϕ. 


10. Show that ∀ x ∀ y Pxy ! ∀ y ∀ x Pyx. 


11. (Eq3) Show that ! ∀ x ∀ y ∀ z(x = y → y = z → x = z). 


12. Show that any consistent set of formulas can be extended to a consistent set having the property that for any formula α, either α ∈ or (¬ α) ∈ . (Assume that the language is countable. Do not use the compactness theorem of sentential logic.) 


13. Show that ! Py ↔ ∀ x(x = y → Px). Remarks: More generally, if t is substitutable for x in ϕ and x does not occur in t, then ! [ϕx t ↔ ∀ x(x = t → ϕ)]. Thus the formula ∀ x(x = t → ϕ) offers an alternative of sorts to the substitution ϕx t . 


14. Show that ! ( ∀ x((¬ Px) → Qx) → ∀ y((¬ Qy) → Py)). 


15. Show that deductions (from ∅) of the following formulas exist: (a) ∃ x α ∨ ∃ x β ↔ ∃ x(α ∨ β). (b) ∀ x α ∨ ∀ x β → ∀ x(α ∨ β). 


16. Show that deductions (from ∅) of the following formulas exist: (a) ∃ x(α ∧ β) → ∃ x α ∧ ∃ x β. (b) ∀ x(α ∧ β) ↔ ∀ x α ∧ ∀ x β. 


17. Show that deductions (from ∅) of the following formulas exist: (a) ∀ x(α → β) → ( ∃ x α → ∃ x β). (b) ∃ x(Py ∧ Qx) ↔ Py ∧ ∃ x Qx.


12개 이상 못풀면 짜지고 ㅋ