Mathematical Logic November 22, 2013 Risults and Solution

Mathematical Logic November 22, 2013 Risults and Solution

1. Mohamed Abdelhamied Vote INS 2. Fatma Metwally Vote 23

3. Paola Urbani Vote 24 4. Aliye Kuerban Vote 25

1. Explain what formula represents the sentence: “I come either tomorrow morning or to- morrow night. In the first case, I eat with you”.

P ≡ I come tomorrow morning Q ≡ I come tomorrow night R ≡ I eat with you

(a) ¬P → Q (b) P → (Q ∨ R) (c) (P → Q) ∨ ¬R (d) P → (Q ∨ ¬R) (e) (P ∨ Q) → ¬R

(f) (P ∨ Q) ∧ (P → R)

Solution: The right sentence is (P ∨ Q) ∧ (P → R).

2. Consider the universe of people and the following language:

Symbol Interpretation

a “Anne” (constant)

C “to be a student” (unary relation) I “to be a professor” (unary relation) A “likes” (binary relation) D “hates” (binary relation) Formalize the following sentences

1

(i) Anne is a professor who likes all students (ii) Every professor likes some student (iii) Some student hates all professor Solution: (i) I(a) ∧ ∀y(C(y) → aAy).

(ii) ∀x(I(x) → ∃y(C(y) ∧ xAy)) (iii) ∃x(C(x) ∧ ∀y(I(y) → xHy))

3. (i) Provide a proof in natural deduction of the formula

(A → (B → C)) → (A → B) → A → C (ii) Find a λ-term which represents a proof of the above formula.

Solution:

[x : A → B]^∗∗ [y : A]^∗ [z : A → (B → C)]^∗∗∗ [y : A]^∗

—————————– —————————————–

xy : B zy : B → C

————————————————————————

(zy)(xy) : C

————————————————————————(→_i)^∗

λy.(zy)(xy) : A → C

————————————————————————(→_i)^∗∗

λx.λy.(zy)(xy) : (A → B) → A → C

————————————————————————(→i)^∗∗∗

λz.λx.λy.(zy)(xy) : (A → (B → C)) → (A → B) → A → C

2