Теоремі про решетки.

2. Рассмотрим решетку M₃ («диамант») на рис. 6.4. Все цепи {0, a, I}, {0, b, I}, {0, c, I} дистрибутивны, следовательно, они модулярны. Возьмем три элемента, не лежащие на одной цепи: a £ I и c. Условие модулярности для них выполняется: a Ú (c Ù I) = (a Ú c) Ù I, так как a Ú c = I Ù I, т.е. I = I. Нетрудно убедиться в том, что условие модулярности в M₃ будет выполняться для любых трех элементов, два из которых находятся в отношении порядка, и, следовательно, решетка M₃ модулярна. Проверим выполнение свойства дистрибутивности для  элементов a, b, c (все остальные тройки элементов в этой решетке дистрибутивны): a Ú (b Ù c) = (a Ú b) Ù (a Ú c). Равенство невыполнимо, так как a Ú (b Ù c)  = a Ú 0 = a, но (a Ú b) Ù (a Ú c) = I Ù I = I, и a ¹ I. Отметим, что выполнимо только неравенство дистрибутивности: a £ I. Таким образом, решетка M₃ модулярна, но не дистрибутивна. Все элементы a, b, c несравнимы, следовательно, для них не определен закон модулярности, но дистрибутивный закон должен выполняться для всех элементов, в том числе для a, b, c.

 

Отсюда следует вывод: решетка может быть модулярной, но недистрибутивной.

 

Обобщая выводы, полученные нами при исследовании дистрибутивных и модулярных решеток, можно сформулировать следующую теорему.

 

Теорема 6.6.

а)  Решетка L модулярна тогда и только тогда, когда она не содержит пентагонов.

б) Модулярная решетка L дистрибутивна тогда и только тогда, когда она не содержит диамантов.

в) Решетка L дистрибутивна тогда и только тогда, когда она не содержит ни пентагонов, ни диамантов.

Основным свойством  модулярных решеток является принцип транспозиции.

 

Теорема 6.7 (принцип транспозиции). В любой модулярной решетке отображения ja: x ® x Ù a  и yb: y ® y Ú b являются взаимно обратными изоморфизмами между интервалами.  [b, a Ú b] и [a Ù b, a].

Доказательство.  Если  x Î [b, a Ú b], то ja(x) Î [a Ù b, a] в силу изотонности ja. Согласно L5,  (x Ù a) Ú b =  x Ù (a Ú b), так как x Î [b, a Ú b], Это означает, что yb(ja(x)) = x.  В силу принципа двойственности   получаем, что ja (yb(y)) = y для всех yÎ[a Ù b, a].

 

Следствие. В любой модулярной решетке

если a ¹ b и оба элемента  покрывают c, то a Ú b покрывает и a, и b;    M1

если a ¹ b и c покрывает оба элемента, то a и b оба покрывают a Ù b.    M2

 

Пример. Для решетки N7 на рис. 6.4 не выполняется условие M2: элементы  b, e покрываются элементом I, однако, ни b, ни e не покрывает b Ù e = 0. Отсюда следует, что решетка N7 немодулярна. Нетрудно проверить, что условие M1 удовлетворяется в этой решетке. Такие решетки, в которых выполняется одно из условий M1 или M2, называются полумодулярными: если в решетке выполняется условие M1, то решетка полумодулярна сверху, а если условие M2 – то полумодулярна снизу. Решетка N7 полумодулярна сверху.

 

1.5. Модулярные решетки с дополнениями

 

Определение 6.9. Дополнением элемента x в решетке с 0 и I называется элемент y такой, что x Ù y = 0 и x Ú y = I. Дополнение x будем обозначать x'.

Определение 6.10. Решетка называется решеткой с дополнениями, если все ее элементы имеют дополнения.

 

Определение 6.11. Решетка L называется решеткой с относительными дополнениями, если каждый ее замкнутый интервал является решеткой с дополнениями.

Давая определение подрешетки, мы определили замкнутый интервал [a, b] решетки как интервал, состоящий из всех элементов x Î L, таких что a £ x £ b. Такой интервал решетки всегда будет подрешеткой. Элемент x¢ является относительным дополнением элемента x Î [a, b], если x Ù x¢  =  a  и x Ú x¢ =  b.

 

Для дистрибутивных решеток  имеет место следующая теорема.

Теорема 6.7. Если в дистрибутивной решетке для фиксированного c

c Ú x = c Ú y и c Ù x = c Ù y, то x = y.    

Доказательство.

x = x Ù (c Ú x) = (закон поглощения) 

= x Ù (c Ú y) = (по условию теоремы) 

= (x Ù c) Ú (x Ù y) = (дистрибутивность)  

= (c Ù y) Ú (x Ù y) = (L2 и по условию c Ù x = c Ù y)  

= (c Ú x) Ù y = (c Ú y) Ù y = y.

Согласно этой теореме в любом  замкнутом интервале [a, b] дистрибутивной решетки элемент c может иметь  самое большее одно относительное  дополнение.

 

Теорема 6.8. Любая модулярная решетка  с дополнениями является решеткой с относительными дополнениями.

Доказательство. Пусть M — произвольная модулярная решетка с дополнениями. Рассмотрим интервал [0, b] Ì M. Если 0 £ x £ b в M, то x Ù (x' Ù b) = (x Ù x') Ù b = 0 Ù b = 0, так как M — решетка с дополнениями, а так как M — модулярна, то x Ú (x' Ù b) = (x Ú x') Ùb = I Ù b = b. Следовательно, B = [0, b] является модулярной подрешеткой с дополнениями решетки М. Если взять теперь [a, b] Ì B, то это будет модулярная решетка с дополнениями в B. Следовательно, по определению, М является модулярной решеткой с относительными дополнениями.

 

1.6. Булевы решетки

Определение 6.12. Булевой решеткой называется дистрибутивная решетка с дополнениями.

 

Теорема 6.10. В булевой решетке  любой элемент х имеет одно и только одно дополнение x'. При этом:

x Ù x' = 0,   x Ú x' = I;      L7

(x')' = x;    (инволюция)   L8

(x Ù y)' = x' Ú y',  (x Ú y)' = x' Ù y'.  (законы де Моргана)  L9

 

Доказательство. По теореме 6.7 в дистрибутивной решетке c Ú x = c Ú y и c Ù x = c Ù y, откуда x = y, т.е. каждый элемент дистрибутивной решетки с дополнениями имеет не более одного дополнения. L7 является определением дополнения. Докажем L8. Дополнение элемента х в дистрибутивной решетке единственно, следовательно, соответствие x ® x' — однозначно. Но, по определению, если х' является дополнением х, то х является дополнением х', следовательно, обратное соответствие также однозначно, т. е. (х')' = х.  L8 доказано.

Докажем L9. Если x и y имеют дополнения x' и y' соответственно, то элемент x Ù y имеет своим дополнением (x Ù y)' , а элемент x Ú y – (x Ú y)' .  В силу единственности дополнения для доказательства первого равенства L9 достаточно показать, что

(x Ù y) Ú (x¢ Ú y' ) = I и (x Ù y) Ù (x¢ Ú y¢) =  0.

Действительно, (x Ù y) Ú (x¢ Ú y' ) = (x¢ Ú y' Ú x) Ù (x¢ Ú y' Ú y) = I Ù I = I.

(x Ù y) Ù (x¢ Ú y¢) = (x Ù y Ù x¢ )Ú (x Ù y Ù y¢)  =  0 Ú 0 =  0.

Второе равенство L9 доказывается двойственно.

 

Лемма 6.7. В булевой решетке x Ù a = 0 тогда и только тогда,  когда x £ a'.

Доказательство. Действительно, если x £ a' то x Ù a £ a' Ù a = 0, и, если x Ù a = 0, то x = x Ù I = x Ù (a Ú a') = (x Ù a) Ú (x Ù a') = 0 Ú (x Ù a') = x Ù a', т. е. x = x Ù a', откуда следует, что . x £ a'.

Из леммы 6.7 следует, что  при a £ b, b' £ a', т. е. взаимно однозначное соответствие x ® x' обращает порядок (антиизотонно). Соответствие x' ® (x')' также антиизотонно, следовательно, x ® x' является дуальным изоморфизмом. Следовательно, любая булева решетка дуально изоморфна самой себе, т. е. самодвойственна.

 

Поскольку дополнения в  булевой решетке единственны, ее можно рассматривать как алгебру.

Определение 6.13. Булевой алгеброй B = <L, Ú, Ù, ¢, 0, I > называется алгебра с двумя бинарными операциями Ú и Ù,  одной унарной операцией ¢ и двумя нульарными операциями 0 и I, удовлетворяющими условиям L1 — L9. (Нульарные операции выделяют элементы 0, I множества L, эти элементы называются выделенными элементами).

 

Рис. 6.6.  Булевы решетки.