Propositional/Predicate Logic, Rules of Inference & Mathematical Induction
Idea in plain words
Logical Connectives: Conjunction (∧), Disjunction (∨), Implication (p → q ≡ ¬p ∨ q), Biconditional (p ↔ q).
Exam tip
High-yield exam topic (Very High).
Explanation
Formal mathematical logic eliminates ambiguity from specifications, automated reasoning, software verification, and compiler construction. The principle of mathematical induction is equivalent to the Well-Ordering Property of positive integers, providing the mathematical bedrock for proving correctness and termination of recursive algorithms.
Key points
- Tautology (always True), Contradiction (always False), Contingency (neither).
- Rules of Inference: Modus Ponens [p, p → q ∴ q], Modus Tollens [¬q, p → q ∴ ¬p], Hypothetical Syllogism [p → q, q → r ∴ p → r], Resolution [p ∨ q, ¬p ∨ r ∴ q ∨ r].
- Quantifiers: Universal ∀x P(x) (True for all x); Existential ∃x P(x) (True for at least one x). Negation: ¬(∀x P(x)) ≡ ∃x ¬P(x).
- Proof Methods: Direct proof, Contrapositive proof (prove ¬q → ¬p to establish p → q), Contradiction (assume ¬p and derive a fallacy).
- Mathematical Induction: Basis Step (prove P(1) is true), Inductive Step (assume P(k) true, prove P(k+1) is true).
Example
Example
Proof by Contradiction: Prove that √2 is irrational. Assume √2 = a/b where gcd(a, b) = 1. Then 2 = a²/b² => a² = 2b² => a² is even => a is even => a = 2k. Then (2k)² = 2b² => 4k² = 2b² => b² = 2k² => b is even. But if both a and b are even, gcd(a,b) ≥ 2, contradicting gcd(a,b) = 1. Hence √2 must be irrational.
Code examples
// Proof by Mathematical Induction:
// Claim: Prove that 1 + 2 + 3 + ... + n = n(n + 1) / 2 for all n ≥ 1.
// 1. Basis Step (n = 1):
// LHS = 1; RHS = 1(1 + 1)/2 = 2/2 = 1. LHS = RHS. Basis step holds!
// 2. Inductive Hypothesis:
// Assume true for n = k: 1 + 2 + ... + k = k(k + 1) / 2
// 3. Inductive Step (n = k + 1):
// LHS = (1 + 2 + ... + k) + (k + 1)
// = [k(k + 1) / 2] + (k + 1)
// = (k + 1) [ (k/2) + 1 ]
// = (k + 1) (k + 2) / 2 = (k + 1)((k + 1) + 1) / 2
// Which is the formula for n = k + 1.
// By PMI, the formula holds for all integers n ≥ 1. Q.E.D.
Exam questions
- [8 Marks] Prove using the Principle of Mathematical Induction that 2^n < n! for all integers n ≥ 4.
- [7 Marks] Without using truth tables, prove the logical equivalence: ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q.
- [7 Marks] Using rules of inference, prove the validity of the conclusion: 'If it rains, the grass is wet. The grass is not wet. Therefore, it did not rain.'