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