xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

Propositional Logic代写-S2 2022

时间：2022-09-03

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

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