2.26.5. Переход к обратному отношению

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

Пример 2.26

Если отношение , заданное на множестве означает «быть начальником», то обратное ему отношение означает «быть подчинённым». Запись или можно прочитать как является начальником . Тогда соотношение или читается как является подчинённым .

2.26.6. Произведение отношений

Пусть некоторое множество объектов, накотором заданы бинарные отношения , и , . Произведение отношений и определяется следующей высказывательной формой:

.

Следовательно, соотношение (или ) равносильно тому, что существует такой элемент , для которого выполнено и .

Пример 2.27

Допустим, что – множество людей, на котором заданы бинерные отношения , и , . Пусть отношение означает «быть женой», а отношение «быть отцом». Соотношение (или ) означает, что является женой , а соотношение (или ) означает, что является отцом . Тогда означает «быть женой отца», т.е. «мать» или «мачеха». Запись (или можно интерпретировать, как элемент является женой отца элемента , т.е. матерью элемента или мачехой.

Пример 2.28.

Домустим, что на множестве как на множестве людей заданы отношения , и , , означающие следующее: «быть братом», а «быть родителем». Тогда соотношение (или ) читается как является братом , а соотношение (или ) – является родителем . Тогда отношение означает «брат одного из родителей» или «дядя» а соотношение (или ) соответствует « является дяей .

Раньше в русском языке (так до сих пор в польском) различались дядя – брат отца (Стрый) и дядя – брат матери (вуй). Это оттличие легко формулируется в терминах произведения отношений.

Пример 2.29

Пусть отношение «быть братом», «быть отцом», «быть матерью». Все эти бинарные отношения заданы на множестве :

, и , , , .

Тогда (или ) – брат отца (или Стрый), а (или ) – брат матери (или вуй).

2.26.7. Транзитивное замыкание

Как и в предыдущих разделах рассмотрим множество с заданным на нём бинарным отношением: , .

Если существует , такой, что выполняется соотношение и (или и ), то существует отношение , заданное но множестве , называемое второй степенью отношения : , т.е. выполняется соотношение или . Если существует цепочка из двух элементов , такая что , и , то или выполняется соотношение , то на множестве задано отношение, называемое третьей степенью отношения . Если существует цепочка элементов, , , …, , такая, что , , …, , то или , на множестве задано отношение, называемое той степенью отношения .

Определение

Транзитивным замыканием называется объединение всех степеней отношений : .

Для отношений, обладающих свойством транзитивности, выполняется равенство: , поэтому для этих отношений .

Вопросы к разделу № 2

1. Запишите высказывательные формы операций над множествами.

2. Начертите диаграммы Эйлера операций над множествами.

3. Что называется покрытием множества?

4. Что называется дизъюнктивным покрытием множества?

5. Дайте определение разбиения множества.

6. Напишите высказывательную форму строгого и нестрогого включения множеств.

7. Начертите диаграммы Эйлера строгого и нестрогого включения множеств.

8. Перечислите свойства операций над множествами.

9. Дайте определение упорядоченного множества.

10. Запишите высказывательную форму декартова произведения множеств.

11. Дайте определение декартовой степени множества.

12. Дайте определение сечения и проекции.

13. Что называется соответствием?

14. Дайте определение композиции соответствий.

15. Дайте определение отображения.

16. Какие виды отображений Вы знаете?

17. Дайте определение функционального отображения.

18. Какое отображение называется инъективным? Сюрьективным? Биективным?

19. Что такое оператор?

20. Дайте определение функционала.

21. Дайте определение линейного оператора.

22. Дайте определение отношения.

23. Какие виды отношений Вы знаете?

24. Дайте определение бинарного отношения.

25. Перечислите способы задания бинарных отношений.

26. Перечислите свойства бинарных отношений.

27. Дайте определение отношения толерантности.

28. Дайте определение отношения порядка.

29. Что Вы понимаете под изоморфизмом отношений?

30. Какое отношение порядка называется решёткой?

31. Приведите примеры решёток.

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

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

34. Запишите высказывательную форму произведения отношений.

35. Что называется степенью отношений?

36. Что называется транзитивным замыканием?