Summary of "Discrete Math - 1.7.2 Proof by Contraposition"
Summary of “Discrete Math - 1.7.2 Proof by Contraposition”
This video explains the proof technique called proof by contraposition, which is a form of indirect proof. It contrasts this method with direct proof and demonstrates how to apply contraposition in mathematical proofs.
Main Ideas and Concepts
Proof by Contraposition
- It is an indirect proof method.
- Relies on the logical equivalence: If P then Q is logically equivalent to If not Q then not P.
- Instead of proving “P implies Q” directly, you prove “not Q implies not P”.
- This approach can sometimes simplify proofs by working with the contrapositive statement.
Direct Proof vs Contraposition
- Direct proof assumes P is true and shows Q is true.
- Contraposition assumes not Q and shows not P.
Logical Foundation
- The truth of “if P then Q” is the same as the truth of its contrapositive “if not Q then not P”.
Methodology / Step-by-step Instructions for Proof by Contraposition
- Identify the implication you want to prove: If P then Q.
- Write down the contrapositive statement: If not Q then not P.
- Assume not Q (the negation of the conclusion).
- Using this assumption, prove not P (the negation of the premise).
- Conclude that since not Q implies not P is true, the original statement If P then Q is true.
- End the proof with a QED symbol or equivalent.
Example Walkthroughs from the Video
Example 1
- Statement: If n is odd (P), then 3n + 2 is odd (Q).
- Contrapositive: If 3n + 2 is not odd (i.e., even) (not Q), then n is not odd (i.e., even) (not P).
- Proof steps:
- Assume n is even → n = 2k for some integer k.
- Substitute into 3n + 2: 3(2k) + 2 = 6k + 2 = 2(3k + 1), which is even.
- Thus, not Q implies not P.
- Therefore, the original statement is true.
Example 2 (Exercise for the viewer)
- Statement: If n is even (P), then 3n + 2 is even (Q).
- Contrapositive: If 3n + 2 is not even (i.e., odd) (not Q), then n is not even (i.e., odd) (not P).
- Proof steps:
- Assume n is odd → n = 2k + 1.
- Substitute into 3n + 2: 3(2k + 1) + 2 = 6k + 3 + 2 = 6k + 5.
- Express 6k + 5 as 2(3k + 2) + 1, which is odd.
- Thus, not Q implies not P.
- Hence, the original statement is true.
Closing Notes
- The video concludes by previewing the next topic: proof by contradiction.
- Viewers are encouraged to try the second example on their own before watching the solution.
Speakers / Sources
- The video features a single instructor or narrator explaining the concepts (no other speakers identified).
- No named individuals mentioned.
Category
Educational
