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

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

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

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

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

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

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

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

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

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

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

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

Рішення:

	0	0	1
	0	1	0
	0	1	0

Рис. 2.12.

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

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

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

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

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

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

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

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

; ; ;

(див. матрицю на рис. 2.13,а);

(див. матрицю на рис. 2.13,б);

(див. матрицю на рис. 2.13,в).

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

.

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

(см. матрицю на рис. 2.13,г).

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

(див. матрицю на рис. 2.13,д).

	1	1	0			0	0	0			0	1	0			0	1	1			1	1	1
	1	0	1			0	1	1			0	1	0			0	1	0			0	1	0
	1	0	1			1	0	0			0	1	0			0	1	0			0	1	1

(а) (б) (в) (г) (д)

Рис. 2.13.

Вправи:

1. Назвати відношення: , , , , , якщо відношення ‑ це:

а) “бути сестрою”; б) “бути мамою”;

в) “бути начальником”; г) “бути колегою”.

2. На множинах , , і визначені відношення , і в такий спосіб:

;

;

.

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

а) і ; г) ;

б) і ; д) ;

в) і ; е) .

3. Нехай і . Опишіть відношення: ; ; ; .

4. На множині визначені відношення:

;

;

;

.

Опишіть відношення ; ; .

У вправах 5, 6, 7 і 8 установити істинність або хибність кожного з наведених нижче висловлень. Для кожного помилкового висловлення приведіть контрприклад.

5. Якщо відношення і рефлексивні, то кожне з відношень:

; ; і рефлексивне.

6. Якщо відношення і симетричні, то кожне з відношень:

; ; і симетричне.

7. Якщо відношення і антисиметричні, то кожне з відношень:

; ; і антисиметричне.

8. Якщо відношення і транзитивні, то кожне з відношень:

; ; і транзитивне.

9. На множині визначене відношення ‑ “бути менше”. Задати характеристичною властивістю і списком відношення: ; ; ; ; і . Визначити властивості цих відношень.

10. На множині задані відношення:

; ; .

Виконати операції над відношеннями . Тобто знайти: ; ; ; ; ; ; ; і , де ( ).

9. На рис. 2.14 схематично представлено розташування складських приміщень підприємства, які утворюють множину . На цій множині задати списком і матрицями відношення: ‑ “перебувати в одному приміщенні”; ‑ “мати загальну стіну”. Знайти транзитивне замикання відношень і .

Рис. 2.14.

9. Відношення ‑ “довести до відома ”, визначене на множині , представлено ланцюжком схематично (рис. 2.15). Обчислити транзитивне замикання відношення .

Рис. 2.15

9. На множині визначене відношення , яке задано матрицею (рис. 2.16,а). Які властивості має відношення ? Записати матрицю транзитивного замикання .

10. На множині визначені відношення і , які задані матрицями (рис. 2.16, б, в). Які властивості мають відношення і . Здійснити операції над відношеннями і . Які властивості мають отримані відношення?

	1	1	1	1			0	1	0	0			0	1	0	0
	0	0	1	1			1	0	1	0			1	0	0	1
	0	1	1	1			0	1	1	0			0	0	0	0
	0	1	0	0			1	0	0	0			0	1	0	0

(а) (б) (в)

Рис. 2.16.

9. Відношення задане матрицею (рис. 2.17 варіанти а ‑ г). Визначити властивості відношення . Виконати унарні операції над відношенням , визначити властивості отриманих відношень.

			с					с					с					с
	1	1	0			0	1	0			1	0	1			0	0	1
	0	1	0			1	0	0			0	1	0			0	1	0
	0	1	1			0	0	0			1	0	1			1	0	0

(а) (б) (в) (г)

Рис. 2.17.

9. Відношення і задані матрицями (рис. 2.18 варіанти а і б). Визначити властивості цих відношень. Виконати бінарні операції над відношеннями і . Визначити властивості отриманих відношень.

	1	1	0	1			0	0	0	1			0	1	0	0			0	1	0	0
	0	1	0	0			1	1	1	1			1	0	1	1			0	0	0	1
	1	0	1	0			0	0	1	0			0	1	1	0			0	1	0	0
	0	1	0	1			1	0	0	0			0	0	0	1			1	0	1	0

(а) (б)

Рис. 2.18