Binary relation: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Binary relation'''--- бинарное отношение. <math>R</math> is a ''' binary relation''' on <math>V</math> if <math>R \subseteq V \times V</math>. …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Binary relation''' | '''Binary relation''' — ''[[бинарное отношение]].'' | ||
<math>R</math> is a ''' binary relation''' on <math>V</math> if <math>R \subseteq V \times V</math>. <math>R</math> is '''reflexive''' on <math>V</math> if for all <math>v \in V </math> <math>(v,v) \in R</math> and '''irreflexive''' otherwise. <math>R</math> is '''transitive''' on <math>V</math>, if for all <math>u, v, w \in V</math> <math>(u,v) \in R</math> and | <math>\,R</math> is a ''' binary relation''' on <math>\,V</math> if <math>R \subseteq V \times V</math>. <math>\,R</math> is '''reflexive''' on <math>\,V</math> if for all <math>v \in V </math> <math>(v,v) \in R</math> and '''irreflexive''' otherwise. <math>\,R</math> is '''transitive''' on <math>\,V</math>, if for all <math>u, v, w \in V</math> <math>(u,v) \in R</math> and | ||
<math>(v,w) \in R</math> implies <math>(u,w) \in R</math>. <math>R</math> is ''' symmetric''', if <math>(v,w) \in | <math>(v,w) \in R</math> implies <math>(u,w) \in R</math>. <math>\,R</math> is ''' symmetric''', if <math>(v,w) \in R</math> implies <math>(w,v) \in R</math>, and '''antisymmetric''' on <math>V</math>, if | ||
R</math> implies <math>(w,v) \in R</math>, and ''' antisymmetric''' on <math>V</math>, if | for all <math>u, v \in V</math> <math>(u,v) \in R</math> and <math>(v,u) \in R</math> implies <math>\,u = v</math>. | ||
for all <math>u, v \in V</math> <math>(u,v) \in R</math> and <math>(v,u) \in R</math> implies <math>u = v</math>. | |||
The ''' inverse''' of a relation <math>R</math>, denoted by <math>R^{-1}</math>, is obtained | The '''inverse''' of a relation <math>\,R</math>, denoted by <math>\,R^{-1}</math>, is obtained | ||
by reversing each of the pairs belonging to <math>R</math>, so that <math>aR^{-1}b</math> iff | by reversing each of the pairs belonging to <math>\,R</math>, so that <math>\,aR^{-1}b</math> iff | ||
<math>bRa</math>. Let <math>R^{U}</math> denote the union and <math>R^{I}</math> the intersection of a | <math>\,bRa</math>. Let <math>\,R^{U}</math> denote the union and <math>\,R^{I}</math> the intersection of a | ||
collection of relations <math>\{R_{k}: \; k \in {\mathcal C}\}</math> in <math>S</math>, where | collection of relations <math>\{R_{k}: \; k \in {\mathcal C}\}</math> in <math>\,S</math>, where | ||
<math>{\mathcal C}</math> is some nonempty index set. Then <math>aR^{U}b</math> iff <math>aR_{k}b</math> | <math>{\mathcal C}</math> is some nonempty index set. Then <math>\,aR^{U}b</math> iff <math>\,aR_{k}b</math> | ||
for some <math>k</math> in <math>{\mathcal C}</math>, and <math>aR^{I}b</math> iff <math>aR_{k}b</math> for each <math>k</math> | for some <math>\,k</math> in <math>{\mathcal C}</math>, and <math>\,aR^{I}b</math> iff <math>\,aR_{k}b</math> for each <math>\,k</math> | ||
in <math>{\mathcal C}</math>. | in <math>{\mathcal C}</math>. | ||
==See also== | ==See also== | ||
*''Equivalence relation'', '' Partial order''. | * ''[[Equivalence relation]]'', | ||
* ''[[Partial order relation]]''. | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 12:54, 7 февраля 2012
Binary relation — бинарное отношение.
[math]\displaystyle{ \,R }[/math] is a binary relation on [math]\displaystyle{ \,V }[/math] if [math]\displaystyle{ R \subseteq V \times V }[/math]. [math]\displaystyle{ \,R }[/math] is reflexive on [math]\displaystyle{ \,V }[/math] if for all [math]\displaystyle{ v \in V }[/math] [math]\displaystyle{ (v,v) \in R }[/math] and irreflexive otherwise. [math]\displaystyle{ \,R }[/math] is transitive on [math]\displaystyle{ \,V }[/math], if for all [math]\displaystyle{ u, v, w \in V }[/math] [math]\displaystyle{ (u,v) \in R }[/math] and [math]\displaystyle{ (v,w) \in R }[/math] implies [math]\displaystyle{ (u,w) \in R }[/math]. [math]\displaystyle{ \,R }[/math] is symmetric, if [math]\displaystyle{ (v,w) \in R }[/math] implies [math]\displaystyle{ (w,v) \in R }[/math], and antisymmetric on [math]\displaystyle{ V }[/math], if for all [math]\displaystyle{ u, v \in V }[/math] [math]\displaystyle{ (u,v) \in R }[/math] and [math]\displaystyle{ (v,u) \in R }[/math] implies [math]\displaystyle{ \,u = v }[/math].
The inverse of a relation [math]\displaystyle{ \,R }[/math], denoted by [math]\displaystyle{ \,R^{-1} }[/math], is obtained by reversing each of the pairs belonging to [math]\displaystyle{ \,R }[/math], so that [math]\displaystyle{ \,aR^{-1}b }[/math] iff [math]\displaystyle{ \,bRa }[/math]. Let [math]\displaystyle{ \,R^{U} }[/math] denote the union and [math]\displaystyle{ \,R^{I} }[/math] the intersection of a collection of relations [math]\displaystyle{ \{R_{k}: \; k \in {\mathcal C}\} }[/math] in [math]\displaystyle{ \,S }[/math], where [math]\displaystyle{ {\mathcal C} }[/math] is some nonempty index set. Then [math]\displaystyle{ \,aR^{U}b }[/math] iff [math]\displaystyle{ \,aR_{k}b }[/math] for some [math]\displaystyle{ \,k }[/math] in [math]\displaystyle{ {\mathcal C} }[/math], and [math]\displaystyle{ \,aR^{I}b }[/math] iff [math]\displaystyle{ \,aR_{k}b }[/math] for each [math]\displaystyle{ \,k }[/math] in [math]\displaystyle{ {\mathcal C} }[/math].
See also
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.