6. Операции над отношениями

Так как отношения являются частным случаем соответствий, то над ними выполняются те же операции, что и над соответствиями: 1) инверсия отношений; 2) композиция отношений.

Инверсией отношения называется отношение , образованное инверсиями пар отношения . еще называют обратным отношением.

Пример. На множестве задано отношение -«меньше или равно»:

- «больше или равно»

Композицией отношений и называется отношение , образованное композициями пар.

Пример. На множестве заданы отношения -«больше» и -«равно». Записать композицию этих отношений.

Отношения и могут быть заданы на разных множествах. Например, отношение -«больше» задано на множестве , а отношение -«равно» на множестве , т.е. , . Тогда , .

Так как отношения являются множествами, то над отношениями выполняются те же операции, что и над множествами: объединение, пересечение, дополнение, разность, сумма по mod 2.

Объединением (пересечением, разностью, симметрической разностью) отношений и называется объединение (пересечение, разность, сумма по mod 2) соответствующих им множеств.

Пример. На множестве заданы отношения -«больше или равно» и -«равно». Выполнить над этими отношениями операции объединения, пересечения, разности, суммы по mod 2.

Дополнением отношения (до ) называется разность .

Пример. На множестве задано отношение -«больше или равно». Записать дополнение отношения .

7. Свойства отношений

Основными свойствами отношений являются:

• рефлексивность

• антирефлексивность

• симметричность

• антисимметричность

• транзитивность

Рефлексивность

Отношение называется рефлексивным, если каждый элемент множества , на котором задано отношение , находится в этом отношении сам с собой, т.е. .

На графе рефлексивного отношения у каждой вершины есть петля.

Пример. Отношение - «меньше или равно», заданное на множестве является рефлексивным.

Антирефлексивность

Отношение называется антирефлексивным, если ни один элемент множества , на котором задано отношение , не находится в этом отношении сам с собой, т.е. .

На графе антирефлексивного отношения ни у одной вершины нет петли.

Пример. Отношение - «меньше», заданное на множестве является антирефлексивным.

Отношение, на графе которого у одних вершин есть петли, а у других нет, не является ни рефлексивным, ни антирефлексивным.

Симметричность

Отношение называется симметричным, если для любой пары , одновременно выполняется условие .

Граф симметричного отношения содержит только двойные ребра, а петли могут быть или не быть.

Пример. Отношение - «быть братом», заданное на множестве людей является симметричным. Пусть - между собой братья, а - никому не брат:

Антисимметричность

Отношение называется антисимметричным, если ни для какой пары различных элементов , одновременно не выполняется условие . Граф антисимметричного отношения содержит только одинарные ребра, а петли могут быть или не быть.

Пример. Отношение - «быть делителем», заданное на множестве является антисимметричным.

Если на графе есть и одинарные и двойные ребра, то отношение, заданное этим графом, не является ни симметричным, ни антисимметричным.

Транзитивность

Отношение называется транзитивным, если из того, что одновременно выполняются условия и следует и условие .

На графе транзитивного отношения если есть два последовательных ребра одного направления, то должно быть замыкающее ребро, идущее из начала первого ребра к концу второго.

Пример. Отношение - «меньше», заданное на множестве является транзитивным.

Антитранзитивного свойства нет.

Примеры отношений

1) Треба побудувати матрицю бінарного відношення „x_i  x_j” на підмножині цілих чисел Х = {1, 2, 3, 5, 6, 4 та визначити властивості відно­шення. Розв'язок у наступному. Маємо відношення R = (X, Q), де Q = (2, 1), (3, 1), (5, 1), (4, 1), (6, 1), (3, 2), (4, 2), (5, 2), (6, 2), (4, 3), (5, 3), (6, 3), (5, 4), (6, 4), (6, 5), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6). У кожному кортежі множини Q перший елемент більше або дорівнює другому. На матриці (рисунок 2-9) одиниці розташовані у клітинах, де перший елемент кортежа взято з елементів множини X, якими позначені рядки матриці, а другий елемент кортежа взято з елементів множини X, якими позначені стовпці матриці.

	1	2	3	4	5	6
1	1	0	0	0	0	0
2	1	1	0	0	0	0
3	1	1	1	0	0	0
4	1	1	1	1	0	0
5	1	1	1	1	1	0
6	1	1	1	1	1	1

Рис. Матриця бінарного відношення x_i  x_j

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

рефлексивність – тому, що у множині Q наявні всі кортежі з ХХ, з однаковими першим та другим елементами; на матриці це виглядає як наявність одиниць у всіх клітинах головної діагоналі;

несиметричність – тому, що є приклад, коли кортеж (нехай це буде кортеж (4,1)) є у складі множини Q, а симетричний кортеж (це буде кор­теж (1,4) там відсутній (на матриці клітина, симетрична відносно головної діагоналі міститиме 0);

антисиметричність – тому, що немає жодного прикладу, симетричних відносно головної діагоналі одиниць на матриці та кортежів у множині Q, у яких елементи є переставлені (це підсилена несиметричність, коли вона є, про несиметричність іноді не згадують, бо несиметричність присутня обов'язково);

транзитивність – тому, що немає жодного спростовуючего прикладу ланцюжка з двох кортежів у множині Q, таких, у яких однакові дру­гий елемент першого та перший елемент другого кортежа, для яких був би видсутній у множині Q кортеж, що складається з першого елемента першого кортежа та другого елемента другого кортежа. Це тому, що, якщо a  b, а b  c, то завжди a  c.

2) Треба побудувати матрицю бінарного відношення „мати однаковий залишок від ділення на 3” на підмножині цілих чисел Х = {1, 2, 3, 4, 5} та визначити властивості відношення. Розв'язок такий. Матрицю показано на рис. 2 – 10.

	1	2	3	4	5
1	1	0	0	1	0
2	0	1	0	0	1
3	0	0	1	0	0
4	1	0	0	1	0
5	0	1	0	0	1

Рис. Матриця бінарного відношення

„мати однаковий залишок від ділення на 3”

Властивості відношення – рефлексивність, симетричність, транзитивність.

3) Треба побудувати матрицю бінарного відношення „мати спільний дільник, відмінний від 1” на підмножині цілих чисел Х = { 1, 2, 3, 4, 5, 6} та визначити властивості відношення. Розв'язок – матрицю показано на рис. 2 – 11.

	3	2	5	6	4	1
3	1	0	0	1	0	0
2	0	1	0	1	1	0
5	0	0	1	0	0	0
6	1	1	0	1	1	0
4	0	1	0	1	1	0
1	0	0	0	0	0	0

Рис. Матриця бинарного відношення „мати спільний дільник, відмінний від 1”

Властивість відношення – симетричність і тільки. Транзитивність по­рушена наявністю спростовуючого прикладу: кортеж (2,6) присутній у множині кортежів, бо числа 2 та. 6 дбають спільний дільник 2, кортеж (6,3) створює ланцюжок з кортежем (2,3) і теж присутній у множині кортежів, бо у чисел є спільний дільник 3. Але кортеж, який будуємо з ланцюжка (2,3) відсутній у множині кортежів, бо числа 2 та 3 не мають спільного дільника, відмінного від 1.