Композиция отношений — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница)
 
Строка 4: Строка 4:
 
<math>\forall a, c: a(R\circ S)c \Leftrightarrow \exists b\in B\mid (aRb)\and (bSc)</math>.
 
<math>\forall a, c: a(R\circ S)c \Leftrightarrow \exists b\in B\mid (aRb)\and (bSc)</math>.
  
Примером такого отношения может служить отношение на некотором множестве населенных пунктов 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>A</math> населенных пунктов <math>R\subseteq A\times A</math> - отношение "можно доехать на поезде", а <math>B\subseteq A\times A</math> - отношение "можно доехать на автобусе". Тогда отношение <math>R\circ S\subseteq A\times A</math> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".
  
 
=Степень отношений=
 
=Степень отношений=

Версия 09:18, 28 сентября 2010

Определение

Композицией бинарных отношений [math]R\subseteq A\times B[/math] и [math]S\subseteq B\times C[/math] называется такое отношение [math] R \circ S [/math], что:

[math]\forall a, c: a(R\circ S)c \Leftrightarrow \exists b\in B\mid (aRb)\and (bSc)[/math].

Примером такого отношения может служить отношение на некотором множестве [math]A[/math] населенных пунктов [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], определяется следующим образом: [math] R^{n} = R^{n-1} \circ R; [/math]

[math] R^1 = R; R^0 = \{ (x, x) \mid x\in A\}[/math]

В связи с этим понятием, также вводятся обозначения: [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], если:

[math] aR^{-1}b \Leftrightarrow bRa [/math]