Означення бінарного відношення, відношення еквівалентності, порядку.

Бінарні відношення – теоретичне підґрунтя теорії прийняття рішень, оскільки для дослідження переваг децидента використовують основні типи бінарних відношень, а властивості бінарних відношень інтерпретуються якісно в термінах системи переваг децидента. Доведені твердження дають можливість побудувати алгоритми перевірки експериментальних відношень на наявність таких важливих властивостей, як транзитивність, ациклічність, лінійність, щоб виявляти і корегувати суперечності в міркуваннях децидента.

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

Відношення — це твердження, що відображає взаємний зв’язок між двома чи більшою кількістю об’єктів.

Наприклад, «Ганна – сестра Івана», «число 12 більше за число 10», «золото важче, ніж алюміній», «весна та зима – пори року». Ці твердження інформують нас про те, що об’єкти належать до одного класу («діти одного батька», «пори року»), або про певний порядок об’єктів у системі («більше», «важче»). У цих прикладах об’єкти і відношення мають конкретні назви, і після підстановки інших об’єктів у твердження відношення може бути правильним або ж утратить сенс.

Отже, необхідною передумовою для побудови відношення є описання множини об’єктів, на яких воно буде визначене, тобто множини–носія відношення. Нехай А – множина певних об’єктів (наприклад, можливих варіантів рішень). Множина всіх пар (х, у), х Î А, у Î А, є декартовим добутком множини А саму на себе, А × А.

ОЗНАЧЕННЯ 2.1. Бінарним відношенням на множині А називається підмножина R Í А × А. Якщо пара (х, у) знаходиться у відношенні R, то цей факт позначається як xRy або (х, у)Î R. Множина А називається носієм відношення R.

Приклад 2.1. Відношення R «знаходиться на колі з одиничним радіусом і центром у початку координат» записується як R = {(x, y) Î А × А | х ² + у ² = 1}, де А – множина дійсних чисел, що є областю визначення (носієм) відношення.

Приклад 2.2. Нехай А = В = N, де N – множина натуральних чисел. Розглянемо відношення «£», тобто R = {(m, n) | m, n Î N, m £ n }. Воно виконується для пар (5, 7), (2, 2), але не виконується для пари (5, 4).

Приклад 2.3. Нехай А = В = N. Відношення «мати спільний дільник, відмінний від 1» виконується для пар (2, 4), (3, 15), але не виконується, наприклад, для будь–якої пари (n, n + 1).

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

Розглянемо основні типи бінарних відношень і можливі операції над ними в матричному та графовому представленні.

Нехай бінарне відношення R означено на скінченній n –елементній множині А. Перенумеруємо елементи цієї множини числами від 1 до n, і розглянемо квадратну матрицю В розміром n × n, у якій i –й рядок та і –й стовпець відповідають і –му елементу множини А. Визначимо елементи матриці В залежно від виконання відношення:

де х_i Î A, х_j Î A.

Отже, відношення R на скінченній n –елементній множині А можна задати матрицею

B (R) = || b_ij (R)||.

Оскільки елементи множини А можна перенумерувати довільним чином і існує n! різних нумерацій, то відповідно існує n! матриць, що описують конкретне бінарне відношення. У подальшому для скорочення вживатимемо запис R замість B (R), якщо з контексту зрозуміло, що йдеться про матрицю.

Приклад 2.4. Нехай А = {1, 2, 3, 4, 5} – носій бінарного відношення «£». Для цього відношення відповідна матриця має вигляд

ОЗНАЧЕННЯ 2.2. Областю визначення бінарного відношення R називається множина

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

Приклад 2.5. Нехай А = {1, 2, 3, 4, 5, 6, 7}, R = «£». Область визначення відношення R є .

Приклад 2.6. Нехай А = {1, 2, 3, 4, 5, 6}, R = {(a, b) | a, b Î A, a = b + 3}. Тоді d_R = {1, 2, 3}.

ОЗНАЧЕННЯ 2.3. Областю значення бінарного відношення R називається множина

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

Приклад 2.7. Нехай А = {1, 2, 3, 4, 5, 6}, R = {(a, b) | a, b Î A, a = b + 2). У цьому випадку d_R = {1, 2, 3, 4}, r_R = {3, 4, 5, 6}.

Поставимо у взаємно однозначну відповідність елементам множини А = { х ₁, х ₂,..., х_n } вершини графа G (R) = á L, N ñ. Тут N = {1,..., n) — множина вершин графа G, L – множина його дуг, причому L = {(і, j) | х_іRx_j }, тобто дуга в графі G з’єднує вершину і з вершиною j лише тоді, коли x_i Î A, x_j Î A перебувають у відношенні R: х_іRx_j (коли х_іRx_i, дуга перетворюється на петлю). Отже, бінарне відношення можна подати у вигляді орієнтованого графа G (R).

Відношення R можна також описати за допомогою перетенів множини А.

ОЗНАЧЕННЯ 2.4. Верхнім перетином R ⁺(x) відношення R множиною–носієм А відносно елемента х називають множину

R ⁺(x) = { y Î А | (у, х) Î R }.

ОЗНАЧЕННЯ 2.5. Нижнім перетином R ^–(х) відношення R множиною–носієм А відносно елемента х називають множину

R ^–(x) = { y Î А | (х, у) Î R }.

У літературі зустрічаються також терміни «прообраз» та позначення R ^–1(х) = R ⁺(x) і «образ» для R (x) = R ^–(x).

Приклад 2.8. Нехай А = {1, 2, 3, 4, 5, 6}, R = «£», х = 2. Тоді R ^–(2) = {2, 3, 4, 5, 6}.

Приклад 2.9. Нехай А = {1, 2, 3, 4, 5, 6}, R = «>», х = 3. Тоді R ^–(3) = {4, 5, 6}.

Отже, R ⁺(х) – це множина всіх елементів у Î А, таких, що знаходяться у відношенні R із фіксованим елементом х, a R ^–(x) – множина всіх елементів у Î А, з якими елемент х знаходиться у відношенні R.

Щоб однозначно описати відношення R за допомогою перерізів, слід задати множину верхніх перерізів R ⁺(x) для всіх елементів х Î А, або множину нижніх перерізів R ^–(x) для всіх х Î А, тобто

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

Означення. Відношення у множині називається відношенням еквівалентності, якщо воно рефлексивне, симетричне і транзитивне.

Виконаємо таке завдання: побудуємо графи заданих відношень.

1) граф відношення «бути паралельним», за умови, що а || b || с, k || d || e, f || h.

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

Властивості рефлективності, симетричності і транзитивності.

2) граф відношення «бути рівними» на множині відрізків, якщо a = b = c, d = e, відрізок h не дорівнює жодному з даних відрізків.

Це відношення також має властивості рефлективності, симетричності і транзитивності.

3) На множині А = {1/2,1/3,1/4,2/4,2/6,3/6} встановлено відношення «бути рівним». Побудуємо граф даного відношення.

Усі ці відношення мають властивості рефлективності, симетричності і транзитивності.

Приклади відношень еквівалентності: відношення рівності на довільній множині; відношення паралельності прямих на площині; відношення подібності на множині усіх трикутників; відношення рівносильності на множині рівнянь; відношення «навчатися в одній групі» на множині студентів коледжу.

Дане відношення розбило задані множини на підмножини:

1) { a, b, c }, { d, e }, { f, h } – підмножини паралельних між собою прямих;

2) { a, b, c }, { e, d }, { h }; - підмножини рівних між собою відрізків;

3) {1/2, 2/4, 3/6}, {1/3, 2/6}, {1/4} підмножини рівних між собою дробів.

Ці множини не перетинаються, а їх об’єднання співпадає з множиною X.

Отже, якщо у множині Х задано відношення еквівалентності, то воно розбиває цю множину на підмножини, які попарно не перетинаються (класи еквівалентності).

І навпаки: якщо дане відношення, задане на множині Х, визначило розбиття цієї множини на класи, то це відношення є відношенням еквівалентності.

Отже, за допомогою відношення еквівалентності виконується досить поширена операція – розбиття непорожньої множини на підмножини, які називають класами еквівалентності, при якому:

1) кожен елемент множини належить одному і тільки одному класу;

2) будь-які два елементи одного класу перебувають у даному відношенні еквівалентності;

3) будь-які два елементи, що належать різним класам, не перебувають у цьому відношенні.

Граф відношення еквівалентності є об’єднанням кількох повних графів. Навпаки, якщо граф деякого відношення на множині розпадається на кілька повних графів, то воно є відношенням еквівалентності. Відношення еквівалентності наочно зображується системою повних графів, побудованих на класах еквівалентності. Повним називається граф, в якого всі точки сполучено стрілками і всі вершини мають петлі.

Всі елементи одного класу еквівалентності мають однакові властивості, що дає можливість вивчати властивості одного елемента і поширювати їх на всі елементи класу.

О з н а ч е н н я 2.21. Відношенням нестрогого порядку «» (нестрогим порядком)називається відношення, яке має властивості рефлективності, антисиметричності та транзитивності.

О з н а ч е н н я 2.22. Відношенням строгого порядку «<» (строгим порядком)називається відношення, яке має властивості антирефлективності, асиметричності та транзитивності.

Нехай задано відношення «» – нестрогий порядок на множині . Йому можна поставити у відповідність строгий порядок «<», який визначається таким чином: x < y тоді і тільки тоді коли та . І навпаки, нехай «<»– відношення строгого порядку на множині . Йому можна поставити у відповідність відношення «» таким чином: тоді і тільки тоді, коли або . Тобто за нестрогим порядком ми можемо визначити відповідний йому строгий порядок і навпаки.

Якщо на деякій множині задане відношення порядку (для всіх, або деяких пар його елементів), то кажуть, що на множині заданий частковий порядок.

Теорема: для того, щоб відношення α дозволяло розбити множину Х на класи, що попарно не перетинаються, необхідно і достатньо, щоб відношення α було відношенням еквівалентності.

Оскільки у формулюванні цієї теореми є слова необхідно і достатньо, то доведення теореми складається із двох частин: 1) із доведення необхідності; 2) із доведення достатності. Цю теорему приймемо без доведення.

Означення: бінарне відношення α, визначене у множині Х, називається відношенням строгого порядку, якщо воно антирефлексивне, антисиметричне і транзитивне.

Прикладами відношень строгого порядку є: відношення «менше» у множині цілих чисел; відношення «бути старшим» на множині людей; відношення «бути вищим» на множині дерев тощо.

Означення: бінарне відношення α, визначене у множині Х, називається відношенням нестрогого порядку, якщо воно рефлексивне, антисиметричне і транзитивне.

Прикладами відношень нестрогого порядку є: відношення «більше або дорівнює» у множині раціональних чисел; відношення подільності на множині натуральних чисел тощо.

Означення: відношення порядку в множині Х називається відношенням лінійного порядку, якщо для будь-яких елементів х,уєХ виконується умова хαу٧уαх. Якщо ж відношення не має такої властивості, то його називають відношенням часткового порядку.

Прикладом відношення лінійного порядку є відношення «більше» чи «менше» на множині чисел.

Означення: якщо відношення α в множині Х є відношенням часткового порядку, то множину Х називають частково впорядкованою множиною.

Означення: якщо відношення α в множині Х є відношенням лінійного порядку, то множину Х називають лінійно впорядкованою множиною.

Лінійно впорядковані множини мають ряд властивостей. Нехай а,в,сєХ і множина Х лінійно впорядкована відношенням α. Якщо відомо, що аαв^вαс, то говорять, що елемент в лежить між елементами а і с.

Означення: множина Х, яка лінійно впорядкована відношенням α, називається дискретною, якщо між будь-якими двома її елементами знаходиться лише скінченна множина елементів.

Прикладом дискретних множин є множини натуральних і цілих чисел.

Означення: множина Х, яка лінійно впорядкована відношенням α, називається щільною в собі, якщо для будь-яких двох різних її елементів існує елемент цієї множини, що лежить між ними.

Прикладом щільних в собі множин є множина дійсних чисел.

Дата добавления: 2015-07-10