Propositional Logic and Proof by Induction: A Step-by-Step Guide
Logic and induction are where many students first meet "proof" in computing maths. Both follow strict rules, which is good news: once you know the template, you can write answers that get full marks every time.
1. Propositions and connectives
A proposition is a statement that is either true or false, such as "7 is prime". Connectives join propositions:
| Symbol | Name | True when… |
|---|---|---|
| ¬p | Negation (not) | p is false |
| p ∧ q | Conjunction (and) | both are true |
| p ∨ q | Disjunction (or) | at least one is true |
| p → q | Implication (if p then q) | every case except p true and q false |
| p ↔ q | Biconditional (if and only if) | both have the same value |
The implication is the one students get wrong most often: p → q is true whenever p is false. "If it rains, I'll bring an umbrella" isn't broken on a dry day.
2. Truth tables
A truth table lists every combination of truth values. With n variables there are 2n rows. Here is p → q and its equivalent ¬p ∨ q:
| p | q | p → q | ¬p | ¬p ∨ q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
The two columns match in every row, so p → q ≡ ¬p ∨ q. A formula that is true in every row is a tautology; one false in every row is a contradiction.
3. Equivalences and De Morgan's laws
- De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, and ¬(p ∨ q) ≡ ¬p ∧ ¬q
- Double negation: ¬¬p ≡ p
- Contrapositive: p → q ≡ ¬q → ¬p (the converse q → p is not equivalent)
- Distributive: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
When simplifying, write the law you used next to each line. Markers give method marks for named steps.
4. Proof by induction: the template
Induction proves that a statement P(n) is true for every integer n ≥ some starting value. Think of dominoes: show the first one falls, and show that any falling domino knocks over the next.
- Base case: show P(n0) is true for the starting value (often n = 1).
- Inductive hypothesis: assume P(k) is true for some arbitrary k ≥ n0.
- Inductive step: using that assumption, prove P(k + 1) is true.
- Conclusion: by the principle of mathematical induction, P(n) is true for all n ≥ n0.
5. Worked example
Prove: 1 + 2 + … + n = n(n + 1)/2 for all n ≥ 1.
Base case (n = 1): left side = 1, right side = 1(2)/2 = 1. True.
Hypothesis: assume 1 + 2 + … + k = k(k + 1)/2 for some k ≥ 1.
Step: 1 + 2 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) (using the hypothesis) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2, which is exactly the formula with n = k + 1.
Conclusion: by mathematical induction, the formula holds for all n ≥ 1. ∎
6. Common mistakes
- Skipping the base case or the written conclusion. Both carry marks.
- Assuming P(k + 1) instead of proving it.
- Not clearly showing where the hypothesis was used in the step.
- Treating p → q as false when p is false.
- Confusing the converse (q → p) with the contrapositive (¬q → ¬p).