MATH0050
Answer all (five) questions.
1.
Below, x, y represent variable symbols, P represents a unary predicate symbol and
Q represents a binary predicate symbol.
(a) Consider the following strings in Lstring:
⇒ Qxy ⇒ ¬PxPy ⇒ Px
⇒⇒⇒ Px¬¬QxyPy∀xPx
For each of these strings, determine whether or not it is a formula in L.
(b) Convert the following formula of Lmath to a formula in L:
((Qxy)⇔ ((∃y) (Py)))⇒ (Py)
(20 marks)
2.
Below, α, β, γ are taken to be distinct primitive propositions.
(a) For each of the following, use the semantic tableaux method to determine
whether or not the given semantic implication holds. If a semantic implication
does not hold, describe every (type of) valuation for which it fails to hold.
(i) {(α⇔ β) ∨ (¬γ)} |= γ ⇒ (α⇒ β)
(ii) {γ ⇒ (α⇒ β)} |= (α⇔ β) ∨ (¬γ)
(b) Determine, without constructing truth tables or further semantic tableaux,
whether or not the following syntactic implication holds:
{(¬γ) ∨ (α⇔ β) , γ} ⊢ α⇒ β
Justify your answer; you may quote, without proof, any relevant results from
our course.
(20 marks)
3.
Below, α, β, γ, δ are taken to be propositions.
(a) Give a direct proof of the following:
{α⇒ (β ⇒ (¬γ)) , α⇒ β} ⊢ α⇒ (¬γ)
(b) Use the Deduction Theorem for propositional logic to show the following:
{α⇒ (¬ (β ⇒ γ)) , (¬δ)⇒ (β ⇒ γ)} ⊢ α⇒ δ
(c) Determine whether or not the following set of propositions is consistent:
{¬ (γ ⇒ β) , β}
(20 marks)
MATH0050 - 2021-2022 first assessment Page 1 of 2
4.
(a) Describe a theory, in a suitably defined first order predicate language L(Π,Ω),
such that a structure U is a (normal) model of the theory if and only if U is a
group of order 5 i.e. a group containing exactly 5 elements.
(b) Describe a theory, in a suitably defined first order predicate language L(Π,Ω),
such that a structure U is a (normal) model of the theory if and only if U is
a graph consisting of at most 7 vertices and in which there exist at least two
vertices each of which is not connected, by an edge, to any vertex.
(c) Does there exist a theory in a suitably defined first order predicate language
L(Π,Ω), such that a structure U is a (normal) model of the theory if and only
if U is a graph consisting of a countably infinite number of vertices?
Justify your answer; you may quote, without proof, any relevant results from
our course.
(20 marks)
5.
(a) For each of the following functions, show that the function is recursive:
(i) h1 : N20 → N0 , h1(m,n) = 4
(ii) h2 : N20 → N0 , h2(m,n) = (m+ 4)n
(b) For each of the following functions, determine whether or not the function is
computable:
g1 : N20 → N0 , g1(m,n) = 4m2n
g2 : N0 → N0 , g2(n) = 4n3 + 5
Justify your answers; you may quote, without proof, any relevant results from
our course.
(20 marks)
MATH0050 - 2021-2022 first assessment Page 2 of 2