Бинарное отношение — различия между версиями
(→См. также) |
м (rollbackEdits.php mass rollback) |
||
| (не показана 31 промежуточная версия 15 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''Бинарным отношением''' '' | + | '''Бинарным отношением''' (англ. ''binary relation'') <tex>R</tex> из множества <math>A</math> в множество <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 = | |definition = | ||
| − | '''Бинарным'''(или '''двуместным''') '''отношением''' | + | '''Бинарным''' (или '''двуместным''') '''отношением''' <tex>R</tex> на множестве <tex>A</tex> называется множество упорядоченных пар элементов этого множества. |
}} | }} | ||
Примерами множеств с введёнными на них бинарными отношениями являются [[Ориентированный граф|графы]] и частично упорядоченные множества. | Примерами множеств с введёнными на них бинарными отношениями являются [[Ориентированный граф|графы]] и частично упорядоченные множества. | ||
== Свойства отношений == | == Свойства отношений == | ||
| − | Для < | + | Для <tex>R \subset A^2</tex> определены свойства: |
| − | * [[Рефлексивное отношение|Рефлексивность]]: < | + | * [[Рефлексивное отношение|Рефлексивность]] (англ. ''reflexivity''): <tex>\forall x \in A \ (xRx)</tex>; |
| − | * [[Рефлексивное отношение|Антирефлексивность]]: < | + | * [[Рефлексивное отношение|Антирефлексивность]] (англ. ''irreflexivity''): <tex>\forall x \in A \ \neg(xRx)</tex>; |
| − | * [[Симметричное отношение|Симметричность]]: < | + | * [[Симметричное отношение|Симметричность]] (англ. ''symmetry''): <tex>\forall x,y \in A \ (xRy \Rightarrow yRx)</tex>; |
| − | * [[Антисимметричное отношение|Антисимметричность]]: < | + | * [[Антисимметричное отношение|Антисимметричность]] (англ. ''antisymmetry''): <tex>\forall x,y \in A \ (xRy \land yRx \Rightarrow x = y)</tex>; |
| − | * [[Транзитивное отношение|Транзитивность]]: < | + | * [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\forall x,y,z \in A \ (xRy \land yRz \Rightarrow xRz)</tex>; |
| − | * | + | * Связность (англ. ''connectivity''): <tex>\forall x,y \in A \ (xRy \lor yRx)</tex>; |
| − | * [[Антисимметричное отношение|Ассимметричность]]: < | + | * [[Антисимметричное отношение|Ассимметричность]] (англ. ''assymetric relation''): <tex>\forall x,y \in A \ (xRy \Rightarrow \neg (yRx))</tex>. |
== Виды отношений == | == Виды отношений == | ||
Выделяются следующие виды отношений: | Выделяются следующие виды отношений: | ||
| − | * квазипорядка | + | * квазипорядка (англ. ''quasiorder'') — рефлексивное транзитивное; |
| − | * эквивалентности | + | * [[Отношение эквивалентности|эквивалентности]] (англ. ''equivalence'') — рефлексивное симметричное транзитивное; |
| − | * частичного порядка | + | * [[Отношение порядка|частичного порядка]] (англ. ''partial order'') — рефлексивное антисимметричное транзитивное; |
| − | * строгого порядка | + | * [[Отношение порядка|строгого порядка]] (англ. ''strict order'') — антирефлексивное антисимметричное транзитивное; |
| − | * линейного порядка | + | * [[Отношение порядка|линейного порядка]] (англ. ''total order'') — полное антисимметричное транзитивное; |
| − | * доминирования | + | * [[Отношение порядка|доминирования]] (англ. ''dominance'') — антирефлексивное антисимметричное. |
== Примеры отношений == | == Примеры отношений == | ||
| − | *Примеры '''рефлексивных отношений''': равенство, одновременность, сходство. | + | *Примеры [[Рефлексивное отношение|'''рефлексивных отношений''']]: равенство, одновременность, сходство. |
| − | *Примеры ''' | + | *Примеры [[Рефлексивное отношение|'''нерефлексивных отношений''']]: «заботиться о», «развлекать», «нервировать». |
| − | *Примеры '''транзитивных отношений''': «больше», «меньше», «равно», «подобно», «выше», «севернее». | + | *Примеры [[Транзитивное отношение|'''транзитивных отношений''']]: «больше», «меньше», «равно», «подобно», «выше», «севернее». |
| − | *Примеры '''симметричных отношений''': равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства). | + | *Примеры [[Симметричное отношение|'''симметричных отношений''']]: равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства). |
| − | *Примеры '''антисимметричных отношений''': больше, меньше, больше или равно. | + | *Примеры [[Антисимметричное отношение|'''антисимметричных отношений''']]: больше, меньше, больше или равно. |
*Примеры '''асимметричных отношений''': отношение «больше» (>) и «меньше» (<). | *Примеры '''асимметричных отношений''': отношение «больше» (>) и «меньше» (<). | ||
| + | |||
== См. также == | == См. также == | ||
| − | * [[ | + | * [[Композиция_отношений|Композиция отношений]] |
| + | * [[Транзитивное_замыкание|Транзитивное замыкание]] | ||
| + | * [[Отношение_порядка|Отношение порядка]] | ||
| + | |||
| + | == Источники информации == | ||
| + | * Новиков Ф. А. {{---}} Дискретная математика для программистов: Учебник для вузов. 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) из множества в множество называется подмножество прямого произведения и и обозначается: . |
Часто используют инфиксную форму записи:
.
Если отношение определено на множестве , то возможно следующее определение:
| Определение: |
| Бинарным (или двуместным) отношением на множестве называется множество упорядоченных пар элементов этого множества. |
Примерами множеств с введёнными на них бинарными отношениями являются графы и частично упорядоченные множества.
Содержание
Свойства отношений
Для определены свойства:
- Рефлексивность (англ. reflexivity): ;
- Антирефлексивность (англ. irreflexivity): ;
- Симметричность (англ. symmetry): ;
- Антисимметричность (англ. antisymmetry): ;
- Транзитивность (англ. transitivity): ;
- Связность (англ. connectivity): ;
- Ассимметричность (англ. assymetric relation): .
Виды отношений
Выделяются следующие виды отношений:
- квазипорядка (англ. quasiorder) — рефлексивное транзитивное;
- эквивалентности (англ. equivalence) — рефлексивное симметричное транзитивное;
- частичного порядка (англ. partial order) — рефлексивное антисимметричное транзитивное;
- строгого порядка (англ. strict order) — антирефлексивное антисимметричное транзитивное;
- линейного порядка (англ. total order) — полное антисимметричное транзитивное;
- доминирования (англ. dominance) — антирефлексивное антисимметричное.
Примеры отношений
- Примеры рефлексивных отношений: равенство, одновременность, сходство.
- Примеры нерефлексивных отношений: «заботиться о», «развлекать», «нервировать».
- Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
- Примеры симметричных отношений: равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).
- Примеры антисимметричных отношений: больше, меньше, больше или равно.
- Примеры асимметричных отношений: отношение «больше» (>) и «меньше» (<).
См. также
Источники информации
- Новиков Ф. А. — Дискретная математика для программистов: Учебник для вузов. 3-е изд. — СПБ.: Питер, 2009 — 50 с.
- Википедия — Бинарное отношение
- Wikia — Бинарное отношение
- Studfiles — Лекции по дискретной математике. Отношения и их свойства
