double arrow

Транзитивное замыкание отношений

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

Определение 11. Пусть отношение R задано на декартовом квадрате A2 некоторого множества A. Транзитивным замыканием отношения R называется новое отношение , состоящее из кортежей , для которых выполняется:

  • либо кортеж ,
  • либо найдется конечная последовательность элементов , такая, что все кортежи принадлежат отношению R.

Очевидно, что .

Пример 7. Пусть множество представляет собой следующее множество деталей и конструкций:

= {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось}

причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением ("непосредственно используется в") и состоит из следующих кортежей:

Конструкция Где используется
Болт Двигатель
Болт Колесо
Гайка Двигатель
Гайка Колесо
Двигатель Автомобиль
Колесо Автомобиль
Ось Колесо

Сейчас читают про: