22954

Relacje

1. Relacja

>    Niech; X_v X₂,..., X_n- dowolne zbiory

Wtedy: Każdy podzbiór R: R c: X, x X₂ x...x X_n nazywamy n - argumentową relacją w iloczynie kartezjańskim X,x X₂x...x X_B

>    Dowolny podzbiór zbiom: XxY

Z Dziedzina i przeciwdziedzina relacji

Niech: Re XxY

>    Dziedzina relacji R: D_R :=| xe X : 3^ : ( x,y) € R}

>    Przeciwdziedzina relacji R: D_R ^:={ y£ Y ^:    :( x,y) € R}

3.    Relacja odwrotna

Niech: ReXxY

>    Relacją odwrotną do relacji R nazywamy relację R~^l taka że: R ' = {(y» *): ( *> y) e R} c Y x X

>    Twierdzenie 1: D_Rl = D_R

dowód: y- dowolny: ye D_R_, <=>3 _KX:\y,x)eR^l <=> 3^* :(x,y) c R <=* ye D'_R >*■ Twierdzenie 2: D_Rt=D_R

dowód: x - dowolny: xe D* , «3_JtV:(y,x)cR‘¹ «3^:(x,y|cR«xe D_R Twierdzenie 3: ( R ¹) =R

dowód: ( x, y) € (R’¹) ‘ <=> 3_W *3^: (y, x) e R ¹ <=>3_wX3_y6ł. :(x,y|eR«(x,y)e R

4.    Złożenie relacji

Niech: ReXxY\ SeWxZ

>    Złożeniem relacji R z relacją S nazywamy relację S OR taka że:

S0R={(x,z):3^_ynH.:(x,y)e RA(y.z)eS) cXxZ

>    Jeżeli Y Pi W = 0 => S OR = 0

>    Twierdzenie 1: D_sateD_R dowód: x - dowolny:

xe D_M,»3_Jl!:(x₁z)eSOR»3₁,j3_)>M:(*j|6RA(jr,z)6S=>3₎„:(x,y|€ fi<=>xe D„

>    Twierdzenie 2: D*_sd(eD*_s dowód: y - dowolny:

^ztD‘_s«<*3_mX:{x,z)eSOR<*3_KX:3_y,_rnW:{x,y)eR*{y,z)eS=>3_yeY:{y,z)eSt* ze D‘_s

>    Twierdzenie 3: (SOR) ¹ =R^_IOS ¹ dowód:

(z,x)e(SOR) ¹ <=>(x,z)e SOR <=> 3^_ynfcr: (x, y) € RA(y,z)eSo <=> lyemw : (y. X) € R-¹ A(z,y) e S¹ <=> 3^_VnU.:(z,y) € S'¹ a(y,x) e R ¹ «•

<=* (z, x) e R ¹ OS'¹