Композиция отношений

2015-01-24T19:01:39Z

31.192.174.84:

{{Определение
|definition=
'''Композицией''' (произведением, суперпозицией) бинарных отношений (англ. ''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 \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=
'''Степень отношения''' <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:

* <tex> R^{n} = R^{n-1} \circ R; </tex>

* <tex> R^{1} = R; </tex>

* <tex> R^{0} = \{ (x, x) \mid x \in A \}</tex>;
}}

В связи с этим понятием, также вводятся обозначения:

<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </tex>

<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> — [[Транзитивное замыкание]] отношения R

== Обратное отношение ==

{{Определение
|definition=
Отношение <tex>R^{-1} \subseteq B\times A</tex> называют '''обратным''' (англ. ''inverse relation'') для отношения <tex> R \subseteq A\times B</tex>, если:

<tex> bR^{-1}a \iff aRb </tex>
}}

{{Определение
|definition=
'''Ядром отношения''' R называется отношение <tex> R\circ R^{-1} </tex>
}}

== Свойства ==

* Ядро отношения R [[Симметричное отношение|симметрично]]:
<tex> a (R \circ R^{-1}) b \iff \exists c: (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^{-1})^{-1} = R </tex>

* <tex> (R \circ S) \circ T = R \circ (S \circ T) </tex>

* <tex> (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) </tex>

* <tex> (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) </tex>

* <tex> (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) </tex>

==Ссылки==
* [http://en.wikipedia.org/wiki/Composition_of_relations Wikipedia | Composition of relations]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Отношения ]]

Викиконспекты - Вклад участника [ru]

Композиция отношений