Антисимметричное отношение — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показана 21 промежуточная версия 5 участников)
Строка 1: Строка 1:
 +
== Основные определения ==
 +
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Антисимметричное''' отношение - бинарное отношение <tex>R \subseteq A\times A</tex>, для которого выполняется:
+
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''антисимметричным''' (англ. ''antisymmetric binary relation''), если для любых элементов <tex>a</tex> и <tex>b</tex> множества <tex>X</tex> из выполнения отношений <tex>aRb</tex> и <tex>bRa</tex> следует равенство <tex>a</tex> и <tex>b</tex>.
<tex> \forall a, b\in A: (aRb) \wedge (bRa) \Rightarrow a = b</tex>.
 
 
}}
 
}}
Определение антисимметричного отношения как <tex> (aRb) \Rightarrow \neg(bRa) </tex> является неверным, поскольку из такого определения также следует [[Рефлексивное_отношение| антирефлексивность]] R.  
+
:<tex>\forall a, b \in X,\ aRb \wedge bRa \; \Rightarrow \; a = b</tex>
 +
Или эквивалентное
 +
{{Определение
 +
|definition =
 +
Бинарное отношение <tex>R</tex> на множестве <tex>X</tex> называется '''антисимметричным''', если для любых неравных элементов <tex>a</tex> и <tex>b</tex> множества <tex>X</tex> из выполнения отношения <tex>aRb</tex> следует невыполнение отношения <tex>bRa</tex>.
 +
}}
 +
:<tex>\forall a, b \in X,\ aRb \wedge a \ne b \Rightarrow \lnot  bRa</tex>
  
Примерами антисимметричных отношений являются, по определению, все отношения полного и частичного порядка(<tex> <, >, \le, \ge </tex> и другие).
+
Определение антисимметричного отношения как <tex> aRb \Rightarrow \neg bRa </tex> является избыточным (и потому неверным), поскольку из такого определения также следует [[Рефлексивное_отношение| антирефлексивность]] R.
  
 +
Антисимметричность отношения не исключает симметричности. Существуют бинарные отношения:
 +
*одновременно симметричные и антисимметричные (отношение равенства);
 +
*ни симметричные, ни антисимметричные;
 +
*симметричные, но не антисимметричные;
 +
*антисимметричные, но не симметричные ("меньше или равно", "больше или равно");
 +
 +
Антирефлексивное антисимметричное отношение иногда называют асимметричным. Следует различать эти два понятия. Формальное определение:
 
{{Определение
 
{{Определение
|definition =  
+
|definition =
'''Асимметричное''' отношение - бинарное отношение R, для которого выполняется:
+
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''асимметричным''' (англ. ''asymmetric binary relation''), если для любых элементов <tex>a</tex> и <tex>b</tex> множества <tex>X</tex> одновременное выполнение отношений <tex>a R b</tex> и <tex>b R a</tex> невозможно.
 +
}}
 +
== Примеры антисимметричных отношений ==
 +
 
 +
Примерами антисимметричных отношений являются, по определению, все отношения [[Отношение порядка|полного и частичного порядка]] (<tex> <, >, \leqslant,  \geqslant </tex> и другие).
 +
 
 +
Антисимметрично отношение делимости на натуральных числах (если <tex>a \mid b</tex> и <tex>b \mid a</tex>, то <tex>a=b</tex>)
 +
 
 +
Отношение включения на <tex>2^U</tex>, где <tex>U</tex> {{---}} универсум, антисимметрично  (<tex> A \subseteq B \wedge B \subseteq A \Rightarrow A = B</tex>).
  
<tex> (a R b) \Rightarrow \neg (b R a) </tex>
+
== Свойства антисимметричного отношения ==
}}
+
 
 +
[[Файл:antisym.png|400px|thumb|right|Граф антисимметричного отношения (не имеет кратных ребер)]]
 +
[[Файл:nonantisym.png|400px|thumb|right|Граф отношения, не являющегося антисимметричным]]
 +
Матрица смежности антисимметричного отношения может содержать единицы на главной диагонали, притом если элемент <tex>a_{ij}</tex> матрицы равен единице, то элемент <tex>a_{ji}</tex> равен нулю.
 +
 
 +
Например, если <tex>A</tex> {{---}} матрица смежности отношения "<tex>\leqslant</tex>" на <tex>X \subset N, X = \{1, 2, 3 ,4 , 5\}</tex>; <tex>B</tex> {{---}} матрица смежности отношения делимости на том же множестве <tex>X</tex>, то
 +
 
 +
<tex> A=\bordermatrix{
 +
        & 1 & 2 & 3 & 4 & 5 \cr
 +
      1 & 1 & 1 & 1 & 1 & 1 \cr
 +
      2 & 0 & 1 & 1 & 1 & 1 \cr
 +
      3 & 0 & 0 & 1 & 1 & 1 \cr
 +
      4 & 0 & 0 & 0 & 1 & 1 \cr
 +
      5 & 0 & 0 & 0 & 0 & 1 \cr } </tex>
 +
 
 +
<tex> B=\bordermatrix{
 +
        & 1 & 2 & 3 & 4 & 5 \cr
 +
      1 & 1 & 1 & 1 & 1 & 1 \cr
 +
      2 & 0 & 1 & 0 & 1 & 0 \cr
 +
      3 & 0 & 0 & 1 & 0 & 0 \cr
 +
      4 & 0 & 0 & 0 & 1 & 0 \cr
 +
      5 & 0 & 0 & 0 & 0 & 1 \cr } </tex>
 +
 
 +
Ориентированный граф, изображающий антисимметричное отношение, не имеет двух дуг с противоположной ориентацией между двумя различными вершинами, однако в нём могут быть петли.
  
Асимметричность отношения R эквивалентна [[Рефлексивное_отношение|антирефлексивности]] и антисимметричности отношения R.
+
Если <tex>a</tex> и <tex>b</tex> {{---}} некоторые антисимметричные отношения, то антисимметричными также являются отношения:
 +
#<tex>a\cap b</tex>
 +
#<tex>a^{-1}</tex>
 +
#<tex>b^{-1}</tex>
 +
Однако объединение и композиция <tex>a</tex> и <tex>b</tex> могут не сохранять антисимметричности.
  
 
==См. также==
 
==См. также==
 +
* [[Бинарное отношение]]
 
* [[Симметричное отношение]]
 
* [[Симметричное отношение]]
 +
 +
== Источники информации ==
 +
* [http://ru.wikipedia.org/wiki/Антисимметричное_отношение Антисимметричное отношение {{---}} Википедия]
 +
* [http://en.wikipedia.org/wiki/Antisymmetric_relation Антисимметричное отношение {{---}} статья на английской Википедии]
 +
* [http://www.madi.ru/study/kafedra/asu_new/metod_new/mil/tpr09_13.shtml#1 Статья на сайте МАДИ]
 +
* [http://en.wikipedia.org/wiki/Asymmetric_relation Wikipedia | Asymmetric relation]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Отношения]]

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

Основные определения

Определение:
Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется антисимметричным (англ. antisymmetric binary relation), если для любых элементов [math]a[/math] и [math]b[/math] множества [math]X[/math] из выполнения отношений [math]aRb[/math] и [math]bRa[/math] следует равенство [math]a[/math] и [math]b[/math].
[math]\forall a, b \in X,\ aRb \wedge bRa \; \Rightarrow \; a = b[/math]

Или эквивалентное

Определение:
Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется антисимметричным, если для любых неравных элементов [math]a[/math] и [math]b[/math] множества [math]X[/math] из выполнения отношения [math]aRb[/math] следует невыполнение отношения [math]bRa[/math].
[math]\forall a, b \in X,\ aRb \wedge a \ne b \Rightarrow \lnot bRa[/math]

Определение антисимметричного отношения как [math] aRb \Rightarrow \neg bRa [/math] является избыточным (и потому неверным), поскольку из такого определения также следует антирефлексивность R.

Антисимметричность отношения не исключает симметричности. Существуют бинарные отношения:

  • одновременно симметричные и антисимметричные (отношение равенства);
  • ни симметричные, ни антисимметричные;
  • симметричные, но не антисимметричные;
  • антисимметричные, но не симметричные ("меньше или равно", "больше или равно");

Антирефлексивное антисимметричное отношение иногда называют асимметричным. Следует различать эти два понятия. Формальное определение:

Определение:
Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется асимметричным (англ. asymmetric binary relation), если для любых элементов [math]a[/math] и [math]b[/math] множества [math]X[/math] одновременное выполнение отношений [math]a R b[/math] и [math]b R a[/math] невозможно.

Примеры антисимметричных отношений

Примерами антисимметричных отношений являются, по определению, все отношения полного и частичного порядка ([math] \lt , \gt , \leqslant, \geqslant [/math] и другие).

Антисимметрично отношение делимости на натуральных числах (если [math]a \mid b[/math] и [math]b \mid a[/math], то [math]a=b[/math])

Отношение включения на [math]2^U[/math], где [math]U[/math] — универсум, антисимметрично ([math] A \subseteq B \wedge B \subseteq A \Rightarrow A = B[/math]).

Свойства антисимметричного отношения

Граф антисимметричного отношения (не имеет кратных ребер)
Граф отношения, не являющегося антисимметричным

Матрица смежности антисимметричного отношения может содержать единицы на главной диагонали, притом если элемент [math]a_{ij}[/math] матрицы равен единице, то элемент [math]a_{ji}[/math] равен нулю.

Например, если [math]A[/math] — матрица смежности отношения "[math]\leqslant[/math]" на [math]X \subset N, X = \{1, 2, 3 ,4 , 5\}[/math]; [math]B[/math] — матрица смежности отношения делимости на том же множестве [math]X[/math], то

[math] A=\bordermatrix{ & 1 & 2 & 3 & 4 & 5 \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 0 & 1 & 1 & 1 & 1 \cr 3 & 0 & 0 & 1 & 1 & 1 \cr 4 & 0 & 0 & 0 & 1 & 1 \cr 5 & 0 & 0 & 0 & 0 & 1 \cr } [/math]

[math] B=\bordermatrix{ & 1 & 2 & 3 & 4 & 5 \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 0 & 1 & 0 & 1 & 0 \cr 3 & 0 & 0 & 1 & 0 & 0 \cr 4 & 0 & 0 & 0 & 1 & 0 \cr 5 & 0 & 0 & 0 & 0 & 1 \cr } [/math]

Ориентированный граф, изображающий антисимметричное отношение, не имеет двух дуг с противоположной ориентацией между двумя различными вершинами, однако в нём могут быть петли.

Если [math]a[/math] и [math]b[/math] — некоторые антисимметричные отношения, то антисимметричными также являются отношения:

  1. [math]a\cap b[/math]
  2. [math]a^{-1}[/math]
  3. [math]b^{-1}[/math]

Однако объединение и композиция [math]a[/math] и [math]b[/math] могут не сохранять антисимметричности.

См. также

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