2 Відношення та операції над ними

2.1 Мета заняття

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

2.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1-10] з таких питань: декартів добуток множин; бінарні та n-арні відношення; область визначення та область значень відношень; способи задання відношень; операції над відношеннями; властивості бінарних відношень; класи бінарних відношень (відношення еквівалентності, порядку і толерантності).

Підготовка і виконання практичного заняття проводиться за два етапи. Перший етап пов’язаний з вивченням на практичних прикладах наступних основних понять і визначень теорії відношень: декартів (прямий) добуток множин; декартова степінь; декартів квадрат, декартів куб множин; -арне відношення; унарне, бінарне відношення; область визначення відношення; область значень відношення; відповідність; повне, тотожне, порожнє відношення; матричний спосіб задання відношень; переріз відношень; фактор-множина; об’єднання, перетин, різниця, доповнення відношень; симетричне (обернене) відношення; композиція відношень; рефлексивні, антирефлексивні, симетричні, антисиметричні, асиметричні, транзитивні, антитранзитивні відношення; відношення еквівалентності; клас еквівалентності; система представників; відношення часткового порядку; частково впорядкована множина; порівнянні та непорівнянні елементи відношень; лінійний порядок; лінійно впорядкована множина (ланцюг); відношення нестрогого і строгого порядку; відношення толерантності.

Під час виконання першого етапу студент повинен запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень.

Другий етап виконання практичного заняття пов’язаний з розв’язуванням практичних завдань, що надаються у підрозділі 2.3, на основі запропонованих типових прикладів (див. підрозділ 2.4).

2.3 Контрольні запитання і завдання

2.3.1 Контрольні запитання

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. Яке відношення в множині називається відношенням нестрогого порядку, а яке називається відношенням строгого порядку?

2.3.2 Контрольні завдання

Завдання 1. Знайти декартів добуток множин ,і.

Завдання 2. Нехай і, де множина натуральних чисел. З яких елементів складаються множини і?

Завдання 3. Побудувати граф і записати список елементів для відношення, яке визначене на множині наступною матрицею

	1	1	1
	1	0	1
	1	1	1

Завдання 4. Побудувати матрицю і записати список елементів для відношень і, що задаються графічно на рис. 2.1.

а) відношення б) відношення

Рисунок 2.1  Відношення і, що задаються графічно

Завдання 5.

Дано дві множини іі визначене бінарне відношення.

Для даного відношення:

а) записати область визначення і область значень;

б) визначити переріз за кожним елементом з ;

в) визначити переріз за підмножинами і;

г) записати матрицю і нарисувати граф;

д) визначити симетричне (обернене) відношення .

Завдання 6. Нехай  множина студентів,  множина дисциплін. Співвідношення , деі, означає «студентвивчає дисципліну». Дайте словесний опис областей визначення і значень, перерізів і оберненого відношення, отриманих у завданні 5.

Завдання 7. Нехай задане відношення і відношенняна множині(і):;.

Знайти відношення,,,,,,і визначити їхню потужність.

Завдання 8. Нехай ,,,і нехай відношення,,визначені таким чином,,. Визначити,,.

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

Завдання 10. Нехай .

Задати відношення і відношенняза допомогою графів, знайти матрицю оберненого відношення. Перевірити за допомогою матриці відношення, чи є воно рефлексивним, симетричним, антисиметричним, транзитивним.

Завдання 11. Показати, що бінарне відношення є рефлексивним, симетричним і нетранзитивним.

Завдання 12. Нехай задана множина , відношення на , де

;

;

;

Яке з відношень є транзитивним? Яке з відношеньє антисиметричним?

Завдання 13. Нехай задана множина . Опишіть відношення, яке задане на множині, що є рефлексивним і симетричним, але не є транзитивним.

Завдання 14.

Нехай і нехай відношенняє множинаПоказати, що відношенняє відношенням еквівалентності.

Завдання 15. Яке з наведених нижче відношень є відношенням часткового порядку на множині?

а)  множина всіх людей, а відношення визначене як, якщостаріше за;

б)  множина всіх громадян України, а відношення визначене як, якщомає більший номер картки соціального страхування, ніж;

в)  множина цілих чисел, визначено як, якщо.

Завдання 16. Для відношення строгого порядку «» на множиніматриця має вигляд

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

Записати відношення у вигляді списку елементів.

Завдання 17. Нехай задане відношення на множині цілих чисел :.

Перевірити, чи є це відношення частково впорядкованим.

Завдання 18. На множині прямих на площині розглянемо відношення перпендикулярності прямих. Визначити, чи буде це відношення відношенням еквівалентності на цій множині.

Завдання 19. На множині прямих на площині розглянемо відношення паралельності прямих. Визначити, чи буде це відношення відношенням еквівалентності на цій множині.

Завдання 20. Розглянемо множину кіл, центри яких перебувають на осі абцис у точках таких, що, де цілі числа. Знайти потужність класів розбивки відношень рівності кіл (кола рівні, якщо їхні радіуси рівні).

2.4 Приклади аудиторних і домашніх завдань

Завдання 1. Перелічити елементи декартова добутку двох множин: і.

Розв’язок.

;

.

Завдання 2. Нехай Х – множина точок відрізка , аY – множина точок відрізка . Визначити множину точок.

Розв’язок.

є множиною точок квадрата з вершинами в точках.

Завдання 3. Нехай задані множини ,,,. Визначити потужність множині.

Розв’язок.

Потужність множини дорівнює, де,,,. Потужність множинидорівнює.

Завдання 4. Скласти 16 різних відношень на множині .

Розв’язок.

Із двох елементів 0 і 1 () можна скластинаборів.

Усього відношень на даних наборах можна скласти .

Перелічимо ці відношення: ,,,,,,,,,,,,,,,.

Завдання 5. Знайти область визначення та область значень відношень:

а) ;

б) ,

с) , де множина дійсних чисел.

Розв’язок.

Для а) область визначення відношення  це множина , область значень це множина ; для б) область визначення це множина , область значень це множина ; для с) область визначення це множина , область значень (множина дійсних чисел).

Завдання 6. Нехай . Задати в явному виді (списком) і матрицею відношення, задане на множині, якщоозначає «бути строго менше».

Розв’язок.

Відношення , як множина, містить усі пари елементівзтакі, що. Тоді задане у вигляді списку відношення буде мати виглядМатриця відношенняпредставлена на рис. 2.2.

Рисунок 2.2  Матриця відношення

Завдання 7. Побудувати на множині граф відношення

.

Розв’язок.

Граф відношення представлений на рис. 2.3.

Рисунок 2.3  Граф відношення

Завдання 8. Нехай задані множини ;і таке відношення на цих множинах:

. Визначити фактор-множину і переріз відношення за підмножиною.

Розв’язок.

Очевидно, ;та ін.

Випишемо переріз за всіма елементами множини у такому вигляді:

Об’єднання множин другого рядка утворять фактор-множину .

Об’єднання перерізів за елементами підмножини є перерізомвідношенняза підмножинами, тобто.

Так, для ,.

Завдання 9. Нехай задані два відношення:

и

Знайти композицію , переріз.

Розв’язок.

Композиція відношень ібуде дорівнювати:

Переріз .

Завдання 10. Нехай ,,,і нехай відношення ,,визначені таким чином,,. Визначити,,,.

Розв’язок.

, ,

,

.

Завдання 11. Нехай , відношення на , де

;

;

;

Яке з відношень є рефлексивним? Яке з відношень є симетричним?

Розв’язок.

Рефлексивним є відношення (має елементи).

Симетричним є відношення і.

Завдання 12. Нехай задана множина і нехай выдношеннявизначено у вигляді

.

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

Розв’язок.

не є рефлексивним, тобто , але.

не є симетричним, оскільки , але.

не є антисиметричним, оскільки і, але.

не є транзитивним, тому що і, але.

Отже, відношення не є відношенням еквівалентності.

Завдання 13. Яке з наведених нижче відношень є відношенням часткового порядку на множині?

а) ;

б) ;

в) ;

г) .

Розв’язок.

Відношенням часткового порядку на множині є відношенняз пунктів а) і г).

Завдання 14. Для відношення нестрогого порядку («бути дільником») на множинізнайти матрицю відношення.

Розв’язок.

Матриця відношення має такий вигляд

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