FIT2014 Theory of Computation Lecture 4 Proofs
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 4
Proofs
slides by Graham Farr
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 27
Overview
I Finding proofs
I Proof by construction
I Proof by cases
I Proof by contradiction
I Proof by induction
I inductive basis
I inductive step
I conclusion
2 / 27
Proof (recap)
I A step-by-step argument that establishes, logically and with certainty, that
something is true.
I Should be verifiable.
I Must be finite.
I Every statement must be:
I something you already know at the start
I a definition
I an axiom
I a previously-proved theorem
or
I a logical consequence of some conjunction of previous statements.
3 / 27
Proof (recap)
If you’ve previously established P,
and also that P ⇒ Q
then you can deduce Q.
(modus ponens)
Exercise in Boolean algebra: Prove that (P ∧ (P ⇒ Q) ) ⇒ Q is a tautology.
If you’ve previously established all of P1,P2, . . . ,Pn
and also that (P1 ∧ P2 ∧ · · · ∧ Pn)⇒ Q
then you can deduce Q.
4 / 27
Finding proofs
There is no systematic method for finding proofs for theorems.
There are deep theoretical reasons for this.
(Gödel, 1931; Church, 1936; Turing, 1936)
Discovering proofs is an art as well as a science. It requires
I skill at logical thinking and reasoning
I understanding the objects you’re working with
I practice, experience
I play, exploration
I creativity and imagination
I perseverence
5 / 27
Finding proofs: general advice
To prove subset relations, A ⊆ B (where A and B are sets):
1. Take a general member of A, and give it a name. e.g., “Let x ∈ A”
2. Use the definition of A to say something about x .
3. Follow through the logical consequences of that,
4. . . . aiming to prove that x also satisfies the definition of B.
See, e.g., Lecture 1, slide 30, proof that DOUBLEWORD ⊆ EVEN-EVEN.
See also: Tutorial 1, exercise 1.
6 / 27
Finding proofs: general advice
To prove set equality, A = B (where A and B are sets):
1. Prove A ⊆ B
2. Prove A ⊇ B
To prove numerical equality, A = B (where A and B represent numbers):
If algebra can transform A to B, then that’s good;
but if not:
1. Prove A ≤ B
2. Prove A ≥ B
7 / 27
Types of proofs
I Proof by construction
I Proof by cases
I Proof by contradiction
I Proof by induction
This list is not exhaustive.
Proofs can be quite individual in character and hard to classify,
although many will follow one of the above patterns.
Many proofs are a mix of these types.
8 / 27
Proof by construction
. . . also known as:
Proof by example
I can be used where the theorem asserts the existence of some object with a
specific property just give the example, show it has the property.
I BUT: an illustration is NOT a proof.
I So, if your example merely illustrates the idea of a proof, then it is not, itself, a
proof (although it might still be useful in illustrating a proof).
I Recall Lecture 1: English has a palindrome.
9 / 27
Proof by cases
. . . also known as:
Proof by exhaustion
or (if lots of cases) “brute force”
I identify a number of different cases which cover all possibilities
I Prove the theorem for each of these cases.
I Recall Lecture 1:
Every English word has a vowel or a “y”.
10 / 27
Proof by contradiction
(also known as: “reductio ad absurdum”)
I Start by assuming the negation of the statement you want to prove.
I Deduce a contradiction.
I Therefore, the statement must be true.
11 / 27
Proof by contradiction
Theorem.
The statement “This statement is false” is not a proposition.
Proof.
Assume that it is a proposition.
Then it must be either true or false.
If it is true, then it is false.
If it is false, then it is true.
So, it is false if and only if it is true.
This is a contradiction.
So our assumption, that the statement is a proposition, must be false.
12 / 27
Proof by contradiction
“Every positive integer was one of his personal friends.”
— J. E. Littlewood on Srinivasa Ramanujan, quoted by G. H. Hardy, Srinivasa Ramanujan (obituary),
Proceedings of the London Mathematical Society 19 (1921) xl–lviii. See p. lvii.
Srinivasa Ramanujan
(1887–1920)
https://mathshistory.st-andrews.
ac.uk/Biographies/Ramanujan/
Theorem.
Every natural number is interesting.
Proof.
Assume that not every natural number is interesting.
So, there exists at least one uninteresting number.
Therefore there exists a smallest uninteresting number.
But that number must be interesting, by virtue of having
this special property of being the smallest of its type.
This is a contradiction, as this number is uninteresting.
Therefore our original assumption was wrong.
Therefore every natural number is interesting.
See, e.g., Ch. 14 (Fallacies), in: Martin Gardner,
The Scientific American Book of Mathematical
Puzzles and Diversions, Simon & Schuster, New
York, 1959.
13 / 27
https://mathshistory.st-andrews.ac.uk/Biographies/Ramanujan/
https://mathshistory.st-andrews.ac.uk/Biographies/Ramanujan/
Proof by contradiction
Comments:
That “theorem” and “proof” is really just an informal argument, as the meaning of
“interesting” is imprecise and subjective.
But it illustrates the structure of proof by contradiction.
It also illustrates the point that, if you know a set of objects is nonempty, then you can
choose an element of smallest size in the set.
Often, the smallest object in a set may have special properties that can help you go
further in the proof.
Can you always choose an object of largest size in a nonempty set?
Is every integer interesting?
Would the above proof still work, if applied to the set of all integers?
14 / 27
More proofs
Recall De Morgan’s Laws:
¬(P ∨ Q) = ¬P ∧ ¬Q
¬(P ∧ Q) = ¬P ∨ ¬Q
We proved these using truth tables.
But, how to prove its extended form? . . .
For all n:
¬(P1 ∨ · · · ∨ Pn) = ¬P1 ∧ · · · ∧ ¬Pn
15 / 27
More proofs
Theorem.
For all n:
¬(P1 ∨ · · · ∨ Pn) = ¬P1 ∧ · · · ∧ ¬Pn
First proof:
Left-Hand Side is True
if and only if P1 ∨ · · · ∨ Pn is False
if and only if P1, . . . ,Pn are all False
if and only if ¬P1, . . . ,¬Pn are all True
if and only if Right-Hand Side is True.
Let’s try for a different proof, using De Morgan’s Law.
16 / 27
More proofs
Theorem.
For all n:
¬(P1 ∨ · · · ∨ Pn) = ¬P1 ∧ · · · ∧ ¬Pn
Second proof (attempt):
¬(P1 ∨ · · · ∨ Pn)
= ¬((P1 ∨ · · · ∨ Pn−1) ∨ Pn) (just grouping . . . )
= ¬(P1 ∨ · · · ∨ Pn−1) ∧ ¬Pn (by De Morgan’s Law)
= . . . and so on and so on . . .
= ¬P1 ∧ · · · ∧ ¬Pn Q.E.D.??
Good try, but reader has to infer how to fill the gap.
It’s shorthand for a “proof” whose length depends on n.
But we can turn its main idea into a proper proof.
17 / 27
Proof by mathematical induction
Suppose you want to prove that a statement S(n) holds for every natural number n.
Principle of Mathematical Induction
IF S(1) is true (inductive basis)
AND ∀k : if S(k) is true︸ ︷︷ ︸
inductive
hypothesis
, then S(k + 1) is true (inductive step)
THEN
∀n : S(n) is true.
S(1), . . . . . . ,S(n),S(n + 1), . . . . . .
18 / 27
Proof by mathematical induction
Theorem.
For all n:
¬(P1 ∨ · · · ∨ Pn) = ¬P1 ∧ · · · ∧ ¬Pn
Second proof: We prove it by induction on the # of propositions.
Inductive basis:
It is trivially true when we have just one proposition:
¬P1 = ¬P1 . . .!
Inductive step:
Suppose it’s true for k propositions:
¬(P1 ∨ · · · ∨ Pk) = ¬P1 ∧ · · · ∧ ¬Pk
(This our Inductive Hypothesis. We will use it later.)
19 / 27
Proof by mathematical induction
(continued)
We have:
¬(P1 ∨ · · · ∨ Pk+1)
= ¬((P1 ∨ · · · ∨ Pk) ∨ Pk+1) (just grouping . . . )
= ¬(P1 ∨ · · · ∨ Pk) ∧ ¬Pk+1 (by De Morgan’s Law)
= ¬P1 ∧ · · · ∧ ¬Pk ∧ ¬Pk+1 (by Inductive Hypothesis)
Conclusion:
So, by the Principle of Mathematical Induction, it’s true for any number of propositions.
20 / 27
Proof by mathematical induction
Theorem.
For all n:
1 + · · ·+ n =
n(n + 1)
2
.
Proof: We prove it by induction on n.
Inductive basis:
When n = 1, LHS = 1 and RHS = 1(1+1)/2 = 1. X
Inductive step:
Suppose it’s true for n = k :
1 + · · ·+ k = k(k + 1)/2
We will deduce that it’s true for n = k + 1.
1 + · · ·+ (k + 1) = (1 + · · ·+ k) + (k + 1) (preparing to use the inductive hypothesis)
21 / 27
Proof by mathematical induction
1 + · · ·+ (k + 1) = (1 + · · ·+ k) + (k + 1) (preparing to use the inductive hypothesis)
= k(k + 1)/2 + (k + 1) (by the Inductive Hypothesis)
= (k + 1)k/2 + (k + 1) (algebra . . . )
= (k + 1)(k/2 + 1)
= (k + 1)(k + 2)/2
= (k + 1)((k + 1) + 1)/2
This is just the equation in the Theorem, for n = k + 1 instead of k .
So the inductive step is now complete. X
Conclusion:
Therefore, by the Principle of Mathematical Induction, the equation holds for all n.
22 / 27
Proof by mathematical induction
Alternatively, we could make the inductive step go from n = k − 1 to n = k , instead
of from n = k to n = k + 1.
Slightly different proof: We prove it by induction on n.
Inductive basis:
When n = 1, LHS = 1 and RHS = 1(1+1)/2 = 1. X
Inductive step:
Suppose it’s true for n = k − 1, where k ≥ 2:
1 + · · ·+ (k − 1) = (k − 1)k/2
We will deduce that it’s true for n = k .
1 + · · ·+ k = (1 + · · ·+ (k − 1)) + k (preparing to use the inductive hypothesis)
23 / 27
Proof by mathematical induction
1 + · · ·+ k = (1 + · · ·+ (k − 1)) + k (preparing to use the inductive hypothesis)
= (k − 1)k/2 + k (by the Inductive Hypothesis)
= k(k − 1)/2 + k (algebra . . . )
= k((k − 1)/2 + 1)
= k(k + 1)/2
This is just the equation in the Theorem, for n = k instead of k − 1.
So the inductive step is now complete. X
Conclusion:
Therefore, by the Principle of Mathematical Induction, the equation holds for all n.
24 / 27
Proof by mathematical induction
Exercise:
Prove by induction that, for all n:
12 + · · ·+ n2 =
n(n + 1)(2n + 1)
6
.
Something to think about:
the relationship between induction and recursion
25 / 27
Proof by mathematical induction
Contrast with “induction” in statistics, which is the process of drawing general
conclusions from data.
Statistical induction is typically used in situations where there is some randomness in
the data.
Statistical induction cannot be used as a step in a mathematical proof.
Mathematical induction is a rigorous and very powerful tool for proofs in mathematics
and computer science.
26 / 27
Revision
Practise doing proofs!
I tutorial sheets, textbooks, . . .
Sipser, pp. 22–25.
For more about Srinivasa Ramanujan, see:
I https://mathshistory.st-andrews.ac.uk/Biographies/Ramanujan/
I R Kanigel, The Man Who Knew Infinity: A Life of the Genius Ramanujan,
Washington Square Press, New York, 1991.
I The Man Who Knew Infinity, feature film, 2015.
I film review: G Farr, The Man Who Knew Infinity: inspiration, rigour and the
art of mathematics, The Conversation, 24 May 2016.
https://theconversation.com/the-man-who-knew-infinity-inspiration-rigour-and-the-art-of-mathematics-59520
27 / 27
https://mathshistory.st-andrews.ac.uk/Biographies/Ramanujan/
https://theconversation.com/the-man-who-knew-infinity-inspiration-rigour-and-the-art-of-mathematics-59520