Wikipedia

Złożenie relacji: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
Konradek (dyskusja | edycje)
12 936 edycji
m drobne redakcyjne
Linia 1:
{{spis treści}}
'''Złożenie relacji binarnychdwuargumentowych''' – pewnaszczególna konstrukcja [[relacja dwuargumentowa|relacji dwuargumentowych]] binarna zdefiniowana za pomocąz dwóch innych relacji dwuargumentowych, a zarazem wynik tej konstrukcji. Przypadkiem szczególnym złożenia relacji jest [[złożenie funkcji]].
 
== Definicja ==
Niech <math>A, B, C</math> będą zbiorami orazustalonego [[uniwersum (matematyka)|uniwersum]], zaś <math>R \subseteq A \times B,</math>&nbsp;&nbsp; oraz <math>S \subseteq B \times C.</math> będą określonymi na tych zbiorach relacjami.
 
'''Złożenie''' relacji <math>S, R</math> to relacja <math>S \circ R</math> definiujemydana następująco:jako
: <math>S\circ R = \leftbigl\{(xa,zc)\in A \times C \midcolon \,\exists_{yb\in B}\,x; a \, R \,y b \,;\text{ oraz }\wedge; b \,y\, S \,z c\rightbigr\}</math>,▼
a więc
: <math>xa \ (S \circ R) \ zc</math> &nbsp;&nbsp;wtedy i tylko wtedy, gdy dla pewnego <math>yb</math> zachodzi &nbsp;&nbsp;<math>xa \, R \,y b \, S \,z c</math>.▼
 
== Przykłady ==
▲: <math>S\circ R = \left\{(x,z)\in A\times C \mid \,\exists_{y\in B}\,x\,R\,y\, \wedge \,y\,S\,z\right\}</math>
 
Można to zapisać symbolicznie:
▲: <math>x \ (S\circ R)\ z</math> &nbsp;&nbsp;wtedy i tylko wtedy, gdy dla pewnego <math>y</math> zachodzi &nbsp;&nbsp;<math>x\,R\,y\,S\,z</math>
 
=== Przykład ===
Niech <math>R</math> i <math>S</math> będą takimi relacjami w zbiorze <math>\mathbb{N},</math> że:
: <math>R=\{(2,1),(3,1),(4,2),(4,5),(5,3)\}</math>
Linia 20 ⟶ 19:
 
== Własności ==
{{zobacz też|relacja dwuargumentowa|o1=własności relacji dwuargumentowych}}
* Operacja złożenia relacji jest [[łączność (matematyka)|łączna]], tj.: <math>S\circ (R\circ T) = (S\circ R)\circ T.</math>▼
* Operacja złożenia relacji nie jest [[Przemiennośćłączność (matematyka)|przemiennałączna]], tj.: nie dla wszystkich relacji <math>S</math> i <math>R</math> zachodzi <math>S\circ R = R\circ S.</math>
▲* Operacja złożenia relacji jest [[łączność (matematyka)|łączna]], tj.: <math>S\circ (R \circ T) = (S \circ R)\circ T.</math>
* Jeśli relacje <math>R</math> i <math>S</math> są [[Funkcja różnowartościowa|iniekcją]], to złożenie relacji <math>S\circ R</math> również jest iniekcją. W odwrocie iniekcja <math>S\circ R</math> implikuje jedynie iniekcję <math>R.</math>▼
* Operacja złożenia relacji nie jest [[Przemienność|przemienna]],
* Jeśli relacje <math>R</math> i <math>S</math> są [[Funkcja „na”|surjekcją]], to złożenie relacji <math>S\circ R</math> również jest surjekcją. W odwrocie surjekcja <math>S\circ R</math> implikuje jedynie surjekcję <math>S.</math>▼
*: istnieją relacje <math>S</math> i <math>R</math>, dla których <math>S \circ R \ne R \circ S.</math>
▲* Jeśli relacje <math>R</math> i <math>S</math> są [[Funkcjajednoznaczne różnowartościowa|iniekcją]]lewostronnie (iniektywne), to złożenie relacji <math>S \circ R</math> również jest iniekcjąjednoznaczne lewostronnie (iniektywne). W odwrociedrugą iniekcjastronę jednoznaczność lewostronna (iniektywność) <math>S \circ R</math> implikujepociąga jedynie iniekcjęjednoznaczność lewostronną (iniektywność) <math>R.</math>
▲* Jeśli relacje <math>R</math> i <math>S</math> są [[Funkcjacałkowite „na”|surjekcją]]prawostronnie (surjektywne), to złożenie relacji <math>S \circ R</math> również jest surjekcjącałkowite prawostronnie (surjektywne). WOdwrotnie odwrociecałkowitość surjekcjaprawostronna (surjektywność) <math>S \circ R</math> implikujepociąga tylko całkowitość jedynieprawostronną surjekcję(surjektywność) <math>S.</math>
 
== Zobacz też ==
* [[półgrupa relacji binarnych|półgrupa relacji dwuargumentowych]]
 
[[Kategoria:Relacje]]
Źródło: „https://pl.wikipedia.org/wiki/Złożenie_relacji”