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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 12 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Композицией бинарных отношений <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:  
+
'''Композицией''' (произведением, суперпозицией) бинарных отношений (англ. ''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 \exists b \in B : (a R b) \wedge (b S c) </tex>.
+
<tex>\forall a \in A, c \in C : a (R \circ S) c \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>  {{---}}  отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)".
  
Примером такого отношения может служить отношение на некотором множестве <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=
 
|definition=
Степень отношения <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:
+
'''Степень отношения''' (англ. ''power of relation'') <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:
  
 
* <tex> R^{n} = R^{n-1} \circ R; </tex>
 
* <tex> R^{n} = R^{n-1} \circ R; </tex>
Строка 23: Строка 22:
 
В связи с этим понятием, также вводятся обозначения:
 
В связи с этим понятием, также вводятся обозначения:
  
<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i}; </tex>
+
<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i} </tex> — [[Транзитивное замыкание]] (англ. ''transitive closure'') отношения <tex>R</tex>;
  
<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> - [[Транзитивное замыкание]] отношения R
 
  
=Обратное отношение=
+
<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> — Транзитивно-рефлексивное замыкание отношения <tex>R</tex>
 +
 
 +
== Обратное отношение ==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Отношение <tex>R^{-1} \subseteq B\times A</tex> называют ''обратным'' для отношения <tex> R \subseteq A\times B</tex>, если:
+
Отношение <tex>R^{-1} \subseteq B\times A</tex> называют '''обратным''' (англ. ''inverse relation'') для отношения <tex> R \subseteq A\times B</tex>, если:
  
<tex> aR^{-1}b \Leftrightarrow bRa </tex>
+
<tex> bR^{-1}a \iff aRb </tex>
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
''Ядром отношения'' R называется отношение <tex> R\circ R^{-1} </tex>
+
'''Ядром отношения''' (англ. ''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})^{-1} = R </tex>
  
* Ядро отношения R [[Симметричное отношение|симметрично]]: <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>R </tex> и  <tex>S </tex> есть композиция отношений, обратных к <tex>R </tex> и  <tex>S : </tex> &nbsp; <tex> (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) </tex>
  
* <tex> (R^{-1})^{-1} = R </tex>
+
* Обратное отношение к объединению отношений <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 \circ S) \circ T = R \circ (S \circ T) </tex>
+
* Обратное отношение к пересечению отношений <tex>R </tex> и  <tex>S </tex> есть пересечение отношений, обратных к <tex>R </tex> и  <tex>S : </tex> &nbsp;<tex> (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) </tex>
  
* <tex> (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) </tex>
+
== См. также ==
 +
* [[Бинарное_отношение|Бинарное отношение]]
 +
* [[Транзитивное_замыкание|Транзитивное замыкание]]
  
* <tex> (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) </tex>
+
==Источники информации==
 +
* Новиков Ф. А. {{---}} Дискретная математика для программистов: Учебник для вузов. 3-е изд. {{---}} СПБ.: Питер, 2009 {{---}} 52 с.
 +
* [http://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> (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) </tex>
+
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Отношения ]]

Текущая версия на 19:28, 4 сентября 2022

Определение:
Композицией (произведением, суперпозицией) бинарных отношений (англ. composition of binary relations) [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] — отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)".

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

Определение:
Степень отношения (англ. power of relation) [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]Транзитивное замыкание (англ. transitive closure) отношения [math]R[/math];


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

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

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


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


Свойства

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

  • Ядро отношения [math] R [/math] симметрично:   [math]a (R \circ R^{-1}) b \iff b (R \circ R^{-1})a [/math]
  • Композиция отношений ассоциативна:   [math] (R \circ S) \circ T = R \circ (S \circ T) [/math]
  • Обратное отношение для отношения, являющемуся обратным к [math] R [/math] есть само [math] R :[/math]   [math] (R^{-1})^{-1} = R [/math]
  • Обратное отношение к композиции отношений [math]R [/math] и [math]S [/math] есть композиция отношений, обратных к [math]R [/math] и [math]S : [/math]   [math] (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) [/math]
  • Обратное отношение к объединению отношений [math]R [/math] и [math]S [/math] есть объединение отношений, обратных к [math]R [/math] и [math]S : [/math]  [math] (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) [/math]
  • Обратное отношение к пересечению отношений [math]R [/math] и [math]S [/math] есть пересечение отношений, обратных к [math]R [/math] и [math]S : [/math]  [math] (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) [/math]

См. также

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