Изменения

{{Определение|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 \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> {{---}} отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)".

{{Определение|definition='''Степень отношений=отношения''' (англ. ''power of relation'') <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:

Степень отношения * <tex>R^{n} = R^{n-1} \subseteq A\times Acirc R; </tex>, определяется следующим образом:

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

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

В связи с этим понятием, также вводятся обозначения: <tex> R^{0+} = \bigcup\limits^{\infty}_{ i=1} R^{i} </tex> — [[Транзитивное замыкание]] (x, xангл. ''transitive closure'') отношения <tex>R</tex>;  <tex> R^{*} = \mid x bigcup\in A 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> [[Симметричное отношение|симметрично]]: &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} = \bigcup\limits)^{\infty-1}_{i=1} R^{i}; </tex>

* Обратное отношение к композиции отношений <tex> R</tex> и <tex>S </tex> есть композиция отношений, обратных к <tex>R </tex> и <tex>S : </tex> &nbsp; <tex> (R \circ S) ^{*-1} = \bigcup\limits(S ^{-1}) \infty}_{i=0} circ (R^{i-1} ) </tex> - [[Транзитивное замыкание]] отношения R

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

Отношение * Обратное отношение к пересечению отношений <tex>R^{-1} \subseteq B\times A</tex> называют ''обратным'' для отношения и <tex>S </tex> есть пересечение отношений, обратных к <tex>R </tex> и <tex>S : </tex> &nbsp;<tex> (R \subseteq Acap S) ^ {-1} = (R^{-1}) \times Bcap (S^{-1}) </tex>, если:

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

Оно [[Симметричное отношение|симметричноКатегория: Дискретная математика и алгоритмы]][[Категория: <tex> a (R \circ R^{-1}) b \Leftrightarrow \exists c: (a R c) \wedge (c R^{-1} b) \Leftrightarrow \exists c: (b R c) \wedge (c R^{-1} a) \Leftrightarrow b (R \circ R^{-1} ) a</tex>Отношения ]]