Złożenie relacji

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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.

Definicja[edytuj | edytuj kod]

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

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

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\circ R)\ z   wtedy i tylko wtedy, gdy dla pewnego y zachodzi   x\,R\,y\,S\,z

Przykład[edytuj | edytuj kod]

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

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

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

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

Własności[edytuj | edytuj kod]

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

Zobacz też[edytuj | edytuj kod]

Półgrupa relacji binarnych