Mathematical Logic AAAAA November 10, 2015
1. Formalise the following sentences in the language of mathematics:
(i) Every old person likes some young person.
Solution: O(x) ≡ x is old; Y (x) ≡ x is young. xLy iff x likes y.
∀x(O(x) → ∃y(Y (y) ∧ xLy)) (ii) Some filmmaker does not like movies.
Solution: ∃x(F (x) ∧ ∀y(M (y) → ¬(xLy)))
2. Find proofs in natural deduction of the following formulas (when this is possible):
(a) ` A ∨ ¬A
You find the proof in the notes.
(b) A → B ` ¬B → ¬A.
Solution:
A → B [A]∗
================(→e)
. B [¬B]∗∗
=======================(¬e)
. ⊥
===================(¬i)∗
. ¬A
==================(→i)∗∗
¬B → ¬A
3. Explain the compactness theorem of first-order logic See the notes.
4. Define a model (with at least two elements) where the following formula is true and a model where it is false:
φ ≡ ∃x(A(x) ∨ ¬∃xA(x))
Solution: Let M = {a, b} be the universe of the model. Define AM(a) = true and AM(b) = true. Choose x = a. Then we have A(a) ∨ ¬∃xA(x) true in the model because A(a) is true.
1
The formula ¬φ = ¬∃x(A(x)∨¬∃xA(x)) is logically equivalent to ∀x¬(A(x)∨¬∃xA(x)) logically equivalent to ∀x(¬A(x) ∧ ¬¬∃xA(x)) logically equivalent to ∀x(¬A(x) ∧
∃xA(x)).
φ is false in a model M iff ¬φ is true in the model M iff ¬A(a) ∧ ∃xA(x) is true for all a ∈ M iff A(a) is false for every a ∈ M and ∃xA(x) is true. Impossible.
2
