代写MATH 0050: Logic 2023-2024 Exercise Set B代写留学生Matlab语言

日期：2024-03-30 06:26

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.