2015-03-08
2072
Определение 4.1. Отношение 
называется транзитивным замыканием отношения 
, определенного на множестве M, тогда и только тогда, когда существуют такие 
, что 
.
Пример
На множестве N определено отношение 
. Тогда транзитивное замыкание этого отношения для значений 1<2<…<6 будет отношение 1<6. (Рисунок 4.1)
Рисунок 4.1
Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком».
Транзитивным замыканием отношения «иметь общую стену» для жильцов одного дома является отношение «жить на одном этаже».
Пример. Пусть R задано на M, 
. R транзитивно, если для любых a,b,с из аRb и bRс следует аRс. Вматрице такого отношения должно выполняться следующее условие: если в i-й строке стоит единица, например в j-й координате (столбце) строки, т.е. 
, то всем единицам в j-й строке (пусть этим единицам соответствуют k-е координаты такие, что 
) должны соответствовать единицы в i- й строке в тех же k -хкоординатах, т.е. 
(и, может быть, еще и в других координатах). Это условие иллюстрируется на рисунке 4.2, где кружком выделена единица , для которой производится проверка условия, а стрелками показана последовательность проверки данного условия.
В матрице транзитивного отношения это условие должно выполняться для любых 
таких, что . И наоборот, если в матрице R имеется хотя бы одна единица , для которой данное условие не выполняется, то R не транзитивно.
Рисунок 4.2
