1.6. Операции над бинарными отношениями

Так как отношения на Х задаются подмножествами rIX´Y, для них определимы те же операции, что и над множествами: Объединение r1Èr2: r1Èr2={(х, у)| (х, у)Îr1 или (х, у)Îr2}.

Пересечение r1Çr2: r1Çr2={(х, у)| (х, у)Îr1 и (х, у)Îr2}. Разность r1\r2: r1\r2={(х, у)| (х, у)Îr1 и (х, у)Ï r2}. Дополнение : . Обратное отношение r -1: х r -1 у тогда и только тогда, когда уrх, r -1={(x, y)| (y, x)Îr}.

Пример 13.

Если r - «быть моложе», то r -1 – «быть старше».

6. Составное отношение (композиция) r1 · r2. Пусть заданы множества М1, М2 и М3 и отношения R1 I М1 ´ М2 и R2 I М2 ´ М3. Составное отношение действует из М1 в М2 посредством R1, а затем из М2 в М3 посредством R2, то есть (a, b) Î R1·R2, если существует такое с Î М2, что (а, с) Î R1 и (a, c) Î R2.

7. Транзитивное замыкание r°. Транзитивное замыкание состоит из таких и только таких пар элементов а и b из М, то есть (a, b)Îr°, для которых в М существует цепочка из (k+2) элементов М, k? 0, что а, с1, с2, …ck, b, между соседними элементами которой выполняется r. Другими словами а r с1, с1 r с2, …, сk r b.

Пример 14.

Для отношения «быть сыном» транзитивным замыканием является отношение «быть прямым потомком по мужской линии».

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 1.6. Операции над бинарными отношениями:

  1. Тема 3. Операции над понятиями
  2. 1.4. Логические операции с понятиями. Операции над классами (объемами понятий)
  3. Операции над понятиями (классами)
  4. Булевы операции над вопросами
  5. Логические операции над вопросами
  6. 12.2. ОПЕРАЦИИ НАД СЛУЧАЙНЫМИ СОБЫТИЯМИ
  7. 1.5.Векторы. Основные операции над векторами.
  8. Линейные операции над векторами в координатах.
  9. Операции над множествами.
  10. Свойства бинарных отношений.
  11. §12. Понятие бинарного отношения между элементами одного множества
  12. §1. Высказывания и операции над ними
  13. §4. Алгебра предикатов. Логические операции над предикатами
  14. 1.2. Операции над множествами. Диаграммы Эйлера-Венна