![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Способи завдання бінарних відношень
Бінарні відношення можна задати такими способами. Спосіб 1. Перерахування елементів, якими утворене відношення. Як елементи бінарного відношення виступають упорядковані пари. Приклад 4.1. Бінарне відношення на множині Спосіб 2. Матриця суміжності. Визначення 4.2. Матриця суміжності
Отже, кожна комірка Приклад 4.2. Дана множина
Спосіб 3. Граф. Бінарне відношення можна задати за допомогою графової діаграми. Визначення 4.3. Граф – це сукупність множини Сигнатура встановлює зв'язок між вершинами графа. Графом також називається і графова діаграма, якою він зображується: вершини позначаються крапками, упорядковані пари вершин – дугами, де дуга спрямована з вершини, що розташована на першій позиції в упорядкованій парі, у вершину, яка розташована на другій позиції. Приклад 4.3. Граф бінарного відношення
Рисунок 4.1 – Граф бінарного відношення із прикладу 4.3
Розглянемо наступний приклад, що ілюструє інформаційний обмін між пристроями ЕОМ, блок-схема якої вперше була запропонована Джоном фон Нейманом. Приклад 4.3. Дано множину
можна задати за допомогою графа (рис. 4.2):
Рисунок 4.2 – Інформаційний обмін між пристроями ЕОМ
Спосіб 4. Фактор-множина Визначення 4.4. Околиця одиничного радіуса елемента
Визначення 4.5. Фактор - множиною
Приклад 4.4. Для бінарного відношення (4.2) із прикладу 4.3 фактор-множина подається так:
де у верхньому рядку розташовані елементи множини
4.2 Властивості бінарних відношень
Бінарні відношення мають три основні властивості, відповідно до яких вони класифікуються: рефлексивність, симетричність, транзитивність. Визначення 4.6. Бінарне відношення
тобто для будь-якого елемента У матриці рефлексивного бінарного відношення
Рисунок 4.3 – Петля в графі рефлексивного бінарного відношення Визначення 4.7. Бінарне відношення
тобто для будь-яких елементів Матриця симетричного бінарного відношення симетрична відносно головної діагоналі:
У графі симетричного бінарного відношення – наявність між кожною парою вершин, що перебувають у відношенні
Приклад 4.5. Видалення в графі із прикладу 4.3 (див. рис. 4.2) дуг
Рисунок 4.5 – Симетричне бінарне відношення Визначення 4.8. Бінарне відношення
для будь-яких трьох елементів Граф транзитивного бінарного відношення характеризується наявністю транзитивно замикаючих дуг (рис. 4.6) для кожних двох пар з умови (посилки) даної властивості (4.9).
Приклад 4.6. У графі на рис. 4.5 транзитивно замикаючими є такі дуги: для впорядкованих пар Вводяться також додаткові властивості, засновані на наведених вище: – антирефлексивність (у матриці суміжності на головній діагоналі всі елементи нульові, у графі не існує петель): – нерефлексивність (у матриці суміжності по головній діагоналі розташовані як нулі, так і одиниці, у графі деякі вершини мають петлі): – антисиметричність (всі відповідні симетричні комірки матриці суміжності різні; у графі немає жодної пари симетрично спрямованих дуг): – несиметричність (якщо умова симетричності порушується хоча б для однієї пари, тобто – нетранзитивність: якщо Приклад 4.7. Після видалення симетричних і транзитивно замикаючих дуг у графі із прикладу 4.3 (див. рис. 4.2), тобто всіх дуг, крім
4.3 Бінарне відношення еквівалентності
Відношення еквівалентності – спеціальний тип бінарного відношення, затребуваний на практиці. Визначення 4.9. Бінарним відношенням еквівалентності 1) рефлексивність означає, що кожний елемент еквівалентний сам собі: 2) симетричність означає, що якщо елемент 3) транзитивність: якщо елемент Відношення еквівалентності ілюструється графом з петлями й симетрично спрямованими дугами, які попарно мають транзитивно замикаючі дуги (рис. 4.8).
Рисунок 4.8 – Граф бінарного відношення еквівалентності Приклад 4.8. Бінарне відношення еквівалентності ілюструє роботу тригера, граф переходів якого зображений на рис. 4.10.
а б Рисунок 4.9 – Граф переходів (а) і структура тригера (б) Визначення 4.10. Клас еквівалентності
Визначення 4.11. Розбивкою множини Нехай 1) будь-яка множина 2) довільні дві множини з розбивки
3) об'єднання всіх множин із
Приклад 4.9. Розбивками триелементної множини
Приклад 4.10. Максимальна розбивка індексу 1 завжди містить одну єдину множину Приклад 4.11. Множина всіх одноелементних підмножин становить найдрібнішу розбивку, індекс якої співпадає з потужністю вихідної множини: Розглянемо схему розбивки множини на класи еквівалентності. Нехай на кінцевій множині – виберемо елемент
– виберемо елемент
У результаті такої побудови породжується система класів Дана система має такі властивості: 1) утворює розбивку, тобто класи попарно не перетинаються: 2) будь-які два елементи з одного класу еквівалентні: 3) будь-які два елементи з різних класів не еквівалентні:
Побудована розбивка (система класів) називається системою класів еквівалентності за відношенням Класи еквівалентності мають такі властивості: 1) елемент належить своєму класу еквівалентності: 2) якщо елемент 3) якщо класи еквівалентності перетинаються, то вони співпадають:
нерівні (різні) класи еквівалентності не перетинаються:
Таким чином, класи еквівалентності або не перетинаються, або співпадають: 4) об'єднанням класів еквівалентності є вся множина Отже, класи еквівалентності утворюють розбивку множини. Матрицю бінарного відношення еквівалентності можна зобразити у блоково-діагональному вигляді (рис. 4.10), де кожна підматриця, що складається з одиниць, відповідає класу еквівалентності.
Рисунок 4.10 – Матриця бінарного відношення еквівалентності
З формальної точки зору модель є фактор-множина елементів об'єкта, що моделюється, щодо деякого відношення еквівалентності, заданого на вихідній системі. Поняття “відношення еквівалентності”, “ фактор-множина”, “класи еквівалентності” використовуються при побудові математичної моделі деякої реально функціонуючої складної системи. Під час дослідження виникає завдання вибору істотних властивостей, деталей, ознак об'єкта, який моделюється. Відношення еквівалентності, з одного боку, ототожнює другорядні, несуттєві ознаки й властивості, з іншого боку – виділяє як представників класів еквівалентності основні властивості.
4.4 Контрольні запитання
1. Яке відношення називається бінарним? 2. Якими способами можна задати бінарне відношення? 3. Як визначається матриця суміжності? 4. Чим визначається розмір матриці суміжності? 5. Що таке граф бінарного відношення? 6. Які властивості мають бінарні відношення? 7. Як визначається властивість рефлексивності? 8. Чим характеризується матриця суміжності рефлексивного бінарного відношення? 9. Які характерні ознаки має граф рефлексивного відношення? 10. Як визначається властивість симетричності?
5 БІНАРНЕ ВІДНОШЕННЯ ПОРЯДКУ
|