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

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

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

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

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

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

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

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

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