Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH 0050: Logic

2023-2024

Exercise Set B

1)  Below, α, β , γ , δ are taken to be propositions.

a)  Use the semantic tableaux method to show that the following semantic implication holds:

{α ⇒ (((¬ (β ⇒ γ)) ⇒ α) ⇒ (¬δ))} |= α ⇒ (¬δ)

b)  Write down a direct proof of the following syntactic implication (a proof that does not assume the validity of any theorems and does not use the Deduction Theorem):

{α ⇒ (((¬ (β ⇒ γ)) ⇒ α) ⇒ (¬δ))} ⊢ α ⇒ (¬δ)

2)  Below, α, β , γ , δ , ϵ are taken to be propositions.

a)  Use the Deduction Theorem for propositional logic to show the following:

{(¬β) ⇒ (¬γ) , (¬α) ⇒ ((¬β) ⇒ γ)} ⊢ (¬α) ⇒ β

b)  Use the Deduction Theorem for propositional logic to show the following:

{α ⇒ ((β ⇒ (¬γ)) ⇒ ((¬δ) ⇒ ϵ))} ⊢ (β ⇒ (¬γ)) ⇒ ((¬δ) ⇒ (α ⇒ ϵ))

3)  After defining, in each case, a suitable set of predicate symbols (Π) and a suitable set of functional symbols (Ω), write down a theory (i.e. a set of sentences) that has as (normal) models (only):

a)  all posets containing at most 5 elements;

b)  all graphs in which every vertex is connected, by edges, to at least 4 other vertices.

4)     a)  Show that the following functions are computable:

(ii)  f2  : N0(2) → N0 ,    f2 (m,n) = 5m + 3n + 4

b)  Show that the following functions are recursive:

(i)  g1  : N0  → N0 ,    g1 (m) = 20

(ii)  g2  : N0(2) → N0 ,    g2 (m,n) = 7mn + 20

For part (b)(ii), you may assume that h : N0(2) → N0 , h(m,n) = m + n, is recursive.