Материал из Викиконспекты
| Определение: |
| Композицией (произведением, суперпозицией) бинарных отношений [math]R\subseteq A\times B[/math] и [math]S\subseteq B\times C[/math] называется такое отношение [math] (R \circ S) \subseteq A\times C[/math], что:
[math]\forall a \in A, c \in C : a (R \circ S) c \iff \exists b \in B : (a R b) \wedge (b S c) [/math]. |
Примером такого отношения может служить отношение на некотором множестве [math]A[/math] населенных пунктов [math]R\subseteq A\times A[/math] - отношение "можно доехать на поезде", а [math]S\subseteq A\times A[/math] - отношение "можно доехать на автобусе". Тогда отношение [math]R\circ S\subseteq A\times A[/math] - отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)".
| Определение: |
Степень отношения [math]R^{n} \subseteq A\times A[/math], определяется следующим образом:
- [math] R^{n} = R^{n-1} \circ R; [/math]
- [math] R^{1} = R; [/math]
- [math] R^{0} = \{ (x, x) \mid x \in A \}[/math];
|
В связи с этим понятием, также вводятся обозначения:
[math] R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; [/math]
[math] R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} [/math] - Транзитивное замыкание отношения R
Обратное отношение
| Определение: |
| Отношение [math]R^{-1} \subseteq B\times A[/math] называют обратным для отношения [math] R \subseteq A\times B[/math], если:
[math] aR^{-1}b \Leftrightarrow bRa [/math] |
| Определение: |
| Ядром отношения R называется отношение [math] R\circ R^{-1} [/math] |
Свойства
- Ядро отношения R симметрично: [math] a (R \circ R^{-1}) b \iff \exists c: (a R c) \wedge (c R^{-1} b) \Leftrightarrow \exists c: (b R c) \wedge (c R^{-1} a) \iff b (R \circ R^{-1} ) a[/math]
- [math] (R^{-1})^{-1} = R [/math]
- [math] (R \circ S) \circ T = R \circ (S \circ T) [/math]
- [math] (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) [/math]
- [math] (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) [/math]
- [math] (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) [/math]
