structural-induction

+26

No comments posted yet

Comments

Slide 1

lec 5M.1 Structural Induction Mathematics for Computer Science MIT 6.042J/18.062J

Slide 2

Structural Induction 7W.2 To prove P(x) holds for all x in recursively defined set R, prove P(b) for each base case b ∈ R P(c(x)) for each constructor, c, assuming ind. hyp. P(x)

Slide 3

lec 5M.3 E ⊆ Even by structural induction on x ∈ E with ind. hyp. “x is even” 0 is even if n is even, then so is n+2, -n

Slide 4

lec 5M.4 Lemma: Every s in M has the same number of ]’s and [’s. Proof by structural induction on the definition of M Matched Paren Strings M

Slide 5

Let EQ ::= {strings with same number of ] and [} lec 5M.5 Matched Paren Strings M Lemma: Every s in M has the same number of ]’s and [’s. Lemma (restated): M ⊆ EQ

Slide 6

lec 5M.6 Structural Induction on M Ind. Hyp. P(s) ::= (s ∈ EQ) Base case (s = λ): λ has 0 ]’s and 0 [’s, so P(λ) is true. Proof: base case is OK

Slide 7

lec 5M.7 Constructor step: s = [r]t can assume P(r) and P(t) #] in s = #] in r + #] in t + 1 #[ in s = #[ in r + #[ in t + 1 Structural Induction on M so P(s) is true constrct case is OK

Slide 8

lec 5M.8 so by struct. induct. Structural Induction on M QED

Slide 9

lec 5M.9 The 18.01 Functions, F18 The set F18 of functions on : Id , constant functions, and sin x are in F18. if f, g ∈ F18, then f + g, f ⋅ g, 2f, the inverse, f(-1), of f, and f  g (the composition of f and g) are in F18.

Slide 10

Some functions in F18: −x cos x ln x = sin(x + pi) lec 5M.10 = (1 – (sin x ⋅sin x))1/2 = (2x log e)(-1) = (x2)(-1) ---inverse = (−1)⋅x The 18.01 Functions, F18

Slide 11

lec 5M.11 Lemma. F18 is closed under taking derivatives: if f ∈ F18, then f´∈ F18 The 18.01 Functions, F18 Class Problem

Slide 12

lec 5M.12 Lemma. F18 is closed under deriv: if f∈F18, then f´∈ F18. Proof: (Structural Induction) Id´ = 1 ∈ F18 c´ = 0 ∈ F18 sin´ = cos ∈ F18 The 18.01 Functions, F18

Slide 13

lec 5M.13 Lemma. F18 is closed under deriv: if f ∈ F18, then f´∈ F18. Proof: if f, g ∈ F18, then (f + g)´= f´+ g´so ∈ F18 (f  g)´ etc. = (f´ g)⋅g´ ∈ F18 The 18.01 Functions, F18

URL:
More by this User
Most Viewed