The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 3 and
Foundations of Computation
The tutorial contains a number of exercises designed for the students to practice the course content. During the lab, the tutor will work through some of these exercises while the 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 lab time.
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 2 3 4
∀xP (x) aP(a) ∀yP(y)
∀-E,1 ∀-I, 2 →-I, 1–3
(∀xP (x)) → (∀yP (y)) Exercise 3
∀ and ∃ (∃xP (x)) → Q
. ∀x(P (x) → Q)
Give a natural deduction proof of the (derived) rule
Example solution has six lines, but any proper proof will do.
Solution.
1 (∃xP (x)) → Q 2a P(a)
3 4 5 6
Try and prove that
∃xP (x)
Q P(a) → Q
∃-I, 2 →-E, 1, 3 →-I, 2–4 ∀-I, 5
∀x(P (x) → Q) Exercise 4
Changing the Order of Quantifiers
∀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 2 3 4 5 6 7
∀y∃xP (x, y)
b
∃xP (x, b) a P(a,b) P(a,b)
∀-E, 1
R, 3
∃-E, 2, 3–4 ∀-I, 5
∃-I, 6
P(a,b) – WRONG – ∀yP(a,y)
∃x∀yP (x, y)
• 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.
[P (a)] .
∃xP (x) q (a arbitrary)
q (aisnotfreeinq) 2
1 2 3 4 5 6
∀y∃xP (x, y)
∃xP (x, b) a P(a,b)
∀yP (a, y)
∃x∀yP (x, y) ∃x∀yP (x, y)
– WRONG –
∀-E, 1
∀-I, 3
∃-I, 4
∃-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
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 2 3 4 5 6 7
(∀xP (x)) ∧ (∀y.P (y) → Q(y)) ∀xP (x)
∀y.P (y) → Q(y)
a P(a)
P (a) → Q(a)
Q(a) ∀zQ(z)
∧-E, 1 ∧-E, 2 ∀-E, 2 ∀-E, 3 →-E, 5, 4 ∀-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 2 3 4 5 6 7 8 9 10
∃x(P (x) ∨ Q(x)) a P(a)∨Q(a)
P(a)
∃xP (x)
(∃xP (x)) ∨ (∃xQ(x)) Q(a)
∃xQ(x)
(∃xP (x)) ∨ (∃xQ(x))
(∃xP (x)) ∨ (∃xQ(x)) (∃xP (x)) ∨ (∃xQ(x))
∃-I, 3 ∨-I, 4
∃-I, 6
∨-I, 7
∨-E, 2, 3–5, 6–8 ∃-E, 1, 2–9
Natural Number Induction
P (n) : 2(n + 2) ≤ (n + 2)2
P (0) : 2(0 + 2) ≤ (0 + 2)2 4≤4
Exercise 8
1. Prove, by natural number induction, that
holds for all natural numbers n ∈ N. Solution.
Base Case. For n = 0, we show that
This is obviously true.
Step Case. Let a be an arbitrary number. Then Assume P (a), that is
Prove P (a + 1), that is
2(a + 2) ≤ (a + 2)2 (IH) 2((a + 1) + 2) ≤ ((a + 1) + 2)2
2((a+1)+2)
Since the base and step cases are established, we can conclude that
∀n(2(n + 2) ≤ (n + 2)2) 4
=2((a+2)+1) =2(a+2)+2 ≤(a+2)2 +2 ≤a2+4a+6 ≤a2+6a+9 =((a+1)+2)2
(arith)
(arith)
(IH)
(arith)
(add the term 2n + 3) (arith)
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.
BaseCase.Weshowthatsumeven 0 = 0 * (0+1).
sumeven 0 = 0 = 0 * (0+1) — SE1 and arith StepCase.Assumethatsumeven n = n * (n+1)(IH).
Weshowthatsumeven (n+1) = (n+1) * ((n+1)+1).
sumeven (n+1)
=2*(n+1)+ sumeven (n+1-1) =2*n+2+ sumeven n =2*n+2+ n * (n+1) =2*(n+1)+ n * (n+1)
= (2 + n) * (n+1)
= (n+1) * ((n+1)+1)
— SE2
— arith
— IH
— arith
— arith
— arith
5
Appendix: Natural Deduction Rules Propositional Calculus
(∧I )
(∨I )
(→I)
(¬I )
(PC)
Predicate Calculus
pq p∧qp∧q (∧E )
p∧qpq
[p] [q] . .
ppp∨qrr
p∨q q∨p
[p] .
(∨E )
r
q pp→q (→ E)
p→q q
[p] .
F p ¬p (¬E )
¬p F
[¬p] .
F pT
(∀I )
∀x. P (x)
P (a) (a arbitrary) ∀x. P (x)
(T)
(∀E )
(∃I )
∃xP (x)
(∃E )
q (a arbitrary)
P (a) P (a)
[P (a)] .
∃xP (x)
q (aisnotfreeinq)
6