МІНІСТЕРСТВО ОСВІТИ І НАУКИ,МОЛОДІ ТА СПОРТУ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”

Відношення, їх властивості та операції над ними методичні вказівки

до виконання практичних робіт

з дисципліни “Комп’ютерна дискретна математика”

для студентів напряму

6.050103 “Програмна інженерія”

Затверджено на засіданні кафедри програмного забезпечення Протокол № 12 від 16.05.2012 р.

Львів – 2012

Відношення, їх властивості та операції над ними. : Методичні вказівки до виконання практичних робіт з дисципліни “Комп’ютерна дискретна математика” для студентів спеціальності “Програмне забезпечення автоматизованих систем” / Укл.: П. В. Сердюк – Львів: Видавництво Національного університету “Львівська політехніка”, 2012. – 31 с.

Укладач П. В. Сердюк., канд. тех. наук, ст. викл.

Відповідальний за випуск Федасюк Д.В., д-р тех. наук, проф.

Рецензенти Денисюк П.Ю., канд. тех. наук, доц. кафедри САПР

Тушницький Р.Б., канд. тех. наук, ст.викл. кафедри ПЗ

Зміст

1.Вступ 4

2.Поняття відношення. Задання відношень 4

3. Властивості бінарних відношень 7

4. Операції над відношеннями 9

5. Відношення еквівалентності 12

6. Відношення часткового порядку 14

7. Приклади виконання практичних завдань 17

8. Завдання до виконання 21

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

Список літератури 27

Відношення, їх властивості та операції над ними

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

1. Вступ

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

2. Поняття відношення. Задання відношень

Означення 2.1. Відношенням R на множині називається деяка підмножина R. Іншими словами, якщо відношення R складається з сукупності , то очевидно.Загалом відношення використовують для позначення властивостей певних груп об’єктів, чисел чи сутностей. Якщо відношення R має певні властивості, то, якщо елемент , то він володіє властивостями відношенняR.

Приклад 2.1. Нехай відношення A є підмножиною декартового простору AR², і володіє властивістю . Тоді, якщо пара (a,b) , то точка (a,b) лежить на прямій ▲

Приклад 2.2. Нехай відношення R має властивість: “X думає, що Y любить Z” визначених на певній множині { Оксана, Наталя, Володя }:

X	Y	Z
Оксана	Володя	Наталя
Наталя	Володя	Наталя
Наталя	Наталя	Володя
Володя	Наталя	Наталя

Якщо відношення задано на декартовому добутку двох множин, то воно називається бінарним, трьох множин – триарним, n множин – n-арним. Бінарні відношення RАхВ здебільшого розглядають за умови А=В.

Означення 2.2. Відношенням на множині А називають підмножину декартового квадрату множини А, тобто RА². Використовують запис аRb, якщо (а, b)R,та запис аb,якщо (а, b)R.

Приклад 2.3. Нехай A={0, 1, 2}, В={а, b} та задано відношення R={(0,а), (0,b), (1,а), (2,b)}. Отже, 0Ra, оскільки (0,а) R, але 1b, оскільки (1,b)R). ▲

Представлення відношення

Задати бінарне відношення на множині А можна за допомогою списку пар, булевої матриці, матриці взаємин, таблиці фактів чи певної властивості відношення. Також відношення можна звести до орієнтованого графа, який можна подати різними способами, що буде розглянуто в методичних вказівках до основ теорії графів.

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

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

Приклад 2.4. Нехай A={1, 2, 3, 4, 6}, а відношення R задано властивістю

R={(а,b)|а націло ділиться b}.

Як записати відношення R впорядкованими парами елементів ?

Очевидно, що R={(1,1), (2,1), (2,2), (3,1), (3,3), (4,1), (4,2), (4,4), (6,1), (6,2) , (6,3), (6,6)}. ▲

Матричний спосіб ґрунтується на поданні відношення R відповідною йому прямокутною булевою матрицею. Розглянемо , де множина , а множина.

Відповідна булева матриця

складатиметься з елементів

де кількість рядків матриці рівна кількості елементів множини A, а кількість стовбців рівна кількості елементів множини B , ,.

Приклад 2.5. Для представлення матричним способом бінарних відношень, зручно вставити значення відповідного i-го елементу матриці A навпроти відповідних стовбців чи рядків. Для наведеного у прикладі 2.4 відношення матриця має такий вигляд:

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

Приклад 2.6. Розглянемо відношення R: “X є одногрупником Y” і відношення S: “X подобається Y” визначених на множині студентів { Володя, Ігор, Степан, Наталя, Олена, Оксана}. Відомо, що Володя і Наталя вчаться у групі ПI-11, а Степан і Олена у групі у групі ПI-12, Наталя подобається Володі і Степану, а Володя подобається Наталі і Олені. Представимо відношення між ними у вигляді таблиці фактів:

X	Y	Відношення
Володя	Наталя	“є одногрупником”, “подобається”
Володя	Олена	“подобається”
Наталя	Володя	“є одногрупником”, “подобається”
Наталя	Степан	“подобається”
Олена	Степан	“є одногрупником”
Степан	Олена	“є одногрупником”

Матриця відношень будується подібним чином до булевої матриці, тільки її елементами у i-му рядку та j-му стовбці будуть відношення, у які входять ці елементи.

Приклад 2.7. Побудуємо матрицю взаємин для відношення у попередньому прикладі.

	Володя	Наталя	Олена	Степан
Володя		“одногрупник” “подобається”	“подобається”
Наталя	“одногрупник”, “подобається”			“подобається”
Олена				“одногрупник”
Степан			“одногрупник”

Очевидно, якщо розглядати матрицю взаємин і таблицю фактів лише для одного відношення, то вони будуть фактично ідентичні булевій матриці і списку впорядкованих пар, але займатимуть більше місця у пам’яті комп’ютера.

Спеціальні відношення

Означення 2.3. Повним відношенням R на множині називають відношення, для якого , тобтоR повністю співпадає з множиною .

Означення 2.4. Порожнім відношенням R на множині називають відношення, для якого .

Означення 2.5. Тотожнім бінарним відношенням R на множині A називають відношення, для якого .

Означення 2.6. Відношення R^-1 називається оберненим до відношення R, якщо bR^-1a тоді і тільки тоді, коли aRb. Очевидно, що (R-1)^-1=R.

Означення 2.7. Відношення R^-1 називається оберненим до відношення R, якщо bR^-1a тоді і тільки тоді, коли aRb. Очевидно, що (R-1)^-1=R.

Приклад 2.8. Наприклад, для відношення “більше або дорівнює” оберненим є відношення “менше або дорівнює”, для відношення “ділиться на” – відношення “є дільником”. ▲