Глава 3. Бинарные отношения на множествах

3.1. Определение и способы задания отношений

Определение. n-местным (n-арным) отношением  на множествах X₁, X₂,…, X_n называют любое подмножество их декартова произведения X₁ X₂… X_n .

Поскольку отношения представляют собой множества специального вида, то между ними определены все предметные и логические операции, введенные ранее для обычных множеств.

Задание отношения  эквивалентно введению на X₁ X₂…X_n некоторого предиката Р(х₁, х₂, …, х_n) (логического условия), для которого: (Р(х₁, х₂, …, х_n) = true) ((х₁, х₂, …, х_n)  ) .

При n = 1 отношение называют унарным, смысл его заключается в задании подмножества исходного множества X.

В случае n = 2 отношение называют бинарным, оно задает на декартовом произведении X₁  X₂ множество упорядоченных пар (х,у), где х  X₁, у  X₂.

Поскольку наиболее распространёнными являются бинарные отношения, у которых X₁ = X₂ = X, в дальнейшем будут рассматриваться только отношения на декартовом квадрате X² = X  X. При необходимости исходное множество дополнительно указывается нижним индексом: _X .

Для обозначения бинарных отношений применяется инфиксная система записи, при которой знак отношения помещается между элементами пары. Если пара (х, у) (х  X, у  X) принадлежит отношению , то это обозначается как х_X у, если (х,у) не принадлежит  – то ( х _X у).

Определение. Полным называют отношение, содержащее весь декартов квадрат X² = X  X. Обозначается оно U_X.

Диагональным называют бинарное отношение, содержащее все пары вида (х, х), где х  X. Обозначается оно id_X.

Для единичного исходного множества (X = 1) id_X = U_X. При X >1 всегда справедливо строгое включение: id_X  U_X.

Отношения на конечных множествах могут быть заданы следующими способами.

3.1.1. Перечисление (список пар)

В этом случае все упорядоченные пары (х,у), образующие множество, указываются в виде некоторой последовательности (списка). Положение пар в списке может быть любым.

Пример 1. Х = Е₂ = {0, 1}. Х ² = {(0; 0); (0; 1); (1; 0); (1; 1)}. Зададим отношение  списком:  = {(0; 0); (1; 0); (1; 1)}. В отношение не включен только один из элементов Х ² — пара (0; 1).

3.1.2. Матрица

Декартов квадрат Х ² = Х  Х множества Х, где определено бинарное отношение, может быть задан в виде матрицы, где, например, строки соответствуют первому элементу пары, а столбцы — второму элементу. Если пара (х, у) входит в отношение , то элемент матрицы Р на пересечении строки, соответствующей х, и столбца, соответствующего у, принимается равным 1. Если пара (х, у) не входит в , то данный элемент равен 0. В тех случаях, когда нельзя сказать ни х у ни (х   у), в матрице будем ставить прочерк «–».

Пример 2. Задать матрицу отношения из примера 1.

Решение имеет вид:

X \ y	0	1
0	1	0
1	1	1

Матричное задание отношений более наглядно при изучении их свойств.

Для того чтобы ввести отношения на бесконечных множествах, как и при задании самих множеств, необходимо применять и другие способы.