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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (<math> -> <tex>)
Строка 1: Строка 1:
= Определение =
 
 
Композицией бинарных отношений <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:  
 
Композицией бинарных отношений <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 \exists b \in B \mid (a R b) \wedge (b S c) </tex>.
+
<tex>\forall a \in A, c \in C : a (R \circ S) c \Leftrightarrow \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> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".
 
Примером такого отношения может служить отношение на некотором множестве <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> - отношение "можно добраться из А в Б, сначала проехав на поезде, а потом на автобусе(только по одному разу)".
Строка 30: Строка 29:
 
''Ядром отношения'' R называется отношение <tex> R\circ R^{-1} </tex>
 
''Ядром отношения'' R называется отношение <tex> R\circ R^{-1} </tex>
  
Оно симметрично: <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>
+
Оно [[Симметричное отношение|симметрично]]: <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>

Версия 00:50, 4 октября 2010

Композицией бинарных отношений [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 \Leftrightarrow \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]

Оно симметрично: [math] 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[/math]