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

Определение:

Композицией (произведением, суперпозицией) бинарных отношений (англ. composition of binary relations) $R\subseteq A\times B$ и $S\subseteq B\times C$ называется такое отношение $(R \circ S) \subseteq A\times C$, что: $\forall a \in A, c \in C : a (R \circ S) c \iff \exists b \in B : (a R b) \wedge (b S c)$.

Примером такого отношения может служить отношение на некотором множестве $A$ населенных пунктов $R\subseteq A\times A$ — отношение "можно доехать на поезде", а $S\subseteq A\times A$ — отношение "можно доехать на автобусе". Тогда отношение $R\circ S\subseteq A\times A$ — отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)".

Степень отношений

Определение:

Степень отношения (англ. power of relation) $R^{n} \subseteq A\times A$, определяется следующим образом: $R^{n} = R^{n-1} \circ R;$ $R^{1} = R;$ $R^{0} = \{ (x, x) \mid x \in A \}$;

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

$R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}$ — Транзитивное замыкание (англ. transitive closure) отношения $R$;

$R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i}$ — Транзитивно-рефлексивное замыкание отношения $R$

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

Определение:

Отношение $R^{-1} \subseteq B\times A$ называют обратным (англ. inverse relation) для отношения $R \subseteq A\times B$, если: $bR^{-1}a \iff aRb$

Определение:

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

Свойства

Композиция отношений обладает следующими свойствами:

• Ядро отношения $R$ симметрично:   $a (R \circ R^{-1}) b \iff b (R \circ R^{-1})a$

• Композиция отношений ассоциативна:   $(R \circ S) \circ T = R \circ (S \circ T)$

• Обратное отношение для отношения, являющемуся обратным к $R$ есть само $R :$   $(R^{-1})^{-1} = R$

• Обратное отношение к композиции отношений $R$ и $S$ есть композиция отношений, обратных к $R$ и $S :$   $(R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1})$

• Обратное отношение к объединению отношений $R$ и $S$ есть объединение отношений, обратных к $R$ и $S :$  $(R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1})$

• Обратное отношение к пересечению отношений $R$ и $S$ есть пересечение отношений, обратных к $R$ и $S :$  $(R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1})$

См. также

• Бинарное отношение
• Транзитивное замыкание

Источники информации

• Новиков Ф. А. — Дискретная математика для программистов: Учебник для вузов. 3-е изд. — СПБ.: Питер, 2009 — 52 с.
• Wikipedia — Composition of relations
• UNC Charlotte — Lectures in Discrete Mathematics: Composition of Relations and Directed Graphs.