# 06-valid-arguments

Views:

## Presentation Description

No description available.

## Presentation Transcript

### Methods of Proof:

1 Methods of Proof CS/APMA 202 Epp, chapter 3 Aaron Bloomfield

### Proof methods:

2 Proof methods We will discuss ten proof methods: Direct proofs Indirect proofs Vacuous proofs Trivial proofs Proof by contradiction Proof by cases Proofs of equivalence Existence proofs Uniqueness proofs Counterexamples

### Direct proofs:

3 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

### Direct proof example:

4 Direct proof example Rosen, section 1.5, question 20 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

### Indirect proofs:

5 Indirect proofs Consider an implication: p→q It’s contrapositive is ¬q→¬p Is logically equivalent to the original implication! If the antecedent (¬q) is false, then the contrapositive is always true Thus, show that if ¬q is true, then ¬p is true To perform an indirect proof, do a direct proof on the contrapositive

### Indirect proof example:

6 Indirect proof example 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

### Which to use:

7 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

### Example of which to use:

8 Example of which to use Rosen, section 1.5, question 21 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

### Example of which to use:

9 Example of which to use Rosen, section 1.5, question 21 (a) 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

### Proof by contradiction:

10 Proof by contradiction Given a statement p, assume it is false Assume ¬p Prove that ¬p cannot occur A contradiction exists 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

### Proof by contradiction example 1:

11 Proof by contradiction example 1 Theorem (by Euclid): There are infinitely many prime numbers. Proof. Assume there are a finite number of primes List them as follows: p 1 , p 2 …, p n . Consider the number q = p 1 p 2 … p n + 1 This number is not divisible by any of the listed primes If we divided p i into 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 .

### Proof by contradiction example 2:

12 Proof by contradiction example 2 Rosen, section 1.5, question 21 (b) 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 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

### End of lecture on 31 January 2007:

13 End of lecture on 31 January 2007

### A note on that problem…:

14 A note on that problem… Rosen, section 1.5, question 21 Prove that if n is an integer and n 3 +5 is odd, then n is even Here, our implication is: If n 3 +5 is odd, then n is even The indirect proof proved the contrapositive: ¬q → ¬p I.e., If n is odd, then n 3 +5 is even The proof by contradiction assumed that the implication was false, and showed that led to a contradiction If we assume p and ¬q, we can show that implies q The contradiction is q and ¬q Note that both used similar steps, but are different means of proving the implication

### How others explain proof by contradiction:

15 How others explain proof by contradiction A very poor explanation, IMHO Suppose q is a contradiction (i.e. is always false) Show that ¬p→q is true Since the consequence is false, the antecedent must be false Thus, p must be true Find a contradiction, such as (r ¬r), to represent q Thus, you are showing that ¬p→(r ¬r) Or that assuming p is false leads to a contradiction

### Vacuous proofs:

16 Vacuous proofs Consider an implication: p→q If it can be shown that p is false, then the implication is always true By definition of an implication Note that you are showing that the antecedent is false

### Vacuous proof example:

17 Vacuous proof example Consider the statement: All criminology majors in CS 202 are female Rephrased: If you are a criminology major and you are in CS 202, then you are female Could also use quantifiers! Since there are no criminology majors in this class, the antecedent is false, and the implication is true

### Trivial proofs:

18 Trivial proofs Consider an implication: p→q If it can be shown that q is true, then the implication is always true By definition of an implication Note that you are showing that the conclusion is true

### Trivial proof example:

19 Trivial proof example Consider the statement: If you are tall and are in CS 202 then you are a student Since all people in CS 202 are students, the implication is true regardless

### Proof by cases:

20 Proof by cases Show a statement is true by showing all possible cases are true Thus, you are showing a statement of the form: is true by showing that:

### Proof by cases example:

21 Proof by cases example Prove that Note that b ≠ 0 Cases: Case 1: a ≥ 0 and b > 0 Then |a| = a, |b| = b, and Case 2: a ≥ 0 and b < 0 Then |a| = a, |b| = -b, and Case 3: a < 0 and b > 0 Then |a| = -a, |b| = b, and Case 4: a < 0 and b < 0 Then |a| = -a, |b| = -b, and

### The thing about proof by cases:

22 The thing about proof by cases Make sure you get ALL the cases The biggest mistake is to leave out some of the cases Don’t have extra cases We could have 9 cases in the last example Positive numbers Negative numbers Zero Those additional cases wouldn’t have added anything to the proof

### End of lecture on 2 February 2007:

23 End of lecture on 2 February 2007

### Proofs of equivalences:

24 Proofs of equivalences This is showing the definition of a bi-conditional Given a statement of the form “p if and only if q” Show it is true by showing (p→q) (q →p) is true

### Proofs of equivalence example:

25 Proofs of equivalence example Rosen, section 1.5, question 40 Show that m 2 =n 2 if and only if m=n or m=-n Rephrased: (m 2 =n 2 ) ↔ [(m=n) (m=-n)] Need to prove two parts: [(m=n) (m=-n)] → (m 2 =n 2 ) Proof by cases! Case 1: (m=n) → (m 2 =n 2 ) (m) 2 = m 2 , and (n) 2 = n 2 , so this case is proven Case 2: (m=-n) → (m 2 =n 2 ) (m) 2 = m 2 , and (-n) 2 = n 2 , so this case is proven (m 2 =n 2 ) → [(m=n) (m=-n)] Subtract n 2 from both sides to get m 2 -n 2 =0 Factor to get (m+n)(m-n) = 0 Since that equals zero, one of the factors must be zero Thus, either m+n=0 (which means m=n) or m-n=0 (which means m=-n)

### Existence proofs:

26 Existence proofs Given a statement: x P(x) We only have to show that a P(c) exists for some value of c Two types: Constructive: Find a specific value of c for which P(c) exists Nonconstructive: Show that such a c exists, but don’t actually find it Assume it does not exist, and show a contradiction

### Constructive existence proof example:

27 Constructive existence proof example Show that a square exists that is the sum of two other squares Proof: 3 2 + 4 2 = 5 2 Show that a cube exists that is the sum of three other cubes Proof: 3 3 + 4 3 + 5 3 = 6 3

### Non-constructive existence proof example:

28 Non-constructive existence proof example Rosen, section 1.5, question 50 Prove that either 2*10 500 +15 or 2*10 500 +16 is not a perfect square A perfect square is a square of an integer Rephrased: Show that a non-perfect square exists in the set {2*10 500 +15, 2*10 500 +16} Proof: The only two perfect squares that differ by 1 are 0 and 1 Thus, any other numbers that differ by 1 cannot both be perfect squares Thus, a non-perfect square must exist in any set that contains two numbers that differ by 1 Note that we didn’t specify which one it was!

### Uniqueness proofs:

29 Uniqueness proofs A theorem may state that only one such value exists To prove this, you need to show: Existence: that such a value does indeed exist Either via a constructive or non-constructive existence proof Uniqueness: that there is only one such value

### Uniqueness proof example:

30 Uniqueness proof example If the real number equation 5x+3=a has a solution then it is unique Existence We can manipulate 5x+3=a to yield x=(a-3)/5 Is this constructive or non-constructive? Uniqueness If there are two such numbers, then they would fulfill the following: a = 5x+3 = 5y+3 We can manipulate this to yield that x = y Thus, the one solution is unique!

### Counterexamples:

31 Counterexamples Given a universally quantified statement, find a single example which it is not true Note that this is DISPROVING a UNIVERSAL statement by a counterexample x ¬R(x), where R(x) means “x has red hair” Find one person (in the domain) who has red hair Every positive integer is the square of another integer The square root of 5 is 2.236, which is not an integer

### A note on counterexamples:

32 A note on counterexamples You can DISPROVE something by showing a single counter example You are finding an example to show that something is not true You cannot PROVE something by example Example: prove or disprove that all numbers are even Proof by contradiction: 1 is not even (Invalid) proof by example: 2 is even

### Mistakes in proofs:

33 Mistakes in proofs Modus Badus Fallacy of denying the hypothesis Fallacy of affirming the conclusion Proving a universal by example You can only prove an existential by example! Disproving an existential by example You can only disprove a universal by example! 