Властивості бінарних відносин

Введення

1. Рефлексивність:

2. Слабка рефлексивність:

3. Сильна рефлексивність:

4. Антірефлексівность:

5. Слабка антірефлексівность:

6. Сильна антірефлексівность:

7. Симетричність:

8. Антисиметричність:

9. Асиметричність:

10. Сильна лінійність:

11. Слабка лінійність:

12. Транзитивність:

Рефлексивність, властивість бінарних (двомісних, двочленних) відносин, що виражає здійснимість їх для пар об'єктів з збігаються членами (так би мовити, між об'єктом і його "дзеркальним відображенням"): відношення R називається рефлексивним, якщо для будь-якого об'єкта х з області його визначення виконується xRx . Типові і найбільш важливі приклади рефлексивних відносин: відносини типу рівності (тотожності, еквівалентності, подібності тощо: будь-який предмет дорівнює самому собі) і відношення несуворого порядку (будь-який предмет не менше й не більше самого себе). Інтуїтивні уявлення про "рівність" (еквівалентності, подобі і т.п.), очевидним чином наділяють його властивостями симетричності і транзитивності, "змушують" і властивість Р., оскільки остання властивість випливає з перших двох. Тому багато вживані в математиці відносини, за визначенням Р. не володіють, виявляється природним довизначити таким чином, щоб вони ставали рефлексивними, наприклад, вважати, що кожна пряма або площина паралельна самій собі, і т.п.

Глава 1. Елементи теорії множин

1.1 Множини

Найбільш проста структура даних, що використовується в математиці, має місце у випадку, коли між окремими ізольованими даними відсутні будь-які взаємозв'язку. Сукупність таких даних є безліч. Поняття множини є невизначені поняттям. Безліч не володіє внутрішньою структурою. Безліч можна уявити собі як сукупність елементів, що володіють деяким загальним властивістю. Для того щоб деяку сукупність елементів можна було назвати множиною, необхідно, щоб виконувалися наступні умови:
Має існувати правило, що дозволяє визначити, чи належить зазначений елемент даної сукупності.
Має існувати правило, що дозволяє відрізняти елементи один від одного. (Це, зокрема, означає, що безліч не може утримувати двох однакових елементів).
Множини зазвичай позначаються великими латинськими літерами. Якщо елемент належить безлічі , То це позначається:

Якщо кожен елемент множини є також і елементом множини , То говорять, що безліч є підмножиною множини :


Підмножина безлічі називається власним підмножиною, якщо

Використовуючи поняття безлічі можна побудувати більш складні і змістовні об'єкти.

1.2 Операції над множинами

Основними операціями над множинами є об'єднання, перетин і різницю.
Визначення 1. Об'єднанням двох множин називається нова безліч

Визначення 2. Перетином двох множин називається нова безліч

Визначення 3. Різницею двох множин називається нова безліч

Якщо клас об'єктів, на яких визначаються різні множини позначити (Універсум), то доповненням множини називають різницю

1.3 Декартово добуток множин

Одним із способів конструювання нових об'єктів з вже наявних множин є декартово добуток множин.
Нехай і - Множини. Вираз виду , Де і , Називається впорядкованою парою. Рівність виду означає, що і . У загальному випадку, можна розглядати впорядковану n-ку з елементів . Впорядковані n-ки інакше називають набори або кортежі.
Визначення 4. Декартові (прямим) добутком множин називається безліч впорядкованих n-ок (наборів, кортежів) виду

Визначення 5. Ступенем декартового твори називається число множин n, що входять в це декартово твір.
Зауваження. Якщо все безлічі однакові, то використовують позначення
.

1.4 Ставлення

Визначення 6. Підмножина декартового добутку множин називається відношенням ступеня n (n-арним ставленням).
Визначення 7. Потужність множини кортежів, що входять у відношення , Називають потужністю відносини .
Зауваження. Поняття відношення є дуже важливим не тільки з математичної точки зору. Поняття відносини фактично лежить в основі всієї реляційної теорії баз даних. Як буде показано нижче, відносини є математичним аналогом таблиць. Сам термін "реляційне представлення даних", вперше введений Коддом [43], походить від терміна relation, понимаемом саме в сенсі цього визначення.
Т. до будь-яка множина можна розглядати як декартовій добуток ступеня 1, то будь-яка підмножина, як і будь-яка множина, можна вважати ставленням ступеня 1. Це не дуже цікавий приклад, який свідчить лише про те, що терміни "відношення ступеня 1" і "підмножина" є синонімами. Нетривіальність поняття відносини проявляється, коли ступінь відношення більше 1. Ключовими тут є два моменти:
По-перше, всі елементи відносини є однотипні кортежі. Однотипність кортежів дозволяє вважати їх аналогами рядків у простій таблиці, тобто в такій таблиці, в якій всі рядки складаються з однакового числа осередків та у відповідних осередках містяться однакові типи даних. Наприклад, відношення, яке складається з трьох наступних кортежів {(1, "Іванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000)} можна вважати таблицею, що містить дані про співробітників та їх зарплатах. Така таблиця буде мати три рядки і три колонки, причому в кожній колонці містяться дані одного типу.
На противагу цьому розглянемо безліч {(1), (1,2), (1, 2,3)}, що складається з різнотипних числових кортежів. Це безліч не є ставленням ні в , Ні в , Ні в . З кортежів, що входять у це безліч не можна скласти просту таблицю. Правда, можна вважати це безліч ставленням ступеня 1 на множині всіх можливих числових кортежів всіх можливих ступенів

,
але таке трактування нічого нового, в порівнянні з поняттям підмножини, не дає.
По-друге. За винятком крайнього випадку, коли відношення є саме декартово твір , Відношення містить у собі не всі можливі кортежі з декартового твору. Це означає, що для кожного відносини є критерій, що дозволяє визначити, які кортежі входять у відношення, а які - ні. Цей критерій, по суті, визначає для нас зміст (семантику) відносини.
Дійсно, кожному відношенню можна поставити у відповідність деякий логічне вираження , Залежне від n параметрів (n-місний предикат) і визначальне, чи буде кортеж належати відношенню . Це логічне вираз називають предикатом відносини . Більш точно, кортеж належить відношенню тоді і тільки тоді, коли предикат цього відношення приймає значення "істина". У свою чергу, кожен n-місний предикат задає деякий n-арне ставлення. Таким чином, існує взаємно однозначна відповідність між n-арнимі відносинами і n-місцевими предикатами.
Якщо це не викликає плутанини, зручно і відношення, і його предикат позначати однієї і тієї ж буквою. Наприклад, ставлення має предикат .

2. Приклади відносин

2.1 Бінарні відносини (відносини ступеня 2)

У математиці велику роль відіграють бінарні відношення, тобто відносини, задані на декартовом творі двох множин .

2.1.1 Відношення еквівалентності

Визначення 8. Ставлення на множині називається відношенням еквівалентності, якщо воно має такі властивості:
для всіх (Рефлексивність)
Якщо , То (Симетричність)
Якщо і , То (Транзитивність)
Зазвичай ставлення еквівалентності позначають знаком або і кажуть, що воно (відношення) задано на множині (А не на ). Умови 1-3 в позначеннях виглядають більш природно:
для всіх (Рефлексивність)
Якщо , То (Симетричність)
Якщо і , То (Транзитивність)
Легко доводиться, що якщо на множині задано відношення еквівалентності, то безліч розбивається на взаємно непересічні підмножини, що складаються з еквівалентних один одному елементів (класи еквівалентності).
Приклад 1. Розглянемо на безлічі дійсних чисел відношення, задане просто рівністю чисел. Предикат такого ставлення:
, Або просто
Умови 1-3, очевидно, виконуються, тому дане відношення є відношенням еквівалентності. Кожен клас еквівалентності цього відношення складається з одного числа.
Приклад 2. Розглянемо більш складне відношення еквівалентності. На множині цілих чисел задамо відношення "рівність за модулем n" наступним чином: два числа і рівні за модулем n, якщо їх залишки при діленні на n рівні. Наприклад, за модулем 5 рівні числа 2, 7, 12 і т.д.
Умови 1-3 легко перевіряються, тому рівність за модулем є відношенням еквівалентності. Предикат цього відношення має вигляд:

Класи еквівалентності цього відносини складаються з чисел, що дають при діленні на n однакові залишки. Таких класів рівно n:
[0] = {0, n, 2n, ...}
[1] = {1, n +1, 2n +1, ...}
...
[N-1] = {n-1, n + n-1, 2n + n-1, ...}

2.1.2 Відносини порядку

Визначення 9. Ставлення на множині називається відношенням порядку, якщо воно має такі властивості:
для всіх (Рефлексивність)
Якщо і , То (Антисиметричність)
Якщо і , То (Транзитивність)
Зазвичай ставлення порядку позначають знаком . Якщо для двох елементів і виконується , То говорять, що "Передує" . Як і для відносини еквівалентності, умови 1-3 в позначеннях виглядають більш природно:
для всіх (Рефлексивність)
Якщо і , То (Антисиметричність)
Якщо і , То (Транзитивність)
Приклад 3. Простим прикладом ставлення порядку є відношення, що задається звичайним нерівністю на множині дійсних чисел . Зауважимо, що для будь-яких чисел і виконується або , Або , Тобто будь-які два числа можна порівняти між собою. Такі відносини називаються відносинами повного порядку.
Предикат даного відносини є просто утвердження .
Приклад 4. Розглянемо на безлічі всіх співробітників деякого підприємства ставлення, що задається наступним чином: співробітник передує співробітнику тоді і тільки тоді, коли виконується одна з умов:

є начальником (не обов'язково безпосереднім)
Назвемо таке відношення "бути начальником". Легко перевірити, що відношення "бути начальником" є відношенням порядку. Зауважимо, що на відміну від попереднього прикладу, існують такі пари співробітників і , Для яких не виконується , Ні (Наприклад, якщо і є товаришами по службі). Такі відносини, в яких є незрівнянні між собою елементи, називають відносинами часткового порядку.

2.1.3 Функціональне ставлення

Визначення 10. Ставлення на декартовом творі двох множин називається функціональним відношенням, якщо воно має наступну властивість:
Якщо і , То (Однозначність функції).
Зазвичай, функціональне ставлення позначають у вигляді функціональної залежності - тоді і тільки тоді, коли . Функціональні відносини (підмножини декартового твори!) Називають інакше графіком функції або графіком функціональної залежності.
Предикат функціонального відносини є просто вираз функціональної залежності .

2.1.4 Ще приклад бінарного відношення

Приклад 5. Нехай безліч є наступне безліч молодих людей: {Вовочка, Петя, Маша, Олена}, причому відомі наступні факти:
Вовочка любить Вовочку (егоїст).
Петя любить Машу (взаємно).
Маша любить Петю (взаємно).
Маша любить Машу (себе не забуває).
Олена любить Петю (нещасна любов).
Інформацію про взаємини даних молодих людей можна описати бінарним відношенням "любити", заданому на безлічі . Це відношення можна описати кількома способами.
Спосіб 1. Перерахування фактів у вигляді довільного тексту (як це зроблено вище).
Спосіб 2. У вигляді графа взаємин:

Малюнок 1 Граф взаємин

Спосіб 3. За допомогою матриці взаємин:
Таблиця 1. Матриця взаємин

Кого Хто	Вовочка	Петя	Маша	Лена
Вовочка	Любить
Петя			Любить
Маша		Любить	Любить
Лена		Любить

Спосіб 4. За допомогою таблиці фактів:
Таблиця 2 Таблиця фактів

Хто любить	Кого люблять
Вовочка	Вовочка
Петя	Маша
Маша	Петя
Маша	Маша
Лена	Петя

З точки зору реляційних баз даних найбільш кращим є четвертий спосіб, т.к він допускає найбільш зручний спосіб збереження і маніпулювання інформацією. Дійсно, перерахування фактів як текстова форма зберігання інформації доречна для літературного твору, але насилу піддається алгоритмічної обробці. Зображення у вигляді графа наочно, і його зручно використовувати як кінцеву форму подання інформації для користувача, але зберігати дані в графічному вигляді незручно. Матриця взаємин вже більше відповідає вимогам інформаційної системи. Матриця зручна в обробці і компактно зберігається. Але одна невелика зміна, наприклад, з'явився ще Вася і закохався в нещасну Олену, вимагає перебудови всієї матриці, а саме, додати і колонок, і стовпців. Таблиця фактів вільна від усіх цих недоліків - при додаванні нових дійових осіб просто додаються нові рядки.
Що стосується предиката даного ставлення, то він має такий вигляд (діз'юнктівная нормальна форма):
R (x, y) = {(x = "Вовочка" AND y = "Вовочка") OR (x = "Петя" AND y = "Маша") OR (x = "Маша" AND y = "Петя") OR (x = "Маша" AND y = "Маша") OR (x = "Лєна" AND y = "Петя")}
Зауваження. Наведене ставлення не є ні транзитивним, ні симетричним або антисиметричних, ні рефлексивним, тому воно не є ні ставленням еквівалентності, ні ставленням порядку, ні будь-яким іншим розумним ставленням.
Зауваження. Велика частина світової літератури існує і має сенс лише остільки, оскільки бінарне відношення "любити" не є відношенням еквівалентності. Зокрема, з цієї причини людство не розбивається на класи еквівалентності взаємно люблячих особин. Вивченням характеристик даного відносини і відповідного йому предиката займалося (і продовжує займатися) велика кількість експертів, таких як Толстой Л.М., Шекспір ​​В. та ін

2.2 n-арні відносини (відносини ступеня n)

У математиці n-арні відносини розглядаються відносно рідко, на відміну від баз даних, де найбільш важливими є саме відносини, задані на декартовом творі більш ніж двох множин.
Приклад 6. У певному університеті на математичному факультеті навчаються студенти Іванов, Петров і Сидоров. Лекції їм читають викладачі Пушніков, Циганов і Шаріпов, причому відомі наступні факти:
Пушніков читає лекції з алгебри і баз даних, відповідно, 40 і 80 годин на семестр.
Циганов читає лекції з геометрії, 50 годин на семестр.
Шаріпов читає лекції з алгебри та геометрії, відповідно, 40 і 50 годин на семестр.
Студент Іванов відвідує лекції з алгебри у Шаріпова і по базах даних у Пушнікова.
Студент Петров відвідує лекції з алгебри у Пушнікова і з геометрії у Циганова.
Студент Сидоров відвідує лекції з геометрії у Циганова і по базах даних у Пушнікова.
Для того щоб формально описати дану ситуацію (наприклад, з метою розробки інформаційної системи, що враховує дані про хід навчального процесу), введемо три множини:
Безліч викладачів = {Пушніков, Циганов, Шаріпов}.
Безліч предметів = {Алгебра, Геометрія, Бази даних}.
Безліч студентів = {Іванов, Петров, Сидоров}.
Наявні факти можна розділити на дві группи.1 група (факти 1-3) - факти про викладачів, 2 група (факти 4-6) - факти про студентів.

Для того щоб відобразити факти 1-3 (характеризують викладачів і читані ними лекції), введемо відношення на декартовом творі , Де - Безліч раціональних чисел. А саме, впорядкована трійка тоді і тільки тоді, коли викладач читає лекції з предмету в кількості годин на семестр. Назвемо таке ставлення "Читає лекції з ...". Безліч кортежів, що утворюють відношення зручно представити у вигляді таблиці:
Таблиця 3 Ставлення "Читає лекції з ..."
Для того щоб відобразити факти 4-6 (характеризують відвідування студентами лекцій), введемо відношення на декартовом творі . Упорядкована трійка тоді і тільки тоді, коли студент відвідує лекції з предмету у викладача . Назвемо це відношення "Відвідувати лекції". Його також представимо у вигляді таблиці:
Таблиця 4 Відношення "Відвідувати лекції"
Розглянемо відношення докладніше. Воно задано на декартовом творі . Це твір, що містить 3 * 3 * 3 = 27 кортежів, можна назвати "Студенти-Лекції-Викладачі". Безліч являє собою сукупність всіх можливих варіантів відвідування студентами лекцій. Ставлення ж показує поточний стан навчального процесу. Очевидно, що ставлення є змінним у часі ставленням.
Отже, факти про хід навчального процесу вдалося відобразити у вигляді двох відносин третього ступеня (3-арних), а самі відносини зобразити у вигляді таблиць з трьома колонками.
Зручність використання табличної форми для завдання відносини визначається в даному випадку наступними чинниками:
Всі використовувані безлічі кінцеві.
При додаванні або видаленні студентів, предметів, викладачів просто додаються або видаляються відповідні рядки в таблиці.
Нас зараз не цікавить питання, чи хороші отримані відносини. Зауважимо поки тільки, що, як показують наступні зауваження, не будь-яку рядок можна додати в таблицю "Відвідувати лекції".
Зауваження. У таблицю "Відвідувати лекції" не можна додати дві однакові рядки, т.к таблиця зображує ставлення , А в відношенні (як і в будь-якій безлічі) не може бути двох однакових елементів. Це приклад синтаксичного обмеження - таке обмеження задано у визначенні поняття відношення (однакових рядків не може бути ні в одній таблиці, яка задає відношення).
Зауваження. У таблицю "Відвідувати лекції" не можна додати кортеж (Іванов, Геометрія, Пушніков). Дійсно, з таблиці "Читає лекції з ...", що представляє відношення , Випливає, що Пушніков не читає предмет "Геометрія". Виявилося, що таблиці пов'язані один з одним, і істотним чином! Це приклад семантичного обмеження - таке обмеження є наслідком нашої трактування даних, що зберігаються у відношенні (наслідком розуміння сенсу даних).

3. Транзитивне замикання відносин

Введемо поняття транзитивного замикання, пов'язане з бінарними відношеннями, що знадобиться в подальшому.
Визначення 11. Нехай ставлення задано на декартовом квадраті деякого безлічі . Транзитивне замикання відносини називається нове ставлення , Що складається з кортежів , Для яких виконується:
або кортеж ,
або знайдеться кінцева послідовність елементів , Така, що всі кортежі належать відношенню .
Очевидно, що .
Приклад 7. Нехай безліч являє собою наступне безліч деталей і конструкцій:
= {Болт, Гайка, Двигун, Автомобіль, Колесо, Вісь}
причому деякі з деталей і конструкцій можуть бути використані при складанні інших конструкцій. Взаємозв'язок деталей описується відношенням ("Безпосередньо використовується в") і складається з наступних кортежів:
Таблиця 5 Відношення R
Транзитивне замикання складається з кортежів (додані кортежі позначені сірим кольором):

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

Висновки

Безліч - це невизначені поняття, що представляє деяку сукупність даних. Елементи безлічі можна відрізняти один від одного, а також визначати, чи належить даний елемент даній безлічі. Над множинами можна виконувати операції об'єднання, перетину, різниці і доповнення.
Нові безлічі можна будувати за допомогою поняття декартового твору (звичайно, є й інші способи, але вони нас у даний момент не цікавлять). Декартово твір декількох множин - це множина кортежів, побудований з елементів цих множин.
Ставлення - це підмножина декартового добутку множин. Відносини складаються з однотипних кортежів. Кожне відношення має предикат відносини і кожен n-місний предикат задає n-арне ставлення.
Відношення є математичним аналогом поняття "таблиця".
Відносини отримали ступінь і потужністю. Ступінь відносини - це кількість елементів у кожному кортежі відносини (аналог кількості стовпців у таблиці). Потужність відносини - це потужність множини кортежів відносини (аналог кількості рядків у таблиці).
У математиці найчастіше використовують бінарні відносини (відносини ступеня 2). У теорії баз даних основними є відносини ступеня . У математиці, як правило, відносини задані на нескінченних множинах і мають нескінченну потужність. У базах даних навпаки, потужності відносин кінцеві (число збережених рядків у таблицях завжди звичайно).