Chapter 6 : Proof Techniques Flashcards
List out 2 types of Proof
- Direct Proof
- Indirect Proof
List out the type of Proof in Direct Proof
- Proof by construction
List out 2 types of Proof in Indirect Proof
- Proof by Contrapositive
- Proof by Contradiction
- Show the answer
- Show the answer is wrong at the end
Sum of 2 even integers is odd
2i + 2j = c , where c is some integer
i + j = c / 2 ( Contradiction Happens )
How can we Proof by Construction ( Direct Proof ) a statement?
Proof p → q
1. Assume p is True
2. Show q is True
3. Conclusion p → q is True
How can we Proof by Contrapositive ( Indirect Proof ) a statement?
Proof p → q ≡ ~q → ~p
1. Identidy ~q → ~p
2. Assume ~q is True
3. Show ~p is True
4. ∴~q → ~p is True
5. p → q is True ( p → q ≡ ~q → ~p )
How can we Proof by Contradiction ( Indirect Proof ) a statement?
Proof p is True ( Single Statement )
1. Assume ~p is True
2. Contradictio happen ( ~p is False )
3. ∴ p is True
Proof p → q is True
1. Assume p ^ ~q is True
2. Contradiction p ^ ~q is False
3. Conclusion p → q is True
~ ( p → q ) ≡ p ^ ~q
p → q is True
~ ( p → q ) is False
Assume ~ ( p → q ) is True
What statement does Axioms ( Postulates ) mean?
- A statement that is assumed to be true without a proof
- Example
A straight line segment can be drawn between any two distinct points.” We don’t try to prove that; we accept it as a starting point
What statement does Hypothesis mean?
- Statements that has conditions of if parts of what we want to prove
- Example
If a triangle is right-angled, then the square of the hypotenuse is the sum of the squares of the other two sides,” the phrase “If a triangle is right-angled” is the hypothesis.
What does the Rules of Inference do?
- Logical steps that used to draw conclusions and to move from one step to another
- Deliverable is New Theorems
- Rules of Inference pass in
- Axioms
- Hypothesis
- Previously Proven Theorems
List out the basic definition below:
1. Even Number
2. Odd Number
- n = 2k
- n = 2k + 1
What does a Direct Proof proofs?
- Shows that a conditional statement p → q is true by showing that if p is true then q must also be true
Proof that “if n is an odd integer, then n² is odd”
We assume that n is odd ( Hypothesis )
n = 2k + 1, where k is some integer ( Definition of Odd )
n = ( 2k + 1 ) ( 2k + 1 )
= 4k² + 4k + 1
= 2 ( 2k² + 2k ) + 1
Let r = 2k² + 2k . Then r is an integer ( Axiom ) therefore n² = 2r + 1
So, we have proved the theorem “if n is an odd integer, then n² is odd”
What to write inside direct proof? ( 5 )
- We assume that n is odd/even
- n = 2k + 1 / n = 2k, where k is some integer
- Equation n² = ( 2k + 1 )( 2k + 1 )
- Let r = … . Then r is an integer therefore … is odd/even
- So, we have proved the theorem “Question”
Prove that “for every 2 integers a and b, if a and b are odd, then ab is odd”
Let i and j are integers
We assume that a and b are odd
a = 2i + 1 , b = 2j + 1 , where i and j is some integer
ab = ( 2i + 1 ) ( 2j + 1 )
= 2 ( 2ij + i + j ) = 1
Let r = 2ij + i + j . Then r is an integer therefore ab is odd
So we have proved the theorem “for every 2 integers a and b, if a and b are odd, then ab is odd”
Give a direct proof if n is an even integer, then n² + 2n is also an even integer
We assume that n is an even integer
Let n = 2k
n² + 2n = ( 2k )² + 2( 2k )
= 4k² + 4k
= 2 ( 2k² + 2k )
Let r = 2k² + 2k . Then r is an integer therefore n² + 2n = 2r is even
So we have proved the theorem “if n is an even integer, then n² + 2n is also an even integer”
Give a direct proof if n is an even integer, then n³ + n is also an even integer
We assume that n is an even integer
Let n = 2k
n³ + n = ( 2k ) ³ + 2k
= 8k³ + 2k
= 2 ( 4k³ + k )
Let r = 4k³ + 2k. Then r is an integer therefore n³ + n = 2r is even
So we have proved the theorem “if n is an even integer, then n³ + n is also an even integer”
What is the formula for the Proof by Contrapositive?
- p → q ≡ ~q → ~p
- So we need to identify ~q is ~p is true to verify that it is equal to p → q
Prove that “if n is an integer and 3n + 2 is odd, then n is odd”
We assume that n is even ( n is odd in question )
Then n = 2k, where k is some integer.
Therefore
3n + 2 = 3 ( 2k ) + 2
= 6k + 2
= 2 ( 3k + 1 ) is even ( 2m )
So we have proved that ~q ( n is even, although n is odd in question ) → ~p ( the equation is even, although the question is odd )
Because the negation of the conclusion of the conditional statement implies that the hypothesis ( p ) is false, the original conditional statement is true.
So, we have proved the theorem “if n is an integer and 3n + 2 is odd, then n is odd”
If x is a real number and 3x³-9x²+x-3 = 0 , then x = 3 using proof by contrapositive
We assume that If x is a real number and 3x³-9x²+x-3 = 0 , then x = 3 is false.
Assume x ≠ 3 then,
3x³-9x²+x-3 = 3x² ( x - 3 ) + 1 ( x - 3 )
= ( 3x² + 1 ) ( x - 3 )
( 3x² + 1 ) ≠ 0 and ( x - 3 ) ≠ 0
Because the negation of the conclusion of the contradictional statement implies that the hypothesis ( p ) is false, the original conditional statement is true
So, we have proved that If x is a real number and 3x³-9x²+x-3 = 0 , then x = 3
- Explanation
(x - 3) ≠ 0: This explicitly states that if x is not equal to 3, then this factor is non-zero. For the entire product (3x² + 1)(x - 3) to be zero in this case, the other factor (3x² + 1) must be zero.
What is the formula for the Proof by Contradiction?
- ~ ( p → q ) ≡ p ^ ~q
Give a proof by contradiction of the theorem : “If 3n + 2 is odd, then n is odd”
Suppose that 3n + 2 is odd and n is even ( p ^ ~q )
Then, n = 2r, where r is some integer
Hence 3n = 6r
3n + 2 = 6r + 2
3n + 2 = 2 ( 3r + 1 )
3n + 2 = 2k , where k = 3r + 1
Thus 3n + 2 is even, which is false ( Contradiction! )
So, we have proved the theorem “If 3n + 2 is odd, then n is odd”
Give a proof by contradiction of the theorem : “If x² ≥ 25 then |x| ≥ 5”
Suppose that x² ≥ 25 then we need to show |x| < 5.
Then either x < 5 or x > -5
If x < 5 then x² < 25
IF x > -5 , we again have x² < 25
In either case, we have a contradiction. Hence |x| ≥ 5 So, we have proved the theorem "If x² ≥ 25 then |x| ≥ 5"
- Explanation
The inequality ∣x∣<5 means that the distance of x from zero is less than 5. Let’s consider what numbers satisfy this condition on the number line:
Numbers that are less than 5 units to the right of zero satisfy this. These are all the numbers x such that 0≤x<5.
Numbers that are less than 5 units to the left of zero also satisfy this. These are all the numbers x such that −5<x≤0.
Use a direct proof to prove that the sum of two odd integers is even
Let a and b are 2 odd integers
a = 2 i + 1 , where i is some integer
b = 2 j + 1 , where j is some integer
a + b = 2i + 1 + 2j + 1
= 2i + 2j + 2
= 2 ( i + j + 1 )
= 2k , where k = i + j + 1
Therefore, we have proved that a + b is even
Use a proof by contradiction to prove that the sum of 2 even integers is even
Assume “Sum of 2 even integers is odd”
Let a and b are even integers
a = 2i, where i is some integer
b = 2j, where j is some integer
a + b = c , where c is some odd integer
2i + 2j = c
2 ( i + j ) = c
i + j = c / 2 → Always Fraction ( Contradiction Error )
i + j is integer but c / 2 is fraction and since c is odd integer
i + j ≠ c / 2 contradiction
We have proven that sum of 2 even integers is even
