Mathematical Logic (Part I) bis November 28, 2014
1. Consider the universe of people. Formalise the following sentences in the language:
Symbol Interpretation
a Mary (constant)
b John (constant)
W to be a singer (unary predicate) E to be english (unary predicate) L likes (binary predicate) H hates (binary predicate)
• John likes all english singers.
∀x(W (x) ∧ E(x) → L(b, x))
• John and Mary like the same singers.
∀x(W (x) → (L(b, x) ↔ L(a, x))
• Mary hates some singer whom John likes.
∃x(W (x) ∧ H(a, x) ∧ L(b, x))
• Not all people like english singers.
¬∀x∀y(W (y) ∧ E(y) → L(x, y))
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 ∨ ¬A. See the lecture notes.
(b) ¬A ∧ ¬B ` ¬(A ∨ B)
[A ∨ B]∗∗
¬A ∧ ¬B [∧e]
¬A [A]∗
[¬e]
⊥
¬A ∧ ¬B [∧e]
¬B [B]∗
[¬e]
⊥ [∨e]∗
⊥
[¬i]∗∗
¬(A ∨ B)
1
(c) ` (A ∧ B) → A → B
[A ∧ B]∗ [∧e] B
[→i] A → B
[→i]∗ A ∧ B → A → B
3. Show that some of the following equivalences are true and some are false:
(a) P ` Q ∧ R if and only if P ` Q and P ` R.
Let P
. . Q ∧ R Then we have
P . . Q ∧ R
[∧e] Q
and
P . . Q ∧ R
[∧e] R
For the converse, let
P . . Q
and P
. . R Then we have:
P . . Q
P . . R [∧i] Q ∧ R (b) P ` Q ∨ R if and only if P ` Q or P ` R.
The equivalence is false, because if we have a proof of Q ∨ R from P we can derive neither a proof of Q nor a proof of R.
2
(c) P ` Q if and only if ¬Q ` ¬P . If P ` Q then we have:
[P ]∗ . .
Q ¬Q
[¬e]
⊥ [¬i]∗
¬P If ¬Q ` ¬P then we have
[¬Q]∗ . .
¬P P
[¬e]
⊥
[RRA]∗ Q
4. Let φ ≡ (∀x∃yA(x, y)) → ∀x∀y(A(x, y) ∨ B(x)) be a sentence. Define a model of φ.
It is sufficient to find a model M where ∀x∃yA(x, y) is false.
Universe: M = {a, b}
AM(a, a) = false AM(a, b) = false AM(b, a) = false AM(b, b) = false
BM(a) = BM(b) = true
3
