Бинарные отношения
В повседневной жизни нам постоянно приходится сталкиваться с понятием «отношения». Отношения – один из способов задания взаимосвязей между элементами множества.
Унарные (одноместные) отношения отражают наличие какого-то одного признака R у элементов множества M (например, «быть красным» на множестве шаров в урне).
Бинарные (двуместные) отношения используются для определения взаимо
связей, которыми характеризуются пары элементов во множестве M.
Например, на множестве людей могут быть заданы следующие отношения: «жить в одном городе», «x работает под руководством y», «быть сыном», «быть старше» и т.д. на множестве чисел: «число a больше числа b», «число a является делителем числа b», «числа a и b дают одинаковый остаток при делении на 3».
В прямом произведении 
, где A - множество студентов какого-либо вуза, B- множество изучаемых предметов, можно выделить большое подмножество упорядоченных пар (a, b), обладающих свойством: «студент a изучает предмет b». Построенное подмножество отражает отношение «изучает», возникающее между множествами студентов и предметов. Число примеров можно продолжить
Отношения между двумя объектами являются предметом исследования экономики, географии, биологии, физики, лингвистики, математики и других наук.
Для строгого математического описания любых связей между элементами двух множеств вводится понятие бинарного отношения.
Бинарным отношением между множествами A и B называется подмножество R прямого произведения . В том случае, когда 
можно просто говорить об отношении R на A.
Пример 1. Выпишите упорядоченные пары, принадлежащие бинарным отношениям R1 и R2, заданными на множествах A 
и 
: 
, 
. Подмножество R1 состоит из пар: 
. Подмножество 
.
Область определения Rна есть множество всех элементов из A таких, что для некоторых элементов 
имеем 
. Иными словами область определения R есть множество всех первых координат упорядоченных пар из R.
Множество значений отношения R на есть множество всех таких, что для некоторых 
. Другими словами множество значений R есть множество всех вторых координат упорядоченных пар из R.
В примере 1 для R1 область определения: 
, множество значений - 
. Для R2 область определения: 
, множество значений: 
.
Во многих случаях удобно использовать графическое изображение бинарного отношения. Оно осуществляется двумя способами: с помощью точек на плоскости и с помощью стрелок.
В первом случае выбирают две взаимно перпендикулярные линии в качестве горизонтальной и вертикальной осей. На горизонтальной оси откладывают элементы множества A и через каждую точку проводят вертикальную линию. На вертикальной оси откладывают элементы множества B, через каждую точку проводят горизонтальную линию. Точки пересечения горизонтальных и вертикальных линий изображают элементы прямого произведения .
Пример 5. Пусть 
, 
.
Пусть R1 задано на перечислением упорядоченных пар: 
. Бинарное отношение R2 на множестве задано с помощью правила: упорядочена пара 
, если a делится на b. Тогда R2 состоит из пар: 
.
Бинарные отношения, из примера 2, R1 и R2 изображены графически на рис. 6 и рис.7.
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
Рис. 6 Рис. 7
Чтобы изобразить бинарное отношение с помощью стрелок, слева изображаются точками элементы множества A, справа - множества B. Для каждой пары (a, b), содержащейся в бинарном отношении R, проводится стрелка от a к b, 
. Графическое изображение бинарного отношения R1, приведенного в примере 6, показано на рис.8.
| |||||||
| Рис.8 |
Бинарные отношения на конечных множествах могут быть заданы матрицами. Предположим, что задано бинарное отношение R между множествами A и B. 
, 
.
Строки матрицы нумеруются элементами множества A, а столбцы – элементами множества B. Ячейку матрицы, стоящую на пересечении i - ой строки и j - ого столбца принято обозначать через Cij, а заполняется она следующим образом:
Полученная матрица будет иметь размер 
.
Пример 6.Пусть задано множество 
. На множестве задайте списком и матрицей отношение R – «быть строго меньше».
Отношение R как множество содержит все пары элементов (a, b) из M такие, что 
.
.
Тогда 
Матрица отношения, построенная по вышеуказанным правилам, имеет следующий вид:
Свойства бинарных отношений:
1. Бинарное отношение R на множестве 
называетсярефлексивным, если для любого элемента a из M пара (a, a) принадлежит R, т.е. имеет место 
для любого a из M:
.
Отношения «жить в одном городе», «учиться в одном вузе», «быть не больше» являются рефлексивными.
2. Бинарное отношение называется антирефлексивным,если оно не обладает свойством рефлексивности для любых a:
.
Например, «быть больше», «быть младше» - это антирефлексивные отношения.
3. Бинарное отношение R называется симметричным, если для любых элементов a и b из M из того, что пара (a, b) принадлежит R, 
, вытекает, что пара (b, a) принадлежит R, т.е.
.
Симметрична параллельность прямых, т.к. если 
// 
, то // . Симметрично отношение «быть равным» на любом множестве или «быть взаимнопростым на N».
Отношение R симметрично тогда и только тогда, когда R=R-1
4. Если для несовпадающих элементов 
верно отношение 
, но ложно 
, то отношение антисимметрично. Можно сказать иначе:
и 
.
Антисимметричными являются отношения «быть больше», «быть делителем на N», «быть младше».
5. Бинарное отношение R называется транзитивным, если для любых трех элементов 
из того, что пары (a, b) и (b, c) принадлежат R, следует, что пара (a, c) принадлежит R:
и 
Транзитивны отношения: «быть больше», «быть параллельным», «быть равным» и др.
6. Бинарное отношение R антитранзитивно, если оно не обладает свойством транзитивности.
Например, «быть перпендикулярным» на множестве прямых плоскости ( 
, 
, но неверно, что 
).
Т.к. бинарное отношение может быть задано не только прямым перечислением пар, но и матрицей, то целесообразно выяснить, какими признаками характеризуется матрица отношения R, если оно: 1) рефлексивно, 2) антирефлексивно, 3)симметрично, 4) антисимметрично, 5) транзитивно.
Пусть R задано на 
, 
.
1. Если R рефлексивно, то для любого 
имеет место 
, т.е. оно выполняется для всех пар 
. В матрице этим парам соответствуют элементы Cii. Они составляют главную диагональ. Следовательно, главная диагональ матрицы рефлексивного отношения содержит только единицы.
2. R антирефлексивно, если ни для какого 
не выполняется . Из этого следует, что главная диагональ матрицы антирефлексивного отношения содержит только нули.
3. R симметрично, если для пары 
из следует 
, т.е. для любой пары отношение R либо выполняется в обе стороны, либо не выполняется вообще. Таким образом, если в матрице стоит единица на пересечении i - ой строки и j - ого столбца, т.е. Cij =1, то она должна стоять и на пересечении j - ой строки и i - ого столбца, т.е. Cji =1, и наоборот, если Cji =1, то Cij =1. Таким образом, матрица симметричного отношения симметрична относительно главной диагонали.
4. R антисимметрично, если из и следует: 
. Это означает, что в соответствующей матрице ни для каких i, j не выполняется Cij = Cji =1. Таким образом, в матрице антисимметричного отношения отсутствуют единицы, симметричные относительно главной диагонали.
5. Бинарное отношение R на непустом множестве A называется транзитивным если и . Для транзитивности отношения R необходимо и достаточно, чтобы 
,
Пример. 
Если 2<3 и 3<4 , то 2<4 Транзитивны отношения «быть параллельным», «быть больше», «быть равным».
Пример 
, т.е. R – транзитивно
Бинарное отношение R антитранзитивно, если для любых трех элементов не выполняется условие транзитивности на множестве прямых (
,но неверно, что 
).
Рефлексивное, транзитивное и симметричное бинарное отношение R на множестве А называется эквивалентностью на А.
Вышеприведенное условие должно выполняться для любых элементов матрицы. И, наоборот, если в матрице R имеется хотя бы один элемент Cij =1, для которого данное условие не выполняется, то R не транзитивно.
Дата добавления: 2015-08-21; просмотров: 8301;