How to submit:

Submit before actual tutorial time for it to be graded. There are 2 ways to do this:
1. There is a submission box on Canvas for you to submit your document. Either .docx, .pdf, or a picture of your written solutions are acceptable as long as we can read your attempts.
2. Submit your written attempts in-person during our tutorial.

Official due date for submission: 10 Feb 2026, 11:59 PM or during tutorial itself.

Collaboration Policy:

You may discuss high-level ideas with your classmates or friends. You should list your collaborators if you do so.
Do not share your solutions.
ChatGPT (and other LLMs) are not allowed.
Your submission must be of your own write-up.

Late Policy:

< 1 week after submission deadline: 50% penalty
< 2 weeks after submission deadline: 75% penalty
No submissions after 2 weeks.

Overview

This tutorial gives practice questions to be discussed during the relevant tutorial in person. This particular tutorial sheet corresponds to Unit 1 Part 3. It is recommended to either watch the lectures or read the notes for each respective parts before attempting the tutorial sheet.

All the questions here are related to proofs.

Questions 1 and 5 are graded for participation.

That said, we encourage you to try all the questions. This way, when you come for tutorials we can make the best use of your time since you can either verify your solutions, or understand the discussions when our tutors go through the solutions.

Question 1 [Graded for Participation]:

For the following proofs, fill in the blanks with the corresponding rule of deduction used, quoting the appropriate line numbers where necessary.

Sub-part 1

Proof: $\forall x, y \in N [(x = 0) \lor (y = 0) \to (x y = 0)]$

Let $x, y \in N$ be arbitrarily chosen.

Suppose $(x = 0) \lor (y = 0)$ .

Case 1: Assume $x = 0$ .

$x y = 0 \cdot y = 0$ . [ (a) Rule of deduction: Basic algebra ]

Case 2: Assume $y = 0$ .

$x y = x \cdot 0 = 0$ . [ (b) Rule of deduction: Basic algebra ]

In all cases, we have $x y = 0$ . [ (c) Rule of deduction: Proof by cases on lines 2, 3.1, 4.1 ]

$(x = 0) \lor (y = 0) \to (x y = 0)$ . [ (d) Rule of deduction: Implication introduction on lines 2 and 5 ]

$\forall x, y \in N [(x = 0) \lor (y = 0) \to (x y = 0)]$ . [ (e) Rule of deduction: Universal generalisation on lines 1 and 6 ]

Sub-part 2

Proof: $\forall n \in N [n + 1 \neq = 0]$

Let $n \in N$ be arbitrarily chosen.

Suppose, for the sake of contradiction, that $\neg (n + 1 \neq = 0)$ .

$n + 1 = 0$ . [Logically equivalent to line 2]

$n = - 1$ . [Basic algebra]

$\neg (n \in N) .$ [Basic algebra]

$(n \in N) \land \neg (n \in N)$ . [ (f) Rule of deduction: Conjunction on lines 1 and 2.3 ]

$⊥$ . [ (g) Rule of deduction: Contradiction rule on line 2.4 ]

$n + 1 \neq = 0$ . [ (h) Rule of deduction: Proof by contradiction on line 2.5 ]

$\forall n \in N [n + 1 \neq = 0]$ . [Universal generalisation on lines 1 and 3]

Question 2:

For each of the following proofs, identify where there were incorrect/missing steps of justification, and discuss potential corrections to them.

Sub-part 1

Proof: $\forall x \in Z, \exists y \in Z [y > x]$

Let $y = x + 1$ .

Since $x + 1 > x$ , $y > x$ . [Basic algebra]

$\forall x \in Z, \exists y \in Z [y > x]$ . [Existential generalisation on line 2]

Missing a line introducing $x$ as a variable and not explaining which domain it draws from. Missing a universal instantiation rule. In general, the last line itself is actually packing multiple things into a single line. But it’s not following what the existential generalisation rule is doing.

Sub-part 2

For any integer $x$ , we define the predicate $e v e n (x)$ to be the following:

e v e n (x) \equiv \exists k \in Z [x = 2 k]

Proof: $\forall x \in Z [e v e n (x) \to e v e n (x^{2})]$

Let $x$ be arbitrarily chosen.

Suppose $e v e n (x)$ .

Let $x = 2 k$ . [Instantiation on line 2]

Then $x^{2} = 2 m$ , where $m = k^{2}$ . [Basic algebra]

Therefore $e v e n (x^{2})$ . [Definition of $e v e n$ ]

On line 1, we didn’t specify which domain $x$ is drawn from. We’re skipping the step of first unpacking the definition. Line 4 has done the algebra wrong, $m$ should be $2 k^{2}$ . At the end of the proof, we need to finish the proof with 2 more lines by re-introducing the implication, and then applying universal generalisation.

Sub-part 3

Proof: $\forall n \in Z [2 n \neq = 1]$

Suppose, for the sake of contradiction, that $\exists n \in Z [2 n = 1]$ .

Let $n \in Z$ be such that $2 n = 1$ . [Universal instantiation on line 1]

But multiplying any number by $2$ gives an even number and $1$ is not even, so this is impossible. [Contradiction]

$\forall n \in Z [2 n \neq = 1]$ . [Proof by contradiction on line 3]

The biggest issue to focus on here is that line 3 is in English and we’re not really applying the contradiction rule to obtain a contradiction here. It’s not really following the proof system on how to actually obtain a contradiction.

Question 3:

Fill in the missing steps in the following proof, given the rules of deduction.

You may use the following lemma in your proof:

Lemma

$\forall x \in Z [e v e n (x) \lor o dd (x)]$ .

We also define the following predicate:

o dd (x) \equiv \exists k \in Z [x = 2 k + 1]

Proof: $\forall n \in Z [e v e n (n^{2} + 3 n)]$

Let $n \in Z$ be arbitrarily chosen.

$e v e n (n) \lor o dd (n)$ . [Universal instantiation of given lemma]

Case 1: $e v e n (n)$ .

$\exists k \in Z [n = 2 k]$ . [Definition of $e v e n$ ]

Let $p \in Z$ be such that $n = 2 p$ . [Existential instantiation on line 3.1]

$n^{2} + 3 n = (2 p)^{2} + 3 (2 p) = 4 p^{2} + 6 p = 2 (2 p^{2} + 3 p)$ . [Basic algebra]

Since $p \in Z$ , we know that $2 p^{2} + 3 p \in Z$ . [Basic algebra]

$\exists k \in Z [n^{2} + 3 n = 2 k]$ . [Existential generalisation on line 3.4]

$e v e n (n^{2} + 3 n)$ . [Definition of $e v e n$ ]

Case 2: $o dd (n)$ .

$\exists k \in Z [n = 2 k + 1]$ . [Definition of $o dd$ ]

Let $q \in Z$ be such that $n = 2 q + 1$ . [Existential instantiation on line 4.1]

$n^{2} + 3 n = (2 q + 1)^{2} + 3 (2 q + 1) = 4 q^{2} + 4 q + 1 + 6 q + 3 = 2 (2 q^{2} + 5 q + 2)$ . [Basic algebra]

Since $q \in Z$ , we know that $2 q^{2} + 5 q + 2 \in Z$ . [Basic algebra]

$\exists k \in Z [n^{2} + 3 n = 2 k]$ . [Existential generalisation on line 4.4]

$e v e n (n^{2} + 3 n)$ . [Definition of $e v e n$ ]

In all cases, $e v e n (n^{2} + 3 n)$ . [Proof by cases on lines 2, 3.6, 4.6]

$\forall n \in Z [e v e n (n^{2} + 3 n)]$ . [Universal generalisation on lines 1 and 5]

Question 4:

For this question, we refer to the following definition of rational numbers:

x \in Q \equiv \exists p \in Z, \exists q \in Z [q \neq = 0 \land x = \frac{p}{q}]

Prove the following statement:

\forall n \in Z [n \in Q]

Solution

Let $n \in Z$ be arbitrarily chosen.

$1 \in Z$ . [Basic algebra]

$n = \frac{n}{1}$ . [Basic algebra]

$1 \neq = 0$ . [Basic algebra]

$1 \neq = 0 \land n = \frac{n}{1}$ . [Conjunction on lines 3 and 4]

$\exists p \in Z, \exists q \in Z [q \neq = 0 \land n = \frac{p}{q}]$ . [Existential generalisation on line 5]

$n \in Q$ . [Definition of $Q$ ]

$\forall n \in Z [n \in Q]$ . [Universal generalisation on lines 1 and 7]

Question 5 [Graded for Participation]:

Prove the following statement:

\forall m \in Z, \forall n \in Z [e v e n (mn) \to (e v e n (m) \lor e v e n (n))]

You may use the following theorems:

Theorem

$\forall x \in Z [\neg e v e n (x) \equiv o dd (x)]$ .

Theorem

$\forall x \in Z [\neg o dd (x) \equiv e v e n (x)]$ .

Solution

Let $m \in Z$ and $n \in Z$ be arbitrarily chosen.

Assume that $\neg (e v e n (m) \lor e v e n (n))$ .

$\neg e v e n (m) \land \neg e v e n (n)$ . [Logically equivalent to line 2]

$\neg e v e n (m)$ [Specialisation on line 2.1]

$\neg e v e n (n)$ [Specialisation on line 2.1]

$\forall x \in Z [\neg e v e n (x) \equiv o dd (x)]$ [Using Lemma 1]

$o dd (m)$ [Universal instantiation on line 1, 2.2]

$o dd (n)$ [Universal instantiation on line 1, 2.3]

$\exists k \in Z [m = 2 \cdot k + 1]$ . [Definition of $o dd$ ]

Let $s \in Z$ be such that $m = 2 \cdot s + 1$ . [Existential instantiation on lines 1, 2.7]

Let $t \in Z$ be such that $n = 2 \cdot t + 1$ . [Existential instantiation on line 1, 2.7]

$mn = (2 s + 1) (2 t + 1) = 4 s t + 2 s + 2 t + 1 = 2 \cdot (2 s t + s + t) + 1$ . [Basic algebra, from lines 2.8 and 2.9]

Since $s, t \in Z$ , $2 s t + s + t \in Z$ . [Basic algebra, from line 2.10]

$\exists k \in Z [mn = 2 \cdot k + 1]$ . [Existential generalisation on lines 2.10 and 2.11]

$o dd (mn)$ . [Definition of $o dd$ on line 2.12]

Since $m \in Z \land n \in Z$ , $mn \in Z$ [Basic algebra]

$\neg e v e n (mn)$ . [Universal instantiation on line 2.14, 2.4]

$\neg (e v e n (m) \lor e v e n (n)) \to \neg e v e n (mn)$ . [Implication introduction on lines 2 and 2.13]

$e v e n (mn) \to (e v e n (m) \lor e v e n (n))$ . [Logically equivalent to line 3]

$\forall m \in Z, \forall n \in Z [e v e n (mn) \to (e v e n (m) \lor e v e n (n))]$ , [Universal generalisation on lines 1 and 4]

Question 6:

Prove the following statement:

Theorem

$\forall x \in Z [\neg (e v e n (x) \land o dd (x))]$

Solution

Proof:

Let $x \in Z$ be arbitrarily chosen.

Assume for the sake of contradiction that $\neg (\neg (e v e n (x) \land o dd (x)))$ .

$(e v e n (x) \land o dd (x)$ . [Double negation on line 2]

$e v e n (x)$ . [Specialisation on line 2.1]

$\exists k \in Z [2 k = x]$ . [Unpacking definition of $e v e n$ ]

Let $s \in Z$ be such that $2 s = x$ . [Existential instantiation on line 2.3]

$o dd (x)$ . [Specialisation on line 2.1]

$\exists j \in Z [2 j + 1 = x]$ . [Unpacking definition of $o dd$ ]

Let $t \in Z$ be such that $2 t + 1 = x$ . [Existential instantiation on line 2.6]

Then, we have $2 s = 2 t + 1$ . [Basic algebra, from lines 2.4 and 2.7]

$2 (s - t) = 1$ . [Basic algebra]

$s - t = \frac{1}{2}$ . [Basic algebra]

$\neg (s - t \in Z)$ . [Basic algebra, from line 2.10]

Since $s \in Z$ and $t \in Z$ , we have $s - t \in Z$ . [By basic algebra, from lines 2.4 and 2.7]

$(s - t \in Z) \land \neg (s - t \in Z)$ . [Conjunction on lines 2.11 and 2.12]

$⊥$ . [Contradiction rule on line 2.13]

$\neg (e v e n (x) \land o dd (x))$ . [Proof by contradiction rule on line 2.14]

$\forall x \in Z [\neg (e v e n (x) \land o dd (x))]$ . [Universal generalisation on lines 1 and 3]

Note: There’s actually quite a few ways to do this question. But generally, the “most natural” way will probably have you deriving a contradiction somehow.

Question 7 [Bonus]:

You are tasked with building a load balancer that services $C$ clients, and has to balance them between $S$ servers. All clients will request to be serviced at the same time at the start of the day, and the load balancer must assign each client a server immediately at the start of the day.

Your boss tells you to keep costs down, that each server must service fewer than $\frac{C}{S}$ clients in total. Let $c_{i}$ be the number of clients that the $i^{t h}$ server has to service, i.e., $c_{1}$ is the number of clients for the first server, $c_{2}$ is the number of clients for the second server, and so on. Since we have $S$ servers, we have quantities $c_{1}, c_{2}, \dots, c_{S}$ .

Question: Prove to yourself and your boss that this is impossible.

Solution:

Before we begin the proof, let’s formalise what the question wants us to prove. We need to show that the following statement is true:

Given $C \in N, S \in N, c_{1} \in N, c_{2} \in Z, \dots, c_{S} \in N$ such that $(C > 0) \land (\sum_{i = 1}^{S} c_{i} = C)$ , and the set $[S] = {1, 2, \dots, S}$ (refer to this section for an explanation of this notation),

$\neg (\forall i \in [S] [c_{i} < \frac{C}{S}])$

Essentially, that it is impossible (indicated by the " $\neg$ " symbol) for all servers to service fewer than $\frac{C}{S}$ clients. Now that we have a concrete statement down, we can continue proving it:

Solution

Proof:

Let $c_{1}, c_{2}, \dots, c_{S} \in N$ , arbitrarily chosen, be such that $\sum_{i = 1}^{S} c_{i} = C$ .

Assume for the sake of contradiction that $\forall i \in [S] [c_{i} < \frac{C}{S}]$ .

Then, we must have that $c_{1} < \frac{C}{S}$ , $c_{2} < \frac{C}{S}$ , $\dots$ , $c_{S} < \frac{C}{S}$ . [Universal instantiation on line 2.1]

$\sum_{i = 1}^{S} c_{i} = c_{1} + c_{2} + \dots + c_{S} < \frac{C}{S} + \frac{C}{S} + \dots + \frac{C}{S} = S \cdot \frac{C}{S} = C$ . Rewriting this (for presentation’s sake), we have $\sum_{i = 1}^{S} c_{i} < C$ . [Basic algebra]

In particular, $\neg (\sum_{i = 1}^{S} c_{i} = C)$ . [Basic algebra]

$(\sum_{i = 1}^{S} c_{i} = C) \land \neg (\sum_{i = 1}^{S} c_{i} = C)$ . [Conjunction on lines 1 and 2.3]

$⊥$ . [Contradiction rule on line 2.4]

$\neg (\forall i \in [S] [c_{i} < \frac{C}{S}])$ . [Proof by contradiction rule on line 2.5]

Therefore, $\forall c_{1}, c_{2}, \dots, c_{S} \in N [\neg (\forall i \in [S] [c_{i} < \frac{C}{S}])]$ [Universal generalisation on lines 1 and 3]

Thus, such a task is impossible.

Mathematical Techniques for Computing

Explorer

Tutorial 2 Solutions

How to submit:

Collaboration Policy:

Late Policy:

Overview

Question 1 [Graded for Participation]:

Sub-part 1

Sub-part 2

Question 2:

Sub-part 1

Sub-part 2

Sub-part 3

Question 3:

Question 4:

Question 5 [Graded for Participation]:

Question 6:

Question 7 [Bonus]:

Graph View

Table of Contents

Backlinks