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

ВІДНОШЕННЯ, ЇХ ВЛАСТИВОСТІ ТА ОПЕРАЦІЇ НАД НИМИ

МЕТОДИЧНІ ВКАЗІВКИ

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

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

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

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

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

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

ВІДНОШЕННЯ, ЇХ ВЛАСТИВОСТІ ТА ОПЕРАЦІЇ НАД НИМИ

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

Вступ

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

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

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

Приклад 2.1. Нехай відношення A є підмножиною декартового простору A R ², і володіє властивістю . Тоді, якщо пара (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)}. Отже, 0 Ra, оскільки (0, а) R, але 1 b, оскільки (1,b) R). ▲