CSC236H1 Lecture Notes - Lecture 1: Natural Number, Cnet, Playstation 3
Document Summary
Review: predicates: a predicate is de ned over some variables and denotes a statement about a set of elements. O(n): n is an odd natural number. D(a, b): a divides b. bae ?ah. F (t om, bob): tom is the father of bob. Suppose we want to prove that a predicate p holds for all natural numbers greater than or equal to b n. Proof by simple induction: base case: prove p (b). Induction step: let k n, k b. Psi: if p (b) holds, and for all k n, k b, p (k) implies p (k + 1), then for all n n, n b, p (n) holds. ( b ) K > b pck ) pcktl f n. Suppose we proved that p (b) is true. Suppose we also proved that for all k n, k b, if p (k) holds then p (k + 1) holds. pcb ) pcbtl.
