Mathematical Logic: Solution and Results November 11, 2013
1. Andrea Lazzarotto Voto 30L 2. Panzetta Antonio Voto 28 3. Nguyen Minh Phu Voto 18 4. Erboso Gianluca Voto 30L 5. Palmarini Francesco Voto 24 6. Britti Lorenzo Voto 19 7. Maggiato Alberto Voto 23
The other students have an insufficient vote.
1. Consider the universe of people and the following language:
Symbol Interpretation
a “Anne” (constant)
b “John” (constant)
C “to be a singer” (unary relation) I “to be italian” (unary relation) A “loves” (binary relation) D “hates” (binary relation) Formalize the following sentences
(i) John loves all italian singers (ii) John loves some italian singer
(iii) Anne hates some singer loved by John
(iv) There are people who hate all singers loved by John Solution:
(i) ∀x(I(x) ∧ C(x) → bAx);
(ii) ∃x(I(x) ∧ C(x) ∧ bAx);
(iii) ∃x(aDx ∧ C(x) ∧ bAx);
(iv) ∃x∀y(C(y) ∧ bAy → xDy)
1
2. (i) Provide a proof in natural deduction of Peirce law ((A → B) → A) → A (ii) Is the formula A ∨ ¬A derivable in Intuitionistic Logic? If not, why?
Solution:
(i) See the notes of the course.
(ii) IL satisfies the following condition: `IL A ∨ B iff either `IL A or `IL B. It follows that 6`ILA ∨ ¬A.
3. Give a proof of the formula A → (B → (A → A)) in typed lambda calculus.
Solution:
[x : A]∗ [x : A]∗∗∗
− − − − − − − − (→i)∗
λx.x : A → A [y : B]∗∗
− − − − − − − − − − − − − − −(→i)∗∗
λy.λx.x : B → (A → A)
− − − − − − − − − − − − − − −(→i)∗∗∗
λx.λy.λx.x : A → (B → (A → A))
2
