ii

ii

iii 1 1 1.1..................................... 1 1.2................................... 3 1.3........................... 4 2 9 2.1.................................. 9 2.2............................... 10 2.3............................ 13 3 15 3.1................................. 15 3.2............................. 17 4 19 4.1.................................. 19 4.2............................... 21 5 25 5.1................................ 25 5.2.......................... 27 6 33 6.1................................. 33 6.2................................ 37 6.2.1............................. 38 6.2.2............................. 38 6.2.3............................. 38

iv 6.2.4............................. 40 6.2.5............................. 41 6.2.6.......................... 43 6.2.7......................... 45 6.2.8.................................. 46 6.2.9.............................. 49 6.3................................. 52 6.4................................. 54 6.4.1.......................... 54 6.4.2............................ 56 72 A 77 A.1.................................. 77 A.2.................................. 79 A.3................................... 80 A.4............................... 81 A.5............................ 82 A.6................................... 83 A.7................................. 85 B 87 B.1.................................. 87 B.2.................................. 88 B.3..................... 89 B.4.................................. 91 B.5................................ 92 B.6................................. 93 B.7.................................. 94 B.8..................... 96

1 1 1.1 1.1 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! = 6 1.1. A A = n A n!. n 1.1. 0! = 1 A = A = 0 A 0! = 1 A 1.2 A A k 0 k A A k-

2 1 1.2. 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)! = 60 1.2. 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)! = 6 1.3. A A = n A (n 1)!. n 1.4. n 1 n 2 s n s n 1 + + n s (n 1 + + n s )!. n 1! n s!

1.2 3. n 1 + + n s (n 1 + + n s )! σ i [s] i n i σ n i σ σ = σ i n i! (n 1 + + n s )!. n 1! n s! 1.1. 1.2 1.4 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) = 3 1.5. k, n 0 k n A n ( ) n k = n! (n k)! k! = n(n 1) (n k + 1). k!. k

4 1 1.5. A = {1, 2, 3} A ( 3 2) ( ) 3 3! = = 3 2 (3 2)! 2! 1.1. n N {0} ( n 0) = ( n n) = 1 1.2. 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 1.3 1.6. n k n k. k.

1.3 5 1.6. {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). 1.7. 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).

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

1.3 7 1. k n a n n b n 2. k n a b n k n 3. x 1,..., x n x 1 + x 2 + + 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

8 1 7. *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 2 + + k 1 ( ) n 2 + + k 1 ( ) k 1. k 1 ( n k 1 0 ). *1 ( n) ( k = n 1 ) ( k + n 1 k 1)

9 2 n a 1,..., a n def = a 1 + a 2 + + a n. 2.1 i [n] i [n] a i a i def = a 1 a 2 a n. 2.1. a, b (a + b) 2 = a 2 + 2ab + b 2 (a + b) 3 = a 3 + 3a 2 b + 3ab 2 + b 3 2.1 ( ). 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

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+1 + + 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 + 0 ( ) 5 a 1 b 4 + 1 ( ) 5 a 2 b 3 + 2 ( ) 5 a 3 b 2 + 3 = b 5 + 5ab 4 + 10a 2 b 3 + 10a 3 b 2 + 5a 4 b + a 5. ( ) 5 a 4 b 1 + 4 ( ) 5 a 5 b 0 5 2.1. 1. n ( n i) = 2 n 2. n ( n i) x i = (x + 1) n 3. n ( 1)i( n i) = 0 2.2 ( n k) n, k 0 k n n k *1 *1 n

2.2 11 2.1 n k N {0} ( ) n k = n(n 1) (n k + 1) k N k! 1 k = 0 2.2. 0 n < k ( n k) = 0 2.2. 2.3. n k N 1.2 1 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 2 + + k 1 ( ) n 2 + + k 1 ( ) k 1. k 1 ( n k 1 0 ). 2.3. n N ( n k ) ( ) = ( 1) k n+k 1 k 2.5.

12 2 2.2 ( ). 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

2.3 13 2.3 2.4 ( ). 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.

14 2 1. n/2 ( ) n : = 2 n 1 2i a n/2 1 ( ) n : = 2 n 1 2i + 1 ( ) ( ) ( ) ( n n n n n : 2 + 2 2 0 1 2 3 b ( ) ( ) ( ) ( n n n n n : 2 + 2 2 0 1 2 3 2. ( ) n + m k = k ( )( ) n m i k i ) 2 3 + + ) 2 3 + ( ) 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

15 3 3.1 3.1 ( ). n n 1. n 1 n 1 n 3.1. 3.2. 3.3. n 1, 2,..., 2n 2 n 1

16 3 3.2. 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 = 1 3.4. 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

3.2 17 3.2 3.3 ( ). n m n km k. k 1 (k 1)m km n/m k k 3.5. 3.6. n m n, m n/2 m/2 3.4. 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

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 + 1 3.7. S j = {i 1, i 2,..., i k } k n + 1 i 1 < i 2 < < i k a i1 > a i2 > > a ik. 3.8. n + 1 a i1, a i2,, a ik

19 4 4.1 4.1. A, B A B = A + B A B.. 4.1. 4.2. A, B, C A B C = A + B + C A B A C B C + A B C.. 4.2.

20 4 4.3 ( ). 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 2 + + ( 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

4.2 21 = 1 + ( 1)(1 + ( 1)) t ( ) = 1. a ± 1 a A 1 A 2 A n 4.1. n = 5 A 1 A 5 = A 1 + + A 5 A 1 A 2 A 1 A 3 A 4 A 5 + A 1 A 2 A 3 + + 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 5 4.5. n = 5 4.2 4.1 ϕ 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, 9 4.1. n ϕ(n) = n 1 4.4 ( ). n N n = k i=1 pe i i ϕ(n) = n k i=1 (1 1pi ). n

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. 4.6. 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.

4.2 23 4.3. n = 60 k = 3 p 1 = 2, p 2 = 3, p 3 = 5 e 1 = 2, e 2 = 1, e 3 = 1 n = 2 2 3 1 5 1 ( ϕ(60) = 60 1 1 ) 2 ( 1 1 ) ( 1 1 ) 3 5 = 16. 4.9. n = 60 60 60 4.5 ( ). 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

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

25 5 5.1 5.1 (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 2 +... = a ( 1, 1) 1 1 x. 5.1. x < 1 1 + 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.

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 0 + 1 1 x1 + 1 2 x2 +... = 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) 6 5.5. (1, 2, 3, 4, 5,... ) 1/(1 x) 2 (1, 1, 1,... ) 1/(1 x) 7 5.6. (1 2, 2 2, 3 2, 4 2... ) a(x) = (i + 1) 2 x i = i(i + 1)x i + (i + 1)x i.

5.2 27 (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) 3. 5.2. ( ( m 0 ), ( m 1 ), ( m 2 ),..., ( m n),... ) (1 + x) m. 5.2 5.3 ( 1.5 ). r 1, r 2,..., r n ( ) n+k 1 k r 1 + r 2 + + r n = k.. x < 1 n a(x) = 1 + x + x 2 +... = x i = 1 1 x. a(x) n = (1 + x + x 2 +... )(1 + x + x 2 +... ) (1 + x + x 2 +... ) }{{} n

28 5 x k 5.3. x k r 1 + + 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

5.2 29 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+1 5.4. ( ) ( ) 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

30 5 k (k 3/2)(k 5/2)... (1/2)( 1/2) = 1 + 2 2 k x k k! k=1 (2k 3)(2k 5)... 1( 1) = 1 + 2 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!

5.2 31. [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. 5.7. e x = 1 x1 1! + x2 2!... *2 D(x)

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

33 6 6.1 6.1 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) 1 4 5 2 3 6.1: 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)}

34 6 6.1. 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, 5 6.1. N u = 2 E. u V. 6.2.. 6.2. 6.3 G = (V, E) s, t V s t G

6.1 35 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) 1 4 1 4 5 5 2 3 2 3 (a) P (b) C 6.3. 6.1 V = {1, 2, 3, 4, 5} G = (V, E) 6.5 G = (V, E) u v u, v u, v V u, v G

36 6 6.4 ( ). (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) = 3 1 4 5 2 3 6 7 6.2: *1 G = (V, E) u, v V d(u, v) =

6.2 37 6.1. 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) 6.4. 3, 4 6.2 6.7 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 ] 6.3 1 4 1 4 2 3 2 3 (a) G = (V, E ) (b) G[V ] 6.3:

38 6 G = G[V ] 4 d G (4) = 1, d G (4) = 2, d G (4) = 3 6.2.1 6.8 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: 6.2.2 6.9 G = (V, E) G v V d(v) = 2 G V = n V C n 6.8 ( ). C 5 6.2.3 6.10 G = (V, E) u, v V (u, v) E G V = n V K n

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

40 6 6.2.4 6.11 G = (V, E) v V d(v) = k G k- 6.10 ( ). 3-4- (a) (b) 6.7: 6.2. K n (n 1)- 6.4. n k- kn/2. 6.6.

6.2 41 6.2.5 6.12 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

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 ( ). 6.9. G = (X, Y, E) E X, Y *2 P 1 P 2

6.2 43 (a) (b) 6.9: 6.2.6 6.14 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, 1 1 4 1 4 5 5 2 3 2 3 6 7 6 7 (a) (b) 6.10:

44 6 6.6. 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

6.2 45 6.2.7 6.15 G = (V, E) G 6.14 ( ). 1, 2, 4, 7, 6, 5, 3, 1 1 4 1 4 5 5 2 3 2 3 6 7 6 7 (a) (b) 6.11: 6.10. 2-6.11. 3-6.7 (Ore ). G = (V, E) V = n 3 G u, v V

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 6.12. 6.2.8 6.16 G = (V, E) G G

6.2 47 1 4 5 2 3 6.12: 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. 6.13. 6.9. 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 2 6.14.

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 }) 6.15. 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 1 6.10. G = (V, E) V 2. 6.16. 6.17 G = (V, E) G = (V, E ) G E E G G G 6.16 ( ). 6.1 6.11 ( ). K n n n 2

6.2 49 1 4 1 4 5 5 2 3 2 3 (a) (b) 6.13: 6.1 6.2.9 6.12. G = (V, E) r V (u, v) E d(r, u) d(r, v) = 1. 6.18 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 1 6.17 ( ). r 6.13. (T = (V, E), r) u, v w u, v w u, v

50 6 r 6.14:. 6.17. 6.19 (T = (V, E), r) v V (u, v) E u v (v, w) E w v 6.3. 6.14.. 6.18. 6.20 (T = (V, E), r)

6.2 51 T u d(r, u) T 6.18 ( ). 6.15 r r r (a) (b) 6.15: 6.4. (T = (V, E), r) d N {v V : d(r, v) = d} = 2 d 6.19. (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 6.15. (T = (V, E), r) V = n T log(n + 1) 1

52 6 6.20. 6.3 6.21 G = (V, E) M E e, e M e e M E M v V e M 6.19 ( ). 1 4 1 4 1 4 5 5 5 2 3 2 3 2 3 6 7 6 7 6 7 (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.

6.3 53. ( ) 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 6.21. 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

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 1 6.22. G 2 = G[S T ] N G2 (U) = N(U) T U S [ U N G2 (U) ] 6.23. G 2 G 1, G 2 G 6.4 6.4.1 6.22 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 ( ). 3-2- 6.6. G = (V, E) χ(g) = 1 E =

6.4 55 1 3 1 2 3 2 1 6.24. 1. K n 2. 3. 4. 6.17. 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 6.18. 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]

56 6 v v 1,..., v i [ + 1] i {c(v j ) : 1 j }. c(v) = i c G ( + 1)- G ( + 1)- 6.19 (Brooks ). G = (V, E) G G G - 6.25. ( 1)- 6.4.2 6.23 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 ( ). 5-4- 1 2 4 3 1 5 2 3 2 3

6.4 57 6.20 (Vizing ). G = (V, E) G χ (G) + 1 6.26. χ (G) 6.21. 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)/2 6.27. 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

58 6 6.28. K 5, K 6 6.22. 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. 6.29. 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

6.4 59 c G χ (G) =

60 6 1. 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

61 1. 5!/(2!3!) = 10 2. 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. ( ) 3+3 1 3 = 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

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 + 1 5. 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

. (. ) ( ) ( ) ( ) ( ) n 1 n 2 n k + 1 n k n k = + + + + + k k 1 2 1 0 ( ) ( ) ( ) ( ) ( ) n 1 n 2 n k + 1 n k n k 1 = + + + + + k k 1 2 1 0 k ( ) n i 1 =. k i ( n k 0 ) ( = n k 1 ) 0 63 1. a a = b = 1 b a = x, b = 1 c a = 1, b = 1 2. n(n 1)... (n k + 1) 0 3. 2 3 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.

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 2 + 2 2 0 1 2 ( ) n 2 3 + + 3 ( ) 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) 3. 4. 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

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 1 5. 2.3 2.4 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 = 367 2. 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 2 + + 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] 5. 6. m/2 nm/2 n/2

66 7. [n 2 + 1] [n] (n 2 + 1)/n (n 2 + 1)/n = n + 1 8. 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) 5. 6. A j1 A j2 A ji p j1,..., p ji 7. 8. n n 9. 1, 7, 11, 13, 17, 19, 23, 29, 31,... 1, 49 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 2 +... ) i r i x k r 1 + + r n = k

67 4. (b 0 x 0 + b 1 x 1 + b 2 x 2 +... )(b 0 x 1 + b 1 x 2 + b 2 x 3 +... ) 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 = ( 1 + 1 1 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

68 6. 1. E ( ) V 2 = V ( V 1)/2 2. 3. (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 5. 6. 6.1 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 = 8. 9. E = X Y 10. 2-11. 3-12. 5 2-13. 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) + 1 17. w w w w w u, v w u, v 18. (u, r) E u V r

69 T 19. B = A + 1 20. T k n = 2 k+1 1 21. 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 25. 26. 27. 28. 29. 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

71 1. 2. 3.

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

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

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 1 999 1 A, 10 A, 1000 A A.2. A A, A, A

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

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

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

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

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

A.6 83. 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

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

A.7 85 A.10. A = {1, 2, 3} 2 A = 2 A = 2 3 = 8 0/1 A 1 2 3 2 A 0 0 0 1 0 0 {1} 0 1 0 {2} 0 0 1 {3} 1 1 0 {1, 2} 1 0 1 {1, 3} 0 1 1 {2, 3} 1 1 1 {1, 2, 3} A.11. 2 2 = 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

86 A 1. a 5 10 b c d 3 2 e 60 12 2. 3. 1. {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}} 11. 12. { } 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

87 B B.1 true false B.1 B.1 ( ). 1. 1 1 2 2. 1 1 3 3. A R A 2 A/R A 1. 2. 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

88 B B.2 1 0 0 1 *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 ȳ 0 0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 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

B.3 89 1. 2. 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 ȳ

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)

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) φ φ φ φ φ = φ

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 ).

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) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 B.6 B.10 x, y x y x y x y x y x y x y x y y x

94 B x y x y x y x y 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 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}

B.7 95 2. φ : 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 1. 2. ( 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]

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.8. 1. 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

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

98 B 1. a b c n + 1 d 33 e 101 2. (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) 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 6. B.7 7. A = {a 1, a 2,..., a n } N x N x A, x A,

B.8 99 8.,,, a A B b A B c A B d f : A B e f : A B f f : A A g

101 1. 2. 3. {i : i } {2, 4, 6, 8} {a : a } 4. (1), (4), (5) 5. 6. 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) 10. 2 A = {, {0}, {1}, {0, 1}} 11. 2 = { } 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}

102 2. (1), (3), (5) 16, 47, 8 3. 2, 3, 6, 7, 10, 11, 12 4. 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 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 3. x y x ȳ 0 0 1 0 1 0 1 0 1 1 1 1

103 x y z x (y z) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 4. 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 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 8. 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

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 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 3. 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 = {(φ, φ) : φ φ }

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]