Solutions to Exercises in "Discrete Mathematics Tutorial"

Transcription

1 1 2 (beta ) 3 SOLVED AND TEXIFIED BY 4 ( ( xiaoxinpan@163.com) ( / ) 60.17% 4 xbz 02 chouxiaoya tedy akaru yitianxing xuening ourszf ushing pizzamx datoubaicai echoqing soup1122 lycool hamletyj leejunner zliner sunbird2002 zhaoming169 zqliu qiushuitian1111 tcschen Supremgoooo Smilingface yangling 1985 jianzhentianxia ouyangj0 kylinwang

2

3 ( )

4 4

5 1.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, 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} 1.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} 1.3 (1), (4), (5), (6), (8), (9) 1.4 (1) : A B B C A B x(x B x C) ( ) = A B (A B A C) (x/a) = A C ( ) (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 5

6 A C 1.5 A = {a}, B = {{a}}, C = {{{a}}} A B B C A / C 1.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}} 1.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) 1.8 (1) {4} (2) {1, 3, 5} 6

7 (3) {2, 3, 4, 5} (4) {2, 3, 4, 5} (5) {, {4}} (6) {{1}, {1, 4}} 1.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} 1.10 P(A) = {, {a}} PP(A) = {, { }, {{a}}, {, {a}}} (1), (2), (4), (5) 1.11 : A B = A A B = (A B) B (A B = A) = (A B) B = 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 ( ) ( ) (/ ) ( ) ( ) 7

8 (1) (A B) (A C) = A A B C = : (A B) (A C) = A A (B C) = A ( ) A (B C) = ( 1.11 ) A B C = ( ) (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 ) 1.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 : 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) 8

9 (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) 1.14 : B = E B ( ) = (A A) B ( ) = (A B) ( A B) ( ) = (A C) ( A C) ( ) = (A A) C ( ) = E C ( ) = C ( ) 1.15 A = B = D = G C = F = H 1.16 (1) {3, 4, {3}, {4}} (2) (3) {, { }} 1.17 (1) {, {{ }}, {{{ }}}, {{ }, {{ }}}} (2) {, { }, {{ }}, {, { }}} 9

10 (3) {{ }, {{ }}} 1.18 (1) {, 1, 2, 3} (2) (3) (4) 1.19 (1) A B (2) A (3) B 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 ( ) 1.21 (1) A B = A A B 10

11 : 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) 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)) 11

12 = 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 ( ) = (A B) B (A B = A B) = B ( ) 1.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 1.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 1.24 (A B) C = (A C) B : (A B) C = (A B) C = A ( B C) ( ) = A ( C B) ( ) = ((A C) B) ( ) = (A C) B 12

13 (A B) C = A (B C) : (A B) C = (A B) C = A ( B C) ( ) = 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) 1.25 (1) A (2) A B (3) B A 1.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 ( ) A B C x x A = x A x B ( ) = x C ( ) A C B C (2) 13

14 : 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 1.27 : A A ( 1.1) P(A) ( ) { } P(A) P(A) ( 1.1) { } PP(A) PP(A) ( ) {, { }} PP(A) ( ) {, { }} PPP(A) ( ) {, { }} PPP(A) A A P(A) {, { }} PPP(A) 1.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 ( ) ( ) (/ ) ( ) ( ) (/ ) ( ) 14

15 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) 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 ( ) ( ) (/ ) ( ) ( ) ( ) ( ) ( ) ( ) (/ ) ( ) ( ) ( ) 1.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))) 1 BBS chouxiaoya (1) (4) (1) (5) 15

16 z(( (z A ) (z B)) (x z) (x z)) z(( (z A ) (z B)) (x z)) z( (z A z B) x z) z(z A z B x z) z(z A B x z) x (A B) 1.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) lim A k = lim A k = [0, 1] k k 1.34 lim B k = [0, 1], lim B k = k k 1.35 lim A k = [0, ], lim A k = {0} k k ( ) ( ) ( ) ( )

17 1.6 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) 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 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 ))) ( ) 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 17

18 (2) (1) {A k } x x lim (A k B k ) k k x / (A k B k ) k x B k x lim 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 (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 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 lim A k lim B k lim (A k B k ) k k k x x lim k A k lim k 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 ) 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 ) ( ) ( ) 18

19 (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 )) 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 ( ) 19

20 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(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) ( (1) ) = lim A k (E lim B k ) ( 1.5(1)) k k = lim A k ( lim B k ) k k = lim A k lim B k k k (4) : E = (A k B k ) k N + lim (A k B k ) = lim (A k B k ) k k = 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) ( 1.5(2)) k k = lim A k ( lim B k) k k = lim A k lim B k k k 20

21 2.1 a, b, c = a, b, c = {{{{a}, {a, b}}}, {{{a}, {a, b}}, c}} 2.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 2.3 a, b, c = {{a}, {a, {{b}, {b, c}}}} = a, b, c = {{{{a}, {a, b}}}, {{{a}, {a, b}}, c}} 2.4, = {{ }, {, }} = {{ }} a, {a} = {{a}, {a, {a}}} (3), (5), (7) 2.5 (1) A = B = (2) A = B A = B = (3) A = B = C = 2.6 (1) : 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) 21

22 (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) 2.7 (1) : 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) ) 22

23 =(A C) (B C) 2.8 A = B = A B A A = 2.9 A B A B A B A B 2 A B = 2 mn : A B 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 dom R a ran R ( ) ( ) ( ) a fld R fld R = R 1 (starfish@lilybbs.us) ( ) 23

24 2.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) dom R 1 = {a, b, c} dom R 2 = {a, b, d} dom(r 1 R 2 ) = dom R 1 dom R 2 = {a, b, c, d} (3) ran R 1 = {b, c, d} ran R 2 = {b, c, d} ran R 1 ran R 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 } 2.12 (1) R 1 = { {, { }},,, { },, } (2) R R = {,,, {, { }}, { },, { }, {, { }} } (3) R = R { } = {, {, { }},, } R {{ }} = { { }, } R {, { }} = R = {, {, { }}, { },,, } (4) R[ ] = R[{ }] = {{, { }}, } R[{{ }}] = { } R[{, { }}] = ran R = {{, { }}, } (5) dom R = {, { }} ran R = {{, { }}, } fld R = dom R ran R = {, { }, {, { }}} 2.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 24

25 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 R R 1 R (2) : R R R R R 1 R 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 R x, y x, y R x, y R y, x R ( ) (R ) = x, y R y, x R (R R) x, y R x, y R 1 x, y R R 1 R R R 1 R R 1 R

26 (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 2.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 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

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

28 12, 0 S 0, 4 S 12, 4 / S M(R) = G(R) R 1, 1 R 1, 2 R 2, 1 R 1 2 2, 0 R 0, 3 R 2, 3 / R 2.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 28

29 a, c R 3 c, a R 3 a c 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 a a b c b c b c b c G(R 1 ) G(R 2 ) 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 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 29

30 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 1 ) = a b c d G(R 1 ) M(R 1 ) = M(R 2 ) = M(R 2 R 1 ) = M(R 1 ) M(R 2 ) = = R 2 R 1 = { 1, β } 2.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 R R = R (R R ) 2.23 : R S x, y x, y R S 30

31 = 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 ( ) 2.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 } 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 31

32 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 dom R R 1 R : x, y x, y I dom R x = y x dom R ( ) 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 ran R R R 1 : x, y x, y I ran R x = y x ran R ( ) 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 ( ) 2.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 32

33 N R 1 = { x, y x, y N y = x + 1} k N R1 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 ) dom R 2 ran(r 1 R 2 ) ran R 1 m N + dom(r1 m ) dom R 1 ran(r1 m ) ran R 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 dom R 2 y ran R 1 (dom ran ) dom(r 1 R 2 ) dom R 2 ran(r 1 R 2 ) ran R 1 R 2 = R 1 m m N +, dom(r1 m ) dom R 1 ran(r1 m ) ran R R 1, R 2 fld R 1 fld R 2 = m, n N + (R1 m R2 n = ) : R 1, R 2 ((fld R 1 fld R 2 = ) (R 1 R 2 = )) x, y (R 1 R 2 ) z( x, z R 2 z, y R 1 ) z ran R 2 fld R 2 z dom R 1 fld R 1 z fld R 1 fld R 2 R 1, R 2 ((fld R 1 fld R 2 = ) (R 1 R 2 = )) 2.1 dom(r1 m ) dom R 1 ran(r1 m ) ran R 1 fld(r1 m ) = dom(r1 m ) ran(r1 m ) (fld ) dom R 1 ran R 1 ( ) = fld R 1 (fld ) fld(r2 n ) fld R 2 fld(r1 m ) fld(r2 n ) fld R 1 fld R 2 ( 1.5) = ( ) R1 m R2 n = : m = 0 R 1 R 2 A (R 1 R 2 ) 0 = I A = I A I A ( ) = R1 0 R2 0 m = k (k N) (R 1 R 2 ) k = R1 k R2 k m = k + 1 (R 1 R 2 ) k+1 = (R 1 R 2 ) k (R 1 R 2 ) = (R1 k R2) k (R 1 R 2 ) ( ) = (R1 k R2) k R 1 (R1 k R2) k R 2 ( 2.6(1)) 33

34 2.28 m = 0, n = 15 3 = (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 ( ) 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) 2.30 (1) : R + = t(r) 2.19(3) (R + ) + = t(r + ) = R + (2) : 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 i=0 R i ( ) = 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 3 m, n(m n) m, n(m < n) m = n = 0 34

35 2.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) 2.32 : A = I A I B = P A Q A = P 1 B Q 1 B = P A P 1 A = P 1 B (P 1 ) 1 B = P A P T A = P 1 B (P T ) 1 = P 1 B (P 1 ) T 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 = Q P A (Q P ) 1 B = P A P T C = Q B Q T C = Q P A P T Q T = Q P A (Q P ) T 2.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 2.34 (1) 1 x < 0 4 sgn (signum) sgn(x) = 0 x = 0 1 x > 0 35

36 : 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 : 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 2.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 ( ) 36

37 = 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 m = ( ) k=1 B ik = π 2 π 2 π 2 A B 2.37 : 2.38 A/R = {{1, 6, 11, 16}, {2, 7, 12, 17}, {3, 8, 13, 18}, {4, 9, 14, 19}, {5, 10, 15, 20}} : (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 ) ( m ) ( n ) = A i B j (π 1, π 2 ) i=1 = 1 i m 1 j n j=1 (A i B j ) ( ) = A (A ) 37

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

39 2.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 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 ) (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 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 ) (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 ) 2.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 2.43 { } { } { } { } { } ( 5 = 1 + (2 4 1) { } { }) 4 + C = 1 + (2 4 1) + (3 C ) + C = = 52 39

40 (1) 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 2.46 B {k [1, 2,..., 10] k N + } [1, 2,..., 10] = B A B 1 = 1, 2, 6, 18, 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) 40

41 : 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 ( ) x, z R x, z B B x, z R B (R B ) R B (2) : R B x x 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 41

42 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) : (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 (R B ) R B (4) : (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 2.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) (R ) x, y, x, y / R (/ ) R x 1, x 2, x 3, y 1, y 2, y 3 42

43 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 2.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 (R ) x 1, x 2 R 1 x 2, x 1 R 1 y 1, y 2 R 2 y 2, y 1 R 2 ( ) = x 1 = x 2 y 1 = y 2 (R 1, R 2 ) x 1, y 1 = x 2, y 2 ( 2.1) x 1, y 1, x 2, y 2 = x 2, y 2, x 1, y 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 (R ) x 1, x 2 R 1 x 2, x 3 R 1 y 1, y 2 R 2 y 2, y 3 R 2 ( ) = 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

44 8, 6 8, 3 8, 2 4, , 1 4, 3 4, 2 2, , 1 2, 3 2, 2 1, R 1 R 2 2, 1 1, 3 1, 2 1, 1 R : 2.40 x, y X(x y R x R y ) R x R y x y R X A

45 3.1 R 2, R 3, R 6, R 7 A B R 2, R 6 A B 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 ) f g 2 f g A B f = g : 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 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) = dom f dom g ( 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 45

46 : 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.3 (1), (2), (6), (10) (1), (4), (5), (6), (9), (10) (1), (6), (10) 3.4 f = { S, F S, F A B x(x A (x S F (x) = 1))} f A B f 1 B A 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 = dom f (f A B) = B (f B A) 3.6 : f f C A x y z(x dom f y ran f z ran f xfy xfz y = z) dom f = C ran f A = x y z(x dom f y ran f z ran f xfy xfz y = z) dom f = C ran f B f C B (A B ) 46

47 3.7 ( 10 ) 3.2 f, g A B f g dom g dom f f = g : f g g f x, y x, y g = x dom g (dom ) = x dom f (dom g dom f) 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 / ran f ) k N 2k, k g g k N 2k, k g 2k + 1, k g 2k 2k + 1 g : 1 y(y dom g g(y) ) : y y dom g y B (dom g = B) = x(x A x, y f) (f ) x(x g(y)) 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 ) 47 (g ) ( ) ( )

48 = 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 3.12 : x R x, 0, x f x, 1, x g f, g 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 3.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 B(x B B A ) B(x B x B B A ) x, x R A x, y (A ) ( ) (R A ) x, y R A (2) 48

49 B(x B y B B A ) B(y B x B B A ) y, x R A x, y, z (R A ) ( ) (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 E R A f(r A ) = A f f 3.14 : S f f A (R 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 f, g (S ) f, g A g, f A x(x [0, 1] (f(x) g(x)) 0) x(x [0, 1] (g(x) f(x)) 0) (S ) 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) ( x [0, 1] (g(x) f(x)) 0)) x( x [0, 1] ((f(x) g(x)) 0 (g(x) f(x)) 0)) ( ) 2 (2) 49

50 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) (S ) 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) ( 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 3.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} 3.16 g f(x) = x f g(x) = x 2 + 4x + 14 f g, h 50

51 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) x = y (f ) (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) dom f = R {0} = (, 0) (0, + ) ran f = R {0} = (, 0) (0, + ) dom g = R ran g = {0} R + = R R = [0, + ) dom h = {0} R + = R R = [0, + ) ran h = {0} R + = R R = [0, + ) (2) dom f, dom g, dom h f, g, h 3.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 3.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 (2) : f g 3.5(1) f f f f f 1 f f 51

52 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) ) f(x) = a f(x) = a ( ) f(x) = a x, a f (f(x) ) f(x) = a x, a g (f = g) f(x) = a g(x) = a (g(x) ) 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 (f(x) ) g(x) = y (f(x) = g(x)) x, y g (g(x) ) x(x A f(x) = g(x)) f = g : f h 1 = g h dom(f h 1 ) = dom(g h 1 ) = dom h 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 52

53 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 3.22 f, g (X X)(h f = h g f = g) h : 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 ( 3.6) = h h f (h h ) = h h g (h f = h g) = I X g (h h ) = g ( 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 ( 3.6) = f h h (h h ) = g h h (h f = h g) = g I X (h h ) = g ( 3.6) f, g (X X) f h = g h f = g h

54 3.4 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.24 : 2.9(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 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) ( ) ( ) ( ) 54

55 4.1 (1) (2) (3) (4) a = 4.2 (1) 2 3 = 3; (2) 2 3 = 2; (3) 5 = 4; (4) 6 = 0; (5) 7 = 5; 4.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} : 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 4.5 : A x x A + x A {A} ( ) 55

56 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 + ( ) 4.10 A (1) : A x, x A y(y A x y) = y(y A x y) (y 4.10) = y(y A x y) = x A ( ) 4.10 A (2) : 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 ( ) 4.10 A 4.7 : S = {n n N m(m N m n h(m) = h(n))} 0 / S 0 S S h m N, m 0 56

57 h(m) = h(0) = a m ( 0 ) m n h(m) = h(n + ) = f(h(n)) = a a A ran f 0 / S 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 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 57

58 5.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 ) 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 5.2 (1) (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)

59 : 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] 5.4 : 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.5 : 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(y), y n ( f : x {n} m g : x m +, y x, g(y) = g m, y = n f ) 4.4 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 5.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 5.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 A A N 5.14 N A Schröder-Bernstein A N 59

60 : n = 2 A B κ = card A λ = card B κ ℵ 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) card P(A) ℵ ℵ 0 card A card P(A) ℵ 0 ℵ 0 card A ℵ 0 ℵ 0 card P(A) ℵ 0 Schröder-Bernstein card A = card P(A) = ℵ 0 A P(A) P(A) 5.11 (1) f : N A, x N, f(x) = (x + 1) 7 f card A = card N = ℵ 0 (2) f : N B, x N, f(x) = (x + 1) 109 f card B = card N = ℵ 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) = card N = ℵ 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) = card N = ℵ : 5.20 card P(A) = 2 card A, card P(B) = 2 card B 2 card A = 2 card B card A = card B 5.7 card A card B card B card A 5.22(4) 2 card A 2 card B 2 card B 2 card A Schröder-Bernstein 2 card A = 2 card B card P(A) = 2 card A = 2 card B = card P(B) 5.13 (1) 60

61 : n N S = {{{0}}, {1}, {2},..., {n 1}} card S = n, S N = {{0}}, x = 0 f : N S N, x N, f(x) = {x}, 0 < x < n x n, x n f n + ℵ 0 = card(s N) = card N = ℵ 0 (2) : 1 n N + S = {nm m N} f : N S, x N, f(x) = nx f S N g : (n S) N, x, y (n S), g( x, y ) = x + y g n S N n ℵ 0 = card(n S) = card N = ℵ 0 (3) : 5.1 N N N N N =, N N = N ℵ 0 + ℵ 0 = card(n N ) = card N = ℵ 0 (4) 5.1(2) 5.14 (1) : K κ card = 0, K =, K = K κ + 0 = card(k ) = card K = κ (2) : K κ K = κ 0 = card(k ) = card = 0 (3) : K κ card({ }) = 1, K K { } ( f : K K { }, x K, f(x) = x, ) κ 1 = card(k { }) = card K = κ (4) : K κ ( K) = { } κ 0 = card( K) = card({ }) = 1 (5) : K κ κ 0 K (K ) = κ 1 = card( K ) = card = 0 (6) : K 1, K 2 κ K 1 K 2 = K 1, f(x) x K 1 f : 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 1 n 0 card( N) = card = 0 ℵ 0 61

62 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) g(y) (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 κ (7) : K κ f : K ({ } K), x K, f(x) = {, x } f K ({ } K) κ 1 = card({ } K) = card K = κ (8) : n N card({n}) = 1, n {n} = n + 1 = card(n {n}) = card(n + ) = n + 62

63 6.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) 6.3 (1) : x, y A x y x, y y, x R x y x, y y, x R R I A x, y Cn 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 = Cn 2 = n(n 1)/2 6.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, 63

64 : 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 6.5 : 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.6 (1) F (0) = A ( ran(f (seg 0))) (γ ) = A ( {F (x) x seg 0}) ( ) = A ( ) (seg 0 = ) = A F (1) = A ( ran(f (seg 1))) (γ ) = A ( {F (x) x seg 1}) ( ) = A ( {F (0)}) (seg 1 = {0}) = A ( {A}) (F (0) = A) = A ( A) F (2) = A ( ran(f (seg 2))) (γ ) = A ( {F (x) x seg 2}) ( ) = A ( {F (0), F (1)}) (seg 2 = {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 + )))) (γ ) 64

65 = 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 + ) x N, x < n x S n + S N S = N n N F (n + ) = A ( F (n)) (2) : (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))) (3) : ran F = {F (0), F (1), F (2), } B = ran F = F (n) x B n N x F (n) (2) x F (n + ) F (n + ) ran F x F (n + ) ran F = B x B x B 4.10 B A = F (0) ran F A ran F = B 6.7 (1) : 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 6.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) (g ) 65 n N

66 I B g(x) B I B g(y) ( 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 : F a, b A a b 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 a b F (a) F (b) F A, S, 6.10 : α β α β 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)) ( 3.3) g 1 (x) 0 g 1 (y) (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 (α) α 1 F A, S, F A, S, 66

67 67

68 = 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 V (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) (b) G (a) G 0 G G : u v (u, v) xbz 68

69 G d n, d n 1,, d 2, d 1 1 d 1 1 d 1 < d 2 < < d n d i (i = 1, 2,, n) d n n G 7.5 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 ) a f a f b e b e c d c d G 1 G 2 : 6 2- G G v 1 V (G ) f(v 1 ) = a v 1 ( G 2 ) b, c, d, e, f G = G 1 G G 2 3 V (G) = 6 G K G = G G 1 G G 1 G (1) (2) 69

70 a f a f a f b e b e b e c d c d c d G 1 G (1) G (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) 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 7.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 70

71 G 1 G 11 K 4 G 6, G 18, G 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 G 5, G 6, G 7 5 ( G i = Gj = Gk G i = Gj G k = Gm i, j, k, m 5 ) 71

72 7.11 : 2 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 d(v) v G G u, v, w V (G)((u, v), (v, w) E(G) (u, w) E(G)) ( ) ( ) : (u, v V (G), u v u v (u, v) E(G)) Γ = w 0 w 1 w k 1 w k u v ( w 0 = u w k = v) (u, v) / E(G) k 2 u, v, w V (G)((u, v), (v, w) E(G) = (u, w) E(G)) (w 0, w 1 ), (w 1, w 2 ) E(G) (w 0, w 2 ) E(G) Γ = w 0 w 2 w k 1 w k : G 7.4 G 7.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) : Γ = v 0, v 1,..., v l Γ v 0 Γ δ(g) 3 v 1 v i, v j (2 i < j l) v 0 2 G G 9 3 G 7 2 G 18 72

73 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 : G κ(g) = (1) n 2 δ(g) < n 2 2n 4 < n n < 4 G p(g) 2 G G 2 2 n 2p(G) 4 n < 4 G δ(g) = κ(g) = 0 G δ(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) = δ(g) = n (1) : v V (G) v d(v) + 1 δ(g) + 1 G G p(g) = k 2 V 1, V 2,, V k k V (G) = V i ( V (G) ) i=1 k(δ(g) + 1) ( V i δ(g) + 1) k( n 2 + 1) ( ) 2( n 2 + 1) (k 2 n ) = n + 2 > n k = 1 G (2) : V 1 G t = V 1 1 G G G δ(g V 1 ) δ(g) V 1 n + k 1 2 G V 1 (1) δ(g V 1 ) < V (G V 1) = n t 2 2 n + k 1 2 t < n t 2 t > k 1 t k G k- t 73

74 (1) : v 1 V (G) v 2 N G (v 1 ) 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 7.20 : v G (G) = n 2 G v u d(g) = 2 G u v ( u v ) V (G) {u, v} v u G = G v G ( V (G ) {u} u ) 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 (v) G 7.18 G x = E(G) + p(g) = E(G ) + p(g ) G = G v v G p(g ) = p(g ) 1 E(G ) = E(G ) V (G ) = i E(G ) = i p(g ) x = E(G )

75 p(g ) = E(G ) + p(g ) + 1 = i + 1 E(G) = (i + 1) p(g) n = i + 1 : G G 7.5 G n 1 m < n m n G 7.22 : 2 K 2 3 B 7.20 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 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 7.23 n = 4r, δ = s, λ = r, κ = (1) 7.24 (1) 7.12 G G (2) 7.12 (3) : 6 v K n 6 H H = K 6 (1) H K 3 K 3 K 3 K 3 3 v 1 K : 7.4 D D D 75

76 8.1 : G C = e i1 e i2 e im G C e E(G) 1 k m e ik = e C e ik Γ = e ik+1 e im e i1 e ik 1 G e G e e λ(g) 2 G G B = {B 1, B 2,, B k } G V i = V (B i ) E i = E(B i ) i = 1, 2,, k B i, B j B B i B j G (1) B i = G[V i ] (2) V i V j (3) V i V j 1 (4) G 2 H = V, E H H (5) E i E j = {(v, v) v V i V j (v, v) E(G)} (6) G = B : (1) (2) V i V j (1) B i = G[V i ] G[V j ] = B j B i B j B i B j B j B i 2- B i (3) v 1, v 2 V i V j v 1 v 2 u V i {v 1, v 2 } w V j {v 1, v 2 } u w v 1 Γ 1 u w v 2 Γ ( 7.20 V i 3 V j 3 V i 2 V i V j 2 V i = V i V j V j (2) ) B i u v 2 v 1 B j v 2 w v 1 Γ 1 Γ 2 B i B j 2- ( B i B j B i B j v 1 v 2 B i B j B i B j ) (2) V i V j V i V j ( 1.32 (2) V i V j = V i V j V i V i V j = V j V i V j (2) ) B i B j B i B j 2- B i, B j (4) H H G[V ] v V (G) V G[V {v}] v V v G[V ] G H G[V ] B s = G[V ] 76

77 B t B B t B s H B s B t V (H) 2 V (B s ) V (B t ) 2 (3) H (5) e = (x, y) E i E j x, y V i V j (3) V i V j 1 x = y e = (x, x) v V i V j (1) (v, v) E(G) (v, v) E i E j (6) B G G B G B e = (u, v) E(G) u v (u, v) H = G[{(u, v)} 2 (4) H G B s e E(B s ) E( B) V (G) V ( B) G G v B v B V (G) V ( B) G B (v, v) E(G) G v V ( B) B s B v V (B s ) (1) (v, v) E(B s ) E( B) G B G = B : G k B 1, B 2,, B k G 8.1 G B i S i = {C i1, C i2,, C ini } B i = S i S = n S i 8.1(6) G = S S i=1 C ij, C st S C ij C st S i = s C ij C st i s 8.1(5) C (x, x) C C = (x, x) ( x C ) C ij C st e e = (x, x) C ij = C st = G[{e}] C ij C st G = S 8.1 G G 8.1 G S = {C 1, C 2, C r } B i G S i = {C j C j S E(C j ) E(B i ) } S i B i = S i B i S i B i e E(B i ) C j ( G = S) C j S i e E(C j ) E( S i ) E(B i ) S i B i v e E(B i ) E( S i ) v V ( S i ) V (B i ) V ( S i ) B i S i S i B i C j S i C j B i S i e = (u, v) E(C j ) E(B i ) e ( e C j = e C j B i e E(B i ) {e} = C j B i ) u v 8.1(6) C j B s ( B s B i ) (u, v) E(B i ) E(B s ) u, v V (B i ) V (B s ) 8.1(3) B i = S i B i 8.1 G 77

78 8.3 : 2k v 1, v 2,, v 2k E = {(v 2i 1, v 2i ) i = 1, 2,, k} G = G E G 8.1 G C C E C k ( E C k ) t P 1, P 2,, P t t E(G) = t i=1 (1 t k) E(P i ) P i n i 1 s n i P i s ( P i s 1 s 1 n s + 1 s ) t s(t s m) m G G G 2k k 1 m n 1 2k 1 k t k P 1, P 2,, P k E(G) = k E(P i ) G G 1 = G[V 1 ] G v V 1 d G1 (v) = d G (v) : E(G 1 ) E(G) d G1 (v) d G (v) d G1 (v) < d G (v) (u, v) E(G) (u, v) / E(G 1 ) u v v V 1 u V 1 G 1 = G[V 1 ] V 1 (u, v) E(G 1 ) : G v 0 v 0 G 8.1 G G v 0 C 0 G = G E(C 0 ) 2 v i V (G) v i V (C 0 ) v i G d G (v i ) = d G (v i ) 2 v i / V (C 0 ) d G (v i ) = d G (v i ) G v 0 / V (C 0 ) d G (v 0 ) = d G (v 0 ) > 0 G 1 v 0 G 8.2 G G 1 C 1 G 1 C 1 v 0 G v 0 C 1 C 1 v 0 G ( C 0 ) C 1 G v 0 v 0 G v 0 v 0 v 0 ( v 0 v i v 0 v 0 v i Γ v i t t 1 v i Γ 2 v i Γ 1 v i Γ E(G) v i ) C G = G E(C) G G 1 G 8.2 G G 1 ( C 1, C 2, C k ) C 1 v 0 C 1 ( v 0 G ) C 1 G v 0 i=1 78