Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH 0050 final assessment
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