Prove P → Q by proving the equivalent ¬Q → ¬P
Proof by contrapositive exploits a fundamental fact of logic: the statement P → Q is logically equivalent to ¬Q → ¬P. Instead of proving P → Q directly, we prove ¬Q → ¬P. This is not a roundabout method -- it is proving the exact same thing in a different form.
Use contrapositive when the negation of Q gives you something concrete to work with, or when the direct path from P to Q feels unnatural.
See why P → Q and ¬Q → ¬P have identical truth tables. They are false in exactly the same situation: when P is true and Q is false.
See why P → Q and ¬Q → ¬P are logically equivalent. They have the same truth values in every possible scenario!
| P | Q | P → Q | ¬Q | ¬P | ¬Q → ¬P | Match? |
|---|---|---|---|---|---|---|
| T | T | T | F | F | T | ✓ |
| T | F | F | T | F | F | ✓ |
| F | T | T | F | T | T | ✓ |
| F | F | T | T | T | T | ✓ |
Notice: P → Q and ¬Q → ¬P have identical truth values in every row!
P → Q ≡ ¬Q → ¬P. These are not just "related"—they're the exact same statement in different logical clothing. Proving one automatically proves the other. This is why contrapositive is so powerful: you're not taking a detour, you're walking the same path in reverse!
Key insight: Do not confuse the contrapositive (¬Q → ¬P) with the converse (Q → P). The converse is a completely different statement and is NOT equivalent to the original.
These two techniques are often confused. Contrapositive proves an equivalent statement directly; contradiction seeks an impossibility. See the difference side-by-side.
These two techniques are often confused! Let's clarify the differences and practice choosing the right approach.
| Aspect | Contrapositive | Contradiction |
|---|---|---|
| What you prove | An equivalent statement (¬Q → ¬P) | The original statement (P) by showing ¬P is impossible |
| What you assume | ¬Q (the negation of the conclusion) | ¬P (the negation of what you want to prove) |
| What you derive | ¬P (the negation of the hypothesis) | A logical impossibility (X ∧ ¬X) |
| Type of proof | Direct proof of an equivalent statement | Indirect proof via impossibility |
| Best used when | ¬Q gives useful concrete information | Direct/contrapositive seem hard, or proving existence/uniqueness |
Prove: "If n² is odd, then n is odd"
What's the best proof technique?
Key insight: A contrapositive proof is really a direct proof of an equivalent statement. It never needs to reach a contradiction -- it just proves ¬Q → ¬P in a straight line.
Walk through the classic example: "if n² is even, then n is even." The direct proof is awkward, but the contrapositive -- "if n is odd, then n² is odd" -- is a clean two-line calculation.
Walk through classic contrapositive proofs step by step. See how assuming ¬Q leads us to prove ¬P.
We want to prove: If n² is even, then n is even.
Key insight: Contrapositive shines for statements about divisibility and parity. "If n is odd" immediately gives n = 2k+1, which is easy to square and analyze.