Способы задания бинарных отношений

По определению отношения R между элементами множества A есть всякое подмножество декартова произведения A ´ A, то есть множество, элементами которого являются упорядоченные пары. Поэтому способы задания отношений, по существу, такие же, как и способы задания множеств.

Отношение R на множестве A можно задать, перечислив все пары элементов, взятых из множества A и связанных этим отношением.

Формы записи при этом могут быть различными.

ПРИМЕР. Некоторое отношение R на множестве Х = {4, 5, 6, 7, 9}можно задать, записав множество пар: {(5,4),(6,4),(6,5),(7,4),(7,5),(7,6),(9, 4),(9,5),(9,6),(9,7)}.То же отношение можно задать при помощи графа.

Отношения на конечном множестве Х можно представлять наглядно, при помощи особых чертежей, состоящих из точек, соединенных стрелками. Такие чертежи называют графами.

ПРИМЕР. Построим граф отношения «меньше», заданного на множестве Х = {2, 4, 6, 8}. Для этого элементы множества Х изобразим точками (их называют вершинами графа), а отношение «меньше» – стрелкой.

                      2                                 4

                   8·                                       6

Рисунок 3.1 – Граф бинарного отношения «меньше»

ПРИМЕР. На том же множестве Х можно рассмотреть другое отношение – «кратно». Граф этого отношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе.

Рисунок 3.2 – Граф бинарного отношения «кратно»

Чаще отношение R на множестве A задают, указав характеристическое свойство всех пар элементов, находящихся в отношении R. Это свойство задается при помощи предложения с двумя переменными.

ПРИМЕР. Пусть заданы рассмотренные выше отношения «меньше» и «кратно», причем использована краткая форма предложений «число х меньше числа у» и «число х кратно числу у». Некоторые такие предложения можно записать используя символы. Например, отношения «меньше» и «кратно» можно было записать в таком виде: «х < у», «х у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или х – у = 3). Отношение между прямыми плоскости задают, используя символы: х // у, х ^ у.

Для отношения R, заданного на множестве A, всегда можно задать отношение R ^-1, ему обратное.

ПРИМЕР, если R – отношение “ х меньше у ”, то обратным ему будет отношение “ у меньше х ”.

Матрица бинарного отношения

Рассмотрим два конечных множества A ={ a ₁, a ₂,…, a _m} и B ={ b ₁, b ₂,…, b _n} и бинарное отношение . Определим матрицу  размера m × n бинарного отношения R по следующему правилу:

Полученная матрица содержит полную информацию о связях между элементами.

Любая матрица, состоящая из 0 и 1, является матрицей некоторого бинарного отношения.

ПРИМЕР. Матрица бинарного отношения , A ={1,2,3}, заданного графом отношения имеет вид