The Australian National University (compiled: 12:26, Sunday 24th July, 2022) S2 2022
School of Computing Practical Session 3
Convenor: Pascal Bercher
Lecturer of the respective content: Pascal Bercher
Credit for exercises: Dirk Pattinson, Victor Rivera, and several convenors and lecturers from earlier years
Foundations of Computation
The practical contains a number of exercises designed for the students to practice the course content. During the practical
session, the tutor will work through some of these exercises while students will be responsible for completing the remaining
exercises in their own time. There is no expectation that all the exercises will be covered in the practical session.
Covers: Lecture Material Week 3
At the end of this tutorial, you will be able to
• determine free and bound variables of first order formulae;
• prove first order formulae using Natural Deduction;
• determine whether first order formulae are T or F ;
• prove properties by induction.
Exercise 1 Interpretation of First Order Logic
Let S = (U, θ) be a situation for first order logic where U = N = {0, 1, 2, 3, . . . } is the domain of discourse, we have
one unary relation symbol E(x) that stands for “x is even”, and one binary relation symbol D(x, y) that stands for “x is
divisible by y”. That is, we have
θ(D) = {(x, y) | x divisible by y} and θ(E) = {0, 2, 4, . . . }
so that for example, all of (5, 1), (10, 5), (12, 6) are elements of θ(D), but for example (5, 2) ̸∈ θ(D).
For each of the following formulae ϕ, determine the free variables, and all situations based on θ in which the formula ϕ is
true.
(Here, a situation based on θ is a situation for which θ(D) and θ(E) are as given above.)
Justify your answer briefly (in a single sentence).
1. D(x, x)
2. ∃x.D(x, x)
3. ∀x.∃y.D(x, y)
4. ∃y.E(y) ∧D(x, y)
5. ∀y.¬E(y)→ D(y, x)
6. ∀y.E(y) ∧D(x, y)
Note: The exercise may seem heavy on notation and terminology, please refer to slide 41 onward in Lecture 2, and slide
6 in Lecture 3.
Solution.
1. free variable is x, and D(x, x) holds for all valuations, as every number is divisible by itself.
2. no free variables, and ∃x.D(x, x) holds for all valuations.
3. again, no free variables, and ∀x.∃y.D(x, y) says that all numbers are divisible by some number, so evaluates to
true.
4. ∃y.E(y) ∧D(x, y) has one free variable x and says that x is divisible by an even number. This formula holds for
all valuations θ for which θ(x) is even.
5. ∀y.¬E(y)→ D(y, x) has a free variable x and says that x divides all odd numbers. The only such number is 1.
6. ∀y.E(y) ∧D(x, y) has x as a free variable, but holds for no assignments, as the formula in particular states that all
numbers are even!
1
We see that only the free variables are relevant for the truth of a formula under an assignment.
Exercise 2 Change of bound variables
Prove the statement (∀x.P (x)) → (∀y.P (y)) using natural deduction. Even the simplest Predicate Calculus facts must
be proved, such as change of bound variables. Example solution has four lines, but any proper proof will do.
Solution.
1 ∀xP (x)
2 a P (a) ∀-E, 1
3 ∀yP (y) ∀-I, 2
4 (∀xP (x))→ (∀yP (y)) →-I, 1–3
Exercise 3 ∀ and ∃
Give a natural deduction proof of the (derived) rule
(∃xP (x))→ Q
∀x(P (x)→ Q)
.
Example solution has six lines, but any proper proof will do.
Solution.
1 (∃xP (x))→ Q
2 a P (a)
3 ∃xP (x) ∃-I, 2
4 Q →-E, 1, 3
5 P (a)→ Q →-I, 2–4
6 ∀x(P (x)→ Q) ∀-I, 5
Exercise 4 Changing the Order of Quantifiers
Try and prove that
∀y.∃x.P (x, y)→ ∃x.∀y.P (x, y).
This example was mentioned in the lectures. Is the formula valid? If so, prove it. If not, then explain why you can’t.
Solution.
1 ∀y∃xP (x, y)
2 b ∃xP (x, b) ∀-E, 1
3 a P (a, b)
4 P (a, b) R, 3
5 P (a, b) – WRONG – ∃-E, 2, 3–4
6 ∀yP (a, y) ∀-I, 5
7 ∃x∀yP (x, y) ∃-I, 6
• The guard variable a at line (3) prevents us from moving between steps (4) and (5).
• Line (5) violates the (a is not free in q) clause in the rule.
∃xP (x)
[P (a)]
...
q (a arbitrary)
q (a is not free in q)2
1 ∀y∃xP (x, y)
2 ∃xP (x, b) ∀-E, 1
3 a P (a, b)
4 ∀yP (a, y) – WRONG – ∀-I, 3
5 ∃x∀yP (x, y) ∃-I, 4
6 ∃x∀yP (x, y) ∃-E, 2, 3–5
• Here step (4) is wrong, as at this point, the variable b is not arbitrary: it appears in the assumption P (a, b) at step
(3).
• According to the other examples of ∀-I, we should have a vertical bar labelled b, alongside lines preceding step (3),
which would be indented (this must include all the lines containing b). How could you do that in this case?
Exercise 5 Truth in First-Order Logic
Given the first-order situation S = (U, θ) with U = {0, 1, 2}, a unary relation symbol P (x) and a binary relation symbol
R(x, y) with
θ(P ) = {0, 1} and θ(R) = {(0, 0), (0, 1), (1, 2)}
determine which of the following first-order formulae are true in S, and justify your answer briefly (in a single sentence).
1. ∀x.P (x)→ ¬R(x, x)
2. ∀x.¬R(x, x) ∧ ∃y.P (y)
3. (∃x.∃y.R(x, y))→ ∀x.P (x)
4. ∃x.∃y.(R(x, y)→ ∀x.P (x))
Solution.
1. is false, as we have for example P (0) but also R(0, 0) so that the formula doesn’t hold for x = 0.
2. is false, as the formula states in particular that ¬R(x, x) for all x, and we have R(0, 0).
3. is false, as the antecedent ∃x.∃y.R(x, y) is true (e.g. R(1, 2)) but the consequence ∀x.P (x) is false, as P (2) does
not hold.
4. is true, because e.g. for x = y = 2 we have that R(x, y) is false so that R(x, y)→ ∀x.P (x) is true.
Exercise 6 Quantified Version of Modus Ponens
Give a natural deduction proof of the following derived rule:
(∀x.P (x)) ∧ (∀y.P (y)→ Q(y))
∀z.Q(z)
This is a quantified version of implication elimination. Again one only needs elimination (∀-E) and introduction (∀-I).
Example solution has seven lines, but any proper proof will do.
Solution.
1 (∀xP (x)) ∧ (∀y.P (y)→ Q(y))
2 ∀xP (x) ∧-E, 1
3 ∀y.P (y)→ Q(y) ∧-E, 2
4 a P (a) ∀-E, 2
5 P (a)→ Q(a) ∀-E, 3
6 Q(a) →-E, 5, 4
7 ∀zQ(z) ∀-I, 6
3
Exercise 7 Existential Quantifiers and Disjunction
Give a proof of the following derived rule
∃x.(P (x) ∨Q(x))
(∃x.P (x)) ∨ (∃x.Q(x))
that establishes that ∃ distributes over ∨. Working with the existential quantifier is trickier but there’s a strong similarity.
Example solution has ten lines, but any proper proof will do.
Solution.
1 ∃x(P (x) ∨Q(x))
2 a P (a) ∨Q(a)
3 P (a)
4 ∃xP (x) ∃-I, 3
5 (∃xP (x)) ∨ (∃xQ(x)) ∨-I, 4
6 Q(a)
7 ∃xQ(x) ∃-I, 6
8 (∃xP (x)) ∨ (∃xQ(x)) ∨-I, 7
9 (∃xP (x)) ∨ (∃xQ(x)) ∨-E, 2, 3–5, 6–8
10 (∃xP (x)) ∨ (∃xQ(x)) ∃-E, 1, 2–9
Exercise 8 Natural Number Induction
1. Prove, by natural number induction, that
P (n) : 2(n+ 2) ≤ (n+ 2)2
holds for all natural numbers n ∈ N.
Solution.
Base Case. For n = 0, we show that
P (0) : 2(0 + 2) ≤ (0 + 2)2
4 ≤ 4
This is obviously true.
Step Case. Let a be an arbitrary number. Then Assume P (a), that is
2(a+ 2) ≤ (a+ 2)2 (IH)
Prove P (a+ 1), that is
2((a+ 1) + 2) ≤ ((a+ 1) + 2)2
2((a+ 1) + 2)
= 2((a+ 2) + 1) (arith)
= 2(a+ 2) + 2 (arith)
≤ (a+ 2)2 + 2 (IH)
≤ a2 + 4a+ 6 (arith)
≤ a2 + 6a+ 9 (add the term 2n+ 3)
= ((a+ 1) + 2)2 (arith)
Since the base and step cases are established, we can conclude that
∀n(2(n+ 2) ≤ (n+ 2)2)
4
2. In the lecture, we have shown that the sum of the first n odd numbers is equal to n2. Here, we consider the sum of
the first n even numbers, i.e. the function
sumeven 0 = 0 -- SE1
sumeven n = 2 * n + sumeven (n-1) -- SE2
Prove, by natural number induction, that
sumeven n = n * (n+1)
for all natural numbers n ∈ N.
Solution.
Base Case. We show that sumeven 0 = 0 * (0+1).
sumeven 0 = 0 = 0 * (0+1) -- SE1 and arith
Step Case. Assume that sumeven n = n * (n+1) (IH).
We show that sumeven (n+1) = (n+1) * ((n+1)+1).
sumeven (n+1)
= 2 * (n+1) + sumeven (n+1-1) -- SE2
= 2 * n + 2 + sumeven n -- arith
= 2 * n + 2 + n * (n+1) -- IH
= 2 * (n+1) + n * (n+1) -- arith
= (2 + n) * (n+1) -- arith
= (n+1) * ((n+1)+1) -- arith
5
Appendix: Natural Deduction Rules
Propositional Calculus
(∧I) p q
p ∧ q
(∧E) p ∧ q
p
p ∧ q
q
(∨I) p
p ∨ q
p
q ∨ p
(∨E)
[p] [q]
...
...
p ∨ q r r
r
(→ I)
[p]
...
q
p→ q
(→ E) p p→ q
q
(¬I)
[p]
...
F
¬p
(¬E) p ¬p
F
(PC)
[¬p]
...
F
p
(T )
T
Predicate Calculus
(∀I) P (a) (a arbitrary)
∀x. P (x)
(∀E) ∀x. P (x)
P (a)
(∃I) P (a)
∃xP (x)
(∃E) ∃xP (x)
[P (a)]
...
q (a arbitrary)
q (a is not free in q)
6