MATH 0050: Logic
University College London 2022-2023
MATH 0050 final assessment - 2020-2021: a set of solutions
1. (a) The set of formulae in the first order predicate language (is denoted by L and) is defined inductively
as follows:
· If P is an n-ary predicate symbol and x1, · · · xn are variable symbols, then Px1 · · ·xn is a
formula.
· If α is a formula, then so is ¬α.
· If α, β are formulae, then so is ⇒ αβ.
· If x is a variable symbol and α is a formula, then ∀xα is a formula.
Let us now consider the given strings:
◦ The string ⇒ ¬Qxy ⇒ ∀x⇒ PxPy is not a formula.
If the string ⇒ ¬Qxy ⇒ ∀x ⇒ PxPy were a formula, then ¬Qxy ⇒ ∀x ⇒ PxPy would
have to consist of two formulae. We note that Qxy is a formula (since Q is a binary, or 2-ary,
predicate symbol), and, hence, ¬Qxy is a formula; so, if the string ¬Qxy ⇒ ∀x ⇒ PxPy
were to consist of two formulae, the string ⇒ ∀x⇒ PxPy would be a formula. For this, latter
string, we note that Px and Py are formulae (since P is a unary, or 1-ary, predicate symbol),
and, hence, that ⇒ PxPy is a formula, and, in turn, that ∀x ⇒ PxPy is a formula. As such,
the string ⇒ ∀x ⇒ PxPy consists of a ⇒ symbol followed, on the right, by a single formula,
namely the formula ∀x⇒ PxPy. None of the defining rules of formulae allows us to construct
a formula that consists of a ⇒ symbol, followed, on the right, by a single formula. Therefore,
the string ⇒ ∀x ⇒ PxPy cannot be a formula, and, hence, as might be indicated above, the
given string, ⇒ ¬Qxy ⇒ ∀x⇒ PxPy, cannot be a formula.
◦ The string ⇒ ∀x⇒ Px⇒ ¬Qxy∀yPyQyx is a formula.
We may use the definition of formula, given above, to construct the string as a formula. We
may obtain Px and Py, as well as Qxy and Qyx, as formulae (since P is a unary, or 1-ary,
predicate symbol, and Q is a binary, or 2-ary, predicate symbol). Since Py is a formula, ∀yPy
is a formula, while, since Qxy is a formula, ¬Qxy is a formula. It follows that, since ∀yPy
and ¬Qxy are formulae, ⇒ ¬Qxy∀yPy is (also) a formula. It follows, in turn, that, since Px
and ⇒ ¬Qxy∀yPy are formulae, ⇒ Px ⇒ ¬Qxy∀yPy is (also) a formula, and, hence, that
∀x ⇒ Px ⇒ ¬Qxy∀yPy is a formula. Finally, since ∀x ⇒ Px ⇒ ¬Qxy∀yPy and Qyx are
formulae, the given string, ⇒ ∀x⇒ Px⇒ ¬Qxy∀yPyQyx, is (also) a formula.
1
(b) Let us transform the given formulae into formulae in L, as required. We start with:
· ((Px) ∨ (¬ (Py)))⇒ Qxy
· (((∀y) (Py)) ∧ (¬ (Px)))⇒ ((∃x) (Qyx))
Note that we cannot use the symbols ‘∃’, ‘∨’, ‘∧’, ‘⇔’, or brackets in L, and we must write strings
of the form ‘α⇒ β’ as ‘⇒ αβ’.
Let us gradually transform these formulae.
First, let us avoid the use of the ‘∨’ symbol above, by using the general convention that states that
‘α ∨ β’ corresponds to ‘(¬α)⇒ β’:
· ((¬ (Px))⇒ (¬ (Py)))⇒ Qxy
· (((∀y) (Py)) ∧ (¬ (Px)))⇒ ((∃x) (Qyx))
Similarly, let us avoid the use of the ‘∧’ symbol above, by using the general convention that states
that ‘α ∧ β’ corresponds to ‘¬(α⇒ (¬β))’:
· ((¬ (Px))⇒ (¬ (Py)))⇒ Qxy
· (¬ (((∀y) (Py))⇒ (¬ (¬ (Px)))))⇒ ((∃x) (Qyx))
Next, let us avoid the use of the ‘∃’ symbol above, by using the general convention that states that
‘(∃x)(α)’ corresponds to ‘¬((∀x)(¬α))’:
· ((¬ (Px))⇒ (¬ (Py)))⇒ Qxy
· (¬ (((∀y) (Py))⇒ (¬ (¬ (Px)))))⇒ (¬ ((∀x) (¬ (Qyx))))
Let us next rewrite strings of the form ‘α ⇒ β’ as ‘⇒ αβ’, starting with the innermost (“most
bracketed”) ‘⇒’ symbols:
· (⇒ (¬ (Px)) (¬ (Py)))⇒ Qxy
· (¬ (⇒ ((∀y) (Py)) (¬ (¬ (Px)))))⇒ (¬ ((∀x) (¬ (Qyx))))
and finishing by dealing with the outermost ‘⇒’ symbols:
· ⇒ (⇒ (¬ (Px)) (¬ (Py)))Qxy
· ⇒ (¬ (⇒ ((∀y) (Py)) (¬ (¬ (Px))))) (¬ ((∀x) (¬ (Qyx))))
We have essentially completed the transformation of our formulae in Lmath into formulae in L.
It now remains to remove all brackets present, since, in the setting of L, these are unnecessary (and,
in any case, not allowed).
So, finally, as formulae in L, the given elements of Lmath become:
· ⇒⇒ ¬Px¬PyQxy
· ⇒ ¬ ⇒ ∀yPy¬¬Px¬∀x¬Qyx
Overall:
· ((Px) ∨ (¬ (Py)))⇒ Qxy corresponds to ⇒⇒ ¬Px¬PyQxy
· (((∀y) (Py)) ∧ (¬ (Px)))⇒ ((∃x) (Qyx)) corresponds to ⇒ ¬ ⇒ ∀yPy¬¬Px¬∀x¬Qyx
2
2. (a) (i) We form a semantic tableau starting from ¬ (((α ∨ β)⇔ (¬γ))⇒ ((¬γ) ∧ β)).
¬(((α ∨ β)⇔ (¬γ))⇒ ((¬γ) ∧ β))
(α ∨ β)⇔ (¬γ) , ¬((¬γ) ∧ β)
ggggg
ggggg
ggggg
ggggg
ggg
¬¬γ ¬β
SSSS
SSSS
SSSS
SSSS
SSSS
SSSS
SSSS
SSSS
SSSS
SSSS
γ
lll
lll
lll
lll
lll
α ∨ β , ¬γ ¬(α ∨ β) , ¬¬γ α ∨ β , ¬γ
UUUU
UUUU
UUUU
UUUU
UUUU
UU
¬(α ∨ β) , ¬¬γ
closed ¬α , ¬β α β ¬α , ¬β
γ open closed γ
open open
There exist open branches.
Since there exist open branches, we deduce that ((α ∨ β)⇔ (¬γ)) ⇒ ((¬γ) ∧ β) is not a
tautology.
By considering the open branches, we may describe every (type of) valuation, v, for which the
original proposition fails to be true:
· If v(α) = 0 and v(β) = 0 and v(γ) = 1, then v (((α ∨ β)⇔ (¬γ))⇒ ((¬γ) ∧ β)) = 0
· If v(α) = 1 and v(β) = 0 and v(γ) = 0, then v (((α ∨ β)⇔ (¬γ))⇒ ((¬γ) ∧ β)) = 0
3
(ii) We form a semantic tableau starting from ¬ (((¬γ) ∧ β)⇒ ((α ∨ β)⇔ (¬γ))).
¬(((¬γ) ∧ β)⇒ ((α ∨ β)⇔ (¬γ)))
(¬γ) ∧ β , ¬ ((α ∨ β)⇔ (¬γ))
¬γ , β
ggggg
ggggg
ggggg
ggggg
gg
VVVV
VVVV
VVVV
VVVV
VVVV
V
¬ (α ∨ β) , ¬γ α ∨ β , ¬¬γ
¬α , ¬β γ
NNN
NNN
NNN
NNN
NNN
closed α β
closed closed
All branches are closed.
Hence, the proposition ((¬γ) ∧ β)⇒ ((α ∨ β)⇔ (¬γ)) is a tautology.
4
(b) The given proposition is not a theorem.
We may start by noting the Completeness Theorem for propositional logic, which states that, for a
set of propositions S and a proposition δ:
S |= δ if and only if S ⊢ δ
As a result, we may conclude that it holds that |= ((α ∨ β)⇔ (¬γ))⇔ ((¬γ) ∧ β) if and only if it
holds that ⊢ ((α ∨ β)⇔ (¬γ)) ⇔ ((¬γ) ∧ β) holds, i.e. that ((α ∨ β)⇔ (¬γ)) ⇔ ((¬γ) ∧ β) is
a theorem if and only if it is a tautology.
Let us now try to show that the given proposition is not a tautology.
By examining the structure of the propositions present in this proposition and/or our solution to part
(a), we may describe a (type of) valuation for which the proposition is false.
For example, the given proposition is false for any valuation v for which
v (α) = 0 and v (β) = 0 and v (γ) = 1
For any such valuation v, v (α ∨ β) = 0 and v (¬γ) = 0. Therefore, v ((α ∨ β)⇒ (¬γ)) = 1 and
v ((¬γ)⇒ (α ∨ β)) = 1, so that v ((α ∨ β)⇔ (¬γ)) = 1.
Similarly, for any such valuation v, v (¬γ) = 0 and v (β) = 0, so that v ((¬γ) ∧ β) = 0.
Then, since v ((α ∨ β)⇔ (¬γ)) = 1 and v ((¬γ) ∧ β) = 0, we may deduce that
v (((α ∨ β)⇔ (¬γ))⇒ ((¬γ) ∧ β)) = 0 and v (((¬γ) ∧ β)⇒ ((α ∨ β)⇔ (¬γ))) = 1
so that
v (((α ∨ β)⇔ (¬γ))⇔ ((¬γ) ∧ β)) = 0
i.e. so that ((α ∨ β)⇔ (¬γ))⇔ ((¬γ) ∧ β) is not a tautology.
Hence, overall, we may conclude that the proposition ((α ∨ β)⇔ (¬γ))⇔ ((¬γ) ∧ β) is (also) not
a theorem, as indicated above.
5
3. (a) Consider {α⇒ ((¬β)⇒ γ) , α⇒ ((¬β)⇒ (¬γ))} ⊢ α⇒ β.
By the Deduction Theorem, to show {α ⇒ ((¬β)⇒ γ) , α ⇒ ((¬β)⇒ (¬γ))} ⊢ α ⇒ β, it is
due to suffice to give a proof of {α ⇒ ((¬β)⇒ γ) , α ⇒ ((¬β)⇒ (¬γ)) , α} ⊢ β; we do so
below:
1. α⇒ ((¬β)⇒ γ) Hypothesis
2. α⇒ ((¬β)⇒ (¬γ)) Hypothesis
3. α Hypothesis
4. ((¬β)⇒ (¬γ))⇒ (((¬β)⇒ γ)⇒ β) Axiom 3
5. (¬β)⇒ γ Modus ponens on lines 1, 3
6. (¬β)⇒ (¬γ) Modus ponens on lines 2, 3
7. ((¬β)⇒ γ)⇒ β Modus ponens on lines 4, 6
8. β Modus ponens on lines 5, 7
Hence, the original syntactic implication, {α ⇒ ((¬β)⇒ γ) , α ⇒ ((¬β)⇒ (¬γ))} ⊢ α ⇒ β,
holds.
(b) The following is a direct proof of the given syntactic implication:
1. (α⇒ (¬β))⇒ (γ ⇒ α) Hypothesis
2. ¬β Hypothesis
3. γ ⇒ (α⇒ δ) Hypothesis
4. (γ ⇒ (α⇒ δ))⇒ ((γ ⇒ α)⇒ (γ ⇒ δ)) Axiom 2
5. (γ ⇒ α)⇒ (γ ⇒ δ) Modus ponens on lines 3, 4
6. (¬β)⇒ (α⇒ (¬β)) Axiom 1
7. α⇒ (¬β) Modus ponens on lines 2, 6
8. γ ⇒ α Modus ponens on lines 1, 7
9. γ ⇒ δ Modus ponens on lines 5, 8
6
(c) A set S of propositions is consistent if there does not exist a proposition α (α ∈ L0) such that S ⊢ α
and S ⊢ ¬α; if there exists a proposition α such that S ⊢ α and S ⊢ ¬α, we may say that the set
S is inconsistent.
Let us consider the given set of propositions, {¬α , ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))}; we try to show
that we may prove each of the propositions β ⇒ ((γ ⇒ δ)⇒ (¬α)) and¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))
from the relevant set, i.e. that {¬α , ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))} ⊢ β ⇒ ((γ ⇒ δ)⇒ (¬α)) and
{¬α , ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))} ⊢ ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α))) (both) hold.
The following is a (direct) proof of β ⇒ ((γ ⇒ δ)⇒ (¬α)) from {¬α , ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))}:
1. ¬α Hypothesis
2. (¬α)⇒ ((γ ⇒ δ)⇒ (¬α)) Axiom 1
3. (γ ⇒ δ)⇒ (¬α) Modus ponens on lines 1, 2
4. ((γ ⇒ δ)⇒ (¬α))⇒ (β ⇒ ((γ ⇒ δ)⇒ (¬α))) Axiom 1
5. β ⇒ ((γ ⇒ δ)⇒ (¬α)) Modus ponens on lines 3, 4
Similarly, the following is a (direct) proof of the proposition ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α))) from the
given set propositions, i.e. from {¬α , ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))}:
1. ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α))) Hypothesis
Hence, it holds that {¬α , ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))} ⊢ β ⇒ ((γ ⇒ δ)⇒ (¬α)) and it also
holds that {¬α , ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))} ⊢ ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α))).
So, we may conclude that the given set of propositions, {¬α , ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))}, is not
consistent, i.e. that {¬α , ¬ (β ⇒ ((γ ⇒ δ)⇒ (¬α)))} is inconsistent.
7
4. (a) Let us first define an appropriate L(Π,Ω), i.e. sets of predicates and functionals we will use:
Π = {=,≤} , Ω = {A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11}
such that each of the predicate symbols ‘=’ and ‘≤’ is a binary predicate symbol, and such that each
of the functional symbols ‘A1’, ‘A2’, ‘A3’, ‘A4’, ‘A5’, ‘A6’, ‘A7’, ‘A8’, ‘A9’, ‘A10’, ‘A11’ is a 0-ary
functional symbol.
Then, we may use the theory consisting of the following sentences:
· (∀x)(x ≤ x)
· (∀x)(∀y)(((x ≤ y) ∧ (y ≤ x))⇒ (x = y))
· (∀x)(∀y)(∀z)(((x ≤ y) ∧ (y ≤ z))⇒ (x ≤ z))
· (∀x)(x = x)
· (∀x)(∀y) ((x = y)⇒ (y = x))
· (∀x)(∀y)(∀z) (((x = y) ∧ (y = z))⇒ (x = z))
· (∀x)(∀y)(∀z) ((x = y)⇒ ((z ≤ x)⇒ (z ≤ y)))
· (∀x)(∀y)(∀z) ((x = y)⇒ ((x ≤ z)⇒ (y ≤ z)))
· (∀x)((x = A1) ∨ (x = A2) ∨ (x = A3) ∨ (x = A4) ∨ (x = A5) ∨ (x = A6)
∨ (x = A7) ∨ (x = A8) ∨ (x = A9) ∨ (x = A10) ∨ (x = A11))
· ¬((∃x)(∀y)(x ≤ y))
8
(b) Let us first define an appropriate L(Π,Ω), i.e. sets of predicates and functionals we will use:
Π = {∼,=} , Ω = ∅
such that ‘∼’ and ‘=’ are binary predicate symbols.
Then, we may use the theory consisting of the following sentences:
· (∀x)(¬(x ∼ x))
· (∀x)(∀y)((x ∼ y)⇒ (y ∼ x))
· (∀x) (x = x)
· (∀x)(∀y) ((x = y)⇒ (y = x))
· (∀x)(∀y)(∀z) (((x = y) ∧ (y = z))⇒ (x = z))
· (∀x)(∀y)(∀z) ((x = y)⇒ ((z ∼ x)⇒ (z ∼ y)))
· (∀x)(∀y)(∀z) ((x = y)⇒ ((x ∼ z)⇒ (y ∼ z)))
· (∀x)(¬((∃y)(∃z)(∃w)((x ∼ y)∧(x ∼ z)∧(x ∼ w)∧(¬(y = z))∧(¬(y = w))∧(¬(z = w)))))
9
5. (a) (i) Below is a diagrammatic description of a register machine that computes
f1 : N0 → N0 , f1(m) = 8
S1R1−1 55

S2
R1+1
%%
S3
R1+1
%%
S4
R1+1
%%
S5
R1+1
%%
S6
R1+1
%%
S7
R1+1
%%
S8
R1+1
%%
S9
R1+1
%%
S0
(ii) Below is a diagrammatic description of a register machine that computes
f2 : N30 → N0 , f2(m,n, k) = m+ 3n+ 4k + 5
S1
R2−1
**

S4
R1+1
dd S3
R1+1
ee S2
R1+1
ee
S5
R3−1
++

S9
R1+1
ee S8
R1+1
ee S7
R1+1
ee S6
R1+1
ee
S10
R1+1
&&
S11
R1+1
&&
S12
R1+1
&&
S13
R1+1
&&
S14
R1+1
%%
S0
10
(b) The given function, h, is computable.
In order to justify this, we may use the result that states that a function is computable if and only if
it is recursive.
We start by noting that the function
h1 : N20 → N0 , h1(m,n) = m+ n
is recursive; we may obtain it by using primitive recursion:
· h1(m, 0) = m, which we may obtain using a projection function, i.e. by projecting (to) the
‘first input’, m.
· h1(m, k + 1) = h1(m, k) + 1, which we may obtain using the successor function.
This allows us to show that the function
h2 : N20 → N0 , h2(m,n) = mn
is recursive; we may obtain it by using primitive recursion:
· h2(m, 0) = 0, which we may obtain using a zero or projection function, i.e. by applying a zero
function or by projecting (to) the ‘second input’, 0.
· h2(m, k + 1) = h2(m, k) + m = h1(h2(m, k),m), which we may obtain using the relevant
addition function h; we may obtain the summand m using a projection function.
We may now show that the function
h : N20 → N0 , h(m,n) = (m+ 4)n+1
is recursive; we may obtain it by using primitive recursion:
· h(m, 0) = m+ 4 = m+ 1 + 1 + 1 + 1, which we may obtain using (a composition involving)
the successor function, four times, as well as a projection function, i.e. by projecting (to) the
‘first input’, m, and then applying the successor function four times.
· h(m, k+1) = (m+4) ·h(m, k) = h2(m+4, h(m, k)), which we may obtain using the relevant
multiplication function h2; we may obtain the term m + 4 using (a composition involving) the
successor function, four times, as well as a projection function, i.e. by projecting (to) the ‘first
input’, m, and then applying the successor function four times.
So, overall, we deduce that the function h is recursive, and, therefore, computable.
11
(c) The given function is not recursive.
We may prove this by contradiction.
Suppose that g is a recursive function. Then it must appear in the given list of all recursive functions
from N0 to N0, i.e. in the list f0, f1, f2, · · · , so that g = fn for some n ∈ N0.
However, g(n) = 9fn(n)+8b, i.e. fn(n) = 9fn(n)+8b. From this, we obtain fn(n)− 9fn(n) = 8b
i.e. −8fn(n) = 8b, or, equivalently, −fn(n) = b. This equation cannot hold for a function from N0
to N0 (for every n in N0, fn(n) ≥ 0, so that −fn(n) ≤ 0, while, by assumption, b > 0).
As a result, g(n) ̸= fn(n), i.e. g and fn differ in their value at/for the number n.
So, it cannot be the case that g = fn, which leads to the required contradiction.
Hence, g is not a recursive function.