Способы задания бинарных отношений
Бинарные отношения
ОТНОШЕНИЯ
Многие задачи математики, техники и других областей человеческой деятельности получают удобную интерпретацию на языке теории отношений. Все арифметические операции — это по существу некоторые отношения между числовыми множествами.
Говорят, что задано бинарное отношение от множества X к множеству Y, если указан закон, ставящий в соответствие элементам множества X элементы множества Y.
Каждое бинарное отношение можно рассматривать как множество упорядоченных пар, у которых первый элемент принадлежит X, а второй принадлежит Y и соответствует данному x.
Если А – бинарное отношение, то соотношение хRу можно записать также в виде (х, у)Î R, где R Ì Х ´ Y.
R =
Элемент х называют п ервой координатой, а элемент у - вт орой координатой упорядоченной пары.
Пример. Рассмотрим
Пусть отношение R задается свойством “ х делится на у ”, т.е. тогда и только тогда, когда y является делителем x.
|
|
Частным случаем бинарных отношений является случай, когда множество X совпадает с множеством Y (). В этом случае говорят, что задано бинарное отношение в множестве X. ()
Бинарное отношение можно задать различными способами:
1) Перечислить все пары, связанные между собой отношением.
2) Указать общие свойства, характеризующие данное отношение. Это наиболее общий способ, позволяющий задать практически любые отношения.
3) Графический способ, или задание отношения с помощью графа. В этом случае элементы множеств X и Y обозначаются точками, а элементы, связанные отношениями, соединяются направленными стрелками (рис. 2.1а). В случае рисуется одно множество (рис. 2.1б).
а) | б) |
Рис.2.1. Граф бинарного отношения |
4) Матричный способ. При этом отношение описывается матрицей, количество столбцов которой соответствует количеству элементов множества X, а строк – Y. Элемент матрицы, находящийся на пересечении j столбца и i строки равен 1, если соответствующие элементы множеств X и Y связаны бинарным отношением, и 0 - в противном случае.
Если отношение R задано в множестве X, то матрица будет квадратной.
Если в матрице отношения возникает нулевой столбец, то это значит, что соответствующий элемент не связан ни с одним другим элементом этим отношением. То же самое можно сказать про нулевую строку.
Область определения отношения R – это подмножество всех элементов х множества Х,для которыхнайдется элемент y, связанный с данным элементом отношением R.
Область значения отношения R – подмножество всех элементов y множества У, для которых найдутся элементы x, связанные с y отношением R ().
|
|
Пример: |
Если область определения отношения совпадает с некоторым множеством X, то говорят, что отношение определено на X.
Заслуживают внимания три частных случая отношений в Х:
1) полное (универсальное) отношение Р = Х ´ X, которое имеет место для каждой пары элементов из Х (например, отношение «учиться в одной группе» на множестве студентов данной группы);
2) тождественное (диагональное) отношение Е, равносильное х=х (например, равенство на множестве действительных чисел);
3) пустое отношение, которому не удовлетворяет ни одна пара элементов из Х (например, отношение «быть братом» на множестве женщин).
Полному отношению соответствует матрица, все клетки которой заполнены единицами, тождественному - единичная матрица, пустому - нулевая матрица. Графы полного, тождественного и пустого отношений изображены на рис. 2.2 (для пустого отношения граф состоит из изолированных вершин).
а) | б) | в) |
Рис.2.2. Графы полного (а), тождественного (б) и пустого (в) отношений. |