Д.1.7 Відношення еквівалентності, порядку й домінування

Д.1.6 Способи завдання бінарних відношень

Можна привести кілька різних способів завдання бінарних відношень (переваги кожного зі способів визначаються властивостями множини ).

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

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

для всіх , .

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

При цьому .

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

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

– рефлексивність ;

– антирефлексивність ;

– симетричність ;

– асиметричність ;

– антисиметричність ;

– транзитивність ;

Розглянемо деякі, найбільш важливі з практичної точки зору, типи відношень.

Відношенням еквівалентності (позначається значками “=” або “ ~ ”) називається відношення, що задовольняє наступним властивостями:

– рефлексивності ;

– симетричності ;

– транзитивності .

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

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

Відношенням нестрогого порядку (використовуються позначення: , ) називається відношення, що має наступні властивості:

– рефлексивності ,

– антисиметричності ,

– транзитивності .

Відношенням строгого порядку (використовуються позначення , ) називається відношення, що має наступні властивості:

– антирефлексивності хибне;

– асиметричності та взаємновиключаєтся;

– транзитивності з .

Відношенням домінування називається відношення, що задовольняє двом властивостям: антирефлексивності й асиметричності. Говорять, що " домінує " (позначається ), коли в якомусь сенсі перевершує . Це відношення, як правило, використовується для опису адміністративних, управлінських, а в загальному випадку ієрархічних систем.

Дата добавления: 2017-02-01; Просмотров: 62; Нарушение авторских прав?; Мы поможем в написании вашей работы!