ii

Transcription

1

2 ii

3 iii

4 iv A 77 A A A A A A A B 87 B B B B B B B B

5 A A A 1.1. A = {1, 2, 3} A (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). A 3! = A A = n A n!. n ! = 1 A = A = 0 A 0! = 1 A 1.2 A A k 0 k A A k-

6 A = {1, 2, 3, 4, 5} A 3- (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1), (1, 2, 4), (1, 4, 2), (2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1),. (3, 4, 5), (3, 5, 4), (4, 3, 5), (4, 5, 3), (5, 3, 4), (5, 4, 3). A 3-5!/(5 3)! = A k, n 0 k n A = n A k- n! (n k)! = n(n 1) (n k + 1).. k 1.3 A A A 1.3. A = {1, 2, 3, 4} A (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2). A (4 1)! = A A = n A (n 1)!. n 1.4. n 1 n 2 s n s n n s (n n s )!. n 1! n s!

7 n n s (n n s )! σ i [s] i n i σ n i σ σ = σ i n i! (n n s )!. n 1! n s! k, n 0 k n A n A k ( n k) 1.2. ( n k) n C k 1.4. A = {1, 2, 3} A {1, 2}, {1, 3}, {2, 3}. A ( 3 2) = k, n 0 k n A n ( ) n k = n! (n k)! k! = n(n 1) (n k + 1). k!. k

8 A = {1, 2, 3} A ( 3 2) ( ) 3 3! = = 3 2 (3 2)! 2! 1.1. n N {0} ( n 0) = ( n n) = n, k k n k 1 k n 1 1. ( ) ( n k = n n k) 2. ( ) n k = n k (n 1 k 1) 3. ( ) ( n k = n 1 ) ( k + n 1 k 1) 1.3. n k 1. n k 2. n n n 1 k 1 ( n 1 k 1) k 1,..., k 1 2 k k 3. n k n n ( n 1 k 1) n n 1 k 1 ( ) n 1 k n n 1 k n k n k. k.

9 {a, b, c} (a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c). {0, 1} (0, 0, 0), (0, 0, 1), (0, 1, 0),, (1, 1, 1) n k ( ) n + k 1. k k. k n 1 (n 1) + k 1.4 ( ) (n + k 1)! n + k 1 =. (n 1)! k! k σ σ a 1, a 2,..., a n 1 a 1 t 1 i : 2 i n 1 a i 1 a i t i a n 1 t n i : 1 i n i t i i:1 i n t i = k σ f 1.3. f 1.7. {a, b, c} (a, a), (a, b), (a, c), (b, b), (b, c), (c, c).

10 6 1 {0, 1} (0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1) A = {1, 2, 3} A 1.5. x 1, x 2,..., x n x 1 + x x n = k.

11 k n a n n b n 2. k n a b n k n 3. x 1,..., x n x 1 + x x n = k k N {0} (x 1,..., x n ) Z n a i [n][x i 0] b i [n][x i 1] k n 4. n k n 2k 1 5. A A = n S 2 A S 2 n 1 S 1, S 2 S S 1 S 2 6. A, B A = n, B = k f : A B 4.5 a A B b A B n = k c A B n k d A B n k

12 *1 k 1 ( ) n = k ( ) n = k ( ) ( ) n i 1 n 1 = + k 1 k 1 k ( ) ( ) n i 1 n 1 = + k i k n k ( ) n k 1 ( ) n k 1 ( ) k 1. k 1 ( n k 1 0 ). *1 ( n) ( k = n 1 ) ( k + n 1 k 1)

13 9 2 n a 1,..., a n def = a 1 + a a n. 2.1 i [n] i [n] a i a i def = a 1 a 2 a n a, b (a + b) 2 = a 2 + 2ab + b 2 (a + b) 3 = a 3 + 3a 2 b + 3ab 2 + b ( ). a, b n 0 (a + b) n = n ( ) n a i b n i. i. n n = 0 (a+b) 0 = 1 n ( n i) a i b n i = ) a 0 b 0 = 1 n ( 0 0 (a + b) n+1 = (a + b) (a + b) n n ( n = (a + b) i = a n ( n i ) a i b n i ) a i b n i + b n ( ) ( ) n a i b n i i

14 10 2 n ( ) n n ( ) n = a i+1 b n i + a i b n i+1 i i ( n 1 ( ) ( n = a n+1 + )a i+1 b n i + b n+1 + i n 1 ( ) n n = a n+1 + b n+1 + a i+1 b n i + i i i=1 n ( ) n n = a n+1 + b n+1 + a i b n+1 i + i 1 i=1 i=1 n (( ) n = a n+1 + b n i i=1 n ( n + 1 = a n+1 + b n+1 + i i=1 n+1 ( ) n + 1 = a i b n+1 i. i ( )) n a i b n+1 i i 1 n ( ) n )a i b n i+1 i i=1 ( ) n a i b n i+1 ( ) n a i b n+1 i i ) a i b n+1 i ( 1.2 3) 2.1 ( ). n = 5 (a + b) 5 = ( ) 5 a 0 b ( ) 5 a 1 b ( ) 5 a 2 b ( ) 5 a 3 b = b 5 + 5ab a 2 b a 3 b 2 + 5a 4 b + a 5. ( ) 5 a 4 b ( ) 5 a 5 b n ( n i) = 2 n 2. n ( n i) x i = (x + 1) n 3. n ( 1)i( n i) = ( n k) n, k 0 k n n k *1 *1 n

15 n k N {0} ( ) n k = n(n 1) (n k + 1) k N k! 1 k = n < k ( n k) = n k N k n 1. ( ) ( n k = n n k) 2. ( ) n k = n k (n 1 k 1) 3. ( ) ( n k = n 1 ) ( k + n 1 k 1) 2.4. n k N 7 1 k n ( ) n = k ( ) n = k ( ) ( ) n i 1 n 1 = + k 1 k 1 k ( ) ( ) n i 1 n 1 = + k i k n k ( ) n k 1 ( ) n k 1 ( ) k 1. k 1 ( n k 1 0 ) n N ( n k ) ( ) = ( 1) k n+k 1 k 2.5.

16 ( ). n x < 1 (1 + x) n = k=0 ( ) n x k. k. f(x) = (1 + x) n a = 0 (1 + x) n = = = k=0 f (k) (0) x k k! ( f(x) ) n(n 1)... (n k + 1) 1 n k k=0 k=0 ( ) n x k. k k! x k 2.3. n N x < 1 1 (1 x) n = k=0 ( n + k 1 k ) x k.. 1 = (1 + ( x)) n (1 x) n ( ) n = ( x) k k k=0 ( ) n + k 1 = ( 1) k ( x) k. ( 2.3) k k=0 ( ) n + k 1 = x k. k k=0

17 ( ). n ( n ) n ( n ) n 2πn n! 2πn (1 + 1/n). e e 2.5. n, k k n ( n ) ( k n ( en k k) k ) k.. ( ) n k = k 1 n i k i k 1 n ( n ) k k =. k ( ) n k nk k! n k 1 ( e ) k ( en 2πk k k ) k.

18 n/2 ( ) n : = 2 n 1 2i a n/2 1 ( ) n : = 2 n 1 2i + 1 ( ) ( ) ( ) ( n n n n n : b ( ) ( ) ( ) ( n n n n n : ( ) n + m k = k ( )( ) n m i k i ) ) ( ) n 2 n = 1 n ( ) n 2 n = 1 n n ( ) 2 n = i ( ) 2n n 3. (2n 1)(2n 3) 3 1 n! 2 n = ( ) 2n n 4. n ( ) n a i = n2 n 1 i n ( ) n b ( 1) i+1 i = 0 i 5. k ( ) n ( 1) i i ( ) n 1 = ( 1) k k

19 ( ). n n 1. n 1 n 1 n n 1, 2,..., 2n 2 n 1

20 a, b a b 1 x, y 0 xa yb = 1.. i : 1 i b f i = i a 1 f i 0 f i = q i b + r i q i 0, 0 r i b 1 1 a 1 = q 1 b + r 1 2 a 1 = q 2 b + r 2 3 a 1 = q 3 b + r 3. b a 1 = q b b + r b 0 {r 1,..., r b } {r 1,..., r b } {1,..., b 1} {1,..., b 1} = b 1 i, j [b] i < j r i = r j (ja 1) (ia 1) = (q j b + r j ) (q i b + r i ) (j i)a = (q j q i )b a, b j i b 0 < j i < b 0 {r 1,..., r b } i [b] r i = 0 i a 1 = q i b + r i i a q i b = n [ a 1, a 2,..., a n N, S [n] n ] a i. i S a 1,..., a n S [n] i S a i n

21 ( ). n m n km k. k 1 (k 1)m km n/m k k n m n, m n/2 m/ a = (a 1, a 2,..., a n 2 +1) n + 1 n + 1. n + 1 n + 1 i [n 2 + 1] a a i, a i+1,..., a n2 +1 a i z i

22 18 3 z i [n] S 1 = {i [n 2 + 1] : z i = 1} S 2 = {i [n 2 + 1] : z i = 2}. S n = {i [n 2 + 1] : z i = n} j [n] S j n S j = {i 1, i 2,..., i k } k n + 1 i 1 < i 2 < < i k a i1 > a i2 > > a ik n + 1 a i1, a i2,, a ik

23 A, B A B = A + B A B A, B, C A B C = A + B + C A B A C B C + A B C

24 ( ). A 1, A 2,..., A n A 1 A 2 A n = n ( 1) i 1 A j1 A j2 A ji. i=1 1 j 1 <j 2 < <j i n. *1 a A 1 A 2 A n A j1 A j2 A ji a a a a A 1 A 2 A n a A 1, A 2,..., A t A t+1, A t+2,..., A n a A 1 A 2 A t i : t + 1 i n a A i i [n] {j 1, j 2,..., j i } [n] {j 1, j 2,..., j i } [t] a A j1 A j2 A ji {j 1, j 2,..., j i } [t] a A j1 A j2 A ji 4.3. a A j1 A j2 A ji S ) ) ) S = ( 1) 1 1 ( t 1 + ( 1) 2 1 ( t ( 1) t 1 ( t t 4.4. t ( ) t S = ( 1) ( 1) i i i=1 t ( ) t = 1 + ( 1) ( 1) i i *1 n

25 = 1 + ( 1)(1 + ( 1)) t ( ) = 1. a ± 1 a A 1 A 2 A n 4.1. n = 5 A 1 A 5 = A A 5 A 1 A 2 A 1 A 3 A 4 A 5 + A 1 A 2 A A 3 A 4 A 5 A 1 A 2 A 3 A 4 A 2 A 3 A 4 A 5 + A 1 A n = ϕ n n n 1 n ϕ(n) 4.2. ϕ(6) = 2 1, 5 ϕ(7) = 6 1, 2, 3, 4, 5, 6 ϕ(10) = 4 1, 3, 7, n ϕ(n) = n ( ). n N n = k i=1 pe i i ϕ(n) = n k i=1 (1 1pi ). n

26 22 4. i : 1 i k p i n A i A i = n/p i 1 j 1 < < j i k A j1 A j2 A ji = n p j1 p j2 p ji A 1 A 2 A k = = k ( 1) i 1 i=1 k ( 1) i 1 i=1 k = n ( 1) i 1 = n i=1 ( 1 1 j 1 <j 2 < <j i k 1 j 1 <j 2 < <j i k 1 j 1 <j 2 < <j i k (1 1p1 ) (1 1p2 ) A j1 A j2 A ji n p j1 p j2 p ji 1 p j1 p j2 p ji )) (1 1pk 4.7. k = 3 A 1 A 2 A k = n n k i=1 (1 1pi ). k ) A 1 A 2 A k + n (1 1pi i=1 = n. A 1 A 2 A k + ϕ(n) = n 4.8.

27 n = 60 k = 3 p 1 = 2, p 2 = 3, p 3 = 5 e 1 = 2, e 2 = 1, e 3 = 1 n = ( ϕ(60) = ) 2 ( 1 1 ) ( 1 1 ) 3 5 = n = ( ). A, B A = n, B = k n k f : A B k ( ) k ( 1) i (k i) n = i k ( ) k ( 1) k i i n. i. f : A B U U = k n B = {y 1,..., y k } i [k] E i y i f : A B E i def = {f U : y i f(a)}. U \ i [k] E i U \ i [k] E i = U i [k] E i = k n i [k] E i. i [k] E i = = k ( 1) i 1 i=1 k ( 1) i 1 i=1 1 j 1 <j 2 < <j i k ( k i ) (k i) n. E j1 E j2 E ji U \ E i = kn i [k] i [k] E i

28 24 4 = k n = k n + = k ( 1) i 1 i=1 k ( 1) i i=1 k ( 1) i ( ) k (k i) n i ( ) k (k i) n i ( ) k (k i) n. i 4.6 ( ). k, n k n n k 1 k! k ( ) k ( 1) k i i n. i

29 (a 0, a 1, a 2..., ) a(x) a(x) def = a i x i. (a 0, a 1, a 2,..., ) a(x) a(x) def = a i xi i!. x R a a(x) 5.1. (1, 1, 1,... ) a(x) a(x) = 1 x i = 1 + x + x = a ( 1, 1) 1 1 x x < x + x 2 + = 1/(1 x) 5.2. (1, 2, 4, 8, 16, 32,... ) a(x) a(x) = 2 i x i = (2x) i = 1 1 2x.

30 26 5 a ( 1/2, 1/2) 5.3. ln(1 + x) ln(1 x) = n=1 xn /n (0, 1, 1/2, 1/3,... ) a(x) a(x) = 0 x x x = 0 + i=1 x n n = ln(1 x). a ( 1, 1) 5.2. x < 1 ln(1 x) = n=1 xn /n 5.1. (a 0, a 1, a 2,... ) (b 0, b 1, b 2,... ) a(x), b(x) 1. (a 0 + b 0, a 1 + b 1, a 2 + b 2,... ) a(x) + b(x) 2. (ca 0, ca 1, ca 2 ) ca(x) 3. (0,..., 0, a }{{} 0, a 1, a 2,... ) x t a(x) t 4. (a t, a t+1, a t+2,... ) (a(x) t a ix i )/x t 5. cx x (a 0, ca 1, c 2 a 2,... ) a(cx) 6. x t x (a 0, 0,..., 0, a }{{} 1, 0,..., 0, a }{{} 2,... ) a(x t ) t t 7. (a 1, 2a 2, 3a 3,... ) a (x) 8. (0, a 0, a 1 /2, a 2 /3,... ) a(x)dx 9. (c 0, c 1, c 2,... ) c n = n a ib n i c(x) = a(x)b(x) 5.4. (1, 0, 1, 0, 1, 0,... ) 1/(1 x 2 ) (1, 1, 1,... ) 1/(1 x) (1, 2, 3, 4, 5,... ) 1/(1 x) 2 (1, 1, 1,... ) 1/(1 x) (1 2, 2 2, 3 2, ) a(x) = (i + 1) 2 x i = i(i + 1)x i + (i + 1)x i.

31 (i + 1)x i = = ix i 1 = i=1 ( ) 1 = 1 x (x i ) = i=1 1 (1 x) 2 (x i ) = ( ) x i i(i + 1)x i = i(i + 1)x i i=1 i=1 = x i(i + 1)x i 1 i=1 ( ) = x (x i+1 ) = x (x i ) = x x i = x ( ) 1 = 1 x 2x (1 x) 3 a(x) = 1 (1 x) 2 + 2x (1 x) 3 = 1 + x (1 x) ( ( m 0 ), ( m 1 ), ( m 2 ),..., ( m n),... ) (1 + x) m ( 1.5 ). r 1, r 2,..., r n ( ) n+k 1 k r 1 + r r n = k.. x < 1 n a(x) = 1 + x + x = x i = 1 1 x. a(x) n = (1 + x + x )(1 + x + x ) (1 + x + x ) }{{} n

32 28 5 x k 5.3. x k r r n = k r 1,..., r n 2.3 a(x) n = 1 (1 x) n = k=0 ( n + k 1 k ) x k x k ( ) n+k 1 k 5.4. n + 1 a 1, a 2,..., a n+1 a 1 a 2 a n+1 n ( 2n n ) /(n + 1) 5.1. n n n+1 = 4 (a(b(cd))), (a((bc)d)), ((ab)(cd)), ((a(bc))d), (((ab)c)d).. n + 1 n b n b 0 = 1 b n b 1,..., b n 1 a 1 (a 2 a 3 a n+1 ) (a 1 a 2 ) (a 3 a n+1 ) (a 1 a 2 a 3 ) (a 4 a n+1 ). (a 1 a 2 a 3 a n ) a n+1 b n = n 1 b k b n 1 k. k=0

33 b i B(x) *1 B(x) = b i x i = b 0 x 0 + i 1 b j b i 1 j x i i=1 j=0 ( ) ( ) = 1 + b i x i b i x i ( ) ( ) B(x) = 1 + b i x i b i x i+1 ( ) ( ) = 1 + x b i x i b i x i = 1 + x (B(x)) 2 x (B(x)) 2 B(x) + 1 = 0. B(x) x lim x 0 B(x) = b 0 = 1 1 4x = (1 4x) 1/2 = 1 + B(x) = 1 ± 1 4x. 2x B(x) = 1 1 4x. 2x = 1 + ( ) 1/2 ( 4x) k ( ) k (1/2)( 1/2)... (1/2 k + 1) ( 1) k 4 k x k k! k=1 k=1 *1 B(x) lim n (b n ) 1/n

34 30 5 k (k 3/2)(k 5/2)... (1/2)( 1/2) = k x k k! k=1 (2k 3)(2k 5)... 1( 1) = k x k k! k=1 (2k 3)(2k 5)... 1 = 1 2 k x k k! k=1 2 (2k 3)(2k 5)... 1 = 1 2 k 1 x k k (k 1)! k=1 ( ) 1 2(k 1) = 1 2 x k ( 3) k k 1 k=1 B(x) = = = = 1 i=1 ( 1 2 i=1 1 i 2x ( i=1 1 2(i 1) ) i i 1 x i x ( 1 2(i 1) i i 1 1 i + 1 ( 2i i ) x i ) x i 1 ( 2(i 1) ) i 1 x i) b n = ( ) 1 2n. n + 1 n 5.5. [n] π : [n] [n] i [n][π(i) i] n ( 1) i n!. i!

35 [n] d n d 0 = 0, d 1 = 0 [n + 1] π d n+1 d n, d n 1 i [n] π(n + 1) = i [n + 1] π (1) π(i) = n + 1 (2) π(i) n + 1 (1) d n 1 (2) d n 5.5. i [n] n d n+1 = n(d n + d n 1 ). d i D(x) = d i(x i /i!) *2 D (x) = i=1 d i x i 1 (i 1)! D (x) = x D (x) + x D(x), 5.6. (1 x)d (x) = x D(x). D(x) = e x 1 x e x = 1 x1 1! + x2 2!... *2 D(x)

36 32 5 D(x) = (1 x1 1! + x2 ( = ) x 1 + 1! i = ( 1) j x i j! j=0 i ( 1) = i! j j! j=0 1 1 x = 1 + x + x ) (1 2!... + x + x ) ( 1 1 1! + 1 2! xi i! ) ( x ! + 1 2! + 1 ) x ! n ( 1) i d n = n!. i!

37 V E V V G = (V, E) V E (u, v) (v, u) G = (V, E) G V (G) G E(G) G 6.1 ( ). V = {1, 2, 3, 4, 5} G = (V, E) : G V (G) E(G) V (G) = {1, 2, 3, 4, 5} E(G) = {(1, 2), (1, 3), (1, 4), (2, 4), (3, 5), (4, 5)}

38 G = (V, E) E V ( V 1)/2 6.2 G = (V, E) u, v V (u, v) E u v u N u N u = {v V : (u, v) E} u u d G (u) d(u) d G (u) = N u 6.2 ( ). 6.1 G = (V, E) N 1 = {2, 3, 4} N 2 = {1, 4} N 3 = {1, 5} N 4 = {1, 2, 5} N 5 = {3, 4} 1,4 2, 3, N u = 2 E. u V G = (V, E) s, t V s t G

39 P = (v 0, v 1, v 2,..., v k ) 1. v 0 = s 2. v k = t 3. i [k][(v i 1, v i ) E] i, j [k] {0} i j v i v j P P = (v 0, v 1, v 2,..., v k ) k 6.4 G = (V, E) P = (v 0, v 1,..., v k ) v 0 v k v 0 = v k P i, j [k] i j v i v j P P = (v 0, v 1, v 2,..., v k ) k 6.3 ( ). 6.1 V = {1, 2, 3, 4, 5} G = (V, E) P = (1, 2, 4, 5) C = (1, 3, 5, 4, 1) (a) P (b) C V = {1, 2, 3, 4, 5} G = (V, E) 6.5 G = (V, E) u v u, v u, v V u, v G

40 ( ). (a) (b) 6.6 G = (V, E) u, v V u v u v d(u, v) *1 6.5 ( ). G = (V, E) V = {1, 2,..., 7} d(1, 1) = 0, d(2, 7) = 2, d(3, 7) = : *1 G = (V, E) u, v V d(u, v) =

41 G = (V, E) d : V V N {0} 1. u, v V d(u, v) 0 2. u, v V u = v d(u, v) = 0 3. u, v V d(u, v) = d(v, u) 4. u, v, w V d(u, v) d(u, w) + d(w, v) , G = (V, E) V V, E E G = (V, E ) G V V G = (V, E ) V G G[V ] (u, v) E u V v V 6.6 ( ). G = (V, E) 6.1 V = {1, 2, 3, 4}, E = {(1, 2), (1, 3), (2, 4)} G = (V, E ) G[V ] (a) G = (V, E ) (b) G[V ] 6.3:

42 38 6 G = G[V ] 4 d G (4) = 1, d G (4) = 2, d G (4) = G = (V, E) G a, b V d(a) = d(b) = 1 v V \ {a, b} d(v) = 2 G V = n V P n 6.7 ( ). P 5 6.4: G = (V, E) G v V d(v) = 2 G V = n V C n 6.8 ( ). C G = (V, E) u, v V (u, v) E G V = n V K n

43 : 6.9 ( ). 3,,4, (a) K 3 (b) K 4 (c) K 5 6.6: 6.3. K n ( n 2). 6.5.

44 G = (V, E) v V d(v) = k G k ( ) (a) (b) 6.7: 6.2. K n (n 1) n k- kn/

45 G = (V, E) V [X, Y ] X Y =, X Y = V G[X] G[Y ] G[X] = (X, ), G[Y ] = (Y, ) G G = (X, Y, E) 6.11 ( ). (a) (b) 6.8: 6.5. G = (V, E) G G. ( ) G G = (X, Y, E) C = (v 1, v 2,..., v k, v 1 ) G v 1 X G G[X], G[Y ] v 1, v 3,..., v k 1 X, v 2, v 4,..., v k Y k C ( ) G = (V, E) V G V u V X, Y V

46 42 6 X Y def = {v V : d(u, v) 2 0}, def = {v V : d(u, v) 2 1}. [X, Y ] V G[X], G[Y ] G X Y = V X, Y X Y = [X, Y ] V 6.7. X Y = V X Y = G[X] G[Y ] v 1, v 2 X (v 1, v 2 ) E u v 1, v 2 P 1, P 2 X E(P 1 ) 2 0, E(P 2 ) 2 0 P 1, (v 1, v 2 ), P 2 P 2 *2 v 1, v 2 X (v 1, v 2 ) E G[X] 6.8. G[Y ] 6.13 G = (X, Y, E) E = X Y G 6.12 ( ) G = (X, Y, E) E X, Y *2 P 1 P 2

47 (a) (b) 6.9: G = (V, E) G 6.13 ( ). 1, 2, 4, 6, 7, 4, 1, 6, 5, 3, 1 1, 6, 5, 3, 1, 2, 4, 6, 7, 4, (a) (b) 6.10:

48 G = (V, E) G G. ( ) G C = (a 0, a 1,..., a l ) a i V, a 0 = a l, l = E v V v v C k C G C v 2k v ( ) G G C C 6.1. E \ E(C) u V (C) v V (C) (u, v) E \ E(C). (u, v) E \ E(C) u, v V (C) G e = (u, v) E \ E(C) E \ E(C) = C u V (C) 6.2. e C. u e C P = (u, a 1, a 2,..., a k ) a 1 = v i [k] a i u a i = u G G = (V, E \ (E(C) E(P ))) G u, a k G d G (u) 2 1 d G (a k ) 2 1 d G (a k ) 1 a k+1 V (a k, a k+1 ) E(G ) P = (u, v, a 1, a 2,..., a k, a k+1 ) P u e = (u, v) C C C u C C u E(C) = E C

49 G = (V, E) G 6.14 ( ). 1, 2, 4, 7, 6, 5, 3, (a) (b) 6.11: (Ore ). G = (V, E) V = n 3 G u, v V

50 46 6 d(u) + d(v) n.. G u, v V d(u) + d(v) < n G = (V, E) G = (V, E ) E E e E G = (V, E {e}) u, v V (u, v) E d G (u) + d G (v) < n E E (u, v) E (u, v) E d(u) + d(v) d G (u) + d G (v) < n e = (u, v) E G = (V, E {e}) C = (u, v 1, v 2,..., v n 2, v, u) 6.3. i : 2 i n 2 (u, v i ) E (v, v i 1 ) E. (u, v i ) E (v, v i 1 ) E u v i v i+1 v n 2 v v i 1 v i 2 v 1 u G d G (u) = d d G (v) (n 3) (d 1) + 1 = n d 1 d G (u) + d G (v) d + n d 1 = n 1. d G (u) + d G (v) < n G = (V, E) G G

51 : 6.15 ( ). V = {1, 2, 3, 4, 5} G = (V, E) 6.8. G = (V, E) u, v u v (u, v) E (u, v) (V V ) \ E G = (V, E) V 1 G E = V 1. ( ) G V V = 1 V n G = (V, E) G E = V 1 V = n + 1 G = (V, E) e E G = (V, E \ {e}) G T 1, T 2 T 1, T

52 48 6 E(T i ) = V (T i ) 1 i = 1, 2 E = E(T 1 ) + E(T 2 ) + 1 = (V (T 1 ) 1) + (V (T 2 ) 1) + 1 = n. ( V (T 1 ) + V (T 2 ) = n + 1) ( ) G = (V, E) E = V 1 G G C C e 1 E G 1 = (V, E \ {e 1 }) G i G k = (V, E \{e 1,..., e k }) G k E(G k ) = V 1 E > E(G k ) = V 1 E = V G = (V, E) V G = (V, E) G = (V, E ) G E E G G G 6.16 ( ) ( ). K n n n 2

53 (a) (b) 6.13: G = (V, E) r V (u, v) E d(r, u) d(r, v) = T = (V, E) r V T T (u, v) E d(r, u) < d(r, v) (u, v) r (T, r) r T (u, v) u v v u T r T T v 1,..., v k v 1 v k v k v ( ). r (T = (V, E), r) u, v w u, v w u, v

54 50 6 r 6.14: (T = (V, E), r) v V (u, v) E u v (v, w) E w v (T = (V, E), r)

55 T u d(r, u) T 6.18 ( ) r r r (a) (b) 6.15: 6.4. (T = (V, E), r) d N {v V : d(r, v) = d} = 2 d (T = (V, E), r) d N A, B V A B def = {v V : d(r, v) < d} def = {v V : d(r, v) = d} B A (T = (V, E), r) V = n T log(n + 1) 1

56 G = (V, E) M E e, e M e e M E M v V e M 6.19 ( ) (a) (b) (c) 6.16: 6.5. G = (V, E) V 6.16 ( ). G = (X, Y, E) X = Y G U X[ U N(U) ]. N(U) def = u U N u.

57 ( ) G M E X = {x 1,..., x n }, Y = {y 1,..., y n } M = {(x i, y i ) E : i [n]} U X S [n] U = {x i : i S} M {y i : i S} N(U). U = S = {y i : i S} N(U). ( ) X = Y = n n = 1 n k *3 X = Y = n G = (X, Y, E) U X[ U N(U) ] G n = k + 1 X = Y = n G = (X, Y, E) X = {x 1,..., x n }, Y = {y 1,..., y n } G U X[ U N(U) ] *4 1. U X[ U < N(U) ]. 2. U X[ U = N(U) ]. 1 (x n, y n ) E X = X \ {x n }, Y = Y \ {y n } G G = G[X Y ] 1 U X [ U N G (U) ]. N G (U) = N(U) Y G M M {(x n, y n )} G 2 2 S X S = N(S) T = N(S) S = T G G 1, G 2 *3 *4

58 54 6 G 1 = G[S T ] G 2 = G[S T ] S = X \ S, T = Y \ T E(G 1 ) E(G 2 ) = G G 2 = G[S T ] N G2 (U) = N(U) T U S [ U N G2 (U) ] G 2 G 1, G 2 G G = (V, E) k f : V {1,..., k} f f G k- (u, v) E f(u) f(v) f G k- G k- k G χ(g) 6.20 ( ) G = (V, E) χ(g) = 1 E =

59 K n G = (V, E) χ(g) = k V V 1,..., V k i : 1 i k, u, v V i [(u, v) E].. G k- i : 1 i k V i = {v V : f(v) = i} V 1,..., V k V G = (V, E) G G ( + 1)-. V V = 1 V = n 1 V = n G = (V, E) v V G[V \ {v}] ( + 1)- c : V \ {v} [ + 1]

60 56 6 v v 1,..., v i [ + 1] i {c(v j ) : 1 j }. c(v) = i c G ( + 1)- G ( + 1) (Brooks ). G = (V, E) G G G ( 1) G = (V, E) k f : E {1,..., k} f f G k- e, e E f(e) f(e ) f G k- G k- k G χ (G) 6.21 ( )

61 (Vizing ). G = (V, E) G χ (G) χ (G) n χ (K n ) = n n χ (K n ) = n 1. n 3 n 2 n K n n n K n c : E(K n ) [n] χ (K n ) n n 1, 2,..., n n n- (n 1)- χ (K n ) n n K n n/2 = (n 1)/ K n E(K n ) ((n 1)/2)χ (K n ) E(K n ) = n(n 1)/2 χ (K n ) n n V (K n ) = {v 1,..., v n } {v 1,..., v n 1 } (n 1) (n 1) v n K n c : E(K n ) [n] n (n 1) (n 1)- (n 1) v {v 1,..., v n 1 } f(v) [n 1] v v v f(v) f(v ) (v, v n ) f(v) K n (n 1)- K n n 1 χ (K n ) n 1

62 K 5, K G = (V, E) G G χ (G) =. χ (G) χ (G) E E = 1 E = m 1 E = m G = (X, Y, E) e 0 = (u 0, v 0 ) E G = (X, Y, E \ {e 0 }) E \ {e 0 } = m 1 χ (G ) G c : E \ {e 0 } [ ] G c : E [ ] G u 0 a [ ] v 0 b [ ] a = b e E \ {e 0 } c(e) = c (e) c(e 0 ) = a c G a b v 0 a b P = (v 0, u 1, v 1, u 2, v 2,... ) 6.4. i, j 0 u i u j i, j 0 v i v j P i 1 u i b j 0 v j a G c : E [ ] c(e 0 ) = a e E \ (E(P ) {e 0 }) c(e) = c (e) e P c(e) = { a : c (e) = b b : c (e) = a

63 c G χ (G) =

64 a G = (V, E) b G = (V, E) k- c G = (V, E) d G = (V, E) χ(g) k e G = (V, E) χ (G) k 2. a K n b G = (X, Y, E) X = Y = n 3. a K n n b 2 c n 3 d n 2

65 !/(2!3!) = a ( ) n n! = k (n k)! k! = n! k! (n k)! = ( ) n. n k b ( ) n n! = = n k (n k)! k! k (n 1)! ((n 1) (k 1))! (k 1)! = n k ( ) n 1. k 1 c ( ) ( ) n 1 n 1 (n 1)! + = k k 1 (n 1 k)!k! + (n 1)! (n k)!(k 1)! (n k)(n 1)! + k(n 1)! = (n k)!k! n(n 1)! = (n k)!k! n! = (n k)!k! ( ) n =. k 3. : : σ 4. ( ) = 10 (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3). 5. x i i

66 62 1. (a) k n (b) n k 2. (a) ( ) ( n+k 1 k (b) k 1 ) n 1 3. (a) ( ) ( n+k 1 k (b) k 1 ) n 1 4. ( ) n k+1 k x1 +x 2 + +x k +x k+1 = n k x 1, x k+1 0, x 2,..., x k 1 n k k X A X S X S S 2 A /2 6. a k n b n! n = k c k ( 1)k i( ) k i i n d ( k n) n! 7. a ( ) ( n 1 k + n 1 k 1) ( ) n k ( ) ( ) n 1 n 1 = + k k 1 ( ) ( ) n 2 n 2 = + + k k 1 ( ) n 1 k 1. ( ). ( ) ( ) ( ) ( ) ( ) k k k + 1 k + 2 n 2 n 1 = k k 1 k 1 k 1 k 1 k 1 ( ) ( ) ( ) ( ) ( ) ( ) k 1 k k + 1 k + 2 n 2 n 1 = k 1 k 1 k 1 k 1 k 1 k 1 n k ( ) n i 1 =. k 1 ( ) ( k k = k 1) b ( ) ( n 1 k + n 1 k 1) ( ) ( ) ( ) n n 1 n 1 = + k k k 1 ( ) ( ) ( ) n 1 n 2 n 2 = + + k k 1 k 2

67 . (. ) ( ) ( ) ( ) ( ) n 1 n 2 n k + 1 n k n k = k k ( ) ( ) ( ) ( ) ( ) n 1 n 2 n k + 1 n k n k 1 = k k k ( ) n i 1 =. k i ( n k 0 ) ( = n k 1 ) a a = b = 1 b a = x, b = 1 c a = 1, b = 1 2. n(n 1)... (n k + 1) b ( ) n = k n(n 1) (n k + 1) k! = n (n 1)(n 2) (n k + 1) k (k 1)! = n ( ) n 1 k. k 1 c ( ) n 1 + k ( ) n 1 = k 1 (n 1) (n k) k! + (n 1) (n k + 1) (k 1)! (n 1) (n k) + (n 1) (n k + 1)k = k! (n 1) (n k + 1)(n k + k) = k! (n 1) (n k + 1)n = ( ) k! n =. k 4.

68 64 5. ( ) n = k ( n)( n 1) ( n k + 1) k! = ( 1)k n(n + 1) (n + k 1) k! k (n + k 1)(n + k) (n + 1)n = ( 1) ( ) k! n + k 1 = ( 1) k. k 1. a n ( ) n = 2 n i n ( ) n ( 1) i = 0 i b ( ) ( ) ( ) n n n ( ) n ( ) n 2 n = n n ( ) n ( 2) i 1 n i i = (( 2) + 1) n 2. S = A B, A = n, B = m S k A i B k i i [k] {0} n = m = k ( ( n n i) = n i) a ( 2n n n ( ) n i i ) = (2n)! n! n! = = i [n] (2n 2i + 2) n! i [n] = 2 n = 2(n i + 1) n! (2n 2i + 1). n! i [n] n i=1 i n i ( ) n 1 i 1 i [n] (2n 2i + 1) n! i [n] = n (2n 2i + 1) n i=1 n! ( ) n 1 i 1 = n2 n 1

69 65 b n ( ) n ( 1) i+1 i = i n i=1 ( 1) i+1 i n i ( ) n 1 i 1 = n n i=1 ( ) n 1 ( 1) i+1 i k ( ) n k ( ) i n 1 ( 1) i = ( 1) i ( 1) i ( 2.3) i i k ( ) i n 1 = i ( ) n + k = ( 2.4 ) k ( ) n 1 = ( 1) k. ( 2.3) k = 0 1. n = n 1 n 1 n 1 3. n 4. b 1,..., b n b 1 def = a 1 b 2 def = a 1 + a 2. b n def = a 1 + a a n b 1,..., b n n b i S = [i] c i n b i c i [n 1] i, j [n] i < j c i = c j b j b i n S = [j] \ [i] m/2 nm/2 n/2

70 66 7. [n 2 + 1] [n] (n 2 + 1)/n (n 2 + 1)/n = n a i1 < a i2 z i1 z i2 + 1 z i1 = z i2 = j 1. S 1 = A \ B, S 2 = B \ A, S 3 = A B S 1, S 2, S 3 A B A B A + B S 1, S 2 S 3 2. A B C S 1,..., S 7 3. a A 1 A 2 A t i : t + 1 i n a A i 4. {j 1, j 2,..., j i } [t] a A j1 A j2 A ji i [t] {j 1, j 2,..., j i } [t] ( t i) A j1 A j2 A ji p j1,..., p ji n n 9. 1, 7, 11, 13, 17, 19, 23, 29, 31,... 1, lim n 2. n x i 1 x n+1 = lim n 1 x = 1 1 x. ln(1 x) = ( 1) i+1 ( x) i = i ( 1) i+1 ( 1) i xi i = x i i. 3. (a(x)) n x k i (1 + x + x ) i r i x k r r n = k

71 67 4. (b 0 x 0 + b 1 x 1 + b 2 x )(b 0 x 1 + b 1 x 2 + b 2 x ) x 1 b 0 b 0 x 2 b 0 b 1 + b 1 b 0 x 3 b 0 b 2 + b 1 b 1 + b 2 b 0 x 4 5. (1) π(n + 1) = i, π(i) = n + 1 i n + 1 π [n + 1] \ {i, n + 1} (2) π(i) n + 1 π(n + 1) = i π n + 1 i [n + 1] \ {i} 6. d n+1 = n(d n + d n 1 ) x i /i! x i d i+1 i! i=1 = x i i d i i! + x i i d i 1 i! i=1 i=1 x i d i+1 i! i=1 = x x i 1 d i (i 1)! + x d i 1 i=1 i=1 x i 1 (i 1)! d 1 = 0 i=1 d i x i 1 (i 1)! = x x i 1 d i (i 1)! + x i=1 d i x i i! 7. D (x)/d(x) = x/(1 x) D (x) D (x) D(x) dx = x 1 x dx. D(x) dx = ln D(x) + c 1 x 1 x dx = ( x ) dx = x ln(1 x) + c 2 ln D(x) = x ln(1 x) + c. x = 0 D(0) = d 0 = 1 c = 0 D(x) = e x ln(1 x) = e x 1 x

72 E ( ) V 2 = V ( V 1)/ (1, 2, 4, 5, 3) (1, 3, 5, 4, 2), (2, 4, 5, 3, 1) (1, 2, 4, 5, 3, 1) (1, 3, 5, 4, 2, 1), (2, 4, 5, 3, 1, 2) 4. 3 d(u, v) d(v, u) d(u, v) d(v, u) 4 u w w v u V N u /2 = kn/2 7. G u v V v X v Y X Y = V X, Y v X v Y v V X Y = E = X Y G G 14. G 15. u, v V G P e 1 E(P ) G 1 u, v e 1 E(P ) E(C) \ {e 1 } u, v 16. 2( V 1) = 2 E = u V N u 2( V 1) w w w w w u, v w u, v 18. (u, r) E u V r

73 69 T 19. B = A T k n = 2 k U X[ U < N(U) ] U X \{x n } U N(U) 1 N(U) \ {y n } 22. U S[ U N G1 (U) ] N G1 (U) = N(U) T 23. U S U > N G2 (U ) N(S U ) = T + N G2 (U ) < S + U = S U U X[ U N(U) ] 24. K n n i, j : i j u i = u j c v i, v j 1. a u, v V [u v (u, v) E] b v V [ N v = k] c X, Y V [(X Y = V ) (X Y = ) (E(G[X]) = E(G[Y ]) = )] d f : V [k], u, v V [(u, v) E f(u) f(v)] e f : E [k], u, v, w V [(e = (u, v) E e = (u, w) E) f(e) f(e )] 2. a n! 2n = (n 1)! 2 b n! n! 2n 3. a n! b 2 c 3 2 n 2 d 2 = n! (n 1)! 2

74

75

76 72 C CNF, 92 D DNF, 93, 50, 2, 21, 43, 43, 43, 78, 49, 78, 30, 93, 38, 42, 51, 52, 87, 46, 36, 78, 35, 38, 95, 87, 49, 92, 78, 81, 34, 25, 49, 77, 83, 94, 1, 87, 79, 88, 91, 40, 81, 93, 48, 95, 95, 49, 80, 77, 77, 95, 95, 81, 35, 35, 33, 54, 54, 54, 5, 4, 50, 91, 93, 78, 41, 51, 49, 49, 49, 93, 35, 45, 45, 45, 88, 49, 79, 37, 79

77 73, 85, 35, 38, 84, 33, 56, 56, 56, 25, 80, 52, 78, 33, 33, 92, 87, 78, 33, 33, 37, 77, 95, 34, 36, 35, 91, 88, 95, 88, 88, 88, 81, 92, 91

78

79

80

81 77 A A.1 A.1 A.2 A a A a A a A a A a A a A A.1 ( ). A 1, 2, 3, 4, 5 1 A 0 A A.1. A A, 10 A, 1000 A A.2. A A, A, A

82 78 A A.3 N : natural Z : integer Q : rational R : real N 0 A.4 A.2 ( ). 1, 2, 3, 4, 5 : {1, 2, 3, 4, 5} : {i N : 1 i 5} A.3. A.1. {1, 2, 3, 1, 1, 3} {1, 2, 3} {2, 1, 3} {1, 2, 3} A.5 A A A A 0 A.3 ( ). A = {1, 2, 3, 4, 5} A = 5 A N, Z, Q, R

83 A.2 79 A.2 A.6 A, B A B A B A B A B A B A B A B A B A = B A B A B A = B A B A B A B A B A B A B A B A B A B B B A A A.1: A B A B A.4 ( ). B = {1, 2, 3, 4, 5} A = {1, 2, 5} A B A B A B A.1. N Z Q R N Z Q R A.4. A (1) A A (2) A A (3) A A (4) (5) A

84 80 A A.3 A.7 U A U A U A Ā Ā def = {a U : a A}. A.5 ( ). U = {1, 2, 3, 4, 5} A = {1, 2, 5} Ā = {3, 4} A.5. Z E E A.2. U A U Ā = A. A.1. U A, B U A B B Ā. 1. A B B Ā 2. B Ā A B A, B X, Y X Y Ȳ X ( ) ( ) X = B, Y = Ā B Ā X Y ( ) Ȳ X X = B, Y = Ā X = B, Ȳ = A Ȳ X A B

85 A.4 81 A.4 A.8 A, B A B A B A B A B A B A B A B A B def = {x : x A x B}, def = {x : x A x B}. A.6 ( ). A = {1, 2, 3, 4, 5} B = {1, 5, 10, 11} A B = {1, 2, 3, 4, 5, 10, 11}, A B = {1, 5}. A.6. A = {1, 2, 3, 4, 5} B = {2, 3, 5, 7, 11} A B, A B A.2 ( ). A, B, C A (B C) = (A B) (A C), A (B C) = (A B) (A C).. A.3. A, B A B = A + B A B.. A.9 A, B A B A B A \ B A B A B

86 82 A A B A \ B A B def = {x : x A x B}, def = {x : (x A x B) x A B}. A.7 ( ). A = {1, 2, 3, 4, 5} B = {1, 5, 10, 11} A \ B = {2, 3, 4}, A B = {2, 3, 4, 10, 11}. A.7. A = {1, 2, 3, 4, 5} B = {2, 3, 5, 7, 11} A \ B, A B A.4. A, B A B = (A \ B) (B \ A) = (A B) \ (A B). A.5 A.5 ( ). U A, B U A B = Ā B A B = Ā B. A.6 ( ). k U A 1,... A k U A 1,..., A k U A 1 A k = Ā1 Āk A 1 A k = Ā1 Āk

87 A k = 1 k 1 k 2 A 1 A k 1 = Ā1 Āk 1. (A.1) A, B A B = Ā B (A.2) A 1 A k = (A 1 A k 1 ) A k = (A 1 A k 1 ) Āk ( (A.2)) = ( Ā 1 Āk 1) Ā k ( (A.1)) = Ā1 Āk. A.10 k N X = {1, 2,..., k} i X A i i X i X A i A i def = A 1 A 2 A k def = A 1 A 2 A k X = {1, 2,..., k} A i = i X A i = Ā i i X Ā i i X i X A.6 A.11

88 84 A A.8 ( ). 1. {{1}, {2}, {3}}, 2. {, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}}, 3. {{a}, {e}, {a, b}, {b, c}, {c, d, e}, {a, b, c, d, e}}. A.8. { }, { } A.9. (1) (2) (3) { } (4) { } (5) 1 1 (6) 1 1 (7) 1 {1} (8) 1 {1} (9) {1} {1} (10) {1} {1} (11) {1} {{1}} (12) {1} {{1}} (13) 1 {1, {1}} (14) 1 {1, {1}} (15) {1} {1, {1}} (16) {1} {1, {1}} A.12 A A A 2 A A.9 ( ). A = {1, 2, 3} 2 A = {, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. A.10. A = {0, 1} 2 A A.3. A B 2 A B A A.7. A 2 A = 2 A. S A A S a A a S 0 a S 1 0/1 2 A A 0/1 A 0/1 2 A

89 A.7 85 A.10. A = {1, 2, 3} 2 A = 2 A = 2 3 = 8 0/1 A A {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} A = 2 0 = 1 A.7 A.13 A A 1, A 2,..., A k A A 1, A 2,..., A k A 1. A = A 1 A 2 A k, 2. i, j : i j A i A j =. A.11 ( ). E O E, O Z A.12. Z

90 86 A 1. a 5 10 b c d 3 2 e {5} {2, 3, 5, {7}} 2. {5} {2, 3, 5, {7}} 3. {7} {2, 3, 5, {7}} 4. {7} {2, 3, 5, {7}} 5. {{5}} {2, 3, 5, {7}} 6. {{7}} {2, 3, 5, {7}} 7. {a, d} {a, b, c, {a, d}} 8. {a, d} {a, b, c, {a, d}} 9. {a, {a, d}} {a, b, c, {a, d}} 10. {a, {a, d}} {a, b, c, {a, d}} { } 4. U = {i Z : 1 i 10} A = {2, 3, 5, 7}, B = {1, 2, 3, 4, 5}, C = {1, 3, 5, 7, 9} a Ā, B, C b A B C c A B C (b), (c) 5. 2 A 3 B a A B b A B c A \ B d A B 6. A = {a, b, c} A 7. A = n A

91 87 B B.1 true false B.1 B.1 ( ) A R A 2 A/R A x + y = 1 B.1. a, b R 1. y = x + b x-y (x, y) = (1, b 1) 2. x a x ax a 1 3. x x 2 + ax + b = 0

92 88 B B *1 B.2 x, y x y x y x y x y x y x y x x x x y x y x y x ȳ B.1. x 1 y x y x 0 y x y B.2. x, y, z x y z x y z B.1. k x 1, x 2,..., x k x 1 x 2 x k x 1 = x 2 = = x k = 0 1 0/1 x 1 x 2 x k x 1 = x 2 = = x k = 1 0 0/1 B.3,, *1 x x = 1 x x = 0 x

93 B x, y x y, x y, x, ȳ φ x 1,..., x n φ x 1,..., x n B.2 ( ). 1. x 2. x ȳ 3. ((x 1 x 2 ) (x 1 x 3 )) (x 1 x 2 x 3 ) B.3. x ȳ x (y z) B.2. x (y z) x (yz) x (yz) x yz B.1 ( ). x, y, z x (y z) = (x y) (x z) x (y z) = (x y) (x z). B.3 B.2 ( ). x, y x y = x ȳ x y = x ȳ

94 90 B. B.3 ( ). x 1,..., x k x 1 x k = x 1 x k x 1 x k = x 1 x k. A.6 B.4 k N A = {1, 2,..., k} i A x i i A i A x i x i def = x 1 x 2 x k def = x 1 x 2 x k A = {1, 2,..., k} x i = x i i A i A x i = x i i A i A B.4. x yz (x y)(x z)

95 B.4 91 B.4 B.5 φ x 1,..., x n (a 1,..., a n ) {0, 1} n (x 1,..., x n ) = (a 1,..., a n ) x 1,..., x n φ φ(a 1,..., a n ) B.3 ( ). φ = x yz 1. (x, y, z) = (0, 1, 0) φ(0, 1, 0) = 0 2. (x, y, z) = (1, 0, 0) φ(1, 0, 0) = 1 B.2. B.4. φ x 1,..., x n φ {0, 1} n {0, 1} x 1,..., x n. x 1,..., x n φ 0 1 B.6 {0, 1} n {0, 1} x 1,..., x n φ x 1,..., x n φ(x 1,..., x n ) B.7 φ, φ x 1,..., x n a {0, 1} n φ(a) = φ (a) φ φ φ φ φ = φ

96 92 B B.8 φ x 1,..., x n a {0, 1} n φ(a) = 1 φ φ 1 φ = 1 a {0, 1} n φ(a) = 0 φ φ 0 φ = 0 B.4 ( ). x x x x x x x x ȳ z yz yz(ȳ z) ȳ z yz yz(ȳ z) B.5. ȳ z yz x yz (x y)(x z) B.5 ( ). φ, φ x 1,..., x n 1. {a {0, 1} n : (φ φ )(a) = 1} = {a {0, 1} n : φ(a) = 1} {a {0, 1} n : φ (a) = 1} 2. {a {0, 1} n : (φ φ )(a) = 1} = {a {0, 1} n : φ(a) = 1} {a {0, 1} n : φ (a) = 1}. B.5 B.9 l j i CNF (l 1 1 l 1 2 l 1 3 ) (l 2 1 l 2 2 l 2 3 ) (l 3 1 l 3 2 l 3 3 ).

97 B.6 93 DNF (l 1 1 l 1 2 l 1 3 ) (l 2 1 l 2 2 l 2 3 ) (l 3 1 l 3 2 l 3 3 ). B.5 (CNF, DNF). x, y, z CNF, DNF CNF : x( x y)( x z)(x ȳ z)(x y z)( x ȳ z). DNF : xy xz xyz xȳ z xȳ z. B.6.. B.4 B.6 B.6. f : {0, 1} 3 {0, 1} x y z f(x, y, z) B.6 B.10 x, y x y x y x y x y x y x y x y y x

98 94 B x y x y x y x y B.7. x, y x y (x y) ( x ȳ).. B.7. x y z B.3. x 1, x 2..., x n x 1 x 2 x n 1 x i 0 1 B.8. x, y x y x y.. B.7 B.11 A A {0, 1} B.6 ( ). φ 1. φ : {0, 1} n {0, 1}

99 B φ : N {0, 1} φ(x) = { 1 : x 0 : 3. A φ : A {0, 1} φ(a) = { 1 : a 0 : B.12 A φ : A {0, 1} A A x A φ(x) = 1 x A [φ(x) = 1] x A [φ(x)] x A φ(x) = 1 x A [φ(x) = 1] x A [φ(x)], B.3. A {0, 1} N, Z, Q, R B.13,,, B.7 ( ). A ( x A[φ(x) = 1]) (y z) φ : A {0, 1} 3. x 1 A, x 2 A, x 3 A[φ(x 1, x 2, x 3, y) = 1] φ : A 4 {0, 1} B.4., B.8 ( ). 1. x N[x Z]

100 96 B 2. x x 0 x 2 x 3 x R[x 0 x 2 x 3 ] 3. c x x c x 2 x 3 c R, x R[x c x 2 x 3 ] B x y x 0 y 2 < x 2. a b x 2 + ax + b = 0 3. b a x 2 + ax + b = 0 4. x a x {y R : y < a} 5. a x x {y R : y < a} B.9. φ x R, y R[φ(x, y) = 1] y R, x R[φ(x, y) = 1]. B.5. B.8

101 B.8 97 B.9 ( ). φ x[φ(x)] x[φ(x)], x[φ(x)] x[φ(x)].. B.10 ( ). φ x 1, x 2, x 3,..., Qx k [φ(x 1, x 2, x 3..., x k )] x 1, x 2, x 3,..., Q x k [φ(x 1, x 2, x 3..., x k )], Q = Q = Q = Q = x 1, x 2, x 3,..., Qx k [φ(x 1, x 2, x 3..., x k )] x 1, x 2, x 3,..., Q x k [φ(x 1, x 2, x 3..., x k )], Q = Q = Q = Q =. A.6

102 98 B 1. a b c n + 1 d 33 e (x y) z 3. (a) x (x ȳ) (b) x (x ȳ) (c) x (x y) (d) x (x y) (e) (x ȳ) ( x y) ( x ȳ) (f) (x ȳ) ( x y) ( x ȳ) (g) x x (h) x (y x) 4. x, y, z x y z, B.3 5. x y z f(x, y, z) B.7 7. A = {a 1, a 2,..., a n } N x N x A, x A,

103 B ,,, a A B b A B c A B d f : A B e f : A B f f : A A g

104

105 {i : i } {2, 4, 6, 8} {a : a } 4. (1), (4), (5) A B = {2, 3, 5} A B = {1, 2, 3, 4, 5, 7, 11} 7. A \ B = {1, 4} A B = {1, 4, 7, 11} 8. = 0 { } { } = 1 9. (2), (3), (4), (7), (10), (11), (13), (15), (16) A = {, {0}, {1}, {0, 1}} = { } 12. A B C = {0} A, B, C A i 5 i A 0, A 1, A 2, A 3, A 4 1. a {i Z : 5 i 10} b {a R : a } c {a : a } d {i N : i 3 2 } e {i N : i 60 i 12}

106 (1), (3), (5) 16, 47, , 3, 6, 7, 10, 11, a Ā = {1, 4, 6, 8, 9, 10}, B = {6, 7, 8, 9, 10}, C = {2, 4, 6, 8, 10} b A B C = {6, 8, 10} c A B C = {1, 2, 4, 6, 7, 8, 9, 10} 5. a A B = {i Z : i 2 3 } b A B = {i Z : i 2 3 } c A \ B = {i Z : i 2 3 } d A B = {i Z : i 2 3 } 6. 2 A = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} 7. 2 A = 2 n 1. 1, 2 2. x y z x y z x y z x y x ȳ

107 103 x y z x (y z) x yz = x (ȳ z) (x y)(x z) = xȳ x z 5. ȳ z ȳ z yz yz yz ȳ z 0 y = z = 1 yz = 1 (x y)(x z) x yz (x y)(x z) x yz (x yz) x yz = x (ȳ z) x = 0 (ȳ z) yz x = 1 (1 y)(1 z) 6. (x y z)(x y z)(x ȳ z)( x ȳ z) xy z xȳ z xȳz xyz 7. x y z x y z x R, y R[x 0 y 2 < x] x = 0 y 2 < x y R a R, b R[x 2 + ax + b = 0 ] a R

108 104 b b R, a R[x 2 + ax + b = 0 ] b = 0 x R, a R[x {y R : y < a}] a = x + 1 a R, x R[x {y R : y < a}] a = 0 x R 9. φ(x, y) x y 2 φ(x, y) x y 1. (1), (4), (5) 2. x y z (x y) z a x y b x y c x d x e x y x ȳ f x y x ȳ g 1 h 1 4. xȳ z xy z xȳz xyz. 5. xȳ z xȳz xyz xy z (x ȳ z)( x y z)( x y z)( x ȳ z) 6. R R = {(φ, φ) : φ φ }

109 105 R 7. [n] = {1, 2,..., n}?? x A : i [n][a i = x] x A : i [n][a i x] 8. a A B def = x A [x B] b A B def = {x : (x A) (x B)} c A B def = {x : (x A) (x B)} d f : A B def = b B, a A [f(a) = b] def e f : A B = a, a A [a a f(a) f(a )] f f : A A def = a A [f(a) = a] g R A 2 def = a A [(a, a) R] def = a, a A [(a, a ) R (a, a) R] def = a, b, c A [(((a, b) R) ((b, c) R)) (a, c) R]

110

111

112