Бинарное отношение

2013-09-08T11:18:11Z

94.19.105.150: /* Примеры отношений */

== Определение ==
{{Определение
|definition =
'''Бинарным отношением''' <tex>R</tex> из множества <tex>A</tex> в множество <tex>B</tex> называется подмножество прямого произведения <tex>A</tex> и <tex>B</tex> и обозначается:
<tex>R \subset A \times B</tex>.
}}

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

Если отношение определено на множестве <tex>A</tex>, то возможно следующее определение:
{{Определение
|definition =
'''Бинарным''' (или '''двуместным''') '''отношением''' <tex>R</tex> на множестве <tex>A</tex> называется множество упорядоченных пар элементов этого множества.
}}
Примерами множеств с введёнными на них бинарными отношениями являются [[Ориентированный граф|графы]] и частично упорядоченные множества.

== Степень отношений ==
Пусть <tex>R</tex> {{---}} отношение на множестве <tex>A</tex>.
{{Определение
|definition =
'''Степенью''' отношения <tex>R</tex> на множестве <tex>A</tex> называется его [[Композиция_отношений|композиция]] с самим собой:

<tex>R^n \ \stackrel{\mathrm{def}}{=} \ R_1 \circ \dots \circ R_n</tex>.

}}

== Свойства отношений ==
Для <tex>R \subset A^2</tex> определены свойства:
* [[Рефлексивное отношение|Рефлексивность]]: <tex>\mathcal {8} x \in A \ (xRx)</tex>;
* [[Рефлексивное отношение|Антирефлексивность]]: <tex>\mathcal {8} x \in A \ (\neg xRx)</tex>;
* [[Симметричное отношение|Симметричность]]: <tex>\mathcal {8} x,y \in A \ (xRy \Rightarrow yRx)</tex>;
* [[Антисимметричное отношение|Антисимметричность]]: <tex>\mathcal {8} x,y \in A \ (xRy \land yRx \Rightarrow x = y)</tex>;
* [[Транзитивное отношение|Транзитивность]]: <tex>\mathcal {8} x,y,z \in A \ (xRy \land yRz \Rightarrow xRz)</tex>;
* Связность: <tex>\mathcal {8} x,y \in A \ (xRy \lor yRx)</tex>;
* [[Антисимметричное отношение|Ассимметричность]]: <tex>\mathcal {8} x,y \in A \ (xRy \Rightarrow \neg (yRx))</tex>.

== Виды отношений ==
Выделяются следующие виды отношений:
* квазипорядка — рефлексивное транзитивное;
* эквивалентности — рефлексивное симметричное транзитивное;
* частичного порядка — рефлексивное антисимметричное транзитивное;
* строгого порядка — антирефлексивное антисимметричное транзитивное;
* линейного порядка — полное антисимметричное транзитивное;
* доминирования — антирефлексивное антисимметричное.

== Примеры отношений ==
*Примеры '''рефлексивных отношений''': равенство, одновременность, сходство.
*Примеры '''нерефлексивных отношений''': «заботиться о», «развлекать», «нервировать».
*Примеры '''транзитивных отношений''': «больше», «меньше», «равно», «подобно», «выше», «севернее».
*Примеры '''симметричных отношений''': равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).
*Примеры '''антисимметричных отношений''': больше, меньше, больше или равно.
*Примеры '''асимметричных отношений''': отношение «больше» (>) и «меньше» (<).

== См. также ==
* [[Композиция_отношений|Композиция отношений]]

== Ссылки ==
* [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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Отношения ]]

Викиконспекты - Вклад участника [ru]

Бинарное отношение