Intro to Discrete Structures Lecture 15 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 15 p 1 35 DeMorgan for Intersection Example 10 Prove n j 1 Aj n Aj j 1 whenever A1 A2 An are subset of a universal U and n 2 Intro to Discrete StructuresLecture 15 p 2 35 DeMorgan for Intersection Intro to Discrete StructuresLecture 15 p 3 35 DeMorgan for Intersection Intro to Discrete StructuresLecture 15 p 4 35 Creative Uses of Mathematical Induction Example Show that every 2n 2n checkerboard with one square removed can be tiled using L shaped triominoes Intro to Discrete StructuresLecture 15 p 5 35 Creative Uses of Mathematical Induction Intro to Discrete StructuresLecture 15 p 6 35 Strong Induction Strong induction is based on the rule of inference 1 P 1 2 k kj 1 P j P k 1 3 nP n which is true for the domain of natural numbers N Intro to Discrete StructuresLecture 15 p 7 35 Strong Induction To prove that P n is true for all natural numbers n where P n is a propositional function we complete two steps Basis step We verify that P 1 is true We show that the conditional statement k j 1 P j P k 1 is true for all natural numbers k Intro to Discrete StructuresLecture 15 p 8 35 Existence of Prime Factorization Example Show that if n is an integer greater than 1 then n can be written as the product of primes Intro to Discrete StructuresLecture 15 p 9 35 Existence of Prime Factorization Intro to Discrete StructuresLecture 15 p 10 35 Existence of Prime Factorization Example 2 Show that if n is an integer greater than 1 then n can be written as the product of primes Intro to Discrete StructuresLecture 15 p 11 35 Winning Strategy Example 3 Intro to Discrete StructuresLecture 15 p 12 35 Winning Strategy Intro to Discrete StructuresLecture 15 p 13 35 Winning Strategy Intro to Discrete StructuresLecture 15 p 14 35 Well Ordering Property The validity of both the principle of mathematical induction and strong induction follows from a fundamental axiom of set of integers the well ordering property THE WELL ORDERING PROPERTY Every nonempty set of nonnegative integers has a least element Intro to Discrete StructuresLecture 15 p 15 35 Division Algorithm Example 5 Use the well ordering property to prove the division algorithm Intro to Discrete StructuresLecture 15 p 16 35 Division Algorithm Intro to Discrete StructuresLecture 15 p 17 35 Cycles in Round Robin Tournament Example 6 Intro to Discrete StructuresLecture 15 p 18 35 Cycles in Round Robin Tournament Intro to Discrete StructuresLecture 15 p 19 35 Recursive Definitions Structural Induction Sometimes it is difficult to define an object explicitly However it may be easy to define this object in terms of itself This process is called recursion Intro to Discrete StructuresLecture 15 p 20 35 Recursively Defined Functions We use two steps to define a function with the set of nonnegative integers as its domain Basis Step Specify the value of the function at zero Recursive Step Give a rule for finding its values from its values at smaller integers Example 1 Suppose that is recursively defined by f 0 3 f n 1 2f n 3 Find f 1 f 2 f 3 and f 4 Intro to Discrete StructuresLecture 15 p 21 35 Fibonacci numbers Definition 1 The Fibonacci numbers f0 f1 f2 are defined by the equation f0 f1 1 and fn fn 1 fn 2 for n 2 3 4 Intro to Discrete StructuresLecture 15 p 22 35 Growth of the Fibonacci Numbers Example 6 Show that whenever n 3 fn n 2 where 1 5 2 Intro to Discrete StructuresLecture 15 p 23 35 Growth of the Fibonacci Numbers Intro to Discrete StructuresLecture 15 p 24 35 Recursively Defined Sets and Structures Example 7 Consider the subset S of integers defined by Basis step 3 S Recursive step If x S and y S then x y S Intro to Discrete StructuresLecture 15 p 25 35 Well Formed Formulae Example 10 We can define the set of well formed formulae for compound statement forms involving T F propositional variables and operators from the set Basis step T F and s where s is a propositional variable are well formed formulae Recursive step If E and F are well formed formulae then E E F E F E F and E F are well formed Intro to Discrete StructuresLecture 15 p 26 35 Structural Induction A proof by structural induction consists of two parts Show that the result holds for all elements in the basis step of the recursive definition Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition the result holds for these new elements The validity of structural induction follows from the principle of mathematical induction of nonnegative integers To see this let P n state that this claim is true for all elements that are generated by n or few applications of these rules Intro to Discrete StructuresLecture 15 p 27 35 Structural Induction Example 13 Show that every well formed formulae for compound propositions contains an equal number of left and right parentheses Intro to Discrete StructuresLecture 15 p 28 35 Intro to Discrete StructuresLecture 15 p 29 35 Intro to Discrete StructuresLecture 15 p 30 35 Intro to Discrete StructuresLecture 15 p 31 35 Intro to Discrete StructuresLecture 15 p 32 35 Intro to Discrete StructuresLecture 15 p 33 35 Intro to Discrete StructuresLecture 15 p 34 35 Intro to Discrete StructuresLecture 15 p 35 35
View Full Document
Unlocking...