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

MATH 0050: Logic

2022-2023

Exercise Set

1) Below, x, y represent variable symbols and P represents a unary predicate symbol.

a) For each of the following strings in Lstring, determine whether or not it is a formula in L:

⇒⇒ ∀xP x¬P y∀yP y   ;   ⇒ P xP x ⇒ ∀y¬P y

b) Convert the following formula in Lmath to an equivalent formula in L:

¬ ((P x) ⇔ ((∀y) (P y)))

2) Below, α, β, γ, δ are taken to be (distinct primitive) propositions.

a) For each of the following propositions, use the semantic tableaux method to determine whether or not the given proposition is a tautology, while, in each case, if the proposition is not a tautology, describe also every (type of) valuation for which it fails to be true:

(i) (γ ⇒ (β ⇒ α)) ⇒ ((¬γ) ∨ (α ⇔ β))

(ii) ((¬γ) ∨ (α ⇔ β)) ⇒ (γ ⇒ (β ⇒ α))

b) (i) Write down a direct proof of the following syntactic implication:

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

(ii) 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 9 elements;

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

4) a) Describe a register machine that shows that the following function is computable:

f : N 20 → N0 , f(m, n) = 3m + n + 10

b) Show that the following function is recursive:

g : N 20 → N0 , g(m, n) = 8mn + 12

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