Methods of Proof Methods of Proof
CS 202 CS 202
Rosen section 1.5
Rosen section 1.5
Aaron Bloomfield
Aaron Bloomfield
In this slide set…
In this slide set…
Rules of inference for propositions Rules of inference for propositions
Rules of inference for quantified Rules of inference for quantified
statements statements
Ten methods of proof
Ten methods of proof
Proof methods in this slide set Proof methods in this slide set
Logical equivalences Logical equivalences
via truth tablesvia truth tables
via logical equivalencesvia logical equivalences
Set equivalences Set equivalences
via membership tablesvia membership tables
via set identitiesvia set identities
via mutual subset proofvia mutual subset proof
via set builder notation and via set builder notation and logical equivalences
logical equivalences
Rules of inference Rules of inference
for propositionsfor propositions
for quantified statementsfor quantified statements
Pigeonhole principle Pigeonhole principle Combinatorial proofs Combinatorial proofs
Ten proof methods in section 1.5:
Ten proof methods in section 1.5:
Direct proofsDirect proofs
Indirect proofsIndirect proofs
Vacuous proofsVacuous proofs
Trivial proofsTrivial proofs
Proof by contradictionProof by contradiction
Proof by casesProof by cases
Proofs of equivalenceProofs of equivalence
Existence proofsExistence proofs
Constructive Constructive Non-constructive Non-constructive
Uniqueness proofsUniqueness proofs
CounterexamplesCounterexamples
Induction Induction
Weak mathematical inductionWeak mathematical induction
Strong mathematical inductionStrong mathematical induction
Structural inductionStructural induction
Modus Ponens Modus Ponens
Consider (p
Consider (p (p→q)) → q (p→q)) → q
p p q q p→q p→q p p (p→q)) (p→q)) (p (p (p→q)) → q (p→q)) → q
T T T T T T T T T T
T T F F F F F F T T
F F T T T T F F T T
F F F F T T F F T T
q
q p
p
Modus Ponens example Modus Ponens example
Assume you are given the following two Assume you are given the following two
statements:
statements:
““you are in this class”you are in this class”
““if you are in this class, you will get a grade”if you are in this class, you will get a grade”
Let p = “you are in this class”
Let p = “you are in this class”
Let q = “you will get a grade”
Let q = “you will get a grade”
By Modus Ponens, you can conclude that you By Modus Ponens, you can conclude that you
will get a grade will get a grade
q
q p
p
Modus Tollens Modus Tollens
Assume that we know:
Assume that we know: ¬ ¬ q and p q and p → → q q
Recall that p Recall that p → → q = q = ¬ ¬ q q → → ¬ ¬ p p
Thus, we know
Thus, we know ¬ ¬ q and q and ¬ ¬ q q → → ¬ ¬ p p We can conclude
We can conclude ¬ ¬ p p
p q p
q
Modus Tollens example Modus Tollens example
Assume you are given the following two Assume you are given the following two
statements:
statements:
““you will not get a grade”you will not get a grade”
““if you are in this class, you will get a grade”if you are in this class, you will get a grade”
Let p = “you are in this class”
Let p = “you are in this class”
Let q = “you will get a grade”
Let q = “you will get a grade”
By Modus Tollens, you can conclude that you By Modus Tollens, you can conclude that you
are not in this class are not in this class
p q p
q
Quick survey Quick survey
I feel I understand moduls ponens I feel I understand moduls ponens and modus tollens
and modus tollens
a)a)
Very well Very well
b)b)
With some review, I’ll be good With some review, I’ll be good
c)c)
Not really Not really
d)d)
Not at all Not at all
Addition & Simplification Addition & Simplification
Addition: If you know Addition: If you know
that p is true, then p
that p is true, then p q q will ALWAYS be true
will ALWAYS be true
Simplification: If p
Simplification: If p q is q is true, then p will true, then p will
ALWAYS be true ALWAYS be true
q p
p
p
q p
Example of proof Example of proof
Example 6 of Rosen, section 1.5 Example 6 of Rosen, section 1.5
We have the hypotheses:
We have the hypotheses:
““It is not sunny this afternoon and it It is not sunny this afternoon and it is colder than yesterday”
is colder than yesterday”
““We will go swimming only if it is We will go swimming only if it is sunny”
sunny”
““If we do not go swimming, then we If we do not go swimming, then we will take a canoe trip”
will take a canoe trip”
““If we take a canoe trip, then we will If we take a canoe trip, then we will be home by sunset”
be home by sunset”
Does this imply that “we will be Does this imply that “we will be
home by sunset”?
home by sunset”?
““It isIt is not not sunny this afternoonsunny this afternoon and it and it is colder than yesterday”
is colder than yesterday”
““We will go swimming only if We will go swimming only if it is it is sunny
sunny””
““If we do not go swimming, then we If we do not go swimming, then we will take a canoe trip”
will take a canoe trip”
““If we take a canoe trip, then we will If we take a canoe trip, then we will be home by sunset”
be home by sunset”
Does this imply that “we will be Does this imply that “we will be
home by sunset”?
home by sunset”?
““It isIt is not not sunny this afternoonsunny this afternoon and and it it is colder than yesterday
is colder than yesterday””
““We will go swimming only if We will go swimming only if it is it is sunny
sunny””
““If we do not go swimming, then we If we do not go swimming, then we will take a canoe trip”
will take a canoe trip”
““If we take a canoe trip, then we will If we take a canoe trip, then we will be home by sunset”
be home by sunset”
Does this imply that “we will be Does this imply that “we will be
home by sunset”?
home by sunset”?
““It isIt is not not sunny this afternoonsunny this afternoon and and it it is colder than yesterday
is colder than yesterday””
““We will go swimmingWe will go swimming only if only if it is it is sunny
sunny””
““If If we dowe do not not go swimming, then we go swimming, then we will take a canoe trip”
will take a canoe trip”
““If we take a canoe trip, then we will If we take a canoe trip, then we will be home by sunset”
be home by sunset”
Does this imply that “we will be Does this imply that “we will be
home by sunset”?
home by sunset”?
““It isIt is not not sunny this afternoonsunny this afternoon and and it it is colder than yesterday
is colder than yesterday””
““We will go swimmingWe will go swimming only if only if it is it is sunny
sunny””
““If If we dowe do not not go swimming, then go swimming, then we we will take a canoe trip
will take a canoe trip””
““If If we take a canoe tripwe take a canoe trip, then we will , then we will be home by sunset”
be home by sunset”
Does this imply that “we will be Does this imply that “we will be
home by sunset”?
home by sunset”?
““It isIt is not not sunny this afternoon and sunny this afternoon and it it is colder than yesterday
is colder than yesterday””
““We will go swimmingWe will go swimming only if only if it is it is sunny
sunny””
““If If we dowe do not not go swimminggo swimming, then , then we we will take a canoe trip
will take a canoe trip””
““If If we take a canoe tripwe take a canoe trip, then , then we will we will be home by sunset
be home by sunset””
Does this imply that “
Does this imply that “ we will be we will be home by sunset
home by sunset ”? ”?
p q r s
t
¬p q r → p
¬r → s s → t t
Example of proof Example of proof
1.1. ¬p ¬p q q 11stst hypothesis hypothesis
2.2. ¬p¬p Simplification using step 1Simplification using step 1 3.3. r → pr → p 22ndnd hypothesis hypothesis
4.4. ¬r¬r Modus tollens using steps 2 & 3Modus tollens using steps 2 & 3 5.5. ¬r → s¬r → s 33rdrd hypothesis hypothesis
6.6. ss Modus ponens using steps 4 & 5Modus ponens using steps 4 & 5 7.7. s → t s → t 44thth hypothesis hypothesis
8.8. tt Modus ponens using steps 6 & 7Modus ponens using steps 6 & 7 q
p
p q
p
q p
q
So what did we show?
So what did we show?
We showed that:
We showed that:
[(¬p [(¬p q) q) (r → p) (r → p) (¬r → s) (¬r → s) (s → t)] → t (s → t)] → t
That when the 4 hypotheses are true, then the That when the 4 hypotheses are true, then the implication is true
implication is true
In other words, we showed the above is a tautology!In other words, we showed the above is a tautology!
To show this, enter the following into the truth To show this, enter the following into the truth
table generator at table generator at
http://sciris.shu.edu/~borowski/Truth/:
http://sciris.shu.edu/~borowski/Truth/:
((~P ^ Q) ^ (R => P) ^ (~R => S) ^ (S => T)) => T ((~P ^ Q) ^ (R => P) ^ (~R => S) ^ (S => T)) => T
More rules of inference More rules of inference
Conjunction: if p and q are true Conjunction: if p and q are true
separately, then p
separately, then pq is trueq is true Disjunctive syllogism: If p
Disjunctive syllogism: If pq is q is true, and p is false, then q must true, and p is false, then q must
be true be true
Resolution: If p
Resolution: If pq is true, and q is true, and
¬p¬pr is true, then qr is true, then qr must be truer must be true Hypothetical syllogism: If p→q is Hypothetical syllogism: If p→q is true, and q→r is true, then p→r true, and q→r is true, then p→r
q p
q p
q p
q p
r q
r p
q p
r q
q p
Example of proof Example of proof
Rosen, section 1.5, question 4 Rosen, section 1.5, question 4
Given the hypotheses:
Given the hypotheses:
“ “ If it does not rain or if it is not If it does not rain or if it is not foggy, then the sailing race will foggy, then the sailing race will be held and the lifesaving be held and the lifesaving
demonstration will go on”
demonstration will go on”
“ “ If the sailing race is held, then If the sailing race is held, then the trophy will be awarded”
the trophy will be awarded”
“ “ The trophy was not awarded” The trophy was not awarded”
Can you conclude: “It rained”?
Can you conclude: “It rained”?
(¬r ¬f) → (s l)
s → t
¬t
r
Example of proof Example of proof
1.1. ¬t¬t 33rdrd hypothesis hypothesis 2.2. s → ts → t 22ndnd hypothesis hypothesis
3.3. ¬s¬s Modus tollens using steps 2 & 3Modus tollens using steps 2 & 3 4.4. (¬r(¬r¬f)→(s¬f)→(sl)l) 11stst hypothesis hypothesis
5.5. ¬(s¬(sl)→¬(¬rl)→¬(¬r¬f)¬f) Contrapositive of step 4Contrapositive of step 4
6.6. (¬s(¬s¬l)→(r¬l)→(rf)f) DeMorgan’s law and double negation lawDeMorgan’s law and double negation law 7.7. ¬s¬s¬l¬l Addition from step 3Addition from step 3
8.8. rrff Modus ponens using steps 6 & 7Modus ponens using steps 6 & 7 9.9. rr Simplification using step 8Simplification using step 8
q
p q
p p
q p
q
p
Quick survey Quick survey
I feel I understand that proof… I feel I understand that proof…
a)a)
Very well Very well
b)b)
With some review, I’ll be good With some review, I’ll be good
c)c)
Not really Not really
d)d)
Not at all Not at all
Modus Badus Modus Badus
Consider the following:
Consider the following:
Is this true?
Is this true?
p p q q p→q p→q q q (p→q)) (p→q)) (q (q (p→q)) → p (p→q)) → p
T T T T T T T T T T
T T F F F F F F T T
F F T T T T T T F F
F F F F T T F F T T
Not a valid
rule!
p
q p
q
p
p q
q
Fallacy of Fallacy of affirming the affirming the
conclusion
conclusion
Modus Badus example Modus Badus example
Assume you are given the following two Assume you are given the following two
statements:
statements:
““you will get a grade”you will get a grade”
““if you are in this class, you will get a grade”if you are in this class, you will get a grade”
Let p = “you are in this class”
Let p = “you are in this class”
Let q = “you will get a grade”
Let q = “you will get a grade”
You CANNOT conclude that you are in this class You CANNOT conclude that you are in this class
You could be getting a grade for another classYou could be getting a grade for another class
p
q p
q
Modus Badus Modus Badus
Consider the following:
Consider the following:
Is this true?
Is this true?
p p q q p→q p→q ¬p ¬p (p→q)) (p→q)) (¬p (¬p (p→q)) → ¬q (p→q)) → ¬q
T T T T T T F F T T
T T F F F F F F T T
F F T T T T T T F F
F F F F T T T T T T
Not a valid
rule!
q q p
p
Fallacy of
Fallacy of
denying the
denying the
hypothesis
hypothesis
Modus Badus example Modus Badus example
Assume you are given the following two Assume you are given the following two
statements:
statements:
““you are not in this class”you are not in this class”
““if you are in this class, you will get a grade”if you are in this class, you will get a grade”
Let p = “you are in this class”
Let p = “you are in this class”
Let q = “you will get a grade”
Let q = “you will get a grade”
You CANNOT conclude that you will not get a You CANNOT conclude that you will not get a
grade grade
You could be getting a grade for another classYou could be getting a grade for another class
q q p
p
Quick survey Quick survey
I feel I understand rules of inference I feel I understand rules of inference for Boolean propositions…
for Boolean propositions…
a)a)
Very well Very well
b)b)
With some review, I’ll be good With some review, I’ll be good
c)c)
Not really Not really
d)d)
Not at all Not at all
Just in time for Valentine’s Day…
Just in time for Valentine’s Day…
Bittersweets: Dejected sayings Bittersweets: Dejected sayings
I MISS MY EX I MISS MY EX
PEAKED AT 17 PEAKED AT 17
MAIL ORDER MAIL ORDER
TABLE FOR 1 TABLE FOR 1
I CRY ON Q I CRY ON Q
U C MY BLOG? U C MY BLOG?
REJECT PILE REJECT PILE
PILLOW HUGGIN PILLOW HUGGIN
ASYLUM BOUND ASYLUM BOUND
DIGNITY FREE DIGNITY FREE
PROG FAN PROG FAN
STATIC CLING STATIC CLING
WE HAD PLANS WE HAD PLANS
XANADU 2NITE XANADU 2NITE
SETTLE 4LESS SETTLE 4LESS
NOT AGAIN NOT AGAIN
Bittersweets: Dysfunctional sayings Bittersweets: Dysfunctional sayings
RUMORS TRUE RUMORS TRUE
PRENUP OKAY? PRENUP OKAY?
HE CAN LISTEN HE CAN LISTEN
GAME ON TV GAME ON TV
CALL A 900# CALL A 900#
P.S. I LUV ME P.S. I LUV ME
DO MY DISHES DO MY DISHES
UWATCH CMT UWATCH CMT
PAROLE IS UP! PAROLE IS UP!
BE MY YOKO BE MY YOKO
U+ME=GRIEF U+ME=GRIEF
I WANT HALF I WANT HALF
RETURN 2 PIT RETURN 2 PIT
NOT MY MOMMY NOT MY MOMMY
BE MY PRISON BE MY PRISON
C THAT DOOR? C THAT DOOR?
What we have shown What we have shown
Rules of inference for propositions Rules of inference for propositions
Next up: rules of inference for quantified Next up: rules of inference for quantified
statements
statements
Rules of inference for the Rules of inference for the
universal quantifier universal quantifier
Assume that we know that
Assume that we know that x P(x) is true x P(x) is true
Then we can conclude that P(c) is true Then we can conclude that P(c) is true
Here c stands for some specific constant Here c stands for some specific constant
This is called “universal instantiation” This is called “universal instantiation”
Assume that we know that P(c) is true for Assume that we know that P(c) is true for
any value of c any value of c
Then we can conclude that Then we can conclude that x P(x) is true x P(x) is true
This is called “universal generalization” This is called “universal generalization”
Rules of inference for the Rules of inference for the
existential quantifier existential quantifier
Assume that we know that
Assume that we know that x P(x) is true x P(x) is true
Then we can conclude that P(c) is true for Then we can conclude that P(c) is true for some value of c
some value of c
This is called “existential instantiation” This is called “existential instantiation”
Assume that we know that P(c) is true for Assume that we know that P(c) is true for
some value of c some value of c
Then we can conclude that Then we can conclude that x P(x) is true x P(x) is true
This is called “existential generalization” This is called “existential generalization”
Example of proof Example of proof
Rosen, section 1.5, question 10a Rosen, section 1.5, question 10a
Given the hypotheses:
Given the hypotheses:
““Linda, a student in this class, owns Linda, a student in this class, owns a red convertible.”
a red convertible.”
““Everybody who owns a red Everybody who owns a red convertible has gotten at least one convertible has gotten at least one
speeding ticket”
speeding ticket”
Can you conclude: “Somebody in Can you conclude: “Somebody in this class has gotten a speeding this class has gotten a speeding
ticket”?
ticket”?
C(Linda) R(Linda)
x (R(x)→T(x))
x (C(x)T(x))
Example of proof Example of proof
1.1. x (R(x)→T(x))x (R(x)→T(x)) 33rdrd hypothesis hypothesis
2.2. R(Linda) → T(Linda)R(Linda) → T(Linda) Universal instantiation using step 1Universal instantiation using step 1 3.3. R(Linda)R(Linda) 22ndnd hypothesis hypothesis
4.4. T(Linda)T(Linda) Modes ponens using steps 2 & 3Modes ponens using steps 2 & 3 5.5. C(Linda)C(Linda) 11stst hypothesis hypothesis
6.6. C(Linda) C(Linda) T(Linda) T(Linda) Conjunction using steps 4 & 5Conjunction using steps 4 & 5
7.7. x (C(x)x (C(x)T(x))T(x)) Existential generalization using Existential generalization using step 6
step 6
Thus, we have shown that “Somebody in this class has gotten a speeding ticket”
Example of proof Example of proof
Rosen, section 1.5, question Rosen, section 1.5, question 10d 10d
Given the hypotheses:
Given the hypotheses:
“ “ There is someone in this class There is someone in this class who has been to France”
who has been to France”
“ “ Everyone who goes to France Everyone who goes to France visits the Louvre”
visits the Louvre”
Can you conclude: “Someone Can you conclude: “Someone in this class has visited the in this class has visited the
Louvre”?
Louvre”?
x (C(x)F(x))
x (F(x)→L(x))
x (C(x)L(x))
Example of proof Example of proof
1.1. x (C(x)x (C(x)F(x))F(x)) 11stst hypothesis hypothesis
2.2. C(y) C(y) F(y) F(y) Existential instantiation using step 1Existential instantiation using step 1 3.3. F(y)F(y) Simplification using step 2Simplification using step 2
4.4. C(y)C(y) Simplification using step 2Simplification using step 2 5.5. x (F(x)→L(x))x (F(x)→L(x)) 22ndnd hypothesis hypothesis
6.6. F(y) → L(y)F(y) → L(y) Universal instantiation using step 5Universal instantiation using step 5 7.7. L(y)L(y) Modus ponens using steps 3 & 6Modus ponens using steps 3 & 6 8.8. C(y) C(y) L(y) L(y) Conjunction using steps 4 & 7Conjunction using steps 4 & 7
9.9. x (C(x)x (C(x)L(x))L(x)) Existential generalization usingExistential generalization using step 8
step 8
Thus, we have shown that “Someone
How do you know which one to How do you know which one to
use? use?
Experience!
Experience!
In general, use quantifiers with statements In general, use quantifiers with statements
like “for all” or “there exists”
like “for all” or “there exists”
Although the vacuous proof example on slide Although the vacuous proof example on slide 40 is a contradiction
40 is a contradiction
Quick survey Quick survey
I feel I understand rules of inference I feel I understand rules of inference for quantified statements…
for quantified statements…
a)a)
Very well Very well
b)b)
With some review, I’ll be good With some review, I’ll be good
c)c)
Not really Not really
d)d)
Not at all Not at all
Proof methods Proof methods
We will discuss ten proof methods:
We will discuss ten proof methods:
1.
1. Direct proofsDirect proofs
2.2. Indirect proofsIndirect proofs
3.3. Vacuous proofsVacuous proofs
4.4. Trivial proofsTrivial proofs
5.
5. Proof by contradictionProof by contradiction
6.6. Proof by casesProof by cases
7.7. Proofs of equivalenceProofs of equivalence
8.8. Existence proofsExistence proofs
9.
9. Uniqueness proofsUniqueness proofs
10.10. CounterexamplesCounterexamples
Direct proofs Direct proofs
Consider an implication: p→q Consider an implication: p→q
If p is false, then the implication is always true If p is false, then the implication is always true
Thus, show that if p is true, then q is true Thus, show that if p is true, then q is true
To perform a direct proof, assume that p is
To perform a direct proof, assume that p is
true, and show that q must therefore be
true, and show that q must therefore be
true true
Direct proof example Direct proof example
Rosen, section 1.5, question 20 Rosen, section 1.5, question 20
Show that the square of an even number is an Show that the square of an even number is an even number
even number
Rephrased: if n is even, then n Rephrased: if n is even, then n
22is even is even
Assume n is even Assume n is even
Thus, n = 2k, for some k (definition of even Thus, n = 2k, for some k (definition of even numbers)
numbers)
n n
22= (2k) = (2k)
22= 4k = 4k
22= 2(2k = 2(2k
22) )
As n As n
22is 2 times an integer, n is 2 times an integer, n
22is thus even is thus even
Quick survey Quick survey
These quick surveys are really These quick surveys are really getting on my nerves…
getting on my nerves…
a)a)
They’re great - keep ‘em coming! They’re great - keep ‘em coming!
b)b)
They’re fine They’re fine
c)c)
A bit tedious A bit tedious
d)d)
Enough already! Stop! Enough already! Stop!
Indirect proofs Indirect proofs
Consider an implication: p→q Consider an implication: p→q
It’s contrapositive is ¬q→¬p It’s contrapositive is ¬q→¬p
Is logically equivalent to the original implication!
Is logically equivalent to the original implication!
If the antecedent (¬q) is false, then the If the antecedent (¬q) is false, then the contrapositive is always true
contrapositive is always true
Thus, show that if ¬q is true, then ¬p is true Thus, show that if ¬q is true, then ¬p is true
To perform an indirect proof, do a direct To perform an indirect proof, do a direct
proof on the contrapositive
proof on the contrapositive
Indirect proof example Indirect proof example
If n If n
22is an odd integer then n is an odd integer is an odd integer then n is an odd integer
Prove the contrapositive: If n is an even integer, Prove the contrapositive: If n is an even integer,
then n
then n
22is an even integer is an even integer
Proof: n=2k for some integer k (definition of even Proof: n=2k for some integer k (definition of even
numbers) numbers)
n n
22= (2k) = (2k)
22= 4k = 4k
22= 2(2k = 2(2k
22) ) Since n
Since n
22is 2 times an integer, it is even is 2 times an integer, it is even
Which to use Which to use
When do you use a direct proof versus an When do you use a direct proof versus an
indirect proof?
indirect proof?
If it’s not clear from the problem, try direct If it’s not clear from the problem, try direct
first, then indirect second first, then indirect second
If indirect fails, try the other proofs If indirect fails, try the other proofs
Example of which to use Example of which to use
Rosen, section 1.5, question 21 Rosen, section 1.5, question 21
Prove that if n is an integer and nProve that if n is an integer and n33+5 is odd, then n is +5 is odd, then n is eveneven
Via direct proof Via direct proof
nn33+5 = 2k+1 for some integer k (definition of odd +5 = 2k+1 for some integer k (definition of odd numbers)
numbers)
nn33 = 2k+6 = 2k+6
Umm…Umm…
So direct proof didn’t work out. Next up: indirect So direct proof didn’t work out. Next up: indirect
3 2 6
k n
Example of which to use Example of which to use
Rosen, section 1.5, question 21 (a) Rosen, section 1.5, question 21 (a)
Prove that if n is an integer and nProve that if n is an integer and n33+5 is odd, then n is +5 is odd, then n is eveneven
Via indirect proof Via indirect proof
Contrapositive: If n is odd, then nContrapositive: If n is odd, then n33+5 is even+5 is even
Assume n is odd, and show that nAssume n is odd, and show that n33+5 is even+5 is even
n=2k+1 for some integer k (definition of odd numbers)n=2k+1 for some integer k (definition of odd numbers)
nn33+5 = (2k+1)+5 = (2k+1)33+5 = 8k+5 = 8k33+12k+12k22+6k+6 = 2(4k+6k+6 = 2(4k33+6k+6k22+3k+3)+3k+3)
As 2(4kAs 2(4k33+6k+6k22+3k+3) is 2 times an integer, it is even+3k+3) is 2 times an integer, it is even
Quick survey Quick survey
I feel I understand direct proofs and I feel I understand direct proofs and indirect proofs…
indirect proofs…
a)a)
Very well Very well
b)b)
With some review, I’ll be good With some review, I’ll be good
c)c)
Not really Not really
d)d)
Not at all Not at all
Proof by contradiction Proof by contradiction
Given a statement p, assume it is false Given a statement p, assume it is false
Assume ¬pAssume ¬p
Prove that ¬p cannot occur Prove that ¬p cannot occur
A contradiction existsA contradiction exists
Given a statement of the form p→q Given a statement of the form p→q
To assume it’s false, you only have to consider the To assume it’s false, you only have to consider the case where p is true and q is false
case where p is true and q is false
Proof by contradiction example 1 Proof by contradiction example 1
Theorem (by Euclid): There are infinitely many Theorem (by Euclid): There are infinitely many
prime numbers.
prime numbers.
Proof. Assume there are a finite number of primes Proof. Assume there are a finite number of primes
List them as follows: p
List them as follows: p
11, p , p
22…, p …, p
nn. . Consider the number q = p
Consider the number q = p
11p p
22… p … p
nn+ 1 + 1
This number is not divisible by any of the listed primesThis number is not divisible by any of the listed primes
If we divided p
If we divided pii into q, there would result a remainder of 1 into q, there would result a remainder of 1
We must conclude that q is a prime number, not among We must conclude that q is a prime number, not among the primes listed above
the primes listed above
This contradicts our assumption that all primes are in the list This contradicts our assumption that all primes are in the list
Proof by contradiction example 2 Proof by contradiction example 2
Rosen, section 1.5, question 21 (b) Rosen, section 1.5, question 21 (b)
Prove that if n is an integer and nProve that if n is an integer and n33+5 is odd, then n is even+5 is odd, then n is even
Rephrased: If nRephrased: If n33+5 is odd, then n is even+5 is odd, then n is even
Assume p is true and q is false Assume p is true and q is false
Assume that nAssume that n33+5 is odd, and n is odd+5 is odd, and n is odd
n=2k+1 for some integer k (definition of odd numbers) n=2k+1 for some integer k (definition of odd numbers) nn33+5 = (2k+1)+5 = (2k+1)33+5 = 8k+5 = 8k33+12k+12k22+6k+6 = 2(4k+6k+6 = 2(4k33+6k+6k22+3k+3)+3k+3)
As 2(4k
As 2(4k33+6k+6k22+3k+3) is 2 times an integer, it must be +3k+3) is 2 times an integer, it must be eveneven
Contradiction!
Contradiction!
A note on that problem…
A note on that problem…
Rosen, section 1.5, question 21 Rosen, section 1.5, question 21
Prove that if n is an integer and nProve that if n is an integer and n33+5 is odd, then n is even+5 is odd, then n is even
Here, our implication is: If nHere, our implication is: If n33+5 is odd, then n is even+5 is odd, then n is even
The indirect proof proved the contrapositive: ¬q → ¬p The indirect proof proved the contrapositive: ¬q → ¬p
I.e., If n is odd, then nI.e., If n is odd, then n33+5 is even+5 is even
The proof by contradiction assumed that the implication The proof by contradiction assumed that the implication
was false, and showed a contradiction was false, and showed a contradiction
If we assume p and ¬q, we can show that implies qIf we assume p and ¬q, we can show that implies q
The contradiction is q and ¬qThe contradiction is q and ¬q
Note that both used similar steps, but are different Note that both used similar steps, but are different
How the book explains How the book explains
proof by contradiction proof by contradiction
A very poor explanation, IMHO A very poor explanation, IMHO
Suppose q is a contradiction (i.e. is always false) Suppose q is a contradiction (i.e. is always false)
Show that ¬p→q is true Show that ¬p→q is true
Since the consequence is false, the antecedent must be Since the consequence is false, the antecedent must be false
false
Thus, p must be trueThus, p must be true
Find a contradiction, such as (r
Find a contradiction, such as (r ¬r), to represent q ¬r), to represent q Thus, you are showing that ¬p→(r
Thus, you are showing that ¬p→(r ¬r) ¬r)
Or that assuming p is false leads to a contradictionOr that assuming p is false leads to a contradiction
A note on proofs by contradiction A note on proofs by contradiction
You can DISPROVE something by using a proof You can DISPROVE something by using a proof
by contradiction by contradiction
You are finding an example to show that something is You are finding an example to show that something is not true
not true
You cannot PROVE something by example You cannot PROVE something by example
Example: prove or disprove that all numbers are Example: prove or disprove that all numbers are even even
Proof by contradiction: 1 is not evenProof by contradiction: 1 is not even
(Invalid) proof by example: 2 is even(Invalid) proof by example: 2 is even
Quick survey Quick survey
I feel I understand proof by I feel I understand proof by contradiction…
contradiction…
a)a)
Very well Very well
b)b)
With some review, I’ll be good With some review, I’ll be good
c)c)
Not really Not really
d)d)
Not at all Not at all
Vacuous proofs Vacuous proofs
Consider an implication: p→q Consider an implication: p→q
If it can be shown that p is false, then the If it can be shown that p is false, then the
implication is always true implication is always true
By definition of an implication By definition of an implication
Note that you are showing that the Note that you are showing that the
antecedent is false
antecedent is false
Vacuous proof example Vacuous proof example
Consider the statement:
Consider the statement:
All criminology majors in CS 202 are female All criminology majors in CS 202 are female
Rephrased: If you are a criminology major and Rephrased: If you are a criminology major and you are in CS 202, then you are female
you are in CS 202, then you are female
Could also use quantifiers!
Could also use quantifiers!
Since there are no criminology majors in Since there are no criminology majors in this class, the antecedent is false, and the this class, the antecedent is false, and the
implication is true
implication is true
Trivial proofs Trivial proofs
Consider an implication: p→q Consider an implication: p→q
If it can be shown that q is true, then the If it can be shown that q is true, then the
implication is always true implication is always true
By definition of an implication By definition of an implication
Note that you are showing that the Note that you are showing that the
conclusion is true
conclusion is true
Trivial proof example Trivial proof example
Consider the statement:
Consider the statement:
If you are tall and are in CS 202 then you are If you are tall and are in CS 202 then you are a student
a student
Since all people in CS 202 are students, Since all people in CS 202 are students,
the implication is true regardless
the implication is true regardless
Proof by cases Proof by cases
Show a statement is true by showing all Show a statement is true by showing all
possible cases are true possible cases are true
Thus, you are showing a statement of the Thus, you are showing a statement of the
form:
form:
is true by showing that:
is true by showing that:
p1 p2 ... pn
q
p1 p2 ... pn q
p1 q
p2 q
...
pn q
Proof by cases example Proof by cases example
Prove that Prove that
Note that b ≠ 0 Note that b ≠ 0
Cases:
Cases:
Case 1: a ≥ 0 and b > 0 Case 1: a ≥ 0 and b > 0
Then |a| = a, |b| = b, and Then |a| = a, |b| = b, and
Case 2: a ≥ 0 and b < 0 Case 2: a ≥ 0 and b < 0
Then |a| = a, |b| = -b, and Then |a| = a, |b| = -b, and
Case 3: a < 0 and b > 0 Case 3: a < 0 and b > 0
Then |a| = -a, |b| = b, and Then |a| = -a, |b| = b, and
Case 4: a < 0 and b < 0 Case 4: a < 0 and b < 0
Then |a| = -a, |b| = -b, and Then |a| = -a, |b| = -b, and
b a b
a
b a b a b
a
b a b a b
a b
a
b a b
a b
a b
a
a a a
a
The think about proof by cases The think about proof by cases
Make sure you get ALL the cases Make sure you get ALL the cases
The biggest mistake is to leave out some of The biggest mistake is to leave out some of the cases
the cases
Quick survey Quick survey
I feel I understand trivial and vacuous I feel I understand trivial and vacuous proofs and proof by cases…
proofs and proof by cases…
a)a)
Very well Very well
b)b)
With some review, I’ll be good With some review, I’ll be good
c)c)
Not really Not really
d)d)
Not at all Not at all
End of prepared slides
End of prepared slides
Proofs of equivalences Proofs of equivalences
This is showing the definition of a bi- This is showing the definition of a bi-
conditional conditional
Given a statement of the form “p if and Given a statement of the form “p if and
only if q”
only if q”
Show it is true by showing (p→q) Show it is true by showing (p→q) (q→p) is (q→p) is
true true
Proofs of equivalence example Proofs of equivalence example
Rosen, section 1.5, question 40 Rosen, section 1.5, question 40
Show that mShow that m22=n=n22 if and only if m=n or m=-n if and only if m=n or m=-n
Rephrased: (mRephrased: (m22=n=n22) ↔ [(m=n)) ↔ [(m=n)(m=-n)](m=-n)]
Need to prove two parts:
Need to prove two parts:
[(m=n)[(m=n)(m=-n)] → (m(m=-n)] → (m22=n=n22))
Proof by cases!
Proof by cases!
Case 1: (m=n) → (m
Case 1: (m=n) → (m22=n=n22))
(m)(m)22 = m = m22, and (n), and (n)22 = n = n22, so this case is proven, so this case is proven
Case 2: (m=-n) → (m
Case 2: (m=-n) → (m22=n=n22))
(m)(m)22 = m = m22, and (-n), and (-n)22 = n = n22, so this case is proven, so this case is proven
(m(m22=n=n22) → [(m=n)) → [(m=n)(m=-n)](m=-n)]
Subtract n
Subtract n22 from both sides to get m from both sides to get m22-n-n22=0=0 Factor to get (m+n)(m-n) = 0
Factor to get (m+n)(m-n) = 0
Since that equals zero, one of the factors must be zero Since that equals zero, one of the factors must be zero
Existence proofs Existence proofs
Given a statement:
Given a statement: x P(x) x P(x)
We only have to show that a P(c) exists for We only have to show that a P(c) exists for
some value of c some value of c
Two types:
Two types:
Constructive: Find a specific value of c for Constructive: Find a specific value of c for which P(c) exists
which P(c) exists
Nonconstructive: Show that such a c exists, Nonconstructive: Show that such a c exists, but don’t actually find it
but don’t actually find it
Assume it does not exist, and show a contradiction Assume it does not exist, and show a contradiction
Constructive existence proof Constructive existence proof
example example
Show that a square exists that is the sum Show that a square exists that is the sum
of two other squares of two other squares
Proof: 3 Proof: 3
22+ 4 + 4
22= 5 = 5
22Show that a cube exists that is the sum of Show that a cube exists that is the sum of
three other cubes three other cubes
Proof: 3 Proof: 3
33+ 4 + 4
33+ 5 + 5
33= 6 = 6
33Non-constructive existence proof Non-constructive existence proof
example example
Rosen, section 1.5, question 50 Rosen, section 1.5, question 50
Prove that either 2*10
Prove that either 2*10500500+15 or 2*10+15 or 2*10500500+16 is not a +16 is not a perfect square
perfect square
A perfect square is a square of an integerA perfect square is a square of an integer
Rephrased: Show that a non-perfect square exists in the set Rephrased: Show that a non-perfect square exists in the set {2*10
{2*10500500+15, 2*10+15, 2*10500500+16}+16}
Proof: The only two perfect squares that differ by 1 are 0 Proof: The only two perfect squares that differ by 1 are 0
and 1 and 1
Thus, any other numbers that differ by 1 cannot both be perfect Thus, any other numbers that differ by 1 cannot both be perfect squares
squares
Thus, a non-perfect square must exist in any set that contains Thus, a non-perfect square must exist in any set that contains two numbers that differ by 1
two numbers that differ by 1
Note that we didn’t specify which one it was!Note that we didn’t specify which one it was!
Uniqueness proofs Uniqueness proofs
A theorem may state that only one such A theorem may state that only one such
value exists value exists
To prove this, you need to show:
To prove this, you need to show:
Existence: that such a value does indeed Existence: that such a value does indeed exist
exist
Either via a constructive or non-constructive Either via a constructive or non-constructive existence proof
existence proof
Uniqueness: that there is only one such value Uniqueness: that there is only one such value
Uniqueness proof example Uniqueness proof example
If the real number equation 5x+3=a has a If the real number equation 5x+3=a has a
solution then it is unique solution then it is unique
Existence Existence
We can manipulate 5x+3=a to yield x=(a-3)/5We can manipulate 5x+3=a to yield x=(a-3)/5
Is this constructive or non-constructive?Is this constructive or non-constructive?
Uniqueness Uniqueness
If there are two such numbers, then they would fulfill If there are two such numbers, then they would fulfill the following: a = 5x+3 = 5y+3
the following: a = 5x+3 = 5y+3
We can manipulate this to yield that x = yWe can manipulate this to yield that x = y
Thus, the one solution is unique!
Thus, the one solution is unique!
Counterexamples Counterexamples
Given a universally quantified statement, find a single Given a universally quantified statement, find a single
example which it is not true example which it is not true
Note that this is DISPROVING a UNIVERSAL statement Note that this is DISPROVING a UNIVERSAL statement
by a counterexample by a counterexample
x ¬R(x), where R(x) means “x has red hair”x ¬R(x), where R(x) means “x has red hair”
Find one person (in the domain) who has red hairFind one person (in the domain) who has red hair
Every positive integer is the square of another integer Every positive integer is the square of another integer
The square root of 5 is 2.236, which is not an integerThe square root of 5 is 2.236, which is not an integer
Mistakes in proofs Mistakes in proofs
Modus Badus Modus Badus
Fallacy of denying the hypothesis Fallacy of denying the hypothesis
Fallacy of affirming the conclusion Fallacy of affirming the conclusion
Proving a universal by example Proving a universal by example
You can only prove an existential by example! You can only prove an existential by example!
Quick survey Quick survey
I felt I understood the material in this I felt I understood the material in this slide set…
slide set…
a)a)
Very well Very well
b)b)
With some review, I’ll be good With some review, I’ll be good
c)c)
Not really Not really
d)d)
Not at all Not at all
Quick survey Quick survey
The pace of the lecture for this The pace of the lecture for this slide set was…
slide set was…
a)a)
Fast Fast
b)b)
About right About right
c)c)
A little slow A little slow
d)d)
Too slow Too slow
Quick survey Quick survey
How interesting was the material in How interesting was the material in this slide set? Be honest!
this slide set? Be honest!
a)a)
Wow! That was SOOOOOO cool! Wow! That was SOOOOOO cool!
b)b)
Somewhat interesting Somewhat interesting
c)c)
Rather borting Rather borting
d)d)