c .
.
5.
, , , , , , , , , - , .
, :
;
;
;
;
, , , ;
- ;
, .
5.1.
, X, Y , G Í X ´ Y, . , , G, D .. () = < G, X, Y >, G, X Y.
= < G, X, Y >, G Í X ´ Y .
, Y .
: , , . X Y.
:
G Í X ´ Y G = X ´ Y Ú G Ì X ´Y.
( G , 1G), - ( , 2G).
R , n x m, X, - Y, ri , j :
ri , j = 1 - < xi, yj > Î F;
ri , j = 0, .
, :
, , . 5.1. , , X Y = < X, Y, F >, < xi, yj >, F, , xi yj.
. 5.1.
, F = X ´ Y, . , F = Æ, Æ.
|
|
= < G, X, Y > G = {< a, b >}, X = {a}, Y = {b}. , (b) (a). Î1G, a. bÎ2G .
X = Y, . , . .
:
5.1. = < {< a, a >, < b, b >, < c, a >}, X = {a, b, c}, Y = {a, b} >. . 5.2 .
. 5.2.
5.2. = <G, X, Y>, = {1, 2, 3}, Y = {4, 5} G = {<1,4>; <1,5>; <2, 4>; <2,5>; <3,4>; <3,5>}. 1G = {1, 2, 3}, 2G = {4, 5}. , X ´ Y, .. G = X ´ Y.
5.3. A, B, C. . X, Y, Z, X . . M , N = <G, M, N>.
M = {X, Y, Z }, N = {A, B, C}, G = {<Y, B>, <Z, A>}. G Í M ´ N. . 5.3 .
. 5.3. = < G, M, N >
5.4. <Æ, Æ, Æ> - .
, G Í X ´ Y G-1 Í Y ´ X, <G, X, Y> , <G-1, Y, X> .
5.2.
, , .. , , , , .
= <X, Y, F> D = <W, Z, P> : = <X È W, Y È Z, F È P>.
D : = <X Ç W, Y Ç Z, F Ç P>.
D : = <X \ W, Y \ Z, F \ P>.
-1, , Y -1; X -1, F -1 F .
1 = <X, Y, F> 2 = <W, Z, P> , , 1, - 2, - FP: 1 2 = <X, Z, F P>.
, Y Ç W = Æ, .
W , W W.
|
|
, . (-1)-1 = , ((-1)-1)-1 = -1. -1 = , G = G-1, . , = <G, X, X>, = {1, 2, 3}, G = {< 1, 1 >, < 2, 2 >}. . 5.4 .
. 5.4.
, . . , y ÎY & y Î Z. 1 = <G, X, Y>, 2 = <H, Z, U>. 12 = <GH, X, U> - .
, = {a, b}, Y = {c, d}, Z = {d,e}, U = <k, l>. Z Y.
G = { < a, c >, < b, d > }, H = { < d,k >, < d,e >, < e,k > }. GH = { < b, k >, < b, e > } 12 = < {< b, k >, < b, e >}, X, U >. 1 2 . 5.5.
. 5.5.
:
(12)3 = 1(23).
.
1) . ,
<a, b> Î (12)3 <a, x> Î 12 Ù <x, b> Î 3 <a, x1> Î 1 Ù <x1, x> Î 2 Ù <x, b> Î 3 <a, x1> Î 1 Ù <x1, b> Î 23 <a, b> Î 1(23).
.
2) , .. .
<a, b> Î 1(23) <a, x> Î 1 Ù <x, b> Î 23 <a, x> Î 1 Ù <x, z> Î 2 Ù <z, b> Î 3 <a, x> Î 1 Ù <x, z> Î 2 Ù <z, b> Î 3 <a, z> Î 12 Ù <z, b> Î 3 <a, b> Î (12)3, . , .
:
5.5. 1 = <X, Y, F>;X = {1, 2, 3}; Y = {a, b, c, d}; F = {<1, a>; <1, c>; <2, b>; <2, c>; <3, d>}; 2 = <W, Z, P>; W = {2, 4, 5, 6}; Z = {a, c, d, e}; P = {<2, a>; <2, e>; <4, a>; <4, d>; <5, c>; <5, e>; <6, c>; <6, d>}. , .
: , D, . 5.6, - .
. 5.6, -. , 1 2
5.6. 1 2, , 2 1 2-1.
: 2 .5.7, 1 2-1 - .5.8.
. 5.7. 2
. 5.8. 1 2-1
5.3.
.
= <G, X, Y> Í . Y, . () = { y ÎY/$ x ÎA, < x, y >ÎG} .
. = < G, X, Y >, X = {1, 2, 3}, Y = {a, b, c}, G = {<1, a>, <1, b>, < 2, c >, < 3, b >, < 3, a >} A Í X, A = {1, 3}. () = {a, b} (.5.9).
|
|
() , . :
() = 2[(A ´ Y) Ç G].
1 2 ,
(12)() = 2(1()).
.5.9.
= <G, X, Y> , - . -1() . -1() = { x ÎX/$ y Î, < x, y >ÎG }} .
:
-1() = 1[GÇ(X ´ )].
, G.
5.7. = < G, X, Y > = <{ < 1, a >, < 1, b >, < 1, c >, < 2, a > }, { 1, 2 }, { a, b, c }>, Í Y, = { a, c }. - -1() = { 1, 2 } (.5.10).
. 5.10.
. , Í . :
B = < GÇ(B ´ Y), X, Y >.
. = < G, X, Y >, X = { 1, 2 }, Y = { a, b, c }, G = { <1, a>, <1, b>, < 1, c >, < 2, b >, < 2, > }, = { 1 }. B ´ Y = { < 1, a >, < 1, b >, < 1, c > } B B = <G Ç (B ´ Y), X, Y> = <{ < 1, a >, < 1, b >, < 1, c > }, {1, 2}, {a, b, c}>. (.5.11).
. 5.11.
. = <G, X, Y> W = <H, Z, U>, G Í H, Z = X, U = Y. W . , b, a , W, .
b a.
5.8. = < G, X, Y >, X = {1, 2, 3}, Y = {a, b, c, d}, G = {<1, a>, <1, b>, <2, c>, <3, d>} W = < H, Z, U >, X = {1, 2, 3}, Y = {a, b, c, d}, H = {<1, a>, <1, b>, <2, b>, <2, c>, <3, a>, <3, d>}. W . . 5.12 , .5.13 - W.
. 5.12.
. 5.13. W ( )
:
5.9. = <X, Y, F>; X = {1, 2, 3}; Y = {a, b, c, d}; F = {<1, a>; <1, c>; <2, b>; <2, c>; <3, d>}. 1 Î X = {1,2} .
: 1 (1) = {a, c}. A : (A) = {a, b, c}.
5.10. a Î Y B = {a, b, c}.
|
|
: a -1(a) = {1}. B = {a, b, c} -1(B) = {1, 2}.
5.4.
= <X, Y, F>, , :
(A È B) = (A) È (B);
(A Ç B) Í (A) Ç (B);
(A \ B) Í (A) \ (B);
-1(A È B) = -1(A) È -1(B);
-1(A Ç B) Í -1(A) Ç -1(B);
-1(A \ B) Í -1(A) \ -1(B).
, , , .
, = <X, Y, F> , A Í X, Í Y. :
(A È B) = (A) È (B).
: . , (A È B) Í (A) È (B)., . y, :
yÎ(A È B) yÎ2(((A È B) ´ Y) Ç F)
( )
($xÎX)(<x, y>Î(((A È B) ´ Y) Ç F))
( )
<x, y>Î((A È B) ´ Y) & <x, y>ÎF
( )
xÎ(A È B) & yÎY & <x, y>ÎF
( )
(xÎA Ú xÎB) & yÎY & <x, y>ÎF
( )
xÎA & yÎY & <x, y>ÎF Ú xÎB & yÎY & <x, y>ÎF
( )
<x, y>Î(A ´ Y) & <x, y>ÎF Ú <x, y>Î(B ´ Y) & <x, y>ÎF
<x, y>Î((A ´ Y) Ç F) Ú <x, y>Î((B ´ Y) Ç F)
<x, y>Î[((A ´ Y) Ç F) È ((B ´ Y) Ç F)]
yÎ2[((A ´ Y) Ç F) È ((B ´ Y) Ç F)] yÎ(A) È (B).
, .
:
(A) È (B) Í (A È B).
, :
yÎ(A) È (B) yÎ (A) Ú yÎ(B)
yÎ2((A ´ Y) Ç F) Ú yÎ2((B ´ Y) Ç F)
($xiÎX)(<xi, y>Î((A ´ Y) Ç F) Ú ($xjÎX)(<xj, y>Î((B ´ Y) Ç F)
(, , xi xj ))
(<xi, y>Î(A ´ Y) & <xi, y>ÎF) Ú (<xj, y>Î(B ´ Y) & < xj, y>ÎF)
(xiÎA & yÎY & <xi, y>ÎF) Ú (xjÎB & yÎY & < xj, y>ÎF)
((xiÎA Ú xjÎB) & yÎY & <xi, y>ÎF) Ú ((xiÎA Ú xjÎB) & yÎY & <xj, y>ÎF)
( )
((xÎ(A È B) & yÎY & <x, y>ÎF)
( )
<x, y>Î((A È B) ´ Y) & <x, y>ÎF <x, y>Î(((A È B) ´ Y) Ç F)
yÎ2(((A È B) ´ Y) Ç F) yÎ(A È B).
, .
, .
5.5.
, G . G , . , . . 5.14 - 5.16 . 5.17 - .
. 5.14.
. 5.15.
. 5.16.
|
|
. 5.17.
, = <G, X, Y> ,
("xÎX, "y1, y2ÎY) [< x, y1 >Î G Ù < x, y2 >Î G y1=y2].
, . G , . .5.18, 5.19 . .5.20 .
. 5.18.
. 5.19.
. 5.20.
, , , .5.16 5.19.
, :
("x1, x2 ÎX, "yÎY) [< x1, y >Î G Ù < x2, y >Î G x1 = x2],
= <G, X, Y> , . , = < G, X, Y > = < {<1,2>, <3,2>, <4,5>}; {1, 3, 4}; {2, 5}>. X = {1, 3, 4} . . 5.21 .
. 5.21.
:
1G = X.
:
("x)($y)[< x, y >ÎG].
= <G, X, Y> , . , = <G, X, Y> = < {<1,b>, <2, a>}; {1, 2, 3}; {a, b}>. X = {a, b} . . 5.22 .
. 5.22.
:
2G = Y.
:
("y)($x)[< x, y >ÎG].
= <G, X, Y> , , , , . . 5.23 5.25 - () , .5.26 , .
. 5.23. -
. 5.24. -
. 5.25. -
. 5.26.
. X Y
G: XY.
G X Y , .
G: X.
. = {a1, a2, b1, b2} , . 1 = {a1-2, 1, a1-2, 2, b1-2, 1, b1-2, 2, b1-2, 3} , a, b. 2 = {ab2-1, 1, ab2-1, 2} . , .5.27.
, .
. 5.27.
T = {(x, y): x y}. T : <, >; <, >; <, >; <, >.
Q = {(x, y): x y}. Q : <, >.
, X Y - , , G Í X ´ Y, < G, X, Y > .
:
5.11. , .
. = < X, Y, F > , x Î - (x) , .. . . , x Î X Y, .
.5.28, - , .
.5.28. ,
5.12. , .
. = < X, Y, F > , -1(y) y Î Y X, .. .
.
.5.29, - , .
ࠠ
. 5.29. ,
5.13. , , .
. = < X, Y, F > , x Î X (x) , .. x Î X . . = < X, Y, F > , y Î Y -1(y) , .. y Î Y . .
, .5.28(,,), 5.29(,,), . .5.30, 5.31.
.5.30.
.5.31.
5.14. - .
: , , , . .5.32.
. 5.32. -
- . , . . . 5.32 - :
a 1, b 2, c 3, d 4.
5.15. X = { x 1, x 2, x 3, x 4, x 5 }. - X. - .
: X t:
,
x 1 x 4, x 2 x 3, x 3 x 1, x 4 x 5, x 5 x 5.
5.6.
. XIX .
, .. . F = < , X, Y >, .
X Y , Y. , xÎX <x, y>. .
, 3, .
.5.33 X = {a, b, c, d} Y = {1, 2, 3}, {<a, 1>, <b, 1>, <c, 1>, <d, 3>}.
.5.33. Y
F = < , X, Y >,
, Í X x Y.
, , :
F
XY F: XY.
, < a, b >ÎF, , b. , (F(a)) F(a)=b.
F ,
= DX & X=Y,
DX X ´ X.
F , bÎY, = X ´ {b}.
F ,
("xÎX)[$F(x)].
.
F , , .
: . . :
F-1 F, .. F-1 = <-1, Y, X> . .
F-1 F , F .
F1 F2
(F1F2)(x) = F2(F1(x)).
. F-1.
3 F-1.
1. F-1 .
2. FF-1 1F.
3. F-1F 2F.
. f: X Y , X Y . , |X| > |Y|, f . , :
, Y , || = 12, |Y| = 11, 12 11 , .
1. .
2. = (, Æ, F)?