2.5.1 Правила побудови матриць відношень

Правила побудови матриць відношень: , , , , по відомій матриці відношення :

Матриця доповнення _ в матриці вихідного відношення замінити одиниці нулями, а нулі - одиницями.

Матриця оберненого відношення _ проставити в ній одиниці, які симетричні щодо головної діагоналі відповідним одиницям вихідної матриці відношення .

Матриця складеного відношення _ для кожної одиниці вихідної матриці відношення , що стоїть в -тому рядку і -тому стовпці , в -тому рядку матриці , проставити одиниці в ті -ті стовпці, у яких є одиниці в -тому рядку вихідної матриці.

Матриця транзитивного замикання нетранзитивного відношення . Для її побудови треба виконати цикл (один або декілька) наступних дій:

а) для кожної одиниці у матриці відношення , що стоїть в -тому рядку і -тому стовпці , в -тому рядку матриці проставити одиниці в тих -тих стовпцях, у яких є одиниці в -тому рядку, а також в -тому рядку вихідної матриці;

б) отриману матрицю відношення приймають за вихідну і повторюють процедуру а), виконуючи таким чином наступний цикл обчислень доти, поки матриця не перестане змінюватися, тобто поки в деякому циклі обчислень вихідна і обчислена матриці не збіжаться.

Якщо відношення транзитивне, то матриця його транзитивного замикання збігається з матрицею вихідного відношення, тобто .

Матриця рефлексивного замикання _ побудувати матрицю транзитивного замикання, а потім в отриманій матриці замінити нулі на головній діагоналі, якщо такі є, на одиниці.

Якщо відношення рефлексивно, то матриця рефлексивного замикання збіжиться з матрицею транзитивного замикання, тобто .

Приклад. Які властивості відношення , заданого матрицею на рис. 2.5? Виконати операції над відношенням . Побудувати матриці отриманих відношень.

Розвязання:

Рисунок 2.5 - Відношення

Список відношення

.

Визначимо властивості відношення :

а) нерефлексивне, тому що головна діагональ матриці відношення не містить тільки одиниці;

б) не антирефлексивне, тому що головна діагональ матриці відношення не містить тільки нулі;

б) несиметричне, тому що матриця відношення не симетрична щодо головної діагоналі;

в) не антисиметричне, тому що в матриці відношення відсутні одиниці, симетричні щодо головної діагоналі;

г) нетранзитивне, тому що існують пари, для яких порушується умова транзитивності, наприклад, , , але .

Виконаємо операції над :

; ; ;

(рис. 2.6,а);

(рис. 2.6,б);

(рис. 2.6,в).

Для одержання транзитивного замикання виконаємо процедуру виявлення нетранзитивності для вихідного відношення. Виявлений тільки один випадок порушення транзитивності , , але . Додавши цю пару до , або скориставшись визначенням, одержимо:

.

Перевірка на транзитивність відношення не виявляє в ньому порушення транзитивності, тому

(рис. 2.6,г).

Рефлексивне замикання, відповідно до визначення

(рис. 2.6,д).

Рисунок 2.6 - Матриця властивостей відношення