Бульові грати
Алгебраїчне подання решіток.
Поняття решітки
Нехай аналізовані далі множини А і В - чум.
Найбільшим (найменшим) елементом аÎА називається елемент а, якщо а ³ (£) х, де х Î А.
Теорема: Якщо у множині А існує найбільший елемент, то він єдиний.
Доказ: Припустимо, що існують два найбільші елементи а1 і а 2, тоді :
| а1 = а2; |
| > |
Максимальним (мінімальним) елементом множини А називається елемент аÎА, коли невірно, що а £(³)х, де х Î А.
Мажорантою (мінорантою) множини В (такої, що Æ Ì В Í А) є
елемент а Î А, такий, що елемент а є найбільшим (найменшим) елементом для множини В.
Безліч мажорант (мінорант) множини В утворює верхню (нижню) грань множини В.
Найменший елемент верхньої грані називаєтьсяточною верхньою гранню абоSupremum (Sup).
Найбільший елемент нижньої грані називаєтьсяточною нижньою гранню абоInfimum (Inf).
Частково-упорядковане безліч, в якому будь-яка пара елементів має Sup та Inf називаєтьсярешіткою.
 |
Введемо позначення Sup(a, b) = a b, Inf(a, b) = a b,
Будемо вважати традиційно використовувані тут значки È, Ç які не мають жодного відношення до теоретико-множинних операцій об'єднання та перетину.
Якщо виконуються закони:
1. a È b = b È a 1'. a b = b a
2. (a È b) È c = (b È c) Èa = a È b È c 2'. (a Ç b) Ç c = (b Ç c) Ç a = a Ç b Ç c
3. a È (a Ç b) = a 3'. а Ç (b È a) = a
4. a È a = a 4'. а Ç a = a
то має місцеграти.
Тобто грати можна визначити як алгебру Z = , для операцій якої виконуються перелічені вище закони.
Решітка називаєтьсядистрибутивною, якщо додатково до перерахованих вище виконується дистрибутивний закон:
5. a b Ç c = (a b) Ç(a c) 5'. а Ç (b È c) = a Ç b È a Ç c
Приклад: Недистрибутивні грати:
a b Ç e = (a b) Ç (a e e)
b È c Ç d = b Ç c È b Ç d
b ¹ a недистрибутивність
Ці грати недистрибутивні.
Решітка називаєтьсяобмеженою, якщо вона має максимальний та мінімальний елементи.
Наприклад, якщо взяти відрізок дійсної осі від 0 до 1 (разом з кінцевими точками) і відношення "менше", це буде обмежена решітка. Прибравши крайні точки, отримуємо необмежену решітку.
1 1
- необмежені грати - обмежені
Зазвичай мінімальний елемент грат позначають як 0, а максимальний як 1.
ā- доповнення а, якщо а È ā = 1 і а Ç ā =0
Грати єрешіткою з доповненням, якщо кожен елемент має хоча б одне доповнення.
Обмежені дистрибутивні грати з доповненням єбульової.