1

COMP S264F Unit 2:

Methods of Proof

Dr. Keith Lee

School of Science and Technology
Hong Kong Metropolitan University
 2

Overview
• Proof by inference rules
• Direct proof
• Indirect proof / Proof by contraposition
• Non-proof
• Proof by cases
➢ Exhaustive proof / Proof by exhaustion
• Proof by contradiction
• Mathematical induction
 3

Theroem
• A theorem (lemma) is a statement that can be shown to be true.
• A theorem often takes the following form:
➢p -----------
is true.
• e.g., 2 is an irrational number.
➢p → q -----------
is true.
• e.g., For any integer x, if x is a prime number and x > 3,
then  n (x = 6n - 1 or 6n + 1).
➢p  q -----------
is true.
• e.g., x ( x is a prime number and x > 3 if and only if
 n (x = 6n - 1 or 6n + 1)).

• A lemma is a theorem for helping prove another theorem. It is a

step in the direction of proof of another theorem.
 4

Proof
• A proof is a sequence of statements demonstrating a theorem
is true.
➢We want to a proof to be correct, precise, concise.

• Some of these statements are assumed to be true (axioms,

known fact, definitions), while the truth of other statements is
established based on logical deduction.
 5

Proof: Example
Prove: If  x y P(x, y), then y  x P(x, y).

1. Assume  x y P(x, y) .
2. y P(x0, y) , for some x0 .
3. y  x P(x, y).

Prove: If x  y P(x, y), then  y x P(x, y).

• Counterexample: Consider P(x, y) as x = y.

 6

Deduction / Inference Rules

Why?
Given: P  Q and  P  Q [(P  Q)  (P  Q)]  Q is a
Conclude: Q tautology.

Given: P  Q and Q  R Quiz:

Conclude: P  R Given:  P  false
Conclude: ______
Modus ponens
Given: P and P  Q Given:  P  P
Conclude: Q Conclude: ______

Modus tollens Given: P   P

Given: P  Q and  Q Conclude: ______
Conclude:  P

Recall that p  q is false only when p is true but q is false.

 7

More Inference Rules

Given: x P(x).
Conclude:  x P(x).

Given:  x P(x).
Conclude: P(x0), where x0 is a particular element (an
element, some element) in the domain.

Given: Let x0 be a particular element in the domain. P(x0).

Conclude:  x P(x).
 8

Proof by Inference Rules: Example 1

To prove a proposition p (to be true),
we can start with some proposition p’ that is
known to be true and show that p’  p (is true).
Then it follows that p is true. (Modus ponens)

This is equivalent to the tautology

[ p’  (p’  p) ]  p

Given:
• If you study in HKMU, you have a student card.
• You study in HKMU.
Conclude: You have a student card.
 9

Proof by Inference Rules: Example 2

Modus tollens
Given: p  q and  q
Conclude:  p

This is equivalent to the tautology

[(p  q)   q]   p

Given:
• If Tom studies in HKMU, Tom has a student card.
• Tom does not have a student card.
Conclude: Tom does not study in HKMU.
 10

Proof by Inference Rules: Example 3

Hypothetical Syllogism
Given: p  q and q  r
Conclude: p  r

This is equivalent to the tautology

[(p  q)  (q  r)]  (p  r)

Given:
• If you pass the course, then you pass the exam.
• If you pass the exam, then you have attended the exam.
Conclude: If you pass the course, then you have attended the exam.
 11

Proof by Inference Rules: Example 4

Disjunctive Syllogism
Given: p  q and  p
Conclude: q

This is equivalent to the tautology

[(p  q)   p]  q

Given:
• I study before exam or I fail the course.
• I do not study before exam.
Conclude: I fail the course.
 12

Proving a theorem in the form of p  q

Direct proof: To prove p  q, we assume that p is true,
then show that q is true.
Example: For any integer n, if n is odd, then n2 is odd.
Proof.
• Suppose that n is odd.
• Then, n = 2k + 1 for some integer k.
• It follows that
n2 = (2k+1)2 = (2k)2 + 2(2k)(1) + 12
= 4k2 + 4k + 1
= 2(2k2 + 2k) + 1
• Therefore, n2 is odd.
 13

Indirect Proof / Proof by Contraposition

• Note that p  q is equivalent to  q   p (contrapositive).
• To prove “p  q”, we can prove “ q   p”.

Example 1: For any integer n, if 3n + 2 is odd, then n is odd.

Proof. Assume that n is even (i.e., not odd).
Then 3n, as well as 3n+2, is even (i.e., not odd).
Therefore, 3n + 2 is odd  n is odd.

Example 2: For any integer n, if n2 is even, then n is even.

Proof. We proved its contrapositive in the previous slide:
If n is odd, then n2 is odd.
Therefore, if n2 is even, then n is even.
 14

Non-proof
• Failure to note the justification for each step can lead
easily to non-proofs.

Theorem. (not!) 1 = -1
2
Proof. 1 = 1 = −1 −1 = −1 −1 = −1 = −1.

• At least one of the above steps is false, but each looks

reasonable to the author of the proof.
• Writing out the full justifying axioms for each step reveals:
it is not incorrect that for any x and y, 𝑥𝑦 = 𝑥 𝑦.
 15

Proof by Cases
• To prove “p1  p2  …  pn  q” is true, we note that

p1  p2  …  pn  q
  (p1  p2  …  pn)  q
 ( p1   p2  …   pn)  q [by De Morgan’s law]
 ( p1  q)  (  p2  q )  …  ( pn  q) [by distributive law]
 (p1  q)  (p2  q )  …  (pn  q)

• That means, we should prove each (pi  q) one by one.

 16

Proof by Cases: Example

(more commonly written as “n2  1 mod 3”).

If n is an integer not divisible by 3, then n2 mod 3 = 1.

 If (n mod 3 = 1 or n mod 3 = 2), then n2 mod 3 = 1.
 If (n mod 3 = 1), then n2 mod 3 = 1, and if (n mod 3 = 2),
then n2 mod 3 = 1.
Case 1: If n mod 3 = 1, n = 3k + 1 for some integer k.
It follows that n2 = (3k+1)2 = 9k2 + 6k + 1 = 3(3k2 + 2k) + 1.
Therefore, n2 mod 3 = 1.
Case 2: If n mod 3 = 2, n = 3k + 2 for some integer k.
It follows that n2 = (3k+2)2 = 9k2 + 12k + 4 = 3(3k2 + 4k + 1) + 1.
Therefore, n2 mod 3 = 1.
 17

Exhaustive proof / Proof by Exhaustion

• Exhaustive proof is a special type of proof by cases, where
each case involves checking a single example.

Example: All integers between 10 and 15 exclusive are not

square of another integer.
Proof.
• The numbers between 10 and 15 exclusive 11, 12, 13,14.
• We can check each of these numbers and show that
•
11 ≈ 3.316
12 ≈ 3.464
13 ≈ 3.605
14 ≈ 3.741
 18

Proof by contradiction
• A popular way to prove a proposition.

To prove p, we show that “ p  false” is true.

Note that “ p  false” is equivalent to p.
Thus, it follows that p is true.

• More specifically, we show that for some proposition r,

 p  (r and  r) (is true).
• Note that (r and  r)  false.
• Therefore,  p  false (is true).

• NB. We say that a contradiction occurs when both r and

 r can be deduced.
 19

Proof by contradiction: Example

Definition. A real number is rational if and only if it can be
expressed as a quotient of two integers with a non-zero
denominator. More formally, if r is a real number, then
𝒂
r is rational   integers a, b such that 𝒓 = and b > 0
𝒃

Theorem. 2 is irrational (i.e., not a rational number).

Proof plan:
Assume 2 is rational.
2 = a/b for some integers a, b >0
such that
• a, b are relatively prime (i.e., don’t have a common factor except 1).
false
• a, b are not relatively prime.
 20

Proof by contradiction: Example (cont’)

Theorem. 2 is irrational (i.e., not a rational number).
Proof.
Suppose, for the sake of contradiction, 2 is rational.
𝑎
 integers a, b > 0 such that 2= and a, b are relatively prime.
𝑏
Thus, 2𝑏 = 𝑎  2𝑏 2 = 𝑎2  a2 is even.
In slide 12, we have shown that: If a2 is even, then a is even.
Therefore, a is even. (modus ponens)
 a = 2c for some integer c.
 b2 = a2/2 = (4c2)/2 = 2c2
 b is also even.
As both a and b are even, they have a common factor of 2 and
are not relatively prime. A contradiction occurs.
 21

Puzzle: Halting problem

Is it possible to write a Python function H that
• takes two inputs (arguments): a Python function (binary
string) P and an input (binary string) x;
• and reports “loop forever” if P loops forever with input x,
and “halt” if P halts eventually ?

Program P Program H Output “halt” or

Input x “loop forever”

Theorem. There doesn’t exist such a function H.

 22

Program P Program H Output “halt” or

Input x “loop forever”

Proof. Suppose, for the sake of contradiction, that H exists.

We construct another function K that takes only one input, which

is a Python function P, and works as follows:
1. Call H(P, P)
2. Then, do the following based on the output of H(P, P):
• if H(P, P) returns “halt”, K executes a simple loop forever;
(e.g., b = 2
while b <= 2:
a = 1 )
• if H(P, P) returns “loop forever”, K halts immediately.

PS. H takes two inputs, and K takes one input only.

 23

Program P Program H Output “halt” or

Input x “loop forever”

Proof. Suppose, for the sake of contradiction, that H exists.

Program K
H reports loop
“halt”
P H(P, P)
H reports
“loop forever”
exit

Fact. K(P) does not loop forever.

if and only if
H(P, P) reports “loop forever” (by definition of K)
if and only if
P, when given P as input, loops forever (by definition of H)
 24

Puzzle: Halting problem - Contradiction

Program K
H reports loop
“halt”
P H(P, P)
H reports
“loop forever”
exit

Consider running the function K with K as input.

K(K) either loops forever or halts.

• K(K) loops forever: This happens only when H(K, K) reports

“halt”; i.e., K(K) does not loop forever.

• K(K) halts: This happens only when H(K, K) reports “loop

forever”, i.e., K(K) does not halt.

In both cases, contradiction occurs. Therefore, H cannot exist.

 25

Example: Barber paradox

A town has only 1 male barber. A man in the town is shaved by
the barber if and only if he does not shave himself.

Theorem. Such a barber does not exist.

Assume, for the sake of contradiction, that such a barber exists.

Denote this barber by B.

Does B shave himself?

• Yes: B doesn’t shave himself.
• No: B shaves himself.
 26

Proving a theorem in the form of p  q

(revisited)
• We can also use proof by contradiction.
• p  q is false  p is true and q is false.
• We can show that
(p  q)  (r and  r) for some r.

• N.B. “r and  r” is a contradiction (i.e., always false).

Example 2: For any integer n, if n2 is even, then n is even.

Proof. Assume that n2 is even and n is odd.
Thus, n = 2k + 1 for some k.
Then, n2 = (2k+1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1.
Thus, n2 is odd, which contradicts that n2 is even.
 27

Proving a theorem in the form of p  q

(Summary)
In summary, three possible ways to prove p  q:

• Assume p. … q.

• Assume q. … p.

• Assume p and q. … r and r. A contradiction occurs.

 28

Proving a theorem in the form of p  q

To prove p  q, there are many possible ways.

• First assume p. … q. That is, p  q.

And then assume q. … p. That is, q  p.

• First assume p. … q. That is, p  q.

And then assume p. … q. That is, p  q.

• p  r1  r2  …  q.

• ...
 29

Recap: Negation
Is ( x P(x) ) equivalent to  x P(x) ?
I.e., ( x P(x) )   x P(x) is true or false?

• YES.
• Suppose “( x P(x) )” is true.
x P(x) is false.
There exists x such that P(x) is false.
“ x P(x)” is true.

• Suppose “( x P(x) )” is false.

x P(x) is true.
“ x P(x)” is false.
 30

Mathematical Induction
• Many theorems have the form P(n) for all positive integers n.

• A proof by mathematical induction consists of two steps:

• Basis step (base case): P (1) is true.
• Induction step: for any positive integer i, if P (i) is true,
then P (i+1) is true.
Induction
hypothesis
• When we complete both steps, we have proved that
P(n) is true for all positive integers n.
• Why?
 31

Why Mathematical Induction works?

Let k be any integer. Is P(k) true?

• P(1) (is true).

• P(1)  P(2).
• Thus, P(2).
• P(2)  P(3).
• Thus, P(3).
• P(3)  P(4).
• Thus, P(4).
•…
• Thus, P(k).
 32

Mathematical Induction: Example

Show that any 2n x 2n chessboard with one square removed
can be covered using L-shaped pieces
(each occupying 3 squares) only.

n=2 n=2
n=1
 33

Mathematical Induction: Proof

• Basis step, n = 1: No matter where the missing square is, the
remaining three squares can be covered by one L-shaped piece.

• Inductive step: Assume the claim is true for some n ≥ 1.

Consider a chessboard of size 2n+1 x 2n+1.
➢ Divide the board into 4 quadrants, each containing 2n x 2n
squares.

By the induction hypothesis, the quadrant

containing the missing square can be covered
using L-shaped pieces.

What about the remaining three?

 34

Mathematical Induction: Proof (cont’)

Cover the center using one L-shaped piece.

Then apply the induction hypothesis to cover each

individual quadrant using L-shaped pieces.
 35

Inductive Step
Inductive step: for any positive integer i, if P(i) is true, then
P(i+1) is true.

Another form of inductive step: for any positive integer i, if

P(1)  P(2)  …  P(i) is true, then P(i+1) is true.

Both forms of inductive step can lead to the same conclusion

(i.e., P(n) is true for all n). However in some cases, the
second form is easier to prove.
 36

Example: Big O Notation

• Consider an algorithm A.
• Let f(n) be the number of steps required by an algorithm A
when the input is of size n.
• When we way f(n) = O(n), what does it mean?

• What is O(n)? E.g., 66 n, 23n+1234, 100n, log n, …

• Roughly speaking, f(n) = O(n) if f(n) is at most n multiplied by
a constant.

• Example: MergeSort takes O(n log n) steps to sort n numbers.

 37

Induction
• The following mathematical induction shows that
n2 = O(n)

• Basis step: n = 1, 1 = O(1)

• Induction step:
If n2 = O(n), then
(n+1)2 = n2 + 2n + 1 = O(n) + 2n + 1 = O(n)
 38

Big O Notation: Definition

In general, if a function f(n) = O(n log n), what does it mean?

• Asymptotically, f(n) is at most n log n multiplied by a constant.

(E.g., f(n) = 3 n log n + 1000).

• There exists a constant c such that for all n, f(n) ≤ c n log n.

 c  n f(n) ≤ c n log n. (Too restricted!)

• There exists a constant c such that for all sufficiently large n,

f(n) ≤ c n log n.
 c  no  n if n > no then f(n) ≤ c n log n.