Binary relation: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Binary relation'''--- бинарное отношение. <math>R</math> is a ''' binary relation''' on <math>V</math> if <math>R \subseteq V \times V</math>. …»)
 
Нет описания правки
 
Строка 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.

Текущая версия от 16:31, 23 октября 2018

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.