MATH 0050: Logic 2022-2023
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.
2023-09-02