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

Нехай А – бінарне відношення у множині X. Визначимо основні властивості таких відношень, які повинні виконуватися для всіх (x_i, x_j)ÎA. Говорять, що AÌX´X:

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

Бінарне відношення А називається рефлексивним, якщо AÉE (E – тотожне відношення), тобто воно завжди виконується між об¢єктом і ним самим:

XAx.

Приклад: рівність, самообслуговування.

2. Антирефлексивність

Бінарне відношення А називається антирефлексивним, якщо AÇE=Æ, тобто може виконуватися лише для об’єктів, що не співпадають: із x_iAx_j слідує, що x_i¹x_j.

Приклад: “x є брат y”, але не можна сказати, що x є сам собі брат; строга нерівність, ¢¢бути старшим¢¢.

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

Бінарне відношення А називається симетричним, якщо А=А^-1, тобто при виконанні x_iAx_j Þ x_jAx_i.

Приклад: відстань між двома точками, “бути братом”.

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

Бінарне відношення А називається антисиметричним, якщо АÇА^-1ÌE, тобто відношення x_iAx_j та x_jAx_i виконуються одночасно тоді й тільки тоді, коли x_i=x_j.

Приклад: нестрога нерівність £, включення.

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

Бінарне відношення АÌА називається транзитивним, якщо АÌА, тобто з xAx_j та x_jAx_kÞ x_iAx_k виконується умова (“бути дільником”, “бути родичем”).

6. Еквівалентність

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

Функціональні відношення

Функціональна залежність між змінними, або функція, є частковим випадком відношення.

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

Матриця функціонального відношення, що задане на скінченних множинах X та Y, містить не більше відоднієї одиниці в кожному рядку. Якщо функціональне відношення задано у вигляді графа, то з кожної вершини, котра зображує першу координату, виходить не більше від однієї дуги.

а) функціональне б) функціональне в) нефункціональне

Рис. 4.4.1. Приклади функціонального і нефункціонального відношень

Нехай – функціональне відношення, . Відповідність від першого до другого елемента кожної пари відношення називається функцією , або відображенням множини D_F в Y.

Графіком функції (відображення) називається сукупність точок виду у декартовому добуткові .

Існує декілька видів відображень, а саме: сюр¢єктивне, ін¢єктивне, бієктивне.

Функція називається сюр’єктивним відображенням, якщо . На графі, який зображує сюр’єктивне відображення,з будь-якої вершини виходить точно одна дуга, а до будь-якої вершини, що зображує елемент множини , заходить не менше від однієї дуги (рис 4.4.2).

Рис. 4.4.2. Приклад сюр’єктивного відображення

Функція називається ін’єктивним відображенням, якщо з виходить . На графі, що зображує ін’єктивне відображення, з будь-якої вершини виходить точно одна дуга, а до будь-якої вершини, що зображує елемент множини , заходить не більше від однієї дуги (рис 4.4.3).

Рис. 4.4.3. Приклад ін’єктивного відображення

Функція називається бієктивним відображенням, якщо вона сюр¢єктивна та ін¢єктивна. На графі, котрий зображує бієктивне відображення скінченних множин, із будь-якої вершини виходить точно одна дуга, а до будь-якої вершини, що зображує елемент множини , заходить одна і тільки одна дуга (рис 4.4.4).

 

Рис. 4.4.4. Приклад бієктивного відображення

Нечіткі відношення

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

Використаємо наступні символи: – позначення максимуму відносно елемента або змінної ; – позначення мінімуму відносно елемента або змінної .

Так, запис еквівалентний . Запис еквівалентний .

Першу проекцію нечіткого відношення визначає функція належності . Аналогічно другу проекцію нечіткого відношення визначає функція належності .

Друга проекція першої проекції (або навпаки) називається глобальною проекцією нечіткого відношення і позначається . Таким чином, .

Якщо , то говорять, що відношення нормальне. Якщо , то відношення субнормальне.

Нехай та – два нечітких відношення, такі, що , тоді говорять, що .

Об’єднання двох відношень та позначається або і визначається виразом

Якщо – відношення, то . Результат об’єднання позначається або .

Перетин двох відношень та позначається і визначається виразом

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

Контрольні запитання

1. Як пов¢язані теорія відношень та теорія множин?

2. Що називається відношенням? Назвіть способи задавання відношення.

3. Що являє тотожне відношення, повне відношення, порожнє відношення?

4. Як одержати граф відношення, оберненого до даного?

5. Чи може відношення мати не одну, а кілька властивостей?

6. Дати визначення несіткого відношення.

7. Що являє собою перша та друга, глобальна проекції нечіткого відношення?

8. Що являє собою об’єднання двох нечітких відношень?

 

Лекція 5

Синтез систем на основі поняття про теорію автоматів

1. Загальна характеристика автоматів.

2. Скінченні автомати.

3. Представлення скінченних автоматів.

4. Аналіз кінцевих автоматів.

5. Автомати Мілі та Мура.