Złożenie relacji


Złożenie relacji w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Złożenie relacji binarnych – pewna relacja binarna zdefiniowana za pomocą dwóch innych relacji. Przypadkiem szczególnym złożenia relacji jest złożenie funkcji.

Spis treści

Definicja | edytuj kod

Niech A , B , C {\displaystyle A,B,C} będą zbiorami oraz R A × B , {\displaystyle R\subseteq A\times B,}    S B × C . {\displaystyle S\subseteq B\times C.}

Złożenie relacji S , R {\displaystyle S,R} definiujemy następująco:

S R = { ( x , z ) A × C y B x R y y S z } {\displaystyle S\circ R=\left\{(x,z)\in A\times C\mid \,\exists _{y\in B}\,x\,R\,y\,\wedge \,y\,S\,z\right\}}

Można to zapisać symbolicznie:

x   ( S R )   z {\displaystyle x\ (S\circ R)\ z}   wtedy i tylko wtedy, gdy dla pewnego y {\displaystyle y} zachodzi    x R y S z {\displaystyle x\,R\,y\,S\,z}

Przykład | edytuj kod

Niech R {\displaystyle R} i S {\displaystyle S} będą takimi relacjami w zbiorze N , {\displaystyle \mathbb {N} ,} że:

R = { ( 2 , 1 ) , ( 3 , 1 ) , ( 4 , 2 ) , ( 4 , 5 ) , ( 5 , 3 ) } {\displaystyle R=\{(2,1),(3,1),(4,2),(4,5),(5,3)\}} S = { ( 1 , 3 ) , ( 4 , 1 ) , ( 3 , 6 ) , ( 6 , 8 ) , ( 6 , 7 ) } {\displaystyle S=\{(1,3),(4,1),(3,6),(6,8),(6,7)\}}

Wtedy odpowiednio złożeniem relacji będą:

S R = { ( 2 , 3 ) , ( 3 , 3 ) , ( 5 , 6 ) } {\displaystyle S\circ R=\{(2,3),(3,3),(5,6)\}} R S = { ( 1 , 1 ) } {\displaystyle R\circ S=\{(1,1)\}}

Własności | edytuj kod

  • Operacja złożenia relacji jest łączna, tj.: S ( R T ) = ( S R ) T . {\displaystyle S\circ (R\circ T)=(S\circ R)\circ T.}
  • Operacja złożenia relacji nie jest przemienna, tj.: nie dla wszystkich relacji S {\displaystyle S} i R {\displaystyle R} zachodzi S R = R S . {\displaystyle S\circ R=R\circ S.}
  • Jeśli relacje R {\displaystyle R} i S {\displaystyle S} iniekcją, to złożenie relacji S R {\displaystyle S\circ R} również jest iniekcją. W odwrocie iniekcja S R {\displaystyle S\circ R} implikuje jedynie iniekcję R . {\displaystyle R.}
  • Jeśli relacje R {\displaystyle R} i S {\displaystyle S} surjekcją, to złożenie relacji S R {\displaystyle S\circ R} również jest surjekcją. W odwrocie surjekcja S R {\displaystyle S\circ R} implikuje jedynie surjekcję S . {\displaystyle S.}

Zobacz też | edytuj kod

Na podstawie artykułu: "Złożenie relacji" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy