Building Logical Arguments in Mathematics and Computing
Topics:
- What is a mathematical proof?
- Direct proof method
- Proof by contraposition
- Proof by contradiction
- Proof by cases
- How to choose the right strategy
Topics:
This week (Week 4): We'll use these logical tools to construct mathematical proofs!
| Operator | Symbol | Meaning | When True? |
|---|---|---|---|
| NOT | ¬p | negation | When p is false |
| AND | p ∧ q | conjunction | When both p and q are true |
| OR | p ∨ q | disjunction | When at least one of p, q is true |
| IMPLIES | p → q | implication | When p is false OR q is true |
| IFF | p ↔ q | biconditional | When p and q have same truth value |
This is crucial for proofs!
Common mistake to avoid!
Statement: If it rains, the ground is wet
Contrapositive (equivalent): If the ground is not wet, it's not raining
Converse (NOT equivalent): If the ground is wet, it's raining
∀x P(x)
"For all x, P(x) is true"
"Every x has property P"
Example:
∀n ∈ ℤ, n² ≥ 0
"All integers have non-negative squares"
∃x P(x)
"There exists an x such that P(x) is true"
"At least one x has property P"
Example:
∃n ∈ ℤ, n² = 4
"There exists an integer whose square is 4"
| Statement | Negation | In English |
|---|---|---|
| ∀x P(x) | ∃x ¬P(x) | "Not all x have P" = "Some x doesn't have P" |
| ∃x P(x) | ∀x ¬P(x) | "No x has P" = "All x don't have P" |
Statement: ∀n ∈ ℤ, n² ≥ 0 (All integer squares are non-negative)
Negation: ∃n ∈ ℤ, n² < 0 (Some integer has negative square)
∀x (P(x) → Q(x))
"For all x, if P(x) then Q(x)"
∃x P(x) or ¬∃x P(x)
"There exists..." or "There does not exist..."
Universal statements are like loop invariants: "For all iterations, property P holds"
Existential statements are like search results: "There exists an element satisfying the condition"
Ready? Let's learn how to prove things! →
Keep these handy while writing proofs! Bookmark this slide.
| Contrapositive: | p → q ≡ ¬q → ¬p |
| Implication: | p → q ≡ ¬p ∨ q |
| De Morgan's: | ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Biconditional: | p ↔ q ≡ (p → q) ∧ (q → p) |
| ¬(∀x P(x)) | ≡ ∃x ¬P(x) |
| ¬(∃x P(x)) | ≡ ∀x ¬P(x) |
A proof consists of:
Think of a proof as a program that verifies correctness:
Most theorems have the form: "If P, then Q" written as P → Q
What we assume is true
Example:
"If n is an even integer..."
Hypothesis: n = 2k for some integer k
What we want to prove
Example:
"...then n² is even"
Conclusion: n² = 2m for some integer m
We have four main proof strategies to prove P → Q:
| Method | What You Do | When to Use |
|---|---|---|
| Direct Proof | Assume P is true → Show Q must be true |
There's a clear path from P to Q |
| Contraposition | Assume ¬Q is true → Show ¬P must be true |
Easier to work with negations |
| Contradiction | Assume P ∧ ¬Q is true → Derive something impossible |
Direct path is unclear |
| Cases | Break P into cases → Prove Q in each case |
P naturally splits into scenarios |
Don't worry! We'll explore each method with templates, examples, and strategies.
Direct proof is like running a program forward:
function prove(P) {
// Start with P (input/assumption)
step1 = process(P); // logical deduction
step2 = process(step1); // another deduction
...
return Q; // arrive at conclusion
}
Note: This seems obvious, but explicit proofs like this are the foundation for proving complex algorithm properties!
These often need other methods!
Instead of proving "If P then Q", we prove "If not Q, then not P"
If n² is even,
then n is even
P: n² is even
Q: n is even
If n is not even (odd),
then n² is not even (odd)
¬Q: n is odd
¬P: n² is odd
Like testing error conditions instead of success conditions:
// Instead of: "if valid input, then valid output"
// Test: "if invalid output, then invalid input"
if (!isValidOutput(result)) {
// Prove input must have been invalid
assert(!isValidInput(input));
}
Statement: If n² > 100, then n > 10 or n < -10
Contrapositive: If -10 ≤ n ≤ 10, then n² ≤ 100
The contrapositive is easier - just square the bounds!
Statement: If x is irrational, then √x is irrational
Contrapositive: If √x is rational, then x is rational
Working with "rational" definitions is easier!
To prove P → Q by contradiction:
Like debugging by assuming "the bug doesn't exist":
// Assume: "My code is correct" (no bug)
// But then we observe: program crashes (contradiction!)
// Conclusion: There must be a bug
assert(codeIsCorrect); // Assume true
result = runProgram();
if (result == CRASH) { // Contradiction!
// Our assumption must be wrong
conclusion = "Code has a bug";
}
| Aspect | Contraposition | Contradiction |
|---|---|---|
| What you assume | Assume ¬Q only | Assume P AND ¬Q |
| What you prove | Show ¬P follows | Show impossibility follows |
| Equivalent to | ¬Q → ¬P | (P ∧ ¬Q) → False |
| Feels like | Proving a different statement | Showing assumption is impossible |
Theorem: If n² is even, then n is even
Both work! Contraposition is cleaner here. Contradiction is overkill.
Assume there is a largest prime p.
Consider N = (2 × 3 × 5 × ... × p) + 1 (product of all primes up to p, plus 1)
N is not divisible by any prime ≤ p (leaves remainder 1)
So either N is prime (larger than p) or has a prime factor larger than p
Contradiction! There must be a prime larger than p.
If P ≡ P₁ ∨ P₂ ∨ ... ∨ Pₙ, to prove P → Q:
function prove(input) {
switch(input.type) {
case TYPE_A:
// Prove Q for case A
return proveForCaseA(input);
case TYPE_B:
// Prove Q for case B
return proveForCaseB(input);
case TYPE_C:
// Prove Q for case C
return proveForCaseC(input);
}
// All cases covered → Q proven!
}
| If you see... | Try this first | Why |
|---|---|---|
| "For any even/odd integer..." | Cases | Natural split into even/odd |
| "If A and B, then C" (multiple conditions) |
Direct | Combine conditions forward |
| "If n² has property X, then n has property X" | Contraposition | Easier to work with n than n² |
| "X is irrational/impossible" | Contradiction | Hard to prove "not something" |
| "There are infinitely many..." | Contradiction | Assume finitely many → contradiction |
| "There is exactly one..." | Contradiction (for uniqueness) |
Assume two different ones → contradiction |
| "If x > y, then..." | Direct | Can use inequality algebra |
| You're stuck! | Try contrapositive | Different perspective often helps |
Think: Does n naturally split into cases?
Yes! When dividing by 3, any integer n leaves remainder 0, 1, or 2.
→ Use PROOF BY CASES!
Try working through each case on your own, then check the next slide for the full proof!
The contrapositive transforms this into a much easier statement! See next slide...
Problem: You started with the CONCLUSION and worked to the HYPOTHESIS. That's backwards!
Problem: You ASSUMED "n+2 is even" (the thing you're trying to prove!)
| Statement | Form | Equivalent to P → Q? |
|---|---|---|
| Original | P → Q | Yes (it's itself!) |
| Contrapositive | ¬Q → ¬P | YES |
| Converse | Q → P | NO |
| Inverse | ¬P → ¬Q | NO |
A proof is not just for you — it's for your reader! Make it easy to follow.
Like proving two functions are inverses:
// To prove f and g are inverses:
// 1. Show: f(g(x)) = x for all x
// 2. Show: g(f(x)) = x for all x
// Both directions needed!
You wouldn't expect to write complex programs after one lecture — same with proofs!
Example: Prove binary search finds the target or returns "not found" in O(log n) time
Example: Prove a cryptographic protocol prevents eavesdropping
Think of proof techniques as: