Discrete Mathematics: Lecture 5 - Proofs

discrete mathematics

1. Math211
Discrete Mathematics
Proofs
SAHAR SELIM

2. Agenda
1.7 Introduction to Proofs
direct proof, proof by contraposition, proof by
contradiction
1.8 Proof by Cases ONLY
Discrete Mathematics and Its Applications
Kenneth H. Rosen
Sahar Selim MATH211 Lecture 5 | Proofs
2

3. Theorems, Proofs, and Rules of
Inference
When is a mathematical argument correct?
What techniques can we use to construct a mathematical argument?
Theorem–statement that can be shown to be true.
Proof –sequence of statements, a valid argument, to show that a
theorem is true.
Rules of Inference–rules used in a proof to draw conclusions from
assertions known to be true.
Sahar Selim MATH211 Lecture 5 | Proofs
3

4. Valid Arguments
An argument is a sequence of propositions.
The final proposition is called the conclusionof the argument while the
other propositions are called the premises or hypothesesof the argument.
An argumentis validwhenever the truth of all its premises implies the
truth of its conclusion.
How to show that q logically follows from the hypotheses
(p
1∧p
2 ∧…∧p
n)?
Show that (p
1∧p
2∧…∧p
n) →q is a tautology
One can use the rules of inference to show the validity of an
argument.
Sahar Selim MATH211 Lecture 5 | Proofs
4
p
1
p
2
…
p
n
q
Premises
Conclusion

5. Methods of Proof
1.Direct Proof
2.Proof by Contraposition
3.Proof by Contradiction
4.Proof by Cases
Sahar Selim MATH211 Lecture 5 | Proofs
5

6. 1.7.1. Direct Proof
Sahar Selim MATH211 Lecture 5 | Proofs
6

7. 1. Direct Proofs
Most of the proofs we have seen so far are directproofs
In a direct proof
You assume the hypothesis p is true
Give a direct series (sequence) of implications using the rules
of inference as well as other results (proved independently)
to show that the conclusion qholds.
Sahar Selim MATH211 Lecture 5 | Proofs
7

8. 1. Direct Proofs
Consider an implication: p → q
If p is false, then the implication is always true
Thus, show that if p is true, then q is true
To perform a direct proof, assume that p is true, and show that q
must therefore be true
Sahar Selim MATH211 Lecture 5 | Proofs
8

9. Sahar Selim MATH211 Lecture 5 | Proofs
9
Example 1 -direct proof
Theorem:
Mary is a Math major or a CS major.
If Mary does not like discrete math, she is not a CS major.
If Mary likes discrete math, she is smart.
Mary is not a math major.
Can you conclude Mary is smart?
Informally, what’s the chain of reasoning?
m ∨c
¬d → ¬c
d →s
¬m
((m ∨c) ∧(¬d →¬c) ∧(d →s) ∧(¬m)) →s
?
Let
m -Mary is a Math major
c –Mary is a CS major
d –Mary likes discrete math
s –Mary is smart

10. Sahar Selim MATH211 Lecture 5 | Proofs
10
Example 1 -direct proof
In general, to prove p →q, assume p and show that q follows.
((m ∨c) ∧(¬d →¬c) ∧(d →s) ∧(¬m)) →s
p q

11. Sahar Selim MATH211 Lecture 9 | Mathematical Induction
11
p →q
p____
∴q
modus
ponens
p →q
¬q___
∴¬p
modus tollens
p______
∴p ∨q
Addition
p ∧q
∴p
Simplification
p
q_____
∴p ^ q
Conjunction
p →q
q →r
∴p →r
hypothetical syllogism
p ∨q
¬p___
∴q
disjunctive syllogism
p ∨q
¬p ∨r
∴q ∨r
Resolution
m ∨c
¬d → ¬c
d →s
¬m
__________
s

12. Sahar Selim MATH211 Lecture 5 | Proofs
12
1.m ∨c Premise
2.¬d →¬c Premise
3.d →s Premise
4.¬m Premise
5.c Disjunction Syllogism on 1 & 4
6.d Modus Tollens on 2 & 5
7.s Modus Ponens on 3 7 6
Mary is smart!
Example 1 -direct proof
QED
QED or Q.E.D. ---quod eratdemonstrandum
“which was to be demonstrated”
or “I rest my case” 

13. Example 2 -direct proof
Show that the square of an even number is an even number
Rephrased: if n is even, then n
2
is even
Sahar Selim MATH211 Lecture 5 | Proofs
13

14. Example 2 -direct proof
Show that the square of an even number is an even number
Rephrased: if n is even, then n
2
is even
Assume n is even
Thus, n = 2k, for some k (definition of even numbers)
n
2
= (2k)
2
= 4k
2
= 2(2k
2
)
As n
2
is 2 times an integer, n
2
is thus even
Sahar Selim MATH211 Lecture 5 | Proofs
14

15. 1.7.2. Proof by Contrapositive (Indirect Proof)
Sahar Selim MATH211 Lecture 5 | Proofs
15

16. 2. Proof by Contrapositive (Indirect
Proofs)
Consider an implication: p → q
Recall that (p →q) ≡(¬q →¬p) (Its contrapositive)

You assume that the conclusion is false (¬q), then
Give a series of implications to show that such an assumption implies that
the premise is false (¬p)
Thus, show that if ¬q is true, then ¬p is true
To perform an indirect proof, do a direct proof on the
contrapositive
Sahar Selim MATH211 Lecture 5 | Proofs
16

17. Example 1 -Indirect proof
Prove that if x
3
< 0 then x<0
The contrapositive is “if x ≥0 then x
3
≥0”
Proof:
Sahar Selim MATH211 Lecture 5 | Proofs
17

18. Example 1 -Indirect proof
Prove that if x
3
< 0 then x<0
The contrapositive is “if x ≥0 then x
3
≥0”
Proof:
1.If x=0 → x
3
=0≥0
2.If x>0 → x
2
>0 →x
3
>0 QED
Sahar Selim MATH211 Lecture 5 | Proofs
18

19. Example 2 -Indirect proof
If n
2
is an odd integer then n is an odd integer
Prove the contrapositive:
If n is an even integer, then n
2
is an even integer
Sahar Selim MATH211 Lecture 5 | Proofs
19

20. Example 2 -Indirect proof
If n
2
is an odd integer then n is an odd integer
Prove the contrapositive:
If n is an even integer, then n
2
is an even integer
Proof:
n=2k for some integer k (definition of even numbers)
n
2
= (2k)
2
= 4k
2
= 2(2k
2
)
Since n
2
is 2 times an integer, it is even
Sahar Selim MATH211 Lecture 5 | Proofs
20

21. Which to use?
When do you use a direct proof versus an indirect proof?
If it’s not clear from the problem, try direct first, then indirect
second
If indirect fails, try the other proofs
Sahar Selim MATH211 Lecture 5 | Proofs
21

22. Example of which to use
Prove that if n is an integer and n
3
+5 is odd, then n is even
Via direct proof
n
3
+5 = 2k+1 for some integer k (definition of odd numbers)
n
3
= 2k-4
Umm…
So direct proof didn’t work out. Next up: indirect proof
3
24nk= −
Sahar Selim MATH211 Lecture 5 | Proofs
22

23. Example of which to use
Prove that if n is an integer and n
3
+5 is odd, then n is even
Via indirect proof
Sahar Selim MATH211 Lecture 5 | Proofs
23

24. Example of which to use
Prove that if n is an integer and n
3
+5 is odd, then n is even
Via indirect proof
Contrapositive: If n is odd, then n
3
+5 is even
Assume n is odd, and show that n
3
+5 is even
n=2k+1 for some integer k (definition of odd numbers)
n
3
+5 = (2k+1)
3
+5 = 8k
3
+12k
2
+6k+6 = 2(4k
3
+6k
2
+3k+3)
As 2(4k
3
+6k
2
+3k+3) is 2 times an integer, it is even
Sahar Selim MATH211 Lecture 5 | Proofs
24

25. 1.7.3. Proof by Contradiction (Indirect Proof)
Sahar Selim MATH211 Lecture 5 | Proofs
25

26. 3. Proof by Contradiction
1.Given a statement p, assume it is false
Assume ¬p
Prove that ¬p cannot occur
A contradiction exists
We want to prove p
We show that:
(1)¬p →F(i.e., a False statement , say r ∧¬r)
(2)We conclude that ¬p is false since (1) is Trueand therefore p is True.
Sahar Selim MATH211 Lecture 5 | Proofs
26

27. 3. Proof by Contradiction
2.Given a statement of the form p→q
To assume it’s false, you only have to consider the case where p is
true and q is false
We want to show p →q
(1)Assume the negation of the conclusion, i.e., ¬q
(2)Use it to show that (p ∧¬q ) →F
(3)Since ((p ∧¬q ) → F) ⇔(p →q) we are done
Sahar Selim MATH211 Lecture 5 | Proofs
27

28. Rainy days make gardens grow.
Gardens don’t grow if it is not hot.
When it is cold outside, it rains.
Prove that it’s hot.
Given: R →G
¬H →¬G
¬H →R
Show: H
((R →G) ∧(¬H →¬G) ∧(¬H →R)) →H
?
Example 1 -Proof by Contradiction
Let
R –Rainy day
G –Garden grows
H –It is hot
Hmm. We will assume “not Hot” ≡ “Cold”
Sahar Selim MATH211 Lecture 5 | Proofs
29

29. Sahar Selim MATH211 Lecture 9 | Mathematical Induction
30
p →q
p____
∴q
modus
ponens
p →q
¬q___
∴¬p
modus tollens
p______
∴p ∨q
Addition
p ∧q
∴p
Simplification
p
q_____
∴p ^ q
Conjunction
p →q
q →r
∴p →r
hypothetical syllogism
p ∨q
¬p___
∴q
disjunctive syllogism
p ∨q
¬p ∨r
∴q ∨r
Resolution
R →G
¬H → ¬G
¬H → R
__________
H

30. Given:R →G
¬H → ¬G
¬H → R
Show: H
1. R →G Given
2. ¬H → ¬G Given
3. ¬H → R Given
4. ¬H Assume the contrary
5. R MP (3,4)
6. G MP (1,5)
7. ¬G MP (2,4)
8. G ∧ ¬G contradiction
∴H
Example 1 -Proof by Contradiction
Sahar Selim MATH211 Lecture 5 | Proofs
31
Prove (p)
by contradiction

31. Example 2 -Proof by Contradiction
Prove that if n is an integer and n
3
+5 is odd, then n is even
Rephrased: If n
3
+5 is odd, then n is even
Thus, p is “n
3
+5” is odd, q is “n is even”
Sahar Selim MATH211 Lecture 5 | Proofs
32
Show that (p → q)
by contradiction

32. Example 2 -Proof by Contradiction
Prove that if n is an integer and n
3
+5 is odd, then n is even
Rephrased: If n
3
+5 is odd, then n is even
Thus, p is “n
3
+5” is odd, q is “n is even”
Assume p and ¬q
Assume that n
3
+5 is odd, and n is odd
Since n is odd:
n=2k+1 for some integer k (definition of odd numbers)
n
3
+5 = (2k+1)
3
+5 = 8k
3
+12k
2
+6k+6 = 2(4k
3
+6k
2
+3k+3)
As n = 2(4k
3
+6k
2
+3k+3) is 2 times an integer, n must be even
Thus, we have concluded q
Sahar Selim MATH211 Lecture 5 | Proofs
33
Contradiction!
•We assumed q was false, and
showed that this assumption
implies that q must be true
•As q cannot be both true and
false, we have reached our
contradiction
Show that (p → q)
by contradiction

33. Example 3 -Proof by Contradiction
Theorem (by Euclid): There are infinitely many prime numbers.
Proof by contradiction
Assume there are a finite number of primes
List them as follows: p
1, p
2…, p
n.
Consider the number q = p
1p
2… p
n+ 1
This number is not divisible by any of the listed primes
If we divided p
iinto q, there would result a remainder of 1
We must conclude that q is a prime number, not among the primes
listed above
This contradicts our assumption that all primes are in the list p
1, p
2…, p
n.
Sahar Selim MATH211 Lecture 5 | Proofs
34

34. 1.8.1 Proof by Cases
(WLOG) without loss of generalization
Sahar Selim MATH211 Lecture 5 | Proofs
36

35. 4. Proof by Cases
Sometimes it is easier to prove a theorem by
Breaking it down into cases and
Proving each one separately
Show a statement is true by showing all possible cases are true
To show that (p
1∨p
2∨…∨p
n) →q
We use the tautology
[(p
1∨p
2∨…∨p
n) →q ] ↔[(p
1→q ) ∧(p
2→q) ∧…∧(p
n→q )]
A particular case of a proof by cases is an exhaustive proofin
which all the cases are considered
Sahar Selim MATH211 Lecture 5 | Proofs
37

36. Example 1 -Proof by cases
Theorem
“If n is an integer, then n
2
≥ n ”
Sahar Selim MATH211 Lecture 5 | Proofs
38

37. Example 1 -Proof by cases
Theorem
“If n is an integer, then n
2
≥ n ”
Proof by cases
Case 1n=00
2
= 0
Case 2n > 0, i.e., n >= 1. We get n
2
≥ n since we can multiply both
sides of the inequality by n, which is positive.
Case 3n < 0 n
2
≥ 0 since we can multiply both sides of the
inequality by n, which is negative (changes the sign of the inequality);
we have n
2
≥ 0 > n because n is negative. So, n
2
≥ n.
Sahar Selim MATH211 Lecture 5 | Proofs
39

38. Example 2 -Proof by cases
Prove "if n is an integer n
2
+3n+2 is even."
Cases: n is odd, n is even
Sahar Selim MATH211 Lecture 5 | Proofs
40
Case 1: n is odd Case 2: n is even
n = 2k+1
= (2k+1)
2
+ 3(2k+1) + 2
= 4k
2
+ 4k + 1 + 6k + 3 + 2
= 4k
2
+ 10k + 6
= 2(2k
2
+ 5k + 3)
n = 2k
= (2k)
2
+ 3(2k) + 2
= 4k
2
+ 6k + 2
= 2(2k
2
+ 3k + 1)
Since both cases result
in even values, then
n
2
+3n+2 is even if n is
an integer.

39. Summarizing Proof techniques
Proof Technique Approach to prove P →Q Remarks
Direct Proof Assume P, deduce Q
The standard approach-usually
the thing to try
Proof by ContrapositionAssume ¬Q, derive ¬P
Use this ¬Q if as a hypothesis
seems to give more ammunition
then P would
Proof by Contradiction
Assume P Λ ¬Q, deduce a
contradiction
Use this when Q says something
is not true
Exhaustive Proof
Demonstrate P →Q for all
cases
May only be used for finite
number of cases
Sahar Selim MATH211 Lecture 5 | Proofs
41

40. Sahar Selim MATH211 Lecture 5 | Proofs
44

41. Prove that if a and b are integers, and a + b ≥ 15, then a ≥ 8 or b ≥ 8.
(a + b ≥ 15) → (a ≥ 8) ˅ (b ≥ 8)
(Assume ¬q) Suppose (a < 8) ∧(b < 8).
(Show ¬p) Then (a ≤ 7) ∧(b ≤ 7),
and (a + b) ≤ 14,
and (a + b) < 15.
Problem 1 -Proof by Contraposition
QED
Proof strategy:
Note that negation of conclusion
is easier tostart with here.
Sahar Selim MATH211 Lecture 5 | Proofs
45

42. Problem 2 -Proof by Contraposition
Theorem
For n integer, if 3n + 2 is odd, then n is odd.
i.e. For n integer, 3n+2 is odd → n is odd
Sahar Selim MATH211 Lecture 5 | Proofs
46
Proof by Contraposition:
Let p ---“3n + 2” is odd; q ---“n is odd”; we want to show that p →q
The contraposition of our theorem is ¬q →¬p
n is even →3n + 2 is even
Now we can use a direct proof
Assume ¬q , i.e, n is even therefore n = 2 k for some k
Therefore 3n + 2 = 3 (2k) + 2 = 6 k + 2 = 2 (3k + 1) which is even. QED

43. Theorem “If 3n+2 is odd, then n is odd”
Let p = “3n+2 is odd” and q = “n is odd”
1.assume p and ¬q i.e., 3n+2 is oddand n is not odd
2.because n is not odd, it is even
3.if n is even, n = 2k for some k, and therefore 3n+2 = 3 (2k) + 2 = 2 (3k + 1), which
is even
4.So, we have a contradiction, 3n+2 is oddand 3n+2 is even.
Therefore, we conclude p →q, i.e., “If 3n+2 is odd, then n is odd” Q.E.D.
Problem 2 -Proof by Contradiction
Sahar Selim MATH211 Lecture 5 | Proofs
47

44. Problem 3 -Proof by Contraposition
Prove that if the square of an integer is odd, then the integer must
be odd
Sahar Selim MATH211 Lecture 5 | Proofs
48
•Hence, prove n
2
odd →nodd
•To do a proof by contraposition prove neven →n
2
even
•If nis even, then it can be written as 2mwhere mis an integer,
i.e. even/odd.
•Then, n
2
= 4m
2
which is always even no matter what m
2
is
because of the factor 4.

45. Problem 4 -Proof by Contradiction
√2 is an irrational number
Let p be the proposition ‘√2 is an irrational number’
Assume¬p holds, and show that it yields a contradiction
√2 is rational
→√2 =a/b, a, b ∈ Zanda, b have no common factor (proposition r)
Definition of rational numbers
→2=a
2
/b
2
Squarringthe equation
→(2b
2
=a
2
)→(a
2
is even) →(a=2c ) Algebra
→(2b
2
=4c
2
) →(b
2
=2c
2
)→(b
2
is even) →(b is even) Algebra
→(a, b are even) →(a, b have a common factor 2) →¬r
→(¬p →(r ∧¬r)), which is a contradiction
So, (¬p is false) → (p is true), which means √2 is irrational
Sahar Selim MATH211 Lecture 5 | Proofs
49

46. Problem 5 -Proof by Contradiction
Prove “For all real numbers xand y, if x+ y≥2, then either x
≥1 or y≥1.”
Sahar Selim MATH211 Lecture 5 | Proofs
50
Proof:
•Say the conclusion is false, i.e. x < 1 and y< 1. (Note: or
becomes andin negation.)
•Adding the two conditions, the result is x+ y< 2.
•At this point, this condition is ¬Pif P = x+ y≥2, hence, P Λ ¬P
which is a contradiction.
•Hence, the statement above is true.

47. Problem 6 -Proof by Contradiction
The sum of even integers is even.
Sahar Selim MATH211 Lecture 5 | Proofs
51
Proof:
•Let x= 2m, y= 2nfor integers m and n and assume that x + yis odd.
•Then x+ y= 2m+ 2n= 2k+ 1 for some integer k.
•Hence, 2*(m + k -n) = 1, where m + n -kis some integer.
•This is a contradiction since 1 is not even.

48. Problem 7 -Proof by Cases
Let n ∈ Z. Prove that 9n
2
+3n-2 is even
Observe that 9n
2
+3n-2=(3n+2)(3n-1)
n is an integer →(3n+2)(3n-1) is the product of two integers
Case 1: Assume 3n+2 is even
→9n
2
+3n-2 is trivially even because it is the product of two integers, one of
which is even

Case 2: Assume 3n+2 is odd
→3n+2-3 is even →3n-1 is even →9n
2
+3n-2 is even because one of its
factors is even
Sahar Selim MATH211 Lecture 5 | Proofs
52

49. Problem 8 –
Proof by Contrapositive & Cases
Sahar Selim MATH211 Lecture 5 | Proofs
53

50. Supplementary Material
Discrete Math -1.7.1 Direct Proof
Discrete Math -1.7.2 Proof by Contraposition
Discrete Math -1.7.3 Proof by Contradiction
Discrete Math -1.8.1 Proof by Cases
Sahar Selim MATH211 Lecture 4 | Rules of Inference
54

51. Next Lecture
Set theory
set builder notation, subset, Cartesian product, power set, union,
intersection, complements, set identities.
Sahar Selim MATH211 Lecture 5 | Proofs
55