Список літератури Основна

1. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987. - С.48-62.

2. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.33-41.

3. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.106-115.

Додаткова

4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990. - С.35-43, 68-73.

5. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование. – К.:Наукова думка, 1989. - С.35-50.

Для практичних занять

6. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001. – С.10-13.

Лекція 5. Відношення

Вступ

Лекція має за мету висвітлити початкові поняття з відношень і графіків відношень. Розглянуті визначення і n-арність відношень, типові відношення, множинні операції об’єднання, перетин, різниці, симетричної різниці, декартова добутку. Звернено повагу на ототожнення відношень і їх графіків, що часто використаємо, а також асоціативність декартова добутку відношень.

Лекція містить два підрозділи:

1. Основні поняття відношень

2. Множинні операції відношень

5.1. Основні поняття відношень

Визначення. Під n-арним відношенням чи n-відношенням ⁿ на множинах А₁, А₂, ..., А_n розуміється закон (характеристична властивість), що виділяє в декартовому добутку А₁₂..._n деяку підмножину ⁿ_1,...,An₁₂..._n, що називана (n-вимірним) графіком відношення ⁿ. Якщо А₁=А₂=...=А_n=A, то говорять про n-відношення ⁿ на множині А з графіком ⁿ_ⁿ.

Відношення, як і відповідності, часто позначають грецькими літерами, з індексами чи без них, і спеціальними символами =, .

Часто поняття n-відношення ототожнюється з його графіком, тобто під n-відношенням ⁿ на множинах А₁, А₂, ..., А_n розуміється сама підмножина:

ⁿ_{n}_A₂_n.

Якщо а₁, а₂,..., а_n)ⁿ_{1,.., An}, де а_j_j, j=1, 2,..., n, то говорять, що елементи а₁, а₂,..., а_n знаходяться у відношенні ⁿ ⁿ(a₁, a₂, ..., a_n), так що позначення (а₁, a₂, ..., a_n) ⁿ і ⁿ(a₁, a₂, ... , a_n) рівносильні.

Визначення. Послідовність =(а₁, a₂, ... , a_n)ⁿ_1,...,An називається елементом чи вектором n-відношення ⁿ. Відношення, графіки яких містять скінченні множини векторів, називають скінченними n-відношеннями. Якщо ⁿ_1,...,An=, то ⁿ- порожнє n-відношення (ⁿ), якщо ⁿ_{1, ..., An}=A₁₂_n, то ⁿ- універсальне n-відношення (ⁿ).

Тому що n-відношення ⁿ можна розглядати як підмножини декартова добутку А₁₂А_n, існують різні способи завдання n-відношень, аналогічні способам завдання множин. Так графік ⁿ_{1, ...,An} зручно задавати матрицею, рядками якої є вектори відношення ⁿ.

Приклад. ⁿ_{1, ..., An}={ ^j=(a₁ ^j, a₂ ^j, ... , a_n ^j|j=1, 2, ... , r} - множина усіх векторів, графік у матричній формі

ⁿ_{A1, ..., An}= a₁ ^j1 a₂ ^j1 ... a_n ^j1

a₁ ^ji2 a₂ ^j2 ... a_n ^j2

..................................

a₁ ^jr a₂ ^jr ... a_n ^jr

Відношення ¹ на множини А називають унарними, відношення ² на А, В - бінарними, відношення ³ на А, В, С - тернарними і т.д.

Унарне відношення ¹ на множини А є характеристичною властивістю деякої підмножини ¹_А - графіка даного відношення, таким чином, множина всіх унарних відношень на А збігається з множиною всіх підмножин множини А. Якщо А=n, то число унарних відношень на А дорівнює 2ⁿ.

Лема. Будь-якому n-відношенню  ⁿ на множинах А₁, А₂, ..., А_n відповідає унарне відношення ¹ на множини А₁₂_n таке, що виконується ¹() тоді і тільки тоді, коли для відношення виконується ⁿ(a₁ ^і, a₂ ^і..., a_n ^і), де =(a₁ ^і, a₂ ^і, ..., a_n ^і) - довільний вектор відношення  ⁿ.

Бінарне відношення  на множинах А і В визначається графіком _. Якщо елементи а і b знаходяться у відношенні , то поряд з позначеннями (а, b)_ і (a, b) використовується й аb.

Приклад. а)А=2, 3, 5 _= 2 2

B=2, 3, 4, 5, 6 2 4

3 3

3 6

5 5

б) Таблиця 5.1

	2	3	4	5	6
2	х		х		х
3		х			х
5				х

в)

Рис. 5.1. Бінарне відношення _

Графік тернарного відношення ³ має вигляд ³_{C}С.

З кожною бінарною операцією F(х,у), зокрема з арифметичними операціями “” ”””””” і іншими, може бути зв'язане тернарне відношення ³ таке, що ³(х, у, z) тоді і тільки тоді, коли F(х, у)=z.

Найбільше часто вживаються бінарні відношення (графіки на площині).

Якщо для бінарного відношення ²_А1,А2А₁₂ множини А₁ і А₂ рівні А, то говорять, що визначено відношення на множині А, тобто ²_А.

Визначення. Відношення на множині А називається

а) повним, якщо ²_А=А²;

б) порожнім і позначається 0_А, якщо ²_А=;

в) відношенням рівності і позначається Е_А, якщо і тільки якщо ²_А містить всі можливі пари з однаковими компонентами;

г) відношенням нерівності, якщо ²_А не містить ні однієї пари з однаковими компонентами.