ТОП 10:

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



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

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

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

XAx.

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

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

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

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

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

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

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

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

Бінарне відношення А називається антисиметричним, якщо АÇА-1ÌE, тобто відношення xiAxj та xjAxi виконуються одночасно тоді й тільки тоді, коли xi=xj.

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

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

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

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

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

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

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

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

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

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

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

Нехай – функціональне відношення, . Відповідність від першого до другого елемента кожної пари відношення називається функцією , або відображенням множини DF в 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. Автомати Мілі та Мура.







Последнее изменение этой страницы: 2017-02-21; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.235.30.155 (0.005 с.)