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

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

2. Які властивості має відношення порядку?

3. Яка множина називається впорядкованою?

4. Чим відрізняється лінійний порядок від часткового?

5. Чим відрізняється строгий порядок від нестрогого?

6. Як формулюється аксіома антисиметричності бінарного відношення?

7. Що таке діаграма Хасе?

8. Як визначається покривальність елементів у частково впорядкованій множині?

9. Які елементи називаються порівнянними в частково впорядкованій множині?

10. Що таке верхня (нижня) грань?

11. Який елемент в упорядкованій множині називається найбільшим (найменшим)?

12. Як визначається супремум та інфімум у частково впорядкованій множині?

13. Яка множина називається ланцюгом?

14. Як визначається довжина ланцюга?

15. Як визначається висота елемента?

16. Як визначається висота частково впорядкованої множини?

17. Який елемент називається старшим?

6 Структури. Алгебраїчні системи. Ізоморфізм

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

Поняття структури відноситься до середини XIX ст. Уперше його ввів німецький математик Дедекинд Рихард Юліус Вільгельм. Термін “структура” належить американському вченому Гаррету Біркгофу із Принстонського університету.

6.1 Структура

Визначення 6.1. Структура – частково впорядкована множина, у якій кожна двоелементна підмножина має одну єдину точну верхню (супремум) і точну нижню (інфімум) грані:

:.

Визначення 6.2. Структура –це алгебраїчна система, для елементів якої справедливі закони ідемпотентності, комутативності, поглинання:

1) ;

2) ;

3) ,

і будь-які два елементи мають по одній єдиній точній верхній та нижній грані:

. (6.1)

Зауваження. Упорядкована система елементів не є структурою, якщо не існують супремум або інфімум; або вони існують, але не є єдиними.

Приклад 6.1. Будь-яка лінійно впорядкована множинає структурою, причому, якщо, то. Якможе розглядатися множина дійсних чисел(рис. 6.1).

Рисунок 6.1 – Лінійно впорядкована множина як структура

Приклад 6.2.Множина всіх підмножин даної множини (булеан), упорядкована за включенням, із двома бінарними операціями об'єднання й перетинання:(рис. 6.2).

Рисунок 6.2 – Частково впорядкована множинаяк структура

Визначення 6.3.Структураможе бути також визначена як універсальна алгебра із двома бінарними операціями об'єднання, перетинання(додаванняй множення; диз'юнкції, кон’юнкції), що задовольняють властивості (властивості сформульовані в термінах теоретико-множинних операцій):

1) (ідемпотентність);

2) (комутативність);

3) (асоціативність);

3) (елімінація)

і для будь-яких двох елементів виконується умова

. (6.2)

Визначення 6.4. Підструктурає підмножина структури, що разом з кожною парою елементівмістить також їхнє об'єднання(sup) і перетинання(inf) , тобто

.

Визначення 6.5. Інтервалом називаються підструктури з найменшим елементом і найбільшим елементом :.

Визначення 6.6. Нульовий і одиничний елементи в структурі називаютьсяструктурними нулем і одиницею.

Визначення 6.7. У структурізіструктурними нулем і одиницеюдва елементи,називаються додатковими, якщо,.

Визначення 6.8. Елемент, додатковий до елемента, називаєтьсядоповненням елементав структурі.

Визначення 6.9. Два елементи, що мають спільне доповнення у структурі, називаютьсязв'язанимив.

Приклад 6.3.У структурііз прикладу 6.2 (див. рис. 6.2) підструктуроює сукупність елементів, що може розглядатися як інтервал, обмежений найменшим елементомі найбільшим елементом. Нульовий і одиничний елементи в структурі– цейвідповідно. Прикладом додаткових елементів у структуріможуть служитий, оскільки,.

Серед структур виділяють спеціальні типи, найбільш затребувані на практиці. Це дедекиндові й дистрибутивні структури.