4 (induction) (mathematical induction) P P(0) P(x) P(x+1) n P(n) 4.1 (inductive definition) A A (basis ) ( ) A (induction step ) A A (closure ) A clos

Size: px

Start display at page:

Download "4 (induction) (mathematical induction) P P(0) P(x) P(x+1) n P(n) 4.1 (inductive definition) A A (basis ) ( ) A (induction step ) A A (closure ) A clos"

ありあごちょう
5 years ago
Views:

1 4 (induction) (mathematical induction) P P(0) P(x) P(x+1) n P(n) 4.1 (inductive definition) A A (basis ) ( ) A (induction step ) A A (closure ) A closure 81 3 A 3 A x A x + A A ( A. ) 3 closure A N 1, closure 8 N. 40

2 0 N. n N n + 1 N 83 A = 1, 3, 7, 1, 31,...} 1 A. x A x + 1 A (list) (sequence) ( ) : A A. A List A List A = x 1,..., x n n 0 i.(1 i n x i A)} :, 1,,, 3,, 1 0 nil cons, head, tail. cons(x, x 1,..., x n ) = x, x 1,..., x n head( x 1,..., x n ) = x 1 tail( x 1,..., x n ) = x,..., x n head tail (List A ) 8 head( a, b, c ) = a tail( a, b, c ) = b, c cons(a, ) = a cons(a, b, c ) = a, b, c x A L List A x = head(cons(x, L)) L = tail(cons(x, L)). L L = cons(head(l), tail(l)). cons cons : A A List A List A 41

3 x A L List A cons(x, L) List A cons(x, L) :: x :: L a :: (b :: (c :: ))) = cons(a, cons(b, cons(c, ))) = cons(a, cons(b, c )) = cons(a, b, c ) = a, b, c S 0 S. 1 S. L S head(l) = 0 cons(1, L) S. L S head(l) = 1 cons(0, L) S S = 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1,...} 1,, 3 Lisp Scheme : (1 3) ML : [1,, 3] 4.1. (string) abc 1 0 Λ. ( ) Σ Σ Σ ( ). 87 a, b}. Λ, a, b, aa, ab, ba, bb, Σ Σ (Σ 1) Λ Σ x Σ s Σ xs Σ (Σ ) 1 abc 4

4 Λ Σ x Σ s Σ sx Σ (Σ 3) Λ Σ x Σ x Σ s Σ t Σ st Σ 3 1 Σ bab a, b} Λ a, b}. b a, b} b a, b}. a a, b} ab a, b}. b a, b} bab a, b}. bab a, b} 3 s, t, u Σ 3 stu ( ) s Σ t Σ st Σ u Σ stu Σ t Σ u Σ tu Σ s Σ stu Σ (ab)c a(bc) 88 A = 0, 1} 0 L 0 L. s L 1s L. 89 S = a, b, ab, ba, aab, bba, aaab, bbba,...} a S, b S. s S bs S as S as S bs S (s = a ) (s = b ) (s a strhead(s) = a ) (s b strhead(s) = b ) strhead ( ) A B C (A B) C 43

5 4.1.3 (binary Tree) ( ) 3 [ BinTree] BinTree (L BinTree R BinTree) L, R BinTree. L BinTree L BinTree. 1 ( 0 1 ) L R L, R L R L, R L, R} L, R L R ( ) A ( ) A 1 BinTree A (x A L BinTree A R BinTree A ) L, x, R BinTree A. x L R. (x A L BinTree A ) L, x BinTree A BinTree N ( ), 1,,,, 1,,, 1, 44

6 L, x, R Tree(L, x, R) L, x Tree(L, x). 91 Tree(Tree(,, ), 1, ) Tree(Tree(, ), 1, ) head, tail. label(tree(t 1, x, t )) = x label(tree(t 1, x)) = x left(tree(t 1, x, t )) = t 1 left(tree(t 1, x)) = t 1 right(tree(t 1, x, t )) = t right 1 9 BinTree A T A T A. x A t T A Tree(t, x, t) T A ( ) 93 0, 1} 0, 1 Opps.,, 0,,, 1, Opps. x 0, 1} t Opps Tree(t, x, Tree(right(t), 1, left(t))) Opps, if label(t) = 0 Tree(t, x, Tree(right(t), 0, left(t))) Opps, if label(t) = ( ) 4

7 4.1.4 BNF ( ) BNF (Backus-Naur Form Backus Normal Form) 1 BNF BNF 94 [ ] a, b, c,, z} 0, 1,,, 9} BNF (expression) ::= + - (basis induction step) BNF x y x+y x y x-y abc+31-0 BNF 1 ::= := begin end while do if then else ::= ; while (statement) x:=3; y:=0; while x do begin y:=y+3; x:=x-1 end 4. head, tail ( ) 4 [ f : A B A ] 46

8 (basis) A basis x f(x) B (induction step) A induction step a A b A f(a) f(b) B A f f : A B N f : N B f 0 N f(0) n N f(n) f(n + 1) (n = 0 ) f(n) = f(m) (n = m + 1 ) n = m + 1 f(m) f ( ) f(n + 1) 0 (n = 0 ) f(n) = f(n + 1) + 3 (n = m + 1 ) 3 9 f : N N, n N 1 n + 1 f(n) n 1 f(n) = ((n 1) + 1) + (n + 1) = f(n 1) + (n + 1) f 1 (n = 0 ) f(n) = f(m) + n + 1 (n = m + 1 ) 96 add : N N N. N m (n = 0 ) add(n, m) = add(p, m) + 1 (n = p + 1 ) add(n, m) = n add(n, p) + 1 (m = 0 ) (m = p + 1 ) ( ) 3 f(n) = f(n + 1) f f (recursive function) (inductively defined function) f 47

9 97 times : N N N. 1 0 (n = 0 ) times(n, m) = times(p, m) + m (n = p + 1 ) 98 factorial(n). factorial(n) = 1 (n = 0 ) n factorial(m) (n = m + 1 ) 99 f : N List N f(n) = n,..., 1, 0 0 (n = 0 ) f(n) = cons(n, f(p)) (n = p + 1 ) f(3) = cons(3, f()) = cons(3, cons(, f(1))) = cons(3, cons(, cons(1, f(0)))) = cons(3, cons(, cons(1, 0 ))) = 3,, 1, 0 n = 0 n 1 n = 0, 1,, k n > k f(n) m < n f(m) 100 Fibonacci fib(n) 1 (n = 1, ) fib(n) = fib(n 1) + fib(n ) (n > ) 101 head; List A A, tail; List A List A. (x = ) head(x) = y (x = cons(y, L) ) (x = ) tail(x) = L (x = cons(y, L) ) 10 length : List A N. 0 (x = ) length(x) = 1 + length(l) (x = cons(y, L) ) 1 + length(tail(x)) 103 (concatenation) : List A List A List A. y (x = ) x y = cons(z, L y) (x = cons(z, L) ) 48

10 104 nodes : BinTree A N. 0 (x = ) nodes(x) = 1 + nodes(l) + nodes(r) (x = Tree(L, y, R) ) 10 : Σ Σ Σ. Σ 1 t (s = Λ ) s t = x (u t) (s = xu ) s, t, u Σ x Σ 1 x Σ u Σ s = xu s s (t = Λ ) s t = (s u) x (t = ux ) 4.3 A A P (induction) x, P (x) (base case) P (0). (induction step) x N P (x) 4 P (x + 1) n ( ) n(n+1)(n+1) 6 : P (n) P (0) 0 = P (n) 0 n + 1 n(n + 1)(n + 1) 6 + (n + 1) = (n + 1)(n + )(n + 3) 6 P (n + 1) n N P (n) n N.P (n) 4 (induction hypothesis) 49

11 n 0 : n k P (n) base case P (k) induction step n > k n P (n) P (n + 1) n : P (n) base case n = 1 induction step P (k + 1) P (k + 3) : induction step P (n 1) 0 k < n k P (k) P (n) 107 fib n > 0 (( ) n ( fib(n) = g(n) g(n) = 1 (( 1 + ) n ( 1 ) n ) 1 ) n ) n n.(n > 0 fib(n) = g(n)). n = 1 n = g(1) = 1 (( g() = 1 (( 1 + ) ( 6 + ) ( 4 1 )) = 1 = fib(1) 6 )) = 1 = fib() 4 n > k < n k fib(k) = g(k). n n 1 k = n k = n 1 fib(n) = fib(n ) + fib(n 1) = g(n ) + g(n 1) ( = ) ( 1 + ) n ( (( = ) n ( 1 ) n ) = g(n) 3 ) ( 1 ) n 0

12 4.3. L List A, P (L). P ( ). L List A a A P (L) P (a::l). 108 x, y List A length(x y) = length(x) + length(y) ( ) x x List A y List A.length(x y) = length(x) + length(y) P (x) (base case) x =. y List A P (x) length( y) = length(y) = length( ) + length(y) (induction step) x = a :: z. y List A ( ) length((a :: z) y) = length(a :: (z y)) ( ) = length(z y) + 1 (length ) = length(z) + length(y) + 1 ( P (z) ) ( ) length(a :: z) + length(y) = length(z) length(y) (length ) P (a :: z) x List A P (x) 6 x y x y 6 1

13 4.3.3 ( ) x BinTree A, P (x) P ( ). x, y BinTree A a A P (x), P (y) P (Tree(x, a, y)). (structural induction)

1. A0 A B A0 A : A1,...,A5 B : B1,...,B

1. A0 A B A0 A : A1,...,A5 B : B1,...,B12 2. 3. 4. 5. A0 A B f : A B 4 (i) f (ii) f (iii) C 2 g, h: C A f g = f h g = h (iv) C 2 g, h: B C g f = h f g = h 4 (1) (i) (iii) (2) (iii) (i) (3) (ii) (iv) (4)