Изменения
→Степень отношений
<tex>\forall a \in A, c \in C : a (R \circ S) c \iff \exists b \in B : (a R b) \wedge (b S c) </tex>.
}}
Примером такого отношения может служить отношение на некотором множестве <tex>A</tex> населенных пунктов <tex>R\subseteq A\times A</tex> {{- --}} отношение "можно доехать на поезде", а <tex>S\subseteq A\times A</tex> {{--- }} отношение "можно доехать на автобусе". Тогда отношение <tex>R\circ S\subseteq A\times A</tex> {{--- }} отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)".
== Степень отношений ==
{{Определение
|definition=
'''Степень отношения''' (англ. ''power of relation'') <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:
* <tex> R^{n} = R^{n-1} \circ R; </tex>
В связи с этим понятием, также вводятся обозначения:
<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </tex>— [[Транзитивное замыкание]] (англ. ''transitive closure'') отношения <tex>R</tex>;
<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> — [[Транзитивное Транзитивно-рефлексивное замыкание]] отношения <tex>R</tex>
== Обратное отношение ==
Отношение <tex>R^{-1} \subseteq B\times A</tex> называют '''обратным''' (англ. ''inverse relation'') для отношения <tex> R \subseteq A\times B</tex>, если:
<tex> aRbR^{-1}b a \iff bRa aRb </tex>
}}
{{Определение
|definition=
'''Ядром отношения''' (англ. ''kernel of relation'') <tex>R </tex> называется отношение <tex> R\circ R^{-1} </tex>
}}
== Свойства ==
Композиция отношений обладает следующими свойствами:
* Ядро отношения <tex> R </tex> [[Симметричное отношение|симметрично]]: <tex>a (R \circ R^{-1}) b \iff b (R \circ R^{-1})a </tex>
* Композиция отношений [[Ассоциативная операция|ассоциативна]]: <tex> (R \circ S) \circ T = R \circ (S \circ T) </tex>
* Ядро Обратное отношение для отношения , являющемуся обратным к <tex> R [[Симметричное отношение|симметрично]]:</tex> есть само <tex> a (R \circ R^{-1}) b \iff \exists c: </tex> <tex> (a R c) \wedge (c R^{-1} b) \iff \exists c: (b R c) \wedge (c R^{-1} a) \iff b (= R \circ R^{-1} ) a</tex>
* Обратное отношение к композиции отношений <tex>R </tex> и <tex>S </tex> есть композиция отношений, обратных к <tex>R </tex> и <tex>S : </tex> <tex> (R\circ S) ^ {-1} = (S ^{-1})\circ (R ^{-1} = R ) </tex>
* Обратное отношение к объединению отношений <tex>R </tex> и <tex>S </tex> есть объединение отношений, обратных к <tex>R </tex> и <tex>S : </tex> <tex> (R \circ cup S) \circ T ^ {-1} = (R ^{-1}) \circ cup (S \circ T^{-1}) </tex>
* Обратное отношение к пересечению отношений <tex>R </tex> и <tex>S </tex> есть пересечение отношений, обратных к <tex>R </tex> и <tex>S : </tex> <tex> (R \circ cap S) ^ {-1} = (S R^ {-1}) \circ cap (R S^ {-1}) </tex>
== См. также ==* <tex> (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) </tex>[[Бинарное_отношение|Бинарное отношение]]* [[Транзитивное_замыкание|Транзитивное замыкание]]
==Источники информации==* <tex> (R \cap S) ^ Новиков Ф. А. {{-1--} = (R^} Дискретная математика для программистов: Учебник для вузов. 3-е изд. {{---}} СПБ.: Питер, 2009 {{-1--}}) \cap (S^52 с.* [http://en.wikipedia.org/wiki/Composition_of_relations Wikipedia {{-1--}) <} Composition of relations]* [http:/tex>/math2.uncc.edu/~hbreiter/m1165/Lecture10.pdf UNC Charlotte {{---}} Lectures in Discrete Mathematics: Composition of Relations and Directed Graphs.]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Отношения ]]
