1Albert R Meyer, March 17, 2010 lec 7W.1 Recursive Definitions & Structural Induction Mathematics for Computer ScienceMIT 6.042J/18.062JAlbert R Meyer, March 17, 2010 lec 7W.2 Recursive Definitions Define something in terms of a simpler version of the same thing: Base case(s) that don’t depend on anything else. Constructor case(s) that depend on simpler cases. Albert R Meyer, March 17, 2010 lec 7W.9 Matched Paren Strings, Mset of strings, M { ], [ }*•Base: M, (the empty string) •Constructor:If s, t M, then [s]t MAlbert R Meyer, March 17, 2010 strings in M [] s = t = [[]] s = [] t = [][] s = t =[] [[]][] s = [] t =[] [[[]]] s = [[]] t = 7W.10Matched Paren Strings MAlbert R Meyer, March 17, 2010 not in Mstrings starting with ]are not in M because• does not start with ]• [s]t does not start with ]and everything in M arises inone of these two ways 7W.11Albert R Meyer, March 17, 2010 lec 7W.12 Matched Paren Strings, Mset of strings, M { ], [ }*•Base: M,•Constructor: If s,t M,then [s]t M• That’s all Extremal Clause(Implicit part of definition)2Albert R Meyer, March 17, 2010 Structural Induction 7W.13To prove P(x) holds for all x inrecursively defined set R, prove •P(b) for each base case b R•P(c(x)) for each constructor, c,assuming ind. hyp. P(x)Albert R Meyer, March 17, 2010 lec 7W.14 Lemma:Every s in M has the same number of ]’s and [’s.Proof by structural inductionon the definition of MMatched Paren Strings MAlbert R Meyer, March 17, 2010 Let EQ ::= {strings with same number of ] and [}lec 7W.15 Matched Paren Strings MLemma:Every s in M has the same number of ]’s and [’s.Lemma (restated): M EQAlbert R Meyer, March 17, 2010 lec 7W.17 Structural Induction on MInd. Hyp. P(s) ::= (s EQ)Base case (s = ): has 0 ]’s and 0 [’s,so P() is true.Proof:base case is OKAlbert R Meyer, March 17, 2010 lec 7W.18 Constructor step: s = [r]tcan assume P(r) and P(t)#] in s = #] in r + #] in t + 1 #[ in s = #[ in r + #[ in t + 1 = by P(r) = by P(t)so =Structural Induction on Mso P(s) is true constrct case is OKAlbert R Meyer, March 17, 2010 lec 7W.19 so by struct. induct. Structural Induction on MQEDs M. s EQM EQ3Albert R Meyer, March 17, 2010 lec 7W.20 The 18.01 Functions, F18The set F18 of functions on R:IdR, constant functions, and sin x are in F18. if f, g F18, then f + g, f g, ef, (the constant e) the inverse, f(-1), of f, andf g (the composition of f and g)are in F18.Albert R Meyer, March 17, 2010 lec 7W.21 Some functions in F18:xcos x ln x = (1 – (sin x sin x))1/2= (ex)(-1)= (x2)(-1) ---inverse = (1)xThe 18.01 Functions, F18Albert R Meyer, March 17, 2010 lec 7W.22 Lemma.F18 is closed under taking derivatives: if f F18, then f´ F18The 18.01 Functions, F18Class Problem Albert R Meyer, March 17, 2010 Recursive function on MDef. depth(s) for s Mdepth() ::= 0 depth( [s]t ) ::= max{1+d(s), d(t)}7W.26Albert R Meyer, March 17, 2010 kn recursive function on Nexpt(k, 0) ::= 1 expt(k, n+1) ::= kexpt(k,n)--uses recursive def ofN:• 0 N• if n Nthen n+1 N7W.27Albert R Meyer, March 17, 2010 Recursive Functions summary:f: Data Values f(b) def’d directly for base bf(cnstr(x)) def’d using f(x), x7W.284Albert R Meyer, March 17, 2010 positive powers of two 2 PP2if x,y PP2, then xy PP22, 22, 42, 44, 48, … 2 4 8 16 32 … PP27W.47Albert R Meyer, March 17, 2010 loggy function on PP2 loggy(2)::= 1 loggy(xy) ::= x + loggy(y) for x,y PP2loggy(4) = loggy(22) = 2 + 1 = 3 loggy(8) = loggy(24) = 2 + loggy(4) = 2 + 3 = 5 loggy(16) = loggy(82) = 8 + loggy(2) = 8 + 1 = 97W.49Albert R Meyer, March 17, 2010 loggy function on PP2 loggy(16) = loggy(82) = 9 loggy(16) = loggy(28) = 2 + loggy(8) = 2 + 5 = 77W.50WAIT A SEC!: Albert R Meyer, March 17, 2010 ambiguous constructors The Problem: more than one way to construct elements of PP2 from cnstrct(x,y) = x y 16 = cnstrct(8,2) but also 16 = cnstrct(2,8) ambiguous7W.51Albert R Meyer, March 17, 2010 Team Problems Problems 13lec 7W.53MIT OpenCourseWarehttp://ocw.mit.edu6.042J / 18.062J Mathematics for Computer ScienceSpring 2010For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...