Mathematical Logic (Part I) November 7, 2014
1. Consider the universe of teatchers. Formalise the following sentences in the language:
Symbol Interpretation
a The teatcher John (constant) b The teatcher Mary (constant) W to be a teatcher of math (unary predicate)
E to be a good teatcher (unary predicate) L older than (binary predicate)
H hates (binary predicate)
• Every good teatcher is older than some teatcher of math
∀x(E(x) → ∃y(W (y) ∧ L(x, y)))
For every teacher x, if x is good, then there exists a theacher y of math such that x is older than y
• Some teatcher older than John and Mary hates every good teatcher
∃x(L(x, a) ∧ L(x, b) ∧ ∀y(E(y) → H(x, y)))
There exists a teacher x, who is older than John and older than Mary, and who hates every good teacher
2. Find proofs in natural deduction of the following formulas (when this is possible). (Re- member that the assumptions are on the left part of the symbol ` and the conclusion on the right part).
(a) A ∧ B ` (A ∨ B) ∧ B
A ∧ B [∧e] A [∨i] A ∨ B
A ∧ B [∧e] B
[∧i] (A ∨ B) ∧ B
1
(b) A ∨ B ` A ∧ B
To prove A ∧ B assuming A ∨ B is equivalent to prove the formula (A ∨ B) → (A ∧ B). But this formula is not a tautology. It becomes false when A is true and B is false.
(c) A → B, C → D ` (A ∧ C) → (B ∧ D) A ∧ C
[∧e]
A A → B
B
A ∧ C [∧e]
C C → D
[→e] D[∧e]
B ∧ D (d) A ∨ B, ¬B ` A
A ∨ B [A]∗
[B]∗ ¬B [¬e]
⊥ [⊥e] A
[∨e]∗ A
3. (a) Provide a proof of ¬¬A → A in natural deduction.
[¬A]∗∧ [¬¬A]∗∗
[¬e]
⊥[RRA]∗ A
[→i]∗∗
¬¬A → A
(b) Show that the deduction rule (RRA) can be proven from the other ones if we assume the formula ¬¬A → A.
[¬A]∗ ...
⊥ [¬i]∗
¬¬A ¬¬A → A
[→e] A
4. Explain the completeness theorem of first-order logic.
Notation: T ` φ means “there exists a formal proof of φ whose assumptions are in T . If M is a model, then M |= φ means that the sentence φ is true in M. If T is a set of sentences, M |= T means that every sentence φ ∈ T is true in M.
2
The following is the completeness theorem of first-order logic:
T ` φ if and only if ∀M(M |= T ⇒ M |= φ)
To prove that there exists a formal proof of φ from T , it is sufficient to prove that φ is true in every model satisfying the set T of axioms.
5. Let φ ≡ ∀x∀y(C(a) ∧ C(x) → ∃zB(y, z)) be a sentence, where a is a constant.
(a) Define a model of φ.
Model M with universe: M = {dog, cat, book}
a is a constant symbol: aM = dog.
C is a unary relation symbol. The interpretation is a function CM : M → {true, false}:
CM(dog) = false; CM(cat) = false; CM(book) = false.
B is a binary relation symbol. We interpret BM : M × M → {true, false} as follows: for all x, y ∈ M , BM(x, y) = true iff x = y.
We show that M |= φ.
Consider the formula C(a) ∧ C(x) → ∃zB(y, z), where x, y ranges over M . Since CM(a) ∧ CM(dog), CM(a) ∧ CM(cat) and CM(a) ∧ CM(book) are all false, then the inplication is true for every x and y.
(b) Define a model of ¬φ.
Model M with universe: M = {dog}
aM = dog.
CM(dog) = true.
BM(dog, dog) = false.
Then M |= ¬φ.
3
