Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

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

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

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

ОЗНАЧЕННЯ 2.22. Рефлексивним називається таке відношення Р, для якого справедливе твердження Е Í Р, де Е – діагональне відношення.

Це означає, що для всіх хÎА, де А – носій відношення Р, хРх. У матриці рефлексивного відношення на головній діагоналі завжди стоять 1, а у відповідному графі при кожній вершині є петля.

ОЗНАЧЕННЯ 2.23. Антирефлексивним називається відношення Р, для якого .

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

ОЗНАЧЕННЯ 2.24. Симетричним називається відношення Р, для якого .

Для всіх х, yÎА, які перебувають у такому відношенні Р, тобто хРу, справедливе твердження уРх. У матриці симетричного відношення елементи bij та bji розміщені симетрично відносно головної діагоналі, рівні між собою. У графі G(P) наявність дуги (xi, xj) означає, що є і дуги (хj, хi).

ОЗНАЧЕННЯ 2.25. Асиметричним називається відношення Р, для якого , тобто якщо , то .

У матриці такого відношення для всіх і та j, а на головній діагоналі знаходяться 0. У графі G(P) немає водночас дуг (хi, хj) та (xj, хi), а також петель.

ОЗНАЧЕННЯ 2.26. Антисиметричним називається відношення Р, якщо , де Е – діагональне відношення.

Отже, твердження хРу та уРх справедливі водночас лише тоді, коли х = у. У матриці В(Р) умова виконується для всіх і, j, окрім і = j. У графі G(P) немає водночас дуг (хi, хj) та (xj, хi), але можуть бути петлі.

Приклад 2.20. Розглянемо відношення Р, Q, R:

Відношення P симетричне та рефлексивне, Q – антирефлексивне і асиметричне, R – антисиметричне, що перевіряється безпосередньо за означеннями цих властивостей:

Приклад 2.21. Розглянемо приклади відношень із наведеними вище властивостями.

Відношення між об’єктами «бути подібним», «бути не молодшим» рефлексивні, тому що об’єкт подібний на самого себе (тотожний сам собі), людина не молодша за саму себе.

Відношення «відрізнятися», «бути молодшим», «бути батьком» не рефлексивні. Більше того, вони антирефлексивні (тому що об’єкт не може відрізнятися від самого себе, бути молодшим за самого себе чи бути батьком самому собі).

Відношення «бути родичем» симетричне (якщо А – родич В, то і В – родич А), «бути батьком» – асиметричне (якщо А – батько В, то В не батько А).

Відношення «бути сестрою» не симетричне і не асиметричне. Так, якщо Марія – сестра Ольги, то Ольга – сестра Марії, але якщо Марія – сестра Петра, то, звичайно ж, Петро – не сестра Марії.

Відношення «³» на множині дійсних чисел антисиметричне.

ОЗНАЧЕННЯ 2.27. Транзитивним називається відношення, для якого , тобто якщо xPz і zPy, то хРу.

За індукцією як наслідок отримуємо: якщо xPz1, z1Pz2, ..., znPy, то хРу. У матриці В(Р) транзитивного відношення для довільних значень і, k виконується співвідношення

У графі G(P) транзитивного відношення Р якщо існує шлях з x в у, то існує дуга (х, у).

Із поняттям транзитивного відношення тісно пов’язане поняття операції транзитивного замикання. Для кожного відношення Р означимо відношення як мінімальне транзитивне відношення, у якому міститься відношення Р. Його однозначно означають як , де n = саrd(A), А – носій відношення Р, a card(A) – потужність множини А.

Приклад 2.22. Знайдемо транзитивне замикання відношення

.

,

,

ОЗНАЧЕННЯ 2.28. Ациклічним називається відношення Р, для якого для довільного k.

Для ациклічного відношення з xPz1, z1Pz2, ..., znPy випливає х ¹ у, тобто якщо в графі G(P) ациклічного відношення Р вершини х та у з’єднані шляхом, то в ньому немає дуги (у, х).

Ациклічність і транзитивність – важливі властивості для ТПР, вони відображають певні природні взаємозв’язки між об’єктами. Якщо об’єкт х у певному розумінні кращий за у, а у кращий за z, то природно вважати, що об’єкт х кращий, ніж z (транзитивність), і щонайменше об’єкт z не кращий за х (ациклічність).

ОЗНАЧЕННЯ 2.29. Зв’язним відношенням називається відношення Р, для якого , де – обернене до Р відношення, U – повне, Е – діагональне.

Це означає, що для довільних елементів х, у Î А, х ¹ у, де А – носій відношення Р, чи (х,у) Î Р, чи (у, х) Î Р. У матриці В(Р) хоча б один з елементів bij, bji дорівнює 1, а граф G(P) зв’язний.

Доведемо декілька тверджень, які стосуються взаємозв’язків між властивостями відношень.

ТВЕРДЖЕННЯ 2.1. Відношення Р симетричне тоді й лише тоді, коли .

Доведення. За означенням для симетричного відношення . Оскільки для довільних відношень R і Q з випливає , то підставивши замість R відношення Р, а замість Q, отримаємо , або . Оскільки водночас та , то . ¨

ТВЕРДЖЕННЯ 2.2. Якщо відношення Р асиметричне, то воно антирефлексивне.

Доведення. Нехай для хÎА, де А – носій відношення Р, виконується хРх. За означенням оберненого відношення це означає, що . Однак тоді , що суперечить припущенню про асиметричність відношення Р. ¨

ТВЕРДЖЕННЯ 2.3. Якщо відношення Р та Q симетричні, то симетричні й відношення .

Доведення. За твердженням 2.1, . Виходячи з справедливості співвідношення , отримаємо , що і доводить твердження. Аналогічно . ¨

ТВЕРДЖЕННЯ 2.4. Композиція симетричних відношень Р та Q симетрична тоді й лише тоді, коли .

Доведення. Нехай . Тоді , тобто композиція симетрична, що доводить достатність умови комутативності.

Нехай відношення симетричне. Тоді . Позаяк відношення Р та Q симетричні, то , що й доводить необхідність умови комутативності. ¨

ТВЕРДЖЕННЯ 2.5. Відношення обернене до транзитивного відношення Р, є транзитивним.

Доведення. Нехай Р – транзитивне відношення, й та . Тоді , і внаслідок того, що Р – транзитивне відношення, , тобто . Отже, відношення транзитивне. ¨

ТВЕРДЖЕННЯ 2.6. Перетин довільної кількості транзитивних відношень з одним і тим самим носієм є транзитивним відношенням.

Доведення. Розглянемо множину транзитивних відношень {Рi}, iÎІ, з носієм А. Нехай хРу, yPz. Це означає, що для довільного iÎІ виконується хРiу, yPiz.

Оскільки відношення Рi транзитивне, то хРiz. Оскільки хРiz виконується для довільного iÎІ, це означає, що

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

Результуюче відношення, отримане об’єднанням транзитивних відношень, також транзитивне, якщо виконуються деякі додаткові умови. Уведемо поняття транзитивності одного відношення щодо іншого. Відношення Р називатимемо транзитивним стосовно відношення Q, якщо з хРуÙyQz випливає xPz, а з xQyÙyPzxPz.

Неважко довести твердження 2.7 і 2.8, що визначають умови транзитивності.

ТВЕРДЖЕННЯ 2.7. Якщо два відношення транзитивні й одне з них транзитивне відносно іншого, то об’єднання цих відношень транзитивне.

Нехай Р — довільне бінарне відношення. Відношення називається симетричною складовою відношення Р, а — його асиметричною складовою.

ТВЕРДЖЕННЯ 2.8. Нехай Р – транзитивне відношення. Тоді його симетрична складова PS і асиметрична складова РА транзитивні. А відношення РА транзитивне відносно PS.

 


Читайте також:

  1. Аеродинамічні властивості колісної машини
  2. Аналізатори людини та їхні властивості.
  3. Аналізатори людини та їхні властивості.
  4. Атрибутивні ознаки і властивості культури
  5. Білки, властивості, роль в життєдіяльності організмів.
  6. Біосфера Землі, її характерні властивості
  7. Будова атомів та хімічний зв’язок між атомами визначають будову сполук, а отже і їх фізичні та хімічні властивості.
  8. Будова і властивості аналізаторів
  9. Векторний добуток і його властивості.
  10. Вибір кращих альтернатив за допомогою бінарних відношень
  11. Види і властивості радіоактивних випромінювань
  12. Визначення добутку на множині цілих невід’ємних чисел, його існування та єдиність. Операція множення та її основні властивості (закони).




Переглядів: 5411

<== попередня сторінка | наступна сторінка ==>
Ізоморфізм, гомоморфізм і двоїстість бінарних відношень | Типи бінарних відношень у теорії прийняття рішень

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.005 сек.