Solutions to Exercises in "Discrete Mathematics Tutorial"

Transcription

1 1 2 (beta 10 ) 3 SOLVED AND TEXIFIED BY 4 HONORED REVIEWER BBS (lilybbs.us) ( ) ( xiaoxinpan@163.com) 3 beta ( / ) 40.97% 4 02CS chouxiaoya tedy akaru yitianxing xuening ourszf ushing

2

3 165 2

4 3

5 1. (1) {2}; (2) {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196}; (3) {1, 8, 27, 64}; (4) {0, 1, 2,...}; (5) {2, 3}; (6) {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}. 2. (1) {(x, y) x, y R x 2 + y 2 < 1}; (2) {θ k(k Z θ = π 4 + kπ)}; (3) {x x N x < 8}; (4) {(x, y, z) x, y, z N x 2 + y 2 = z 2 }; (5) {x x R x 2 + 5x + 6 = 0}. 3. (1), (4), (5), (6), (8), (9) 4. (1) A B B C A B x(x B x C) ( ) = A B (A B A C) (x/a) = A C ( ) 4

6 (2) A = {a}, B = {{a}}, C = {{a}, {b}} A B B C A C (3) A = {a}, B = {a, b}, C = {{a, b}, {b, c}} A B B C A / C (4) A = {a}, B = {a, b}, C = {{a, b}, {b, c}} A B B C A C 5. A = {a}, B = {{a}}, C = {{{a}}} A B B C A / C 6. (1) 0 1 {a}, {b}, {c} 2 {a, b}, {a, c}, {b, c} 3 {a, b, c} {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} (2) 0 1 {1}, {{2, 3}} 2 {1, {2, 3}} {, {1}, {{2, 3}}, {1, {2, 3}}} (3) 0 1 { }, {{ }} 2 {, { }} {, { }, {{ }}, {, { }}} (4) 0 1 {{1, 2}} {, {{1, 2}}} (5) 0 1 {{, 1}}, {1} 2 {{, 1}, 1} {, {{, 1}}, {1}, {{, 1}, 1}} 5

7 7. A B A C B (A B) A ( B C) A B A B C A (B C) C (A B C) (A B C) 8. (1) {4}; (2) {1, 3, 5}; (3) {2, 3, 4, 5}; (4) {2, 3, 4, 5}; (5) {, {4}}; (6) {{1}, {1, 4}}. 9. (1) { 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 15, 16, 18, 21, 24, 27, 30, 32, 64}; (2) ; (3) { 7, 6, 5, 4, 3, 2, 1, 4, 5}; (4) { 7, 6, 5, 4, 3, 2, 1, 0, 3, 4, 5, 6, 9, 12, 15, 18, 21, 24, 27, 30}. 10. P(A) = {, {a}} PP(A) = {, { }, {{a}}, {, {a}}} (1), (2), (4), (5) 11. A B = A A B = (A B) B (A B = A) = (A B) B 6

8 = A ( B B) ( ) = A ( ) = ( ) A B = A = A E ( ) = A (B B) ( ) = (A B) (A B) ( ) = (A B) (A B = ) = A B ( ) = A B A B = A A B = A B A B = A B A B = x(x (A B)) x (x (A B)) x (x A x / B) x (x A x B) x( x A x B) x(x A x B) A B ( ) ( ) (/ ) ( ) ( ) (1) (A B) (A C) = A A B C = (A B) (A C) = A A (B C) = A ( ) A (B C) = A B C = ( 1.11 ) ( ) 7

9 (2) (A B) (A C) = A (B C) (A B) (A C) = A (B C) = ( ) A (B C) ( 1.1) (3) (A B) (A C) = A (B C) (A B) (A C) = A (B C) = ( ) A (B C) ( 1.1) (4) (A B) (A C) = A A (B C) = (A B) (A C) = A A (B C) = A ( ) A (B C) = ( 1.11 ) 13. (1) 1.2 A B A B A A B B x x A B x A x B = x A ( ) A B A A B B 1.3 A B A A B B A B 8

10 x x A = x A x B x A B A A B B A B ( ) (A B) C = (A B) C A B ( 1.2) (A B) (A C) ( 1.3) = A ( B C) ( ) = A (B C) ( ) = A (B C) (2) A C = (1) A C = (A B) C = (A B) C = (A C) B ( ) = (A C) B = A B ( 1.11 ) = (A B) ( ) = (A B) (A C) (A C = ) = A ( B C) ( ) = A (B C) ( ) = A (B C) x x A x C x B x / (A B) C x A (B C) (A B) C = A (B C) 9

11 14. B = E B ( ) = (A A) B ( ) = (A B) ( A B) ( ) = (A C) ( A C) ( ) = (A A) C ( ) = E C ( ) = C ( ) 15. A = B = D = G C = F = H 16. (1) {3, 4, {3}, {4}}; (2) ; (3) {, { }}; 17. (1) {, {{ }}, {{{ }}}, {{ }, {{ }}}}; (2) {, { }, {{ }}, {, { }}}; (3) {{ }, {{ }}}; 18. (1) {, 1, 2, 3}; (2) ; (3) ; (4). 19. (1) A B; (2) A; (3) B. 10

12 A, B, C, D A B C D A C B D x x A C x A x C (x A x C) (x A x B x C x D) ( & ) = x B x D x B D 1.5 A, B, C, D A B C D A C B D x x A C x A x C = x B x C ( & ) = x B x D ( & ) x B D A = A E ( ) = A (C C) ( ) = (A C) (A C) ( ) (B C) (B C) ( & 1.4) = B (C C) ( ) = B E ( ) = B ( ) 11

13 21. (1) A B = A A B A B = A x((x A x B) x A) x(((x A x B) x A) (x A (x A x B))) x(( (x A x B) x A) ( x A (x A x B))) x(( x A x B x A) ( x A (x A x B))) x(( x A x A x B) ( x A (x A x B))) x(( x A x A x B) (( x A x A) ( x A x B))) x((1 x B) (1 ( x A x B))) x(1 (1 ( x A x B))) x( x A x B) x(x A x B) A B ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (2) A B = A B A A B = A x((x A x B) x A) x(((x A x B) x A) (x A (x A x B))) x(( (x A x B) x A) ( x A x A x B)) x((( x A x B) x A) ( x A x A x B)) x((( x A x A) ( x B x A)) ( x A x A x B)) x((1 ( x B x A)) (1 x B)) x((1 ( x B x A)) 1) x( x B x A) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 12

14 x(x B x A) B A ( ) (3) A B = A B = B = A B = A (B = ) = A ( 1.7(4)) A B = A B = B ( 1.7(4)) = (A A) B ( 1.7(5)) = A (A B) ( 1.7(2)) = A A (A B = A) = ( 1.7(5)) (4) A B = A B A = B A = B A B = A A (A = B) = A ( ) = A A ( ) = A B (A = B) A B = A B A = A (A B) ( ) = A (A B) (A B = A B) = (A A) B ( ) = A B ( ) = A (B B) ( ) = (A B) B ( ) 13

15 = (A B) B (A B = A B) = B ( ) 22. (1) (2) A = {a}, C = {b}, B = D = {a, b} A B C D A B C D A = C = {a, b}, B = {a, b, c}, D = {a, b, d} A B C D A B C D 23. x B x / C x / B x C x B x / C x A x / A B x A C A B = A C x / A x A B x / A C A B = A C x / B x C 24. (A B) C = (A C) B A B = A C B = C (A B) C = (A B) C = A ( B C) ( ) = A ( C B) ( ) = ((A C) B) ( ) = (A C) B (A B) C = A (B C) (A B) C = (A B) C = A ( B C) ( ) 14

16 = A (B C) ( ) = A (B C) (A B) C = (A C) (B C) (A B) C = (A B) C = (A B C) ( ) = (A B C) (A ) ( ) = (A B C) (A C C) ( ) = (A C B) (A C C) ( ) = (A C) ( B C) ( ) = (A C) (B C) ( ) = (A C) (B C) 25. (1) A; (2) A B; (3) B A. 26. (1) A C B C x x A B x A x B ( ) (x A x B) (x A x C) (x B x C) ( & ) = (x C) (x C) = x C ( ) 15

17 A B C x x A = x A x B ( ) = x C ( & ) A C B C (2) 27. C A C B x x C (x C) (x C) ( ) = (x A) (x B) ( & ) x A B C A B x x C = x A B x A x B A A P(A) { } P(A) P(A) { } PP(A) PP(A) {, { }} PP(A) {, { }} PPP(A) ( 1.1) ( ) ( & ) ( & 1.1) ( ) ( ) ( ) {, { }} PPP(A) A A P A {, { }} PPP(A) 16

18 28. (1) (2), (1) (3), (1) (4), (1) (5) (1) (2) A B B A A B x(x A x B) x( (x B) (x A)) x(x / B x / A) x(x B x A) B A ( ) ( ) (/ ) ( ) (1) (3) A B A B = E A B x(x A x B) x( (x A) (x B)) x(x / A x B) x(x A x B) x(x A B) A B = E ( ) (/ ) ( ) 1 (1) (4) A B A B A A B A x(x A B x A) x((x A x / B) x A) x( (x A x / B) x A) x(( x A x / B) x A) x(( x A x / B) x / A) x(( x A x B) x A) x(( x A x B) x A) ( ) ( ) (/ ) ( ) 1 BBS chouxiaoya (1) (4) (1) (5) 17

19 x( x A x A x B) x( x A x B) x(x A x B) A B ( ) ( ) ( ) (1) (5) A B A B B A B B x(x A B x B) x((x A x / B) x B) x( (x A x / B) x B) x(( x A x / B) x B) x(( x A x B) x B) x(( x A x B) x B) x( x A x B) x(x A x B) A B ( ) ( ) (/ ) ( ) ( ) ( ) 29. x x ( A ) ( B) x ( A ) x ( B) z(z A x z) z(z B x z) z((z A x z) (z B x z)) ( ) = z(z A x z) ( ) = z((z A x z) (z B x z)) ( ) z(( (z A ) (x z)) ( (z B) (x z))) z(( (z A ) (z B)) (x z) (x z)) ( ) z(( (z A ) (z B)) (x z)) ( ) 18

20 z( (z A z B) x z) z(z A z B x z) z(z A B x z) x (A B) ( ) 30. (1) x x P(A) P(B) x P(A) x P(B) x A x B x A B x P(A B) ( ) ( 1.26 (2) ) ( ) (2) x x P(A) P(B) x P(A) x P(B) x A x B ( ) y(y x y A) y(y x y B) ( ) = y((y x y A) (y x y B)) ( ) y(( y x y A) ( y x y B)) y( y x (y A y B)) ( ) y(y x (y A B)) ( ) x A B ( ) x P(A B) ( )

21 lim A k = lim A k = [0, 1]. k k 34. lim B k = [0, 1], lim B k =. k k 35. lim A k = [0, ], lim A k = {0}. k k F G n 0 (n 0 N + k(k N + k n 0 (F (k) G(k)))) n 1 (n 1 N + k(k N + k n 1 F (k))) n 2 (n 2 N + k(k N + k n 2 G(k))) x(a(x) B(x)) = xa(x) xb(x) n 0 = max(n 1, n 2 ) k(k N + k n 0 (k n 1 k n 2 )) (1) x x lim A k lim B k k k lim A k lim B k lim (A k B k ) k k k n 0 (n 0 N + k(k N + k n 0 x A k )) n 0 (n 0 N + k(k N + k n 0 x B k )) n 0 ((n 0 N + k(k N + k n 0 x A k )) ( ) (n 0 N + k(k N + k n 0 x B k ))) ( ) 20

22 n 0 (n 0 N + ( k(k N + k n 0 x A k )) ( k(k N + k n 0 x B k ))) = n 0 (n 0 N + k((k N + k n 0 x A k ) ( ) (k N + k n 0 x B k ))) ( ) n 0 (n 0 N + k( (k N + k n 0 ) x A k ) ( (k N + k n 0 ) x B k )) n 0 (n 0 N + k( (k N + k n 0 ) (x A k x B k ))) n 0 (n 0 N + k(k N + k n 0 (x A k x B k ))) ( ) x lim (A k B k ) ( ) k lim (A k B k ) lim A k lim B k k k k lim (A k B k ) lim A k lim B k k k k x lim (A k B k ) k (1) x A k n 0 (x) k n 0 (x) x A k x lim A k k (A k B k ) (2) (1) {A k } x x lim k k x / (A k B k ) k x B k x lim k B k (1) lim (A k B k ) lim A k lim B k k k k lim (A k B k ) lim A k lim B k k k k lim A k lim B k lim A k lim B k k k k k lim A k lim B k lim A k lim B k k k k k 21

23 lim (A k B k ) = lim A k lim B k k k k lim (A k B k ) lim A k lim B k k k k x lim (A k B k ) k k x A k x B k x / lim A k lim B k x / lim A k x / lim B k {A k } {B k } k k k k x A k x B k x lim (A k B k ) k lim (A k B k ) lim A k lim B k k k k x x lim k A k lim k B k lim A k lim B k lim (A k B k ) k k k n(n N + ( k(k N + k n x A k ))) n(n N + ( k(k N + k n x B k ))) = n(n N + ( k(k N + k n x A k ) k(k N + k n x B k ))) n(n N + k((k N + k n x A k ) ( ) ( ) (k N + k n x B k ))) ( ) n(n N + k(k N + k n (x A k x B k ))) x lim k (A k B k ) ( ) ( ) (2) lim A k lim B k = lim (A k B k ) k k k x x lim A k lim B k k k n 1 (n 1 N + k(k N + k n 1 x A k )) 22

24 n 2 (n 2 N + k(k N + k n 2 x B k )) n 0 (n 0 N + k(k N + k n 0 x A k B k )) ( ) ( 1.6) x lim (A k B k ) ( ) k (1) lim A k lim B k lim A k lim B k k k k k lim A k lim B k lim A k lim B k k k k k lim A k lim B k lim (A k B k ) k k k lim A k lim B k lim (A k B k ) k k k x lim A k lim B k x lim A k n 0 N + k n 0 k k k k x A k n N + n = max(n, n 0 ) x lim B k k k N + k n n B k n k n n 0 x A k x A k B k lim A k lim B k lim (A k B k ) k k k lim A k lim B k lim (A k B k ) k k k lim (A k B k ) lim A k lim B k k k k x x lim k (A k B k ) n(n N + k(k N + k n x A k x B k )) n(n N + k(k N + k n x A k k N + k n x B k )) ( ) ( ) 23

25 = n(n N + ( k(k N + k n x A k ) k(k N + k n x B k ))) n( n N + ( k(k N + k n x A k ) k(k N + k n x B k ))) n(( n N + k(k N + k n x A k )) ( n N + k(k N + k n x B k ))) n( n N + k(k N + k n x A k )) n( n N + k(k N + k n x B k )) n(n N + k(k N + k n x A k )) n(n N + k(k N + k n x B k )) x lim k A k lim k B k ( ) ( ) ( ) ( ) (3) E = (A k B k ) k N + lim (A k B k ) = lim (A k B k ) k k lim k A k lim k ( B k ) = lim k A k lim k (E B k ) = lim A k (E lim B k ) k k = lim A k ( lim B k ) k k = lim A k lim B k k k ( (1) ) ( 1.5(1)) (4) E = (A k B k ) k N + lim (A k B k ) = lim (A k B k ) k k 24

26 = lim A k lim ( B k ) k k ( (2) ) = lim A k lim (E B k ) k k = lim A k (E lim B k ) k k = lim A k ( lim B k ) k k = lim A k lim B k k k ( 1.5(2)) 25

27 1. a, b, c = a, b, c = {{{{a}, {a, b}}}, {{{a}, {a, b}}, c}}. 2. (1) a, b c, d = {{a}, {a, b}} {{c}, {c, d}} = {{a}, {a, b}, {c}, {c, d}}; (2) a, b c, d = {{a}, {a, b}} {{c}, {c, d}} = ; (3) a, b c, d = {{a}, {a, b}} {{c}, {c, d}} = {{a}, {a, b}, {c}, {c, d}}; (4) a, b = {{a}, {a, b}} = {a} {a, b} = {a}; (5) { a, b } = a, b = {{a}, {a, b}}; (6) a, b, c = a, b, c = { a, b } = {{{a}, {a, b}}}; (7) { a, b } = a, b = {a}; (8) { a, b } 1 = { b, a } = b, a = {b} = b. 3. a, b, c = {{a}, {a, {{b}, {b, c}}}} = a, b, c = {{{{a}, {a, b}}}, {{{a}, {a, b}}, c}}. 4., = {{ }, {, }} = {{ }} a, {a} = {{a}, {a, {a}}} (3), (5), (7) 5. (1) A = B = ; (2) A = B A = B = ; (3) A = B = C = ; 6. (1) 26

28 x, y x, y (A C) (B D) (x A y C) (x B y D) ( ) (x A x B) (x A y D) (y C x B) (y C y D) ( ) = (x A x B) (y C y D) ( ) x (A B) (C D) ( ) (A C) (B D) (A B) (C D) (2) x, y x, y (A B) (C D) x A x / B y C y / D ( ) x A y C x / B y / D ( ) = x A y C x / B ( ) = (x A y C x / B) (x A y C y / D) ( ) (x A y C) (x / B y / D) ( ) (x A y C) ( (x B) (y D)) (/ ) (x A y C) (x B y D) ( ) ( x, y A C) ( x, y B D) ( x, y A C) ( x, y / B D) (/ ) x, y (A C) (B D) (A B) (C D) (A C) (B D) 7. (1) 27

29 x, y x, y (A B) C x (A B) y C x A x / B y C x A x B y C (x A x B y C) 0 (x A x B y C) (x A 0) (x A x B y C) (x A y C y C) (x A y C) ( x B y C) (x A y C) (x B y C) ( x, y A C) ( x, y B C) ( x, y A C) ( x, y / B C) x, y (A C) (B C) (A B) C = (A C) (B C) (/ ) ( ) ( ) ( ) ( ) ( ) (/ ) (2) (A B) C =((A B) (B A)) C =((A B) C) ((B A) C) =((A C) (B C)) ((B C) (A C)) ( (1) ) =(A C) (B C) 8. A = B = A B A A = 9. A B A B A B A B 2 A B = 2 mn A B 28

30 R 1 = ; R 2 = { a, 1 }; R 3 = { b, 1 }; R 4 = { c, 1 }; R 5 = { a, 1, b, 1 }; R 6 = { a, 1, c, 1 }; R 7 = { b, 1, c, 1 }; R 8 = { a, 1, b, 1, c, 1 }; B A R 1 1 = ; R 1 2 = { 1, a }; R 1 3 = { 1, b }; R 1 4 = { 1, c }; R 1 5 = { 1, a, 1, b }; R 1 6 = { 1, a, 1, c }; R 1 7 = { 1, b, 1, c }; R 1 8 = { 1, a, 1, b, 1, c }; a R S(S R a S) S S(S R S S a S) {{x}, {x, y}} S({{x}, {x, y}} R S {{x}, {x, y}} a S) (R ) {{x}, {x, y}} S({{x}, {x, y}} R (S = {x} S = {x, y}) a S) ( ) {{x}, {x, y}}({{x}, {x, y}} R (S = {x} a S) (S = {x, y} a S)) ( ) {{x}, {x, y}}({{x}, {x, y}} R (a = x (a = x a = y))) ( ) {{x}, {x, y}}({{x}, {x, y}} R (a = x a = y)) ( ) a domr a ranr ( ) 1 (starfish@lilybbs.us) 29

31 a fldr fldr = R. ( ) 11. (1) R 1 R 2 = { a, b, a, c, b, d, c, c, c, d, d, b, d, d } R 1 R 2 = { b, d } R 1 R 2 = (R 1 R 2 ) (R 1 R 2 ){ a, b, a, c, c, c, c, d, d, b, d, d } (2) domr 1 = {a, b, c} domr 2 = {a, b, d} dom(r 1 R 2 ) = domr 1 domr 2 = {a, b, c, d} (3) ranr 1 = {b, c, d} ranr 2 = {b, c, d} ranr 1 ranr 2 = {b, c, d} (4) R 1 A = { a, b, c, c, c, d } R 1 {c} = { c, c, c, d } (R 1 R 2 ) A = { a, b, a, c, c, c, c, d } R 2 A = { a, c } (5) R 1 [A] = {b, c, d} R 2 [A] = {c} (R 1 R 2 )[A] = (6) R 1 R 2 = { a, c, a, d, d, d } R 2 R 1 = { a, d, b, b, b, d, c, b, c, d } R 1 R 1 = { a, d, c, c, c, d } 12. (1) R 1 = { {, { }},,, { },, }; (2) R R = {,,, {, { }}, { },, { }, {, { }} }; (3) R = ; R { } = {, {, { }},, }; R {{ }} = { { }, }; R {, { }} = R = {, {, { }}, { },,, }; (4) R[ ] = ; R[{ }] = {{, { }}, }; R[{{ }}] = { }; 30

32 R[{, { }}] = ranr = {{, { }}, }; (5) domr = {, { }}; ranr = {{, { }}, }; fldr = domr ranr = {, { }, {, { }}}; 13. (1) R R R R R R 1 R R 1 R x, y x, y R R 1 x, y R x, y R 1 y, x R 1 y, x R y, x R 1 R y, x R R 1 ( ) R R 1 R R x, y x, y R R 1 x, y R x, y R 1 x, y R y, x R = x, y R y, x R (R R ) ( x, y R x, y R ) ( y, x R y, x R ) ( ) ( x, y R x, y R 1) ( y, x R y, x R 1) ( ) ( x, y R ( x, y R ( x, y R y, x R ))) ( y, x R ( y, x R ( y, x R x, y R ))) (R ) = ( x, y R y, x R ) ( x, y R y, x R ) ( ) x, y R y, x R ( ) = x, y R ( ) R R 1 R 31

33 R R 1 R 14. (1) R = { 1, 2, 2, 3 }; (2) R 2 R = x z( x, z R 2 x, z R) ( ) x z ( x, z R 2 x, z R) ( ) x z( x, z R 2 x, z R) ( ) x z( ( y( x, y R y, z R)) x, z R) ( ) x z( y( ( x, y R y, z R)) x, z R) ( ) x z y( ( x, y R y, z R) x, z R) ( ) x y z( ( x, y R y, z R) x, z R) ( 2 ) x y z(( x, y R y, z R) x, z R) R 15. A R x x x x, x / R x x, x / R, A P(A) A A x, y P(A) x, y R y, x R x, y R y, x R x = y S

34 A A P(A) A A A = A A, A / S P(A) =, S, A S A, S A A, S, A S A, A / S T, / T A P(A) A A = A A, A T, A T A, T A, A T A, T, / T A R x x, x R x, y P(A) x, y R xry yrx x, y P(A) x, y R y, x R x, y R y, x R x = y R x, y, z x, y R y, z R x, y R y, z R x, z R S, S, S x y( x, y S y, x S x = y = x = y) x y z( x, y S y, z S x = y = z = x, z S) T = = A, T, T 33

35 x y( x, y T y, x T x = y = x = y) x y z( x, y T y, z T x = y = z = x, z T ) 16. (1) R = { 0, 10, 1, 9, 2, 8, 3, 7, 4, 6, 5, 5, 6, 4, 7, 3, 8, 2, 9, 1, 10, 0 }; S = { 0, 4, 3, 3, 6, 2, 9, 1, 12, 0 }. (2) R 0, 0 / R 5, 5 R 0, 10 R 10, , 10 R 10, 0 0, 0 / R S 0, 0 / S 3, 3 S 0, 4 S 4, 0 / S x, y A x, y S y, x S 12, 0 S 0, 4 S 12, 4 / S M(R) = G(R) R 34

36 1, 1 R 1, 2 R 2, 1 R 1 2 2, 0 R 0, 3 R 2, 3 / R 18. R 1 = { a, a, a, b, b, b, c, b, c, c }; R 2 = { a, b, b, c }; R 3 = { a, b, a, c, c, a, c, b }; R 4 = { a, a, b, b, c, c }; M(R 1 ) = 0 1 0, M(R 2) = 0 0 1, M(R 3) = 0 0 0, M(R 4) = R 1 a, a R 1 a, b R 1 b, a / R 1 R 2 a, a / R 2 a, b R 2 b, a / R 2 a, b R 2 b, c R 2 a, c / R 2 R 3 a, a / R 3 a, b R 3 b, a / R 3 a, c R 3 c, a R 3 a c 35

37 a, c R 3 c, a R 3 a, a / R 3 R 4 a, a R R 1 = { a, a, a, b, b, a, b, b, b, c, c, a, c, c }; R 2 = { a, a, a, b, b, b, c, a, c, b }; R 3 = { a, b, a, c, b, a, b, c, c, a, c, b }; R 4 = { a, a, a, b, a, c, b, c, c, a }; a a b c b c G(R 1 ) G(R 2 ) a a b c b c G(R 3 ) G(R 4 ) R 1 a, a R 1 c, a R 1 a, c / R 1 a, b R 1 b, a R 1 a b c, a R 1 a, b R 1 c, b / R 1 36

38 R 2 c, c / R 2 a, a R 2 a, b R 2 b, a / R 2 R 3 a, a / R 3 a, b R 3 b, a R 3 a b a, b R 3 b, a R 3 a, a / R 3 R 4 b, b / R 4 a, a R 4 a, b R 4 b, a / R 4 a, c R 4 c, a R 4 a c c, a R 4 a, b R 4 c, b / R M(R) = a 1 b 2 c 3 d G(R 1 ) 37

39 21. M(R 1 ) = M(R 2 ) = M(R 2 R 1 ) = M(R 1 ) M(R 2 ) = = R 2 R 1 = { 1, β } 22. R 2.19(1) R = r(r) = R I A R (R R) R ( 1.3) = (R R) (R I A ) (R I A = R) = R (R I A ) ( 2.6(1)) = R R (R = R I A ) R 2.14 R R R R R = R A = {a, b} R = { a, a } R R = { a, a } = R b, b / R R 23. R R = R (R R ) R S x, y 38

40 x, y R S = y, x R S (R S ) z( y, z S z, x R) ( ) = z( z, y S x, z R) (R S ) z( x, z R z, y S) ( ) x, y S R ( ) R S S R S R R S R S R S = S R R S = S R x, y x, y R S x, y S R (R S = S R) z( x, z R z, y S) ( ) = z( z, x R y, z S) (R S ) z( y, z S z, x R) ( ) y, x R S ( ) 24. R 1 = R 2 = { 1, 1 } R 3 = { 2, 2 } R 4 = { 1, 2 } R 5 = { 2, 1 } R 6 = { 1, 1, 1, 2 } R 7 = { 1, 1, 2, 1 } R 8 = { 1, 1, 2, 2 } R 9 = { 1, 2, 2, 1 } R 10 = { 1, 2, 2, 2 } 39

41 R 11 = { 2, 1, 2, 2 } R 12 = { 1, 1, 1, 2, 2, 1 } R 13 = { 1, 1, 1, 2, 2, 2 } R 14 = { 1, 1, 2, 1, 2, 2 } R 15 = { 1, 2, 2, 1, 2, 2 } R 16 = { 1, 1, 1, 2, 2, 1, 2, 2 } R 8, R 13, R 14, R 16 R 1, R 4, R 5, R 9 R 1, R 2, R 3, R 8, R 9, R 12, R 15, R 16 R 1, R 2, R 3, R 4, R 5, R 6, R 7, R 8, R 10, R 11, R 13, R 14 R 1, R 2, R 3, R 4, R 5, R 6, R 7, R 8, R 10, R 11, R 13, R 14, R 16 R 1 R 8 R 16 R 13 R 4 R 14 R 5 R I domr R 1 R x, y x, y I domr x = y x domr ( ) x = y z( x, z R) x = y z( x, z R z, x R 1 ) x = y x, x R 1 R ( ) x, y = x, x x, x R 1 R ( 2.1) = x, y R 1 R ( ) I ranr R R 1 x, y x, y I ranr x = y x ranr ( ) 40

42 x = y z( z, x R) ( ) x = y z( z, x R x, z R 1 ) x = y z( x, z R 1 z, x R) ( ) x = y x, x R R 1 ( ) x, y = x, x x, x R R 1 ( 2.1) = x, y R R 1 ( ) 26. (1) M(R) = M(R 2 ) = M(R 3 ) = R 2 = { a, a, a, c, b, b, b, d } R 3 = { a, b, a, d, b, a, b, c } (2) m = 2, n = 4; (3) R 2 = R 4 R 1 = R 3 R 2 = I A ( ) A (2) m n N R 1 = { x, y x, y N y = x + 1} k N R 1 k = { x, y x, y N y = x + k} m, n N m n R1 m = R1 n R 1, R 2 dom(r 1 R 2 ) domr 2 ran(r 1 R 2 ) ranr 1 m N + dom(r1 m ) domr 1 ran(r1 m ) ranr 1 x, y x, y R 1 R 2 z( x, z R 2 z, y R 1 ) ( ) = z( x, z R 2 ) z( z, y R 1 ) ( ) x domr 2 y ranr 1 (dom ran ) 41

43 dom(r 1 R 2 ) domr 2 ran(r 1 R 2 ) ranr 1 R 2 = R 1 m m N +, dom(r m 1 ) domr 1 ran(r m 1 ) ranr R 1, R 2 fldr 1 fldr 2 = m, n N + (R m 1 R n 2 = ) R 1, R 2 ((fldr 1 fldr 2 = ) (R 1 R 2 = )) x, y (R 1 R 2 ) z( x, z R 2 z, y R 1 ) z ranr 2 fldr 2 z domr 1 fldr 1 z fldr 1 fldr 2 R 1, R 2 ((fldr 1 fldr 2 = ) (R 1 R 2 = )) 2.1 dom(r m 1 ) domr 1 ran(r m 1 ) ranr 1 fld(r m 1 ) = dom(r m 1 ) ran(r m 1 ) domr 1 ranr 1 (fld ) = fldr 1 (fld ) fld(r n 2 ) fldr 2 fld(r m 1 ) fld(r n 2 ) fldr 1 fldr 2 ( 2.1& 1.4) ( 1.5) = ( ) R m 1 m = 0 R 1 R 2 A R n 2 = (R 1 R 2 ) 0 = I A = I A I A ( ) = R 0 1 R 0 2 m = k (k N) (R 1 R 2 ) k = R k 1 R k 2 42

44 m = k + 1 (R 1 R 2 ) k+1 = (R 1 R 2 ) k (R 1 R 2 ) 28. m = 0, n = 15 3 = (R k 1 R k 2) (R 1 R 2 ) ( ) = (R k 1 R k 2) R 1 (R k 1 R k 2) R 2 ( 2.6(1)) = (R k 1 R 1 ) (R k 2 R 1 ) (R k 1 R 2 ) (R k 2 R 2 ) ( 2.6(2)) = R k+1 1 (R k 2 R 1 ) (R k 1 R 2 ) R k+1 2 = R k+1 1 R k+1 2 ( 2.2) = R k+1 1 R k+1 2 ( ) 29. r(r) = { a, a, a, b, b, b, c, c, c, d, d, d }; s(r) = { a, a, a, b, b, a, b, b, c, d, d, c }; t(r) = { a, a, a, b, b, b, c, d } a a a b d b d b d c r(r) c s(r) c t(r) 30. (1) R + = t(r) 2.19(3) (R + ) + = t(r + ) = R + (2) 3 m, n(m n) m, n(m < n) m = n = 0 43

45 R = rt(r) 2.25(3) R 2.19(3) trt(r) = rt(r) 2.19(1) 2.25(3) rtrt(r) = trt(r) (R ) = rtrt(r) = trt(r) = rt(r) = R (3) R R = R R i ( ) i=0 = R R i ( 2.6(1)) i=0 = R i+1 ( 2.17(1)) i=0 = R i (i := i + 1) i=1 = t(r) ( 2.24) = R + ( ) R + = R R 31. a d g e a c d b r(r) f a d g e g e c b f c b f s(r) t(r)

46 A = I A I B = P A Q A = P 1 B Q 1 B = P A P 1 A = P B P 1 B = P A P T A = P 1 B (P T ) 1 B = P 1 A Q 1 C = P 2 B Q 2 C = P 2 P 1 A Q 1 Q 2 B = P A P 1 C = Q B Q 1 C = Q P A P 1 Q 1 B = P A P T C = Q B Q T C = Q P A P T Q T 33. a+bi C a a 0 a 2 > 0 a+bi, a+bi R a + bi, c + di R a + bi C c + di C ac > 0 c + di C a + bi C ca > 0 c + di, a + bi R a 1 +b 1 i, a 2 +b 2 i, a 2 +b 2 i, a 3 +b 3 i R a 1 +b 1 i C a 3 +b 3 i C a 1 a 2 > 0 a 2 a 3 > 0 ab > 0 sgn(a) = sgn(b) 4 a 1 a 2 > 0 a 2 a 3 sgn(a 1 ) = sgn(a 2 ) sgn(a 2 ) = sgn(a 3 ) ( ) = sgn(a 1 ) = sgn(a 3 ) a 1 a 3 > 0 a 1 + b 1 i, a 3 + b 3 i R R C /R = {{a + bi a + bi C a > 0}, {a + bi a + bi C a < 0}}; ( ) R y C /R y y 34. (1) 1 x < 0 4 sgn (signum) sgn(x) = 0 x = 0 1 x > 0 45

47 x(x A x, x R 1 ) x(x A x, x / R 1 ) A x A x, x / R 1 R 1 (2) x(x A ( x, x R 1 x, x R 2 )) x(x A x, x / R 1 R 2 ) A x A x, x / R 1 R 2 R 1 R 2 R 2 R 1 (3) A = {a, b, c}, R 1 = E, R 2 = { a, c, c, a } I A R 1 R 2 r(r 1 R 2 ) = { a, b, b, a, b, c, c, b } I A a, b r(r 1 R 2 ) b, c r(r 1 R 2 ) a, c / r(r 1 R 2 ) r(r 1 R 2 ) r(r 2 R 1 ) R 1 = R 2 = I A R 1 = R 2 = r(r 1 R 2 ) = r(r 2 R 1 ) = I A R 1 R 2 r(r 1 R 2 ) r(r 2 R 1 ) (4) A = {a, b, c}, R 1 = { a, b, b, a } I A, R 2 = { a, c, c, a } I A R 1 R 2 R 1 R 2 = { a, b, a, c, b, a, c, a, c, b } I A ( c, b R 1 R 2 b, c / R 1 R 2 ) R 2 R 1 R 1 = R 2 = I A R 1 = R 2 = R 1 R 2 = R 2 R 1 = I A R 1 R 2 R 1 R 2 R 2 R

48 R x, y A x, y R x, y R 1 ( ) x, y R x, x R (R ) = y, x R ( (2)) R x, y, z A x, y R y, z R = y, x R y, z R (R ) = x, z R ( (2)) R R A 36. (1) B ik / π 2 (2) j, k {1, 2,..., m} j k B ij B ik = (A ij B) (A ik B) ( ) = A ij A ik B B ( ) = B B (π 1 ) = ( ) (3) A B = π 1 B (π 1 A ) ( n ) = A i B = = i=1 n (A i B) ( ) i=1 m (A ik B) (A i B m ) k=1 47

49 m = k=1 B ik ( ) = π 2 π 2 π 2 A B 37. A/R = {{1, 6, 11, 16}, {2, 7, 12, 17}, {3, 8, 13, 18}, {4, 9, 14, 19}, {5, 10, 15, 20}} 38. (1) A / A (2) A i1 B j1, A i2 B j2 A A i1 B j1 A i2 B j2 x(x A i1 B j1 A i2 B j2 ) ( ) x(x A i1 x B j1 x A i2 x B j2 ) ( ) x(x A i1 x A i2 x B j1 x B j2 ) ( ) = x(x A i1 x A i2 ) x(x B j1 x B j2 ) ( ) x(x A i1 A i2 ) x(x B j1 B j2 ) ( ) A i1 A i2 B j1 B j2 ( ) = A i1 = A i2 B j1 = B j2 (π 1, π 2 ) = A i1 B j1 = A i2 B j2 ( ) A i1 B j1, A i2 B j2 R A i1 B j1 A i2 B j2 A i1 B j1 A i2 B j2 = (3) A = A A ( ) = ( π 1 ) ( π 2 ) (π 1, π 2 ) 48

50 ( m ) ( n ) = A i B j i=1 = 1 i m 1 j n j=1 (π 1, π 2 ) (A i B j ) ( ) = A (A ) A A π 1 π 2 A i B j A 1.2 A i B j A i A i B j B j A π 1 π 2 A π 1 π (1) R π = { 1, 2, 1, 3, 2, 1, 2, 3, 3, 1, 3, 2 } I A ; A/R π = π = {{1, 2, 3}, {4}}; (2) π 1 = A/R π1 = {{1}, {2}, {3}, {4}}; R π1 = I A ; π 2 = A/R π2 = {{1, 2}, {3}, {4}}; R π2 = { 1, 2, 2, 1 } I A ; π 3 = A/R π3 = {{1, 3}, {2}, {4}}; R π3 = { 1, 3, 3, 1 } I A ; π 4 = A/R π4 = {{1}, {2, 3}, {4}}; R π4 = { 2, 3, 3, 2 } I A ; π 5 = A/R π5 = π; R π5 = R π = { 1, 2, 1, 3, 2, 1, 2, 3, 3, 1, 3, 2 } I A. 40. A (A A/R 1 B(B A/R 2 A B)) x, y A x, y R 1 A (A A/R 1 x A y A ) ( ) = A A/R 1 x A y A ( ) 49

51 A A/R 1 x A y A B(B A/R 2 A B) ( ) B(A A/R 1 x A y A B A/R 2 A B) ( ) = A A/R 1 x A y A B A/R 2 A B ( ) = B A/R 2 x A y A A B ( ) = B A/R 2 x B y B ( ) = B(B A/R 2 x B y B) ( ) x, y R 2 ( ) A x y(a A/R 1 x A y A B(B A/R 2 x B y B)) A, x, y A A/R 1 x A y A x, y R 1 ( ) x, y R 1 R 1 R 2 ( ) = x, y R 2 ( ) B(B A/R 2 x B y B) ( ) 41. R 3 x, y x, y A B x A y B = x, x R 1 y, y R 2 (R 1, R 2 ) x, y, x, y R 3 (R 3 ) R 3 x 1, x 2, y 1, y 2 x 1, y 1, x 2, y 2 R 3 x 1, x 2 R 1 y 1, y 2 R 2 (R 3 ) = x 2, x 1 R 1 y 2, y 1 R 2 (R 1, R 2 ) x 2, y 2, x 1, y 1 R 3 (R 3 ) 50

52 R 3 x 1, x 2, x 3, y 1, y 2, y 3 x 1, y 1, x 2, y 2 R 3 x 2, y 2, x 3, y 3 R 3 x 1, x 2 R 1 y 1, y 2 R 2 x 2, x 3 R 1 y 2, y 3 R 2 x 1, x 2 R 1 x 2, x 3 R 1 y 1, y 2 R 2 y 2, y 3 R 2 (R 3 ) ( ) = x 1, x 3 R 1 y 1, y 3 R 2 (R 1, R 2 ) x 1, y 1, x 3, y 3 R 3 R 3 (R 3 ) 42. { 4 2} = = 7 R 1 = { b, c, b, d, c, b, c, d, d, b, d, c } I A ; R 2 = { a, c, a, d, c, a, c, d, d, a, d, c } I A ; R 3 = { a, b, a, d, b, a, b, d, d, a, d, b } I A ; R 4 = { a, b, a, c, b, a, b, c, c, a, c, b } I A ; R 5 = { a, b, b, a, c, d, d, c } I A ; R 6 = { a, c, c, a, b, d, d, b } I A ; R 7 = { a, d, d, a, b, c, c, b } I A ; 43. { } { } { } { } { } ( 5 = 1 + (2 4 1) { } { }) 4 + C = 1 + (2 4 1) + (3 C ) + C = = (1) 51

53 R R R 3 1 R 4 (2) R e b c d a 1 a b d 2 c e (1) A, 1 e a (2) A, 2 a, d, e a, b, c, e 46. B {k lcm(1, 2,..., 10) k N + } lcm(1, 2,..., 10) = B A B 1 = 1, 2, 6, 18, 54; 52

54 B 2 = 1, 3, 9, 27, 54; B 3 = 1, 3, 6, 18, 54; B 4 = 1, 3, 9, 18, (2) A 5 A (1) R B x x B = x A (B A) = x, x / R (R ) x, x R (/ ) = x, x R x, x B B ( ) ( x, x R x, x B B) ( ) ( x, x R B B) ( x, x R B) (R B ) x, x / R B (/ ) R B x, y, z x, y R B y, z R B x, y R B B y, z R B B (R B ) x, y R x, y B B y, z R y, z B B x, y R x B y B y, z R y B z B x, y R y, z R x B y B z B ( ) = x, z R x B y B z B (R ) = x, z R x B z B ( ) 53

55 x, z R x, z B B x, z R B R B (2) R B x x B (R B ) x B x B ( ) = x A x B (B A) = x, x R (R ) x, x R x, x B B x, x R B B x, x R B (R B ) R B x, y x, y R B y, x R B x, y R B B y, x R B B (R B ) x, y R x, y B B y, x R y, x B B x, y R x B y B y, x R y B x B x, y R y, x R ( ) = x = y (R ) R B ( (1) ) R B (3) 54

56 (2) R B x, y B R B x, y x B y B x B y B x B y B = x A y A x B y B (B A) ( ) = ( x, y R y, x R) x B y B (R ) ( x, y R x B y B) ( y, x R y B x B) x, y R B y, x R B (4) R B ( ) (R B ) (3) R B C B R B C B B A C A R A y(y C x(x C y, x R)) C B x, y x B y B y, x R B R B B 49. R x, y x, y A B x A y B = y, y R 2 x, x R 1 (R 1, R 2 ) = y, y R 2 ( x, x R 1 y = y) ( ) y, y R 2 ( x, x R 1 y = y) ( y, y R 2 ( x, x R 1 y = y)) ( x, y, x, y R) x, y, x, y / R ( ) ( ) (R ) (/ ) 55

57 R x 1, x 2, x 3, y 1, y 2, y 3 x 1, y 1, x 2, y 2 R x 2, y 2, x 3, y 3 R ( y 1, y 2 R 2 ( x 1, x 2 R 1 y 1 = y 2 )) ( y 2, y 3 R 2 ( x 2, x 3 R 1 y 2 = y 3 )) (R ) ( y 1, y 2 R 2 y 2, y 3 R 2 ) ( y 1, y 2 R 2 x 2, x 3 R 1 y 2 = y 3 ) ( x 1, x 2 R 1 y 1 = y 2 y 2, y 3 R 2 ) ( x 1, x 2 R 1 y 1 = y 2 x 2, x 3 R 1 y 2 = y 3 ) ( ) 4 1 R 2 y 1, y 3 R 2 2 y 1, y 2 R 2 y 2 = y 3 y 1, y 3 R 2 3 y 2, y 3 R 2 y 1 = y 2 y 1, y 3 R 2 4 R 1 = x 1, x 3 R 1 y 1 = y 3 4 x 1, y 1, x 3, y 3 R R R 50. R x, y x, y A B x A y B = x, x R 1 y, y R 2 (R 1, R 2 ) x, y, x, y R (R ) R x 1, x 2, y 1, y 2 x 1, y 1, x 2, y 2 R x 2, y 2, x 1, y 1 R x 1, x 2 R 1 y 1, y 2 R 2 x 2, x 1 R 1 y 2, y 1 R 2 x 1, x 2 R 1 x 2, x 1 R 1 y 1, y 2 R 2 y 2, y 1 R 2 (R ) ( ) 56

58 = x 1 = x 2 y 1 = y 2 (R 1, R 2 ) x 1, y 1 = x 2, y 2 x 1, y 1, x 2, y 2 = x 2, y 2, x 1, y 1 ( 2.1) ( 2.1) R x 1, x 2, x 3, y 1, y 2, x 3 x 1, y 1, x 2, y 2 R x 2, y 2, x 3, y 3 R x 1, x 2 R 1 y 1, y 2 R 2 x 2, x 3 R 1 y 2, y 3 R 2 x 1, x 2 R 1 x 2, x 3 R 1 y 1, y 2 R 2 y 2, y 3 R 2 (R ) ( ) = x 1, x 3 R 1 y 1, y 3 R 2 (R 1, R 2 ) x 1, y 1, x 3, y 3 R (R ) R 51. 8, 6 8 8, 3 8, 2 4, , 1 4, 3 4, 2 2, , 1 2, 3 2, 2 1, 6 R 1 R 2 2, 1 1, 3 1, 2 1, 1 R

59 2.40 x, y X(x y R x R y ) R x R y x y R X A

60 1. R 2, R 3, R 6, R 7 A B R 2, R 6 A B 2. 1 f g f, g A B x, y, z x, y f g x, z f g x, y f x, y g x, z f x, z g = x, y f x, z f ( ) = y = z f g 2 f g A B f = g (f ) x, y f x, y / g x, y / f x, y g x, y f x, y / g x / dom(f g)( z x, z f g x, z g x, y / g z y x, y f x, z f g f y z x, y f x, z f f ) f g 59

61 3 f g f g A B f = g f g f g A B f g A B f g f g dom(f g) = domf domg ( 2.3(1)) = A A (f, g A B) = A ( ) f g A B f g f g A B f g f g A B f g A B f = g f g x, y f x, y / g x, y / f x, y g x, y f x, y / g g z x, z g x, y / g z y x, y (f g) x, z (f g) z y f g 3. (1), (2), (6), (10) (1), (4), (5), (6), (9), (10) (1), (6), (10) 4. f = { S, F S, F A B x(x A (x S F (x) = 1))} f A B f 1 B A 5. 60

62 3.1 A B = A B = A = B A = B A = A B A B B a B f = { x, a x A} A ( A f A B ) f A B A B A = B A B A B = A B = A B = 3.1 A B = B A = A B = B A = A B = B A A B B A f A B A B = B A f B A A = domf 6. = B f f C A x y z(x domf y ranf z ranf xfy xfz y = z) (f A B) (f B A) domf = C ranf A = x y z(x domf y ranf z ranf xfy xfz y = z) domf = C ranf B (A B& ) 61

63 f C B 7. ( 10 ) 3.2 f, g A B f g domg domf f = g f g g f x, y x, y g = x domg (dom ) = x domf (domg domf) z( x, z f) z( x, z f x, z f) (dom ) = z( x, z f x, z g) (f g) ( ) = z( x, z f z = y) (g & x, y g) = x, y f ( ) A = N, f : N N, f(x) = x + 1, g : N N, g(x) = x/2 f f ( 0 N 0 / ranf) k N 2k, k g g k N 2k, k g 2k + 1, k g 2k 2k + 1 g

64 1 y(y domg g(y) ) y y domg y B (domg = B) = x(x A x, y f) (f ) x(x g(y)) (g ) g(y) ( ) g y 1, y 2 B, s P(A) y 1, s g y 2, s g = x(x s x, y 1 f) x(x s x, y 2 f) s = g(y 1 ) (g ) x((x s x, y 1 f) (x s x, y 2 f)) s = g(y 1 ) ( ) = x((x s x, y 1 f) (x s x, y 2 f)) s ( 1) x((x s x, y 1 f) (x s x, y 2 f)) x(x s) ( ) x(( x s x, y 1 f) ( x s x, y 2 f)) x(x s) x( x s ( x, y 1 f x, y 2 f)) x(x s) ( ) x(x s ( x, y 1 f x, y 2 f)) x(x s) = ( x(x s) x( x, y 1 f x, y 2 f)) x(x s) ( ) = x( x, y 1 f x, y 2 f) ( ) = y 1 = y 2 (f ) g g 12. x R x, 0, x f x, 1, x g f, g 63

65 x R x, 0, x f x 1, 1, x f x x 1 x, 0, 0 g x + 1, 0, 0 g x x 1 f, g 13. f : E F, f(x) = A/x f(x) f A R, S E f(r) = f(s) f A/R = A/S x, y x, y R B(x B y B B A/R) ( ) B(x B y B B A/S) (A/R = A/S) x, y S ( ) f(r) = f(s) R = S f f A A F R A = { x, y x, y A B(x B y B B A )} R A E 1 f(r A ) = A R A E x x A x A (A ) B(x B B A ) B(x B x B B A ) ( ) x, x R A (R A ) x, y x, y R A B(x B y B B A ) B(y B x B B A ) (R A ) ( ) 64

66 y, x R A x, y, z (R A ) x, y R A y, z R A B(x B y B B A ) B(y B z B B A ) (R A ) = x B 1 y B 1 B 1 A y B 2 z B 2 B 2 A ( ) = x B 1 B 1 A z B 2 B 2 A y B 1 y B 2 ( ) = x B 1 B 1 A z B 2 B 2 A y B 1 B 2 = x B 1 B 1 A z B 2 B 2 A B 1 B 2 ( ) = x B 1 B 1 A z B 2 B 2 A B 1 = B 2 (B 1 B 2 B 1 = B 2 2 ) = x B 1 z B 2 B 1 A ( ) = B(x B z B B A ) ( ) x, z R A (R A ) R A E R A f(r A ) = A f f 14. S f f A = x(x [0, 1] (f(x) f(x)) = 0) (f [0, 1] R) = x(x [0, 1] (f(x) f(x)) 0) ( ) f, f S (S ) (2) 2 (2) 65

67 S f, g f, g A g, f A x(x [0, 1] (f(x) g(x)) 0) x(x [0, 1] (g(x) f(x)) 0) x((x [0, 1] (f(x) g(x)) 0) (S ) (x [0, 1] (g(x) f(x)) 0)) ( ) x(( x [0, 1] (f(x) g(x)) 0) ( x [0, 1] (g(x) f(x)) 0)) x( x [0, 1] ((f(x) g(x)) 0 (g(x) f(x)) 0)) x( x [0, 1] ((f(x) g(x)) = 0)) x(x [0, 1] ((f(x) g(x)) = 0)) f = g S f, g, h f, g A g, h A x(x [0, 1] (f(x) g(x)) 0) x(x [0, 1] (g(x) h(x)) 0) x((x [0, 1] (f(x) g(x)) 0) ( ) ( ) ( ) (S ) (x [0, 1] (g(x) h(x)) 0)) ( ) x(( x [0, 1] (f(x) g(x)) 0) ( x [0, 1] (g(x) h(x)) 0)) x( x [0, 1] ((f(x) g(x)) 0 (g(x) h(x)) 0)) x( x [0, 1] ((f(x) h(x)) ( ) = (f(x) g(x)) + (g(x) h(x)) 0)) ( ) x(x [0, 1] ((f(x) h(x)) 0)) f, g A S (S ) S f : [0, 1] R, f(x) = x g : [0, 1] R, g(x) = 1 x 0, 1 [0, 1] f(0) g(0) < 0 g(1) f(1) < 0 f, g / S g, f / S S 66

68 15. (1) N/R 1 = {{x} x N}; N/R 2 = {{2k + j k N} j {0, 1}}; N/R 3 = {{3k + j k N} j {0, 1, 2}}; N/R 4 = {{6k + j k N} j {0, 1, 2, 3, 4, 5}}; (2) N/R 2 N/R 3 N/R 4 N/R 1 (3) f 1 (H) = H; f 2 (H) = {0}; f 3 (H) = {0, 1, 2}; f 4 (H) = {0, 2, 4}; 16. g f(x) = x f g(x) = x 2 + 4x + 14 f g, h g 1 (x) = x 4; h 1 (x) = 3 x A A R f : A A/R R = I A f f x, y A x, y R = [x] R = [y] R ( 2.27(2)) f(x) = f(y) (f ) 67

69 x = y (f ) x, y I A R I A R I A R R = I A 2 R = I A f f 1 : A/R A, f 1 ([x]) = x (1) domf = R {0} = (, 0) (0, + ); ranf = R {0} = (, 0) (0, + ); domg = R; rang = {0} R + = R R = [0, + ); domh = {0} R + = R R = [0, + ); ranh = {0} R + = R R = [0, + ); (2) domf, domg, domh f, g, h 19. (1) f(a 1 ) = {1, 2, 3}; f 1 (B 1 ) = {0, 4, 5, 6}. (2) g(a 2 ) = N; g 1 (B 2 ) = {2k + 1 k N} {6}. (3) f g 20. (1) f g 3.5(2) g g g g g 1 g g f = f I B = f g g 1 f g g 1 3.4(2) f = f g g 1 68

70 (2) f g 3.5(1) f f f f f 1 f f g = I B g = f 1 f g f 1 f g 3.4(1) g = f 1 f g f, g A B f = g x(x A f(x) = g(x)) f = g x x A y( x, y f) (f A B) = x, a f ( ) f(x) = a f(x) = a f(x) = a f(x) = a x, a f (f(x) ) ( ) (f(x) ) f(x) = a x, a g (f = g) f(x) = a g(x) = a f(x) = g(x) f = g x(x A f(x) = g(x)) x(x A f(x) = g(x)) x, y x, y f f(x) = y (g(x) ) (f(x) ) 69

71 g(x) = y x, y g x(x A f(x) = g(x)) f = g (f(x) = g(x)) (g(x) ) f h 1 = g h dom(f h 1 ) = dom(g h 1 ) = domh 1 = A 3.3 f h 1 = g h 1 x(x A f h 1 (x) = g h 1 (x)) A x A x X f(x) = g(x) x A, f h 1 (x) = f(h 1 (x)) ( 3.3) = f(x) (h 1 (x) = x) = g(x) (f(x) = g(x)) = g(h 1 (x)) (h 1 (x) = x) = g h 1 (x) ( 3.3) B A 3.3 f h 2 = g h 2 x(x B f h 2 (x) = g h 2 (x)) x x B = f h 2 (x) = g h 2 (x) x X ( ) f(h 2 (x)) = g(h 2 (x)) x X ( 3.3) f(x) = g(x) x X (h 2 (x) = x) x A (A ) B A 22. f, g (X X)(h f = h g f = g) h 70

72 h x 1, x 2 X x 1 x 2 h(x 1 ) = h(x 2 ) f : X X, f(x) = x 1 g : X X, g(x) = x 2 h f = h g f g h f = h g f = g h f = h g f = g h h 3.10(1) h h h f, g (X X) h f = h g f = I X f = h h f = h h g = I X g = g ( 3.6) (h h ) (h f = h g) (h h ) ( 3.6) f, g (X X) h f = h g f = g h f, g (X X)(f h = g h f = g) h h a X x(x X h(x) a)( h(a) a) x x a f : X X, f(x) = x g : X X, g(x) = f h = g h f g h(a) x = a f h = g h f = g f h = g h f = g h h 3.10(2) h h h f, g (X X) f h = g h f = f I X = f h h = g h h = g I X = g ( 3.6) (h h ) (h f = h g) (h h ) ( 3.6) 71

73 f, g (X X) f h = g h f = g h A f A A f n A A (n N) n n = 0 f n = f 0 = I A A A n = k (k 0) n = k + 1 f k+1 = f k f A A ( 3.3) I A I A f n = f n 1 f = f f n 1 = I A n n 1 n 1 0( ) (n 1) N 3.4 f n 1 A A f n 1 f = I A 3.5(3) f f f n 1 = I A 3.5(3) f f (3) f 1 (A B) f 1 (A) f 1 (B) f 1 (A) f 1 (B) f 1 (A B) x x f 1 (A) f 1 (B) x f 1 (A) x f 1 (B) x X f(x) A x X f(x) B ( ) 72

74 x X f(x) A f(x) B x X f(x) A B x f 1 (A B) f 1 (A B) = f 1 (A) f 1 (B) ( ) ( ) 73

75 1. (1) (2) (3) (4) a = 2. (1) 2 3 = 3; (2) 2 3 = 2; (3) 5 = 4; (4) 6 = 0; (5) 7 = 5; 3. S = {n n N n 0 m(m N n = m + )} S = S {0} S N (1) S = 0 S (2) n S( S n N) N n + N n n {n} = n + n + 0 n + n m(m N n = m + ) n + S S S N S = N S = S {0}

76 S = {n m N(m m + n + )} (1) 0 S m N, m m {m} = m + = (m + 0) + = m (2) n S m N, m m + n + (m + n + ) {(m + n + )} = (m + n + ) + = (A m (n + )) + = A m (n ++ ) = m + (n + ) + n + S S = N 5. A x x A + x A {A} x A x {A} x A x = A ( ) ( ) = x A x = A ( 4.10) = x A x A (x = A x A) x A ( ) = x A x {A} ( ) x A {A} x A + 6. (1) 4.10 A + A x, x A ( ) 75

77 y(y A x y) = y(y A x y) (y & 4.10) = y(y A x y) = x A ( ) (2) 4.10 A A A x, x A y(y A x y) = y(y A x y) (y & 4.10) y(y A z(z x z y)) y z(y A (z x z y)) y z( y A ( z x z y)) y z( z x ( y A z y)) y z(z x (y A z y)) z(z x y(y A z y)) z(z x z A ) x A A ( ) ( ) ( ) ( ) ( ) S = {n n N m(m N m n h(m) = h(n))} 0 / S 0 S S h m N, m 0 h(m) = h(0) = a m ( 0 ) m n h(m) = h(n + ) = f(h(n)) = a a A ranf 0 / S 76

78 S N S n 0 S m 0 N, m 0 n 0 h(m 0 ) = h(n 0 ) m 0 n 0 N, n 0 m 0 h(n 0 ) = h(m 0 ) m 0 S m 0, n 0 S 0 / S m 0 0, n m p, n p N m 0 = m + p, n 0 = n + p h f(h(m p )) = h(m + p ) = h(m 0 ) = h(n 0 ) = h(n + p ) = f(h(n p )) f f(h(m p )) = f(h(n p )) h(m p ) = h(n p ) 4.4(m + n + m n) m 0 n 0 m p n p n p S n 0 = n + p > n p n 0 S S n, m N, n m h(n) = h(m) h 77

79 1. f : A B x A, f(x) = x I A f R 1, R 2 A f(r 1 ) = f(r 2 ) (I A R 1 ) ((R 1 I A ) R 1 ) ( & 1.2) (I A R 1 ) ((R 1 I A ) R 1 ) (I A R 1 ) ((R 2 I A ) R 1 ) (f(r 1 ) = f(r 2 )) = (I A (R 2 I A )) R 1 R 1 ( 1.4) (I A (R 2 I A )) R 1 (I A (R 2 I A )) R 1 (I A R 2 ) (I A I A ) R 1 (I A R 2 ) E R 1 (I A R 2 ) R 1 ( ) ( ) ( ) ( ) R 2 R 1 (I A R 2 ) 2. (1) R 2 R 1 R 1 R 2 f(r 1 ) = f(r 2 ) R 1 = R 2 f R B 2.29(3) R I A A f(r I A ) = R f f A B A B 78

80 (2) f : ((A A)/R) (P(A) ), x (A A)/R, f(x) = ran(x) (A A)/R f S P(A) / P(A) S a S x, x S g : A A, x A, g(x) = g (A A) f([g] R ) = S a, x / S f f (A A)/R P(A) 5.1 [0, 1] R [0, 1] [a, b] f : [0, 1] [a, b], x [0, 1], f(x) = (b a)x + a f [0, 1] [a, b] I A A A 3.9 f : A B f 1 : B A A B B A 3.4(3) g : A B f : B C f g : A C A B B C A C 5. 79

81 S = {n n N x(x n m(m n x m))} (1) 0 S x x 0 (2) n S n + x 1 x = n x n n + 2 x n m n n + x m n + 3 n x x {n} n( n x {n} n + = n {n} x {n} {n} = x x n ) m n x {n} m x m + ( f : x {n} m g : x m +, y f(y), y n x, g(y) = g f ) 4.4(m n m, y = n m + n + ) m n x m + n + x n + x n + = n {n} n / x x n x n 1 2 n x 3 m n + x m n S n + S S = N 6. I A : A A A A 3.4(2) g : A B, f : B C f g f g : A C A B B C A C 7. A A N A N A N A A n N n N 5.5 2(2) N A 5.7 (2) A N = A N A A N A 80

82 A A N 5.14 N A Schröder-Bernstein A N n = 2 A B κ = carda λ = cardb κ ℵ 0, λ ℵ 0 κ λ κ ℵ 0 ( 5.22(2)) = ℵ 0 κ ( 5.21(1)) ℵ 0 ℵ 0 ( 5.22(2)) = ℵ 0 ( 5.9(4)) card(a B) = κ λ ℵ 0 n = k(k 2) n = k + 1 k S n = 2 S k + 1 n = k P(A) cardp(a) ℵ ℵ 0 carda cardp(a) ℵ 0 ℵ 0 carda ℵ 0 ℵ 0 cardp(a) ℵ 0 Schröder-Bernstein carda = cardp(a) = ℵ 0 A P(A) P(A)

83 (1) f : N A, x N, f(x) = (x + 1) 7 f carda = cardn = ℵ 0 (2) f : N B, x N, f(x) = (x + 1) 109 f cardb = cardn = ℵ 0 (3) 5.7 N A A B N A B A B N 5.7 (1) A B N Schröder-Bernstein card(a B) = cardn = ℵ 0 (4) C = {n 763 n N n 0} f : N C, x N, f(x) = (x + 1) 763 f N C C A B 5.7 N A B A B N 5.7 (1) A B N Schröder-Bernstein A B N card(a B) = cardn = ℵ cardp(a) = 2 carda, cardp(b) = 2 cardb 2 carda = 2 cardb carda = cardb 5.7 carda cardb cardb carda 5.22(4) 2 carda 2 cardb 2 cardb 2 carda Schröder-Bernstein 2 carda = 2 cardb 13. (1) cardp(a) = 2 carda = 2 cardb = cardp(b) n N S = {{{0}}, {1}, {2},..., {n 1}} cards = n, S N = {{0}}, x = 0 f : N S N, x N, f(x) = {x}, 0 < x < n x n, x n (2) f n + ℵ 0 = card(s N) = cardn = ℵ 0 1 n N + S = {nm m N} f : N S, x N, f(x) = nx f S N 82

84 g : (n S) N, x, y (n S), g( x, y ) = x + y g n S N (3) n ℵ 0 = card(n S) = cardn = ℵ N N N N N =, N N = N ℵ 0 + ℵ 0 = card(n N ) = cardn = ℵ 0 (4) 14. (1) (2) (3) 5.1(2) K κ card = 0, K =, K = K κ + 0 = card(k ) = cardk = κ K κ K = κ 0 = card(k ) = card = 0 K κ card({ }) = 1, K K { }( f : K K { }, x K, f(x) = x, ) 1 n 0 card( N) = card = 0 ℵ 0. 83

85 κ 1 = card(k { }) = cardk = κ (4) K κ ( K) = { } κ 0 = card( K) = card({ }) = 1 (5) (6) K κ κ 0 K (K ) = κ 1 = card( K ) = card = 0 K 1, K 2 κ K 1 K 2 = f : K 1, f(x) x K 1 K 1 K 2 g : K 1 K 2 {K 1, K 2 } K 2, x K 1 K 2, g(x) = K 2, x, x K 2 g(y) (7) K 1 K 2 = g g x, y K 1 K 2, x y (1) x K 1, y K 2 x K 2, y K 1 K 1 K g(x) (2) x, y K 1 f f(x) f(y) 2.1 g(x) g(y) (3) x, y K g(x) g(y) g K 1 K 2 {K 1, K 2 } K 2 κ + κ = card(k 1 K 2 ) = card({k 1, K 2 } K 2 ) = 2 κ 84

86 K κ f : K ({ } K), x K, f(x) = {, x } f K ({ } K) κ 1 = card({ } K) = cardk = κ (8) n N card({n}) = 1, n {n} = n + 1 = card(n {n}) = card(n + ) = n + 85

87 1. A, A, B, B (1) (2) A = {1, 2, 3, 4, 12} A B = {1, 2, 3, 4} B f(1) = 1, f(2) = f(3) = 2, f(4) = 3, f(12) = 4 A, A, B, B f f(2) = f(3) f f(3) B f(4) 3 A 4 f(x) B f(y) x A y A, A, B, B (1) (2) (1) f x, y A x y f(x) = f(y) A, A x A y y A x f(x) B f(y) f(y) B f(x) f(x) = f(y) f (2) x, y A f(x) B f(y) x A y A, A x = y y A x x = y f f(x) = f(y) f(x) B f(y) y A x f(y) B f(x) f(x) B f(y) x, y A, x A y f(x) B f(y) (2) (5) 3. (1) 86

88 x, y A x y x, y y, x R x y x, y y, x R R I A x, y C(n, 2) = n(n 1)/2 R I A R I A n(n 1)/2 R I A R R = I A + R I A I A (R I A ) = n + n(n 1)/2 = n(n + 1)/2 (2) x, y A x y x, y y, x R x A, x, x / R R = C(n, 2) = n(n 1)/2 4. A, A, 6.1 A, A B A, A, x, y A x y x y y x B = {x, y} A B x y x y x y B A, A, A Z + B = f(a) = {f(x) x A} f B N N B < b C = A f 1 (b) = {x x A f(x) = b} C Z + C < c c A R x A x c f(c) = b f(a) f(c) < f(x) f(c) = f(x) f(c) < f(x) R crx f(x) = f(c) = b x, c f 1 (b) x, c A x, c C = A f 1 (b) c C x c c < x R crx c A R A Z Z +, R 5. 87

89 B = {x x A f(x) x} B = B B A t B f(t) t f f(f(t)) f(t) f(t) B f(t) t t 6. (1) F (0) = A ( ran(f (seg0))) (γ ) = A ( {F (x) x seg0}) ( ) = A ( ) (seg0 = ) = A F (1) = A ( ran(f (seg1))) (γ ) = A ( {F (x) x seg1}) ( ) = A ( {F (0)}) (seg1 = {0}) = A ( {A}) (F (0) = A) = A ( A) F (2) = A ( ran(f (seg2))) (γ ) = A ( {F (x) x seg2}) ( ) = A ( {F (0), F (1)}) (seg2 = {0, 1}) = A ( {A, A ( A)}) (F (0) = A, F (1) = A ( A)) = A ( (A (A ( A)))) = A ( (A ( A))) ( ) = A ( A) ( A) ( (A B) = ( A) ( B)) n N, F (n + ) = A ( F (n)) n N F (n + ) = A ( F (n) F (n) F (n + ) S = {x x N F (x + ) = A ( F (x)) F (x) F (x + )} F (0) = A A ( A) = A ( F (0)) = F (1) 0 S n N n 1 x N, x < n x S F (n + ) = A ( ran(f (seg(n + )))) (γ ) 88

90 = A ( {F (x) x seg(n + )}) ( ) = A ( {F (0), F (1),, F (n)}) (seg(n + ) = {0, 1,, n}) = A ( (F (0) F (1) F (n))) = A ( (F (n))) ( F (0) F (1) F (n)) F (n + ) = A ( F (n)) n 1 n 1 N n 1 S F (n) = A ( F (n 1)) F (n 1) F (n) 1.8(1) F (n 1) F (n) F (n 1) F (n) F (n) = A ( F (n 1)) A ( F (n)) = F (n + ) (2) (3) x N, x < n x S n + S N S = N n N F (n + ) = A ( F (n)) (1) F (n + ) = A ( F (n)) a F (n) = a F (n) ( 1.8(2)) = a A ( F (n)) (F (n) A ( F (n))) = a F (n + ) (F (n + ) = A ( F (n))) ranf = {F (0), F (1), F (2), } B = ranf = n N F (n) x B n N x F (n) (2) x F (n + ) F (n + ) ranf x F (n + ) ranf = B x B x B 4.10 B 7. (1) A = F (0) ranf A ranf = B 89

91 Z A S = A N S N S s x A x S x s x / S x Z N s N s x s A S = A (Z N) f : (Z N) N, x (Z N), f( x) = x Z f x y f(x) < f(y) N 6.3(3) Z N, A (Z N) Z 6.1 Z, (2) E(3) = {0, 1, 2}; E( 1) = N; E( 2) = N { 1}; E( n) = N { m m N + m < n}, n N. 8. f, g : A B A, A B, B f, g 3.9 f 1 : B A f f 1 = I B x, y A x A y g(x) B g(y) I B g(x) B I B g(y) (g ) ( 3.6) (f f 1 ) g(x) B (f f 1 ) g(y) (f f 1 = I B ) f(f 1 g(x)) B f(f 1 g(y)) f 1 g(x) A f 1 g(y) ( ) (f ) x, y, x A y f 1 g(x) A f 1 g(y) 6.5 x A x A f 1 g(x) f(x) B f(f 1 g(x)) = g(x) g(x) f(x), x A f(x) = g(x), x A f = g A, A B, B 9 1. F a, b A a b 1 F A, S, F A, S, 90

92 a b( b a) a F (b)( b F (a)) b / F (a)( a / F (b)) F (a) F (b) a b b a a F (a) b / F (a) F (a) F (b) F a, b A a b x x F (a) x a x = a (F (a) ) = x b (a b ) = x F (b) (F (b) ) F (a) F (b) b F (b) b / F (a) F (a) F (b) F (a) F (b) a F (a) F (b) a b F F (a) F (b) F (a) F (b) a b a b 10. a b F (a) F (b) F A, S, α β α β A, α, α f : A α B, 0 β, β g : B β B A g 1 : β A α β f : A β f g 1 : β β f g 1 x, y β x y I β (x) I β (y) (I β ) g g 1 (x) g g 1 (y) (g g 1 = I β ) g(g 1 (x)) g(g 1 (y)) g 1 (x) 0 g 1 (y) ( 3.3) (g ) = g 1 (x) g 1 (y) ( 0 ) f(g 1 (x)) f(g 1 (y)) (f ) f g x f g 1 (x), x β α β α f g 1 (α) g 1 g 1 (α) B A f f g 1 (α) α 91

93 92

94 93

95 = G (1) 9 6 (2) (3) (4) (5) (a) G G ( 1) G i v i, v j V (G i ) v i v j d(v i ) = d(v j ) (b) V (G) 2 G v i, v j V (G) v i v j d(v i ) = d(v j ) (a) G G i (G i ) = n i G v V (G i ), d(v) n i 1 G i d(v) 1 v V (G i ) d(v) n i 1 G i n i (a) 94

96 (b) G (a) G 0 G G u v (u, v) G G 1, G 2 G 1 = G2 G 1 = G2 f 7.3 r n 1, n 2,..., n r (r 1) r K n1,n 2,...,n r r G = V 1, V 2,..., V r, E G = V 1, V 2,..., V r, E V i = V i = n i (i = 1, 2,..., r) ( ) f : V (G) V (G ) f(x) V i x V i (i = 1, 2,..., r) f G = G G G n 1, n 2,..., n r r K n1,n 2,...,n r r K n1,n 2,...,n r G 3-2m = 3n n = G G G 6 3- G ( G 1 G 2 ) 95

97 a f a f b e b e c d c d G 1 G G G v 1 V (G ) f(v 1 ) = a v 1 ( G 2 ) b, c, d, e, f G = G1 G G 2 3 V (G) = 6 G K G = G G 1 G G 1 G 2 6. (1) (2) a f a f a f b e b e b e c d c d c d G 1 G (1) G 3 7. (1) (6, 6, 5, 5, 3, 3, 2) (5, 4, 4, 2, 2, 1) (3, 3, 1, 1, 0) (2, 0, 0, 0) (2) (5, 3, 3, 2, 2, 1) (2, 2, 1, 1, 0) (1, 0, 1, 0) (1, 1, 0, 0) ( ) (3) (3, 3, 2, 2, 2, 2) (2, 1, 1, 2, 2) (2, 2, 2, 1, 1) (1, 1, 1, 1) 96

98 a f a f a f b e b e b e c d G 7.7(2) c G 1 d 7.7(3) c G 2 d 8. a d a d a d a d a d b c b c b c b c b c G 1 G 2 G 3 G 4 G 5 a d a d a d a d a d b c b c b c b c b c G 6 G 7 G 8 G 9 G 10 a d a a a a b c b c b c b c b c G 11 G 12 G 13 G 14 G 15 a a a b b G 16 G 17 G 18 G 19 G 1 G 11 K 4 G 6, G 18, G

99 a a a a a b c b c b c b c b c G 1 G 2 G 3 G 4 G 5 a a a a a b c b c b c b c b c G 6 G 7 G 8 G 9 G 10 a a a a a b c b c b c b c b c G 11 G 12 G 13 G 14 G 15 a a a a a b c b b b G 16 G 17 G 18 G 19 G 20 G 21 G 1 G 16 G 7, G 9, G 10, G 18, G 20, G G 5, G 6, G G 3 4 (1) δ(g) 1 G ( ) 3, 1, 1, 1 2, 2, 1, 1 G 7 G 6 (2) δ(g) = 0 G ( ) 2, 2, 2, 0 G G 5 98

100 3 4 G 5, G 6, G 7 5 ( G i = Gj = Gk G i = G j G k = Gm i, j, k, m 5 ) G E(G) = E(G) E(G) + E(G) = E(K n ) = n(n 1)/2 E(G) = n(n 1)/4 E(G) 4 n(n 1) n n n 4 n 1 n = 4k n = 4k G v 1 G 5 3 v 1 3 v 1 ( G v 1 ) 3 G v 1 3 v 2, v 3, v 4 (1) 3 3 G 3 (2) 3 v 1 G G G G 1 G 2 G 1 v G 1 d(v) G u, v, w V (G), (u, v), (v, w) E(G) (u, w) 1 G G 9 3 G 7 2 G 18 99

101 E(G) ( ) ( ) u, v V (G), u v u v (u, v) E(G) d(u, v) d(u, v) = 1 d(u, v) (u, v) E(G) d(u, v) = i u, v V (G) d(u, v) = i (u, v) E(G) d(u, v) = i + 1 d(u, v) = i+1 w 1, w 2,..., w i ((u, w 1 ), (w 1, w 2 ),..., (w i 1, w i ), (w i, v) E(G)) (u, w i ) E(G) (w i, v) (u, v) E(G) d(u, v) = i d(u, v) = i + 1 ( ) G 7.4 G G 15. Γ = v 0, v 1,..., v l Γ v 0 Γ δ(g) δ(g) v i1, v i2,..., v iδ (G)(i 1 < i 2 <... < i δ (G)) v 0 δ(g) 2 δ(g) 1 Γ v i1 v iδ (G) (v iδ (G), v 0 ) Γ v 0, v 1,..., v iδ (G), v 0 δ(g) + 1 ( v 0 v 0 v 0 δ(g))

102 Γ = v 0, v 1,..., v l Γ v 0 Γ δ(g) 3 v 1 v i, v j (2 i < j l) v 0 v 0, v 1,..., v i, v 0 i + 1 v 0, v 1,..., v j, v 0 j + 1 v 0, v i,..., v j, v 0 j i + 2 d G d i + 1 d j + 1 d j i + 2 d (i + 1) + (j i + 2) (j + 1) = 2 (d d ) d 2 d 2( ) d ( ) d δ(g) (G) n 1 δ(g) n 1 n 2 δ(g) = n 1 G κ(g) κ(g) = n 1 δ(g) = n κ(g) δ(g) = n κ(g) 2δ(G) n + 2 = n 2 κ(g) = n (1) n 0 1 G n 2 δ(g) n (1) λ(g) = δ(g) 1 G (2) 101

103 V 1 G V 1 < k( V 1 k 1) δ(g V 1 ) 1 2 (n+k 1) (k 1) = 1 2 (n k+1) > 1 2 (n k)( G G 1 G k 1 δ(g V 1 ) 1 2 (n+k 1) (k 1)) G V 1 = n k G V 1 (1) V 1 G (1) v 1 V (G) N G (v 1 ) v 2 N G (v 1 ) N G (v 2 ) = ( v 1 v 2 3 G 4 ) N G (v 1 ) = N G (v 2 ) = k G N G (v 1 ) N G (v 2 ) = N G (v 1 ) + N G (v 2 ) N G (v 1 ) N G (v 2 ) = 2k (2) G K k,k (1) v 1, v 2 N G (v 1 ), N G (v 2 ) (1) N G (v 1 ) N G (v 2 ) = N G (v 1 ) = N G (v 2 ) = k N G (v 1 ) N G (v 2 ) = N G (v 1 ) + N G (v 2 ) = 2k = V (G) N G (v 1 ) N G (v 2 ) G u 1, u 2 N G (v i )(i = 1, 2) u 1, u 2 N G (v 1 ) N G (v 1 ) v 1 v 1, u 1, u 2, v 1 3 G 4 N G (v i )(i = 1, 2) G k- k N G (v 1 ) N G (v 2 ) G K k,k 7.3 G

104 20. v G (G) = n 2 G v u d(g) = 2 G u v( u v ) G v u G = G v G ( G u v ) 7.9 E(G ) V (G ) 1 = n 2 G G n 2 m = E(G) = E(G ) + n 2 2n n G E(G) = n p(g) p(g) G n n = 1 n = i n = i + 1 V (G) = i + 1 G x = E(G) + p(g) x = i + 1 v V (G) G = G I G (x) G G v G 7.18 G x = E(G) + p(g) = E(G ) + p(g ) G v G v G v G 1 E(G ) = E(G ), p(g ) = p(g ) 1 V (G ) = i E(G ) = i p(g ) x = E(G ) + p(g ) = E(G ) + p(g ) + 1 = i + 1 E(G) + p(g) = x = i + 1 E(G) = (i + 1) p(g) n = i n = i

105 G G 7.5 G n 1 m < n m n G K 2 3 B Kelley B C B C B e = (u, v ) / E(C) C e = (u, v) E(C) 7.20 e e C (u, v) E(C) E(C ) V (C) V (C ) 2 e C V (C) V (C ) s t( s t V (C) V (C ) 2 ) C Γ = s a t Γ C s t C Γ 1 Γ 2 G E(Γ 1 ) + E(Γ 2 ) = E(C) E(Γ 1 ) E(Γ 2 ) C 1 = Γ 1 Γ, C 2 = Γ 2 Γ G B C C v v e e / C V (B) = V (C), E(B) = E(C) B = C 23. n = 2r, δ = s, λ = r, κ = (1) 24. (1) 7.12 G G (2) 7.12 (3) 6 v K 6 (1) K 6 K 3 K 3 K 3 104

106 K 3 K 3 3 v 1 3 v 1 K D D D 105

107 106

108 A 4 f 1 = { 0, 0, 1, 1 }; f 2 = { 0, 1, 1, 0 }; f 3 = { 0, 0, 1, 0 }; f 4 = { 0, 1, 1, 1 }; f 1 f 3 f 4 f 1 f 2 f 3 f 4 f 1 f 1 f 2 f 3 f 4 f 2 f 2 f 1 f 4 f 3 f 3 f 3 f 3 f 3 f 3 f 4 f 4 f 4 f 4 f

109 i τ(i) τ τ(i) = (i mod n) + 1 A 4. Z Z 1 N 1 M n (R) 0 0 GL n (R) nz R + ab a b {a i } a b = b R(A) I A Z + gcd(a, b) lcm 1 lcm(a, b) gcd 1 5. (1) a, b, c ( a = b = c = 0 ) (2) A = { 1, 0, 1} 6. (1) 0 (2) 0 (3) n =

110 (4) g(x) 0 f/g / S S 7. (1) 1 (2) 1 (3) 1 (4) ab a + b a/b + b/a / Z + Z p = q a = 1, b = 0 a b = b a pa + qb + r = qa + pb + r ( ) p + r = q + r (a = 1, b = 0) p = q 2 p, q {0, 1} (p = q r = 0) a, b, c R (a b) c = a (b c) p(pa + qb + r) + qc + r = pa + q(pb + qc + r) + r p 2 a + pqb + pr + qc + r = pa + pqb + q 2 c + qr + r p 2 a + qc + pr = pa + q 2 c + qr ( ) a, c p 2 = p q 2 = q pr = qr p 2 = p q 2 = q p, q {0, 1} pr = qr p = q r = 0 109

111 3 p + q = 1 r = 0 x R a x = x (p + q)x + r = x p + q = 1 r = 0 ( ) 4a q = 1 (p 0 r = 0) e l x R e l x = x pe l + qx + r = x ( ) q = 1, pe l + r = 0 p 0 r = 0 pe l + r = 0 ( p = r = 0 ) 4b p = 1 (q 0 r = 0) 4a 4c p = q = 1, r = 0 p = q = 1, r = 0 0 4a 4b 110

112 5a q = 0 ((p = 1 r = 0) p 1) p = 1, q = r = 0 q = 0, p = 1 r/(1 p) θ l x R θ l x = θ l pθ l + qx + r = θ l q = 0, pθ l + r = θ l r = 0 p = 1 θ l p 1 θ l = r/(1 p) r 0, p = 1 ( ) 5b p = 0 ((q = 1 r = 0) q 1) 5a 5c p = q = 0 p = q = 0 r 5a 5b x x 1 = x/(1 x)

113 x a b x a b x a b x a b 1 x a a 2 x a b 3 x b a 4 x b b 16 1 a b 2 a b 3 a b 4 a b 5 a b 6 a b a a a a a a a a a a a a a a b a a b b a a b a b b b a b b b b a a b a b 7 a b 8 a b 9 a b 10 a b 11 a b 12 a b a a b a a b a b a a b a a b a a b a b b a b b b b a a b a b b b a b b b 13 a b 14 a b 15 a b 16 a b a b b a b b a b b a b b b a a b a b b b a b b b 3, 5, 12, 14 a 3 b = a b 3 a = b (b 3 a) 3 b = b 3 b = a b 3 (a 3 b) = b 3 a = b 11. 1, 2 3, 4 = 1 3, = 3, 6 3, 4 1, 2 = 3 1, = 3, 10 1, 2 3, 4 = 3, 4 1, 2 ( a, b c, d ) e, f = ac, ad + b e, f = ace, acf + ad + b a, b ( c, d e, f ) = a, b ce, cf + d = ace, acf + ad + b a, b, c, d, e, f A ( a, b c, d ) e, f = a, b ( c, d e, f ) 1, 0 0, x ( x Q ) d a, b Q, ad + b = d a, b A a 0 1/a, b/a ( ) a = 0 c 0c = (1) ϕ : A Z 3, ϕ(a) = 0, ϕ(b) = 1, ϕ(c) = 2 A,, a ϕ = Z3,, a (2) x y = y, x, y A A 112

114 (3) ϕ : A Z 3, ϕ(a) = 1, ϕ(b) = 2, ϕ(c) = 0 A,, a ϕ = Z3,, b b = a a c (4) ϕ : A Z 10, ϕ(a) = 1, ϕ(b) = 6, ϕ(c) = 4 A,, a ϕ = Z10,, c c = b a 13. θ l θ l θ r = θ l θ r θ l θ r = θ r θ l = θ l θ r = θ r θ ( ) θ ( ) θ θ = θ ( θ θ = θ ) θ θ θ = θ θ = θ 14. θ = θ θ = θ( θ = θ θ = θ) V 1 = Z 6, V V V 2 = {0, 2, 4}, V V 3 = {0, 3}, V V 4 = {0}, V 15. (1) V 1 V 2 { 1, 5, 1, 6, 2, 5, 2, 6, 3, 5, 3, 6 },, 1, 6 113

115 1, 5 1, 6 2, 5 2, 6 3, 5 3, 6 1, 5 1, 5 1, 5 2, 5 2, 5 3, 5 3, 5 1, 6 1, 5 1, 6 2, 5 2, 6 3, 5 3, 6 2, 5 2, 5 2, 5 2, 5 2, 5 3, 5 3, 5 2, 6 2, 5 2, 6 2, 5 2, 6 3, 5 3, 6 3, 5 3, 5 3, 5 3, 5 3, 5 3, 5 3, 5 3, 6 3, 5 3, 6 3, 5 3, 6 3, 5 3, 6 1, 6 3, 5 1, 6 (2) V 1 = {1, 2, 3},, 1 V V V 2 = {1, 2},, 1 V V 3 = {1, 3},, 1 V V 4 = {1},, 1 V 16. (1) V 1 V 2 Z 3 Z 2, 0, 0 0, 1 1, 0 1, 1 2, 0 2, 1 0, 0 0, 0 0, 1 1, 0 1, 1 2, 0 2, 1 0, 1 0, 1 0, 0 1, 1 1, 0 2, 1 2, 0 1, 0 1, 0 1, 1 2, 0 2, 1 0, 0 0, 1 1, 1 1, 1 1, 0 2, 1 2, 0 0, 1 0, 0 2, 0 2, 0 2, 1 0, 0 0, 1 1, 0 1, 1 2, 1 2, 1 2, 0 0, 1 0, 0 1, 1 1, 0 (2) V 1 V 2 0, 0 Z 3 Z 2 0, 0 0, 0 0, 1 0, 1 1, 0 2, 0 1, 1 2, ( a, b = c, d a = c b = d)

116 + C C ϕ : C B, a + bi C, ϕ(a + bi) = a b ϕ b a ϕ a + bi, c + di C ϕ((a + bi) + C (c + di)) = ϕ((a + c) + (b + d)i) = a + c b + d (b + d) a + c = a b + c d b a d b ( ) (ϕ ) ( ) = ϕ(a + bi) + ϕ(c + di) (ϕ ) ϕ((a + bi) C (c + di)) = ϕ((ac bd) + (bc + ad)i) ac bd bc + ad = (bc + ad) ac bd = a b c d b a d b ( ) (ϕ ) ( ) = ϕ(a + bi) ϕ(c + di) (ϕ ) ϕ C, + C, C B, +, C, + C, C ϕ = B, +, 19. V 1 V 2 V 2 V 1 A B, 1, 2 B A, 1, 2 ϕ : A B B A, x, y A B, ϕ( x, y ) = y, x ϕ ϕ x 1, y 1, x 2, y 2 A B, i 1, 2 ϕ( x 1, y 1 i x 2, y 2 ) = ϕ( x 1 i x 2, y 1 i y 2 ) = y 1 i y 2, x 1 i x 2 (ϕ ) = y 1, x 1 i y 2, x 2 115