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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 38 промежуточных версий 15 участников)
Строка 1: Строка 1:
−
== Определение ==
+
{{Определение
−
'''Бинарным отношением''' ''R'' из множества ''A'' в множество ''B'' называется подмножество прямого произведения ''A'' и ''B'' и обозначается:
+
|definition =
−
 
+
'''Бинарным отношением''' (англ. ''binary relation'') <tex>R</tex> из множества <math>A</math> в множество <tex>B</tex> называется подмножество прямого произведения <tex>A</tex> и <tex>B</tex> и обозначается:
−
<math>R \subset \Alpha \times \Beta</math>
+
<tex>R \subset A \times B</tex>.
−
 
+
}}
  
 
Часто используют инфиксную форму записи:
 
Часто используют инфиксную форму записи:
−
<math>aRb, \ (a,b) \subset R</math>
+
<tex>aRb, \ \langle x, y \rangle\in R</tex>.
  
−
Если ''A = B'' то ''R'' называют бинарными отношением на множестве ''A'':
+
Если отношение определено на множестве <tex>A</tex>, то возможно следующее определение:
−
<math>R \subset \Alpha \times \Alpha</math>
+
{{Определение
 +
|definition =
 +
'''Бинарным''' (или '''двуместным''') '''отношением''' <tex>R</tex> на множестве <tex>A</tex> называется множество упорядоченных пар элементов этого множества.
 +
}}
 
Примерами множеств с введёнными на них бинарными отношениями являются [[Ориентированный граф|графы]] и частично упорядоченные множества.
 
Примерами множеств с введёнными на них бинарными отношениями являются [[Ориентированный граф|графы]] и частично упорядоченные множества.
 +
 
== Свойства отношений ==
 
== Свойства отношений ==
−
Для <math>R \subset A^2</math> определены свойства:
+
Для <tex>R \subset A^2</tex> определены свойства:
−
# [[Рефлексивное отношение|Рефлексивность]]: <math>\mathcal {8} x \in A \  (xRx)</math>  
+
* [[Рефлексивное отношение|Рефлексивность]] (англ. ''reflexivity''): <tex>\forall  x \in A \  (xRx)</tex>;
−
# [[Рефлексивное отношение|Антирефлексивность]]: <math>\mathcal {8} x \in A \  (\neg xRx)</math>
+
* [[Рефлексивное отношение|Антирефлексивность]] (англ. ''irreflexivity''): <tex>\forall  x \in A \  \neg(xRx)</tex>;
−
# [[Симметричное отношение|Симметричность]]: <math>\mathcal {8} x,y \in A \  (xRy \Rightarrow yRx)</math>
+
* [[Симметричное отношение|Симметричность]] (англ. ''symmetry''): <tex>\forall  x,y \in A \  (xRy \Rightarrow yRx)</tex>;
−
# [[Антисимметричное отношение|Антисимметричность]]: <math>\mathcal {8} x,y \in A \  (xRy \land yRx \Rightarrow x = y)</math>
+
* [[Антисимметричное отношение|Антисимметричность]] (англ. ''antisymmetry''): <tex>\forall  x,y \in A \  (xRy \land yRx \Rightarrow x = y)</tex>;
−
# [[Транзитивное отношение|Транзитивность]]: <math>\mathcal {8} x,y,z \in A \  (xRy \land yRz \Rightarrow xRz)</math>
+
* [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\forall  x,y,z \in A \  (xRy \land yRz \Rightarrow xRz)</tex>;
−
# Полнота(линейность): <math>\mathcal {8} x,y \in A \  (xRy \lor yRx)</math>
+
* Связность (англ. ''connectivity''): <tex>\forall  x,y \in A \  (xRy \lor yRx)</tex>;
−
# [[Антисимметричное отношение|Ассимметричность]]: <math>\mathcal {8} x,y \in A \  (xRy \Rightarrow \neg (yRx))</math>
+
* [[Антисимметричное отношение|Ассимметричность]] (англ. ''assymetric relation''): <tex>\forall  x,y \in A \  (xRy \Rightarrow \neg (yRx))</tex>.
 +
 
 
== Виды отношений ==
 
== Виды отношений ==
 
Выделяются следующие виды отношений:
 
Выделяются следующие виды отношений:
−
* квазипорядка - рефлексивное транзитивное
+
* квазипорядка (англ. ''quasiorder'') — рефлексивное транзитивное;
−
* эквивалентности - рефлексивное симметричное транзитивное
+
* [[Отношение эквивалентности|эквивалентности]] (англ. ''equivalence'') — рефлексивное симметричное транзитивное;
−
* частичного порядка - рефлексивное антисимметричное транзитивное
+
* [[Отношение порядка|частичного порядка]] (англ. ''partial order'') — рефлексивное антисимметричное транзитивное;
−
* строгого порядка -антирефлексивное антисимметричное транзитивное
+
* [[Отношение порядка|строгого порядка]] (англ. ''strict order'') — антирефлексивное антисимметричное транзитивное;
−
* линейного порядка -полное антисимметричное транзитивное
+
* [[Отношение порядка|линейного порядка]] (англ. ''total order'') — полное антисимметричное транзитивное;
−
* доминирования - антирефлексивное асимметричное
+
* [[Отношение порядка|доминирования]] (англ. ''dominance'') — антирефлексивное антисимметричное.
  
 
== Примеры отношений ==
 
== Примеры отношений ==
−
*Примеры '''рефлексивных отношений''': равенство, одновременность, сходство.
+
*Примеры [[Рефлексивное отношение|'''рефлексивных отношений''']]: равенство, одновременность, сходство.
−
*Примеры '''нерефлексвных отношений''': «заботиться о», «развлекать», «нервировать».
+
*Примеры [[Рефлексивное отношение|'''нерефлексивных отношений''']]: «заботиться о», «развлекать», «нервировать».
−
*Примеры '''транзитивных отношений''': «больше», «меньше», «равно», «подобно», «выше», «севернее».
+
*Примеры [[Транзитивное отношение|'''транзитивных отношений''']]: «больше», «меньше», «равно», «подобно», «выше», «севернее».
−
*Примеры '''симметричных отношений''': равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).
+
*Примеры [[Симметричное отношение|'''симметричных отношений''']]: равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).
−
*Примеры '''антисимметричных отношений''': больше, меньше, больше или равно.
+
*Примеры [[Антисимметричное отношение|'''антисимметричных отношений''']]: больше, меньше, больше или равно.
 
*Примеры '''асимметричных отношений''': отношение «больше» (>) и «меньше» (<).
 
*Примеры '''асимметричных отношений''': отношение «больше» (>) и «меньше» (<).
 +
 
== См. также ==
 
== См. также ==
−
* [[Степень отношений]]
+
* [[Композиция_отношений|Композиция отношений]]
−
== Ссылки ==
+
* [[Транзитивное_замыкание|Транзитивное замыкание]]
−
* [http://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 wikipedia.org — Бинарное отношение]
+
* [[Отношение_порядка|Отношение порядка]]
−
* [http://ru.math.wikia.com/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 wikia.com - Бинарное отношение]
+
 
−
* http://www.studfiles.ru/dir/cat14/subj266/file9092/view94463/page2.html
+
== Источники информации ==
 +
* Новиков Ф. А. {{---}} Дискретная математика для программистов: Учебник для вузов. 3-е изд. {{---}} СПБ.: Питер, 2009 {{---}} 50 с.
 +
* [http://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 Википедия {{---}} Бинарное отношение]
 +
* [http://ru.math.wikia.com/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 Wikia {{---}} Бинарное отношение]
 +
* [https://studfiles.net/preview/952560/page:4/ Studfiles {{---}} Лекции по дискретной математике. Отношения и их свойства]
 +
 
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория: Отношения ]]

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

Определение:
Бинарным отношением (англ. binary relation) [math]R[/math] из множества [math]A[/math] в множество [math]B[/math] называется подмножество прямого произведения [math]A[/math] и [math]B[/math] и обозначается: [math]R \subset A \times B[/math].


Часто используют инфиксную форму записи: [math]aRb, \ \langle x, y \rangle\in R[/math].

Если отношение определено на множестве [math]A[/math], то возможно следующее определение:

Определение:
Бинарным (или двуместным) отношением [math]R[/math] на множестве [math]A[/math] называется множество упорядоченных пар элементов этого множества.

Примерами множеств с введёнными на них бинарными отношениями являются графы и частично упорядоченные множества.

Свойства отношений

Для [math]R \subset A^2[/math] определены свойства:

Виды отношений

Выделяются следующие виды отношений:

  • квазипорядка (англ. quasiorder) — рефлексивное транзитивное;
  • эквивалентности (англ. equivalence) — рефлексивное симметричное транзитивное;
  • частичного порядка (англ. partial order) — рефлексивное антисимметричное транзитивное;
  • строгого порядка (англ. strict order) — антирефлексивное антисимметричное транзитивное;
  • линейного порядка (англ. total order) — полное антисимметричное транзитивное;
  • доминирования (англ. dominance) — антирефлексивное антисимметричное.

Примеры отношений

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Бинарное_отношение&oldid=84953»