Factorial Function(Strictly)Increasing / DecreasingAddition / Multiplication of FunctionsSequences and SummationsSequencesGeometric ProgressionArithmetic ProgressionThe Tower of HanoiSlicing PizzaThe Josephus ProblemSolution to the Josephus ProblemSolution to the Josephus ProblemSummationSummationGeometric sumsCardinalityCountable vs. UncountableOdd NumbersIntegersRational NumbersReal NumbersReal NumbersCantor Diagonalization ArgumentHalting ProblemG"odel's Incompleteness TheoremBookIntro to Discrete StructuresLecture 11Pawel M. WocjanSchool of Electrical Engineering and Computer ScienceUniversity of Central [email protected] to Discrete StructuresLecture 11 – p. 1/29Factorial FunctionThe factorial function f : N → Z+is denoted by f(n) = n!.The value of f(n) = n! is the product of the first n positiveintegers, son! = 1 · 2 · · · (n − 1) · nand 0! = 1.Intro to Discrete StructuresLecture 11 – p. 2/29(Strictly) Increasing / DecreasingDefinition 6: Let f : A → B with A, B ⊆ R.The function f is calledincreasing iff(x) ≤ f(y)strictly increasing iff(x) < f(y)whenever x < y.Intro to Discrete StructuresLecture 11 – p. 3/29Addition / Multiplication of FunctionsDefinition 3: Let f1, f2: A → R.Then f1+ f2and f1f2are also functions from A to R definedby(f1+ f2)(x) = f1(x) + f2(x) , (1)(f1f2)(x) = f1(x)f2(x) . (2)Intro to Discrete StructuresLecture 11 – p. 4/29Sequences and SummationsIntro to Discrete StructuresLecture 11 – p. 5/29SequencesDefinition 1: A sequence is a function from a subset of theset of integers (usually the set {0, 1, 2, . . .} or the set{1, 2, 3, . . . , }) to a set S.We use the notation anto denote the image of the integer n.We call ana term of the sequence.Example 1: Consider the sequence {an} with an= 1/n.Intro to Discrete StructuresLecture 11 – p. 6/29Geometric ProgressionDefinition 2: A geometric progression is a sequence ofthe forma, ar, ar2, . . . , arn, . . .where the initial term a and the common ratio r are realnumbers.Remark: A geometric progression is a discrete analogue ofthe exponential function f : R → R, x 7→ arx.Intro to Discrete StructuresLecture 11 – p. 7/29Arithmetic ProgressionDefinition 2: An arithmetic progression is a sequence ofthe forma, a + d, a + 2d, . . . , a + nd, . . .where the initial term a and the common difference r arereal numbers.Remark: A geometric progression is a discrete analogue ofthe linear function f : R → R, x 7→ dx + a.Intro to Discrete StructuresLecture 11 – p. 8/29The Tower of HanoiWe are given a tower of n discs, initially stacked indecreasing size on one of three pegs:The objective is to transfer the entire tower to one of theother pegs, moving only one disc at a time and nevermoving a larger one onto a smaller.Find a simple expression for Tn, the number of minimalmoves required to accomplish this.Intro to Discrete StructuresLecture 11 – p. 9/29Slicing PizzaHow many slices of pizza can a person obtain by making nstraight cuts with a pizza knife?Or, more academically: What is the maximum number of Lnof regions defined by n lines in the plane?Find a simple expression for Ln.Intro to Discrete StructuresLecture 11 – p. 10/29The Josephus ProblemWe start with n people numbered 1 to n around a circle, andwe eliminate every second remaining person until only onesurvives. Denote this person by Jn. For example, here’s thestarting configuration for n = 10.The elimination order is 2, 4, 6, 8, 10, 3, 7, 1, 9, so J10= 5survives.Intro to Discrete StructuresLecture 11 – p. 11/29Solution to the Josephus ProblemFind a (closed form) formula for anthat makes it possible toefficiently compute Jnfor large n.Intro to Discrete StructuresLecture 11 – p. 12/29Solution to the Josephus ProblemFind a (closed form) formula for Jnthat makes it possible toefficiently compute Jnfor large n.Every n ∈ N can be uniquely written as2m+ ℓ with m ≥ 0 and 0 ≤ ℓ < 2m.Observe that m = ⌊log2n⌋ and ℓ = n − 2m.The solution isJn= 2ℓ + 1 .Intro to Discrete StructuresLecture 11 – p. 13/29SummationWe now introduce summation notation. We begin bydescribing the notation used to express the sum of thetermsam, am+1, . . . , an,from the sequence {an}.We use the notationnXj=maj,Pnj=maj, orP1≤j≤najto represent am+ am+1+ . . . + an.Intro to Discrete StructuresLecture 11 – p. 14/29SummationnXj=majHere the variable j is called the index of summation, andthe choice of letter as the variable is arbitrary.The index of summation runs through all integers startingwith its lower limit m and ending with its upper limit n.A large upper case Greek lettersigma, Σ, is used todenote the summation.Intro to Discrete StructuresLecture 11 – p. 15/29Geometric sumsTheorem 1: If a and r are real numbers and r 6= 0, thennXj=0arj=(an+1−ar−1if r 6= 1(n + 1)a if r = 1Intro to Discrete StructuresLecture 11 – p. 16/29CardinalityDefinition 4: The sets A and B have the same cardinalityiff there is a bijection from A to B.Intro to Discrete StructuresLecture 11 – p. 17/29Countable vs. UncountableDefinition 5: A set that either finite or has the samecardinality as the set of natural numbers N = {1, 2, 3, . . .} iscalled countable.A set that is not countable is called uncountable.The cardinality of a finite set S is denoted by |S|.When an infinite set S is countable, we denote thecardinality of S by ℵ0. We write |S| = ℵ0and say that S hascardinality “aleph null”.Intro to Discrete StructuresLecture 11 – p. 18/29Odd NumbersExample 18: Show that the set of odd natural numbers is acountable set.Intro to Discrete StructuresLecture 11 – p. 19/29IntegersExample 19: Show that the set Z of all integers is countable.Intro to Discrete StructuresLecture 11 – p. 20/29Rational NumbersExample 19: Show that the set Q+of positive rationalnumbers is countable.Intro to Discrete StructuresLecture 11 – p. 21/29Real NumbersExample 21: Show that the set R of real numbers isuncountable.Assume the contrary. Then, there is a bijection N → [0, 1)r1= d11d12d13d14. . .r2= d21d22d23d24. . .r3= d31d32d33d34. . .r4= d41d42d43d44. . ....The decimal expansion ri=P∞j=1dij/10jis unique providedwe exclude that we disallows infinite tails 999 . . . in theexpansions.Intro to Discrete StructuresLecture 11 – p. 22/29Real NumbersIntro to Discrete StructuresLecture 11 – p. 23/29Cantor Diagonalization ArgumentForm a new real number with decimal expansionr = 0.d1d2d3d4. . . where the decimal digits are determinedby the following
View Full Document
Unlocking...