Изменения

Перейти к: навигация, поиск

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

1437 байт добавлено, 19:28, 4 сентября 2022
м
rollbackEdits.php mass rollback
<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>
== Обратное отношение ==
{{Определение
|definition=
'''Ядром отношения''' (англ. ''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>
* Ядро отношения R Композиция отношений [[Симметричное отношениеАссоциативная операция|симметричноассоциативна]]:&nbsp; <tex> a (R \circ R^{-1}S) b \iff \exists c: (a circ T = R c) \wedge (c R^{-1} b) \iff \exists c: (b R c) \wedge (c R^{-1} a) \iff b circ (R S \circ R^{-1} T) a</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> (R \circ S) \circ T ^ {-1} = R \circ (S ^ {-1}) \circ T(R ^ {-1}) </tex>
* Обратное отношение к объединению отношений <tex>R </tex> и <tex>S </tex> есть объединение отношений, обратных к <tex>R </tex> и <tex>S : </tex> &nbsp;<tex> (R \circ cup S) ^ {-1} = (S R^ {-1}) \circ cup (R S^ {-1}) </tex>
* Обратное отношение к пересечению отношений <tex>R </tex> и <tex>S </tex> есть пересечение отношений, обратных к <tex>R </tex> и <tex>S : </tex> &nbsp;<tex> (R \cup cap S) ^ {-1} = (R^{-1}) \cup cap (S^{-1}) </tex>
== См. также ==* <tex> (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) </tex>[[Бинарное_отношение|Бинарное отношение]]* [[Транзитивное_замыкание|Транзитивное замыкание]]
==Источники информации==
1632
правки

Навигация