§ 2.2. Действия над бинарными отношениями

В этом параграфе мы определим действия над бинарными отношениями, которые опять приводят к бинарным отношениям.

1. Пересечение отношений называется отношение, которое содержит только общие для пары

Когда не имеют общих пар, т. е. не пересекаются, то говорят, что их пересечение пусто и записывают

Пример 2.1. Пусть матрицы отношений имеют вид

Тогда очевидно, что матрица отношения имеет вид

Таким образом, матрица отношения есть булево пересечение матриц отношений

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

Пример 2.2. Для отношений из примера 2.1 очевидно имеем

Таким образом, матрица отношения есть булева сумма матриц отношений

3. Разностью отношений называется отношение, состоящее из тех пар которые не содержатся в Частный случай разности двух отношений представляет собой операция взятия дополнения к отношению Р (см. ниже .

Пример 2.3. Для отношений из примера 2.1 имеем

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

Пример 2.4. Для отношений из примера 2.1 имеем

5. Дополнением называется отношение, состоящее из тех пар которые не входят в . Отношения образуют разбиение т. е. и

Пример 2.5. Для отношения Р из примера 2.1 имеем

6. Обратным отношением к отношению Р называется отношение, которое содержит пару тогда и только тогда, когда т. е.

Пример 2.6. Для отношения Р из примера 2.1

матрица обратного отношения является транспонированной к исходной матрице отношения Р.

7. Композицией (произведением) отношений называется отношение, которое содержит пару тогда и только тогда, когда существует такое, что т. е. : найдется такое, что

К частным случаям композиции относится квадрат отношения : найдется такое, что По индукции определяется степень отношения Р:

Тот факт, что означает, что существует цепочка элементов такая, что для

Пример 2.7. Для отношений из примера 2.1 композиция этих отношений имеет матрицу

Матрица композиции отношений есть булево произведение матриц этих отношений.

8. Сужением отношения Р на подмножество называется отношение на множестве В, которое состоит из всех тех пар таких, что . Другими словами, (.

Пример 2.8. Сужение отношений Р из примера 1 на подмножество В, состоящего из первого и третьего элементов, имеет матрицу

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

Отношение включения Р которое выполнено тогда и только тогда, когда каждая пара принадлежащая Р, принадлежит также и отношению