Изменения

'''Композицией''' (произведением, суперпозицией) бинарных отношений (англ. ''composition of binary relations'') <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:

<tex>\forall a \in A, c \in C : a (R \circ S) c \Leftrightarrow 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> - отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)". ==Степень отношений==

'''Степень отношения''' (англ. ''power of relation'') <tex>R^{n} \subseteq A\times A</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 \Leftrightarrow bRa iff aRb </tex>

'''Ядром отношения''' (англ. ''kernel of relation'') <tex>R </tex> называется отношение <tex> R\circ R^{-1} </tex>

==Свойства==Композиция отношений обладает следующими свойствами: * Ядро отношения <tex> R </tex> [[Симметричное отношение|симметрично]]: &nbsp; <tex>a (R \circ R^{-1}) b \iff b (R \circ R^{-1})a </tex> * Композиция отношений [[Ассоциативная операция|ассоциативна]]: &nbsp; <tex> (R \circ S) \circ T = R \circ (S \circ T) </tex> * Обратное отношение для отношения, являющемуся обратным к <tex> R </tex> есть само <tex> R :</tex> &nbsp; <tex> (R^{-1})^{-1} = R </tex>

* Ядро отношения Обратное отношение к композиции отношений <tex>R </tex> и <tex>S </tex> есть композиция отношений, обратных к <tex>R [[Симметричное отношение|симметрично]]</tex> и <tex>S : </tex> &nbsp; <tex> a (R \circ R^{-1}) b \Leftrightarrow \exists c: (a R cS) \wedge (c R^{-1} b) \Leftrightarrow \exists c: = (b R c) \wedge (c RS ^{-1} a) \Leftrightarrow b circ (R \circ R^{-1} ) a</tex>

* Обратное отношение к объединению отношений <tex>R </tex> и <tex>S </tex> есть объединение отношений, обратных к <tex>R </tex> и <tex>S : </tex> &nbsp;<tex> (R \cup S) ^ {-1} = (R^{-1})\cup (S^{-1} = R ) </tex>

* Обратное отношение к пересечению отношений <tex>R </tex> и <tex>S </tex> есть пересечение отношений, обратных к <tex>R </tex> и <tex>S : </tex> &nbsp;<tex> (R \circ cap S) \circ T ^ {-1} = (R ^{-1}) \circ cap (S \circ T^{-1}) </tex>

== См. также ==* <tex> (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) </tex>[[Бинарное_отношение|Бинарное отношение]]* [[Транзитивное_замыкание|Транзитивное замыкание]]

==Источники информации==* <tex> (R \cup S) ^ Новиков Ф. А. {{-1--} = (R^} Дискретная математика для программистов: Учебник для вузов. 3-е изд. {{---}} СПБ.: Питер, 2009 {{-1--}}) \cup (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.]