Меню
Главная
Случайная статья
Настройки
|
Транзитивное замыкание в теории множеств — это операция на бинарных отношениях. Транзитивное замыкание бинарного отношения R на множестве X есть наименьшее транзитивное отношение на множестве X, включающее R.
Например, если X — это множество людей (и живых, и мёртвых), а R — отношение «является родителем», то транзитивное замыкание R — это отношение «является предком». Если X — это множество аэропортов, а xRy эквивалентно «существует рейс из x в y», и транзитивное замыкание R равно P, то xPy эквивалентно «можно долететь из x в y самолётом» (хотя иногда придётся лететь с пересадками)
Пример
Пусть множество A представляет собой следующее множество деталей и конструкций:
A = {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось}
причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением R («непосредственно используется в») и состоит из следующих кортежей:
| Конструкция
|
Где используется
|
| Болт
|
Двигатель
|
| Болт
|
Колесо
|
| Гайка
|
Двигатель
|
| Гайка
|
Колесо
|
| Двигатель
|
Автомобиль
|
| Колесо
|
Автомобиль
|
| Ось
|
Колесо
|
Таблица 1. Отношение R.
Транзитивное замыкание состоит из кортежей (добавленные кортежи помечены жирным):
| Конструкция
|
Где используется
|
| Болт
|
Двигатель
|
| Болт
|
Колесо
|
| Гайка
|
Двигатель
|
| Гайка
|
Колесо
|
| Двигатель
|
Автомобиль
|
| Колесо
|
Автомобиль
|
| Ось
|
Колесо
|
| Болт
|
Автомобиль
|
| Гайка
|
Автомобиль
|
| Ось
|
Автомобиль
|
Таблица 2. Транзитивное замыкание отношения R.
Очевидный смысл замыкания R состоит в описании включения деталей друг в друга не только непосредственно, а через использование их в промежуточных деталях, например, болт используется в автомобиле, так как он используется в двигателе, а двигатель используется в автомобиле.
|
|