Русская Википедия:Бинарное отношение
Шаблон:Значения Бина́рное (двуме́стное) отноше́ние (соответствие[1][2]) — отношение между двумя множествами <math>A</math> и <math>B</math>, то есть всякое подмножество декартова произведения этих множеств: <math>R \subseteq A \times B</math>[3]. Бинарное отношение на множестве <math>A</math> — любое подмножество <math>R \subseteq A^2 = A \times A</math>, такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка.
Связанные определения
- Множество всех первых компонент пар из <math>R \subseteq A \times B</math> называется областью определения отношения <math>R</math> и обозначается как <math>\mathrm{Dom}\,R</math>.[4]
- <math>\mathrm{Dom}\,R=\{x\mid\exists y((x,\;y)\in R)\}.</math>
- Множество всех вторых компонент пар из <math>R</math> называется областью значения отношения <math>R</math> и обозначается как <math>\mathrm{Im}\,R</math>.
- <math>\mathrm{Im}\,R=\{y\mid\exists x((x,\;y)\in R)\}.</math>[4]
- Инверсия (обратное отношение) <math>R</math> — это множество <math>\{(x,\;y)\mid(y,\;x)\in R\}</math> и обозначается, как <math>R^{-1}</math>.
- Шаблон:Нп3 (суперпозиция) бинарных отношений <math>R</math> и <math>S</math> — это множество <math>\{(x,\;y)\mid\exists z(xRz\land zSy)\}</math> и обозначается, как <math>R\circ S</math>.[5][6]
Свойства отношений
Бинарное отношение <math>R</math> на некотором множестве <math>M</math> может обладать различными свойствами, например:
- рефлексивность: <math>\forall x\in M:(xRx)</math>,
- антирефлексивность (иррефлексивность): <math>\forall x\in M: \neg(xRx)</math>,
- корефлексивность: <math>\forall x,y\in M: (xRy \Rightarrow x=y)</math>,
- симметричность: <math>\forall x,\;y\in M:(xRy\Rightarrow yRx)</math>,
- антисимметричность: <math>\forall x,\;y\in M:(xRy\wedge yRx\Rightarrow x=y)</math>,
- асимметричность: <math>\forall x,\;y\in M:(xRy\Rightarrow\neg(yRx))</math>,
- транзитивность: <math>\forall x,\;y,\;z\in M:(xRy\wedge yRz\Rightarrow xRz)</math>,
- евклидовость: <math>\forall x,y,z\in M: (xRy \wedge xRz\Rightarrow yRz)</math>,
- полнота (или связность[7]): <math>\forall x,y\in M: (xRy \lor yRx)</math>,
- Шаблон:Нп3 (или слабая связность[7]): <math>\forall x,y\in M: (x\neq y\Rightarrow xRy \lor yRx)</math>,
- Шаблон:Нп3: <math>\forall x,y\in M</math> верно ровно одно из трех утверждений: <math>xRy</math>, <math>yRx</math> или <math>x=y</math>.
Виды отношений
- Рефлексивное транзитивное отношение называется отношением квазипорядка.
- Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.
- Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.
- Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.
- Полное антисимметричное (для любых <math>x, y</math> выполняется <math>xRy</math> или <math>yRx</math>) транзитивное отношение называется отношением линейного порядка.
- Антирефлексивное антисимметричное отношение называется отношением доминирования.
Виды бинарных отношений
- Обратное отношениеШаблон:Уточнить (отношение, обратное к <math>R</math>) — это двуместное отношение, состоящее из пар элементов <math>(y, x)</math>, полученных перестановкой пар элементов <math>(x, y)</math> данного отношения <math>R</math>. Обозначается: <math>R^{-1}</math>. Для данного отношения и обратного ему верно равенство: <math>(R^{-1})^{-1} = R</math>.
- Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
- Рефлексивное отношение — двуместное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любого <math>x</math> этого множества элемент <math>x</math> находится в отношении <math>R</math> к самому себе, то есть для любого элемента <math>x</math> этого множества имеет место <math>xRx</math>. Примеры рефлексивных отношений: равенство, одновременность, сходство.
- Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любого элемента <math>x</math> этого множества неверно, что оно находится в отношении <math>R</math> к самому себе (неверно, что <math>xRx</math>).
- Транзитивное отношение — двуместное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x, y, z</math> из <math>xRy</math> и <math>yRz</math> следует <math>xRz</math> (<math>xRy \wedge yRz \to xRz</math>). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
- Нетранзитивное отношениеШаблон:Уточнить — двуместное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x, y, z</math> этого множества из <math>xRy</math> и <math>yRz</math> не следует <math>xRz</math> (<math>\neg (xRy \wedge yRz \to xRz)</math>). Пример нетранзитивного отношения: «x отец y»
- Симметричное отношение — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых элементов <math>x</math> и <math>y</math> этого множества из того, что <math>x</math> находится к <math>y</math> в отношении <math>R</math>, следует, что и <math>y</math> находится в том же отношении к <math>x</math> — <math>xRy \to yRx</math>. Примером симметричных отношений могут быть равенство, отношение эквивалентности, подобие, одновременность.
- Антисимметричное отношение — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x</math> и <math>y</math> из <math>xRy</math> и <math>yRx</math> следует <math>x = y</math> (то есть <math>R</math> и <math>R^{-1}</math> выполняются одновременно лишь для равных между собой членов).
- Асимметричное отношение — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x</math> и <math>y</math> из <math>xRy</math> следует <math>\neg yRx</math>. Пример: отношения «больше» (>) и «меньше» (<).
- Отношение эквивалентности — бинарное отношение <math>R</math> между объектами <math>x</math> и <math>y</math>, являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, подобие, одновременность.
- Отношение порядка — отношение, обладающие только некоторыми из трёх свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.
- Отношение толерантности — бинарное отношение, удовлетворяющее свойствам рефлексивности и симметричности, но не обязательно являющееся транзитивным. Таким образом, отношение эквивалентности является частным случаем толерантности.
- Функция одного переменного — бинарное отношение <math>R</math>, определённое на некотором множестве, отличающееся тем, что каждому значению <math>x</math> отношения <math>xRy</math> соответствует лишь единственное значение <math>y</math>. Свойство функциональности отношения <math>R</math> записывается в виде аксиомы: <math>(xRy \wedge xRz) \to (y \equiv z)</math>.
- Биекция (взаимно-однозначное отношение) — бинарное отношение <math>R</math>, определённое на некотором множестве, отличающееся тем, что в нём каждому значению <math>x</math> соответствует единственное значение <math>y</math>, и каждому значению <math>y</math> соответствует единственное значение <math>x</math>.
Операции над отношениями
Так как отношения, заданные на фиксированной паре множеств <math>A</math> и <math>B</math> суть подмножества множества <math>A \times B</math>, то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных <math>a \in A</math>, <math>b \in B</math>:
- <math>a \,(R \cup S) \, b \Leftrightarrow a \, R \, b \vee a\, S \, b</math>,
- <math>a \,(R \cap S) \, b \Leftrightarrow a \, R \, b \wedge a\, S \, b</math>,
- <math>a \,\overline{R} \, b \Leftrightarrow \neg a \, R \, b</math>.
Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.
Например, <math>({=}) \cup ({<}) = ({\leqslant})</math>, <math>({=}) \cap ({<}) = \varnothing</math>, то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрогого порядка, а их пересечение пусто.
Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом. Если <math>R \subseteq A \times B</math>, то обратным отношением называется отношение <math>R^{-1}</math>, определённое на паре <math>B</math>, <math>A</math> и состоящее из тех пар <math>(b, a)</math>, для которых <math>a \, R \, b</math>. Например, <math>({<})^{-1} = ({>})</math>.
Пусть <math>R \subseteq A \times B</math>, <math>S \subseteq B \times C</math>. Композицией (или произведением) отношений <math>R</math> и <math>S</math> называется отношение <math>R \circ S \subseteq A \times C</math> такое, что:
- <math>a \, (R \circ S) \, c \Leftrightarrow \exists b \in B: \, a \, (R) \, b \wedge b \, (S) \, c</math>.
Например, для отношения строгого порядка на множестве натуральных числе его умножение на себя определено следующим образом: <math>a({<})({<})b \Leftrightarrow a + 1 < b</math>.
Бинарные отношения <math>R</math> и <math>S</math> называются перестановочными, если <math>RS = SR</math>. Для любого бинарного отношения <math>R</math>, определённого на <math>A</math>, имеет место <math>R\mathsf{Id}_A = \mathsf{Id}_AR</math>, где символом <math>\mathsf{Id}_A</math> обозначено равенство, определённое на <math>A</math>. Однако равенство <math>RR^{-1} = \mathsf{Id}</math> не всегда справедливо.
Имеют место следующие тождества:
- <math>R(ST) = (RS)T</math>,
- <math>(RS)^{-1} = S^{-1}R^{-1}</math>,
- <math>\overline{R^{-1}} = {\overline{R}}^{-1}</math>,
- <math>(R \cup S)^{-1} = R^{-1} \cup S^{-1}</math>,
- <math>(R \cap S)^{-1} = R^{-1} \cap S^{-1}</math>,
- <math>R(S \cup T) = RS \cup RT</math>,
- <math>(R \cup S)T = RT \cup ST</math>.
Аналоги последних двух тождеств для пересечения отношений не имеют места.
Примечания
Литература
- ↑ Шаблон:Статья
- ↑ Шаблон:Cite web
- ↑ Шаблон:Книга
- ↑ 4,0 4,1 Шаблон:Книга
- ↑ Шаблон:Книга
- ↑ Шаблон:Книга
- ↑ 7,0 7,1 Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)
