Изучение порядковой структуры

3. Решетка дистрибутивна тогда и только тогда, когда для любых ее элементов a, b и c имеем: a + b = a + c и ab = ac влекут b = c.

4. Дистрибутивность решетки равносильна выполнению в ней тождества: (a + b)(a + c)(b + c) = = abc.

Покажем, например, что дистрибутивная решетка L удовлетворяет свойству из критерия 3. Пусть a + b = a + c и ab = ac для некоторых b, c из L.

Тогда b = b(a + b) = b(a + с) = ab + bc = = ac + bc = c(a + b) = c(a + с) = с.

Решетка с 0 и 1 называется ограниченной. Если в ограниченной решетке a + b = 1 и ab = 0, то элементы a и b называются дополнениями друг друга.

По свойству 3 в ограниченных дистрибутивных решетках каждый элемент имеет не более одного дополнения. Значит, диамант и пентагон не являются дистрибутивными решетками.

Упражнение 17. Убедитесь непосредственно, что диамант и пентагон не дистрибутивны.

Упражнение 18. Проверьте свойство 2.

Упражнение 19. Докажите y в свойстве 4.

Определение 7. Ограниченная дистрибутивная решетка с 1 * 0, в которой каждый элемент имеет дополнение, называется булевой решеткой.

Сведения о булевых решетках, булевых алгебрах и булевых кольцах можно найти в. Заметим, что эти понятия равносильны, точнее, классы булевых решеток, булевых алгебр и булевых колец с единицей совпадают между собой.

Атомы решетки L с нулем 0 - это минимальные элементы упорядоченного множества L\{0}. Решетка с нулем 0 называется атомной, если для любого ее ненулевого элемента x существует такой атом а, что a # x.

Примеры булевых решеток:

1. Пусть M - произвольное непустое множество. Тогда булеан B(M) есть булева решетка с операциями и и п и порядком с, причем дополнением любого элемента A є B(M) служит его теоретико-множественное дополнение M\A. Булеан B(M) изоморфен прямому произведению Ml экземпляров двухэлементной цепи D = {0, 1}.

2. Рассмотрим множество B всех конечных множеств натуральных чисел и дополнений до них в N (так называемых коконечных множеств). Относительно включения множеств с множество B будет счетной атомной булевой решеткой - подрешеткой булеана B(N).

3. Рассмотрим алгебру (пропозициональных) высказываний A с операциями дизъюнкции, конъюнкции и отрицания. Ее элементами служат формулы логики высказываний. Отношение / равносильности высказываний является конгруэнцией на алгебре A. Соответствующая факторалгебра A// , называемая алгеброй Линденбаума, является булевой решеткой. В ней [P] # [Q] означает, что P^Q - тавтология, т. е. P^Q / И (истина). Дополнением к [P] будет класс []P] отрицания высказывания P.

Решетка +N0, |) - полная атомная дистрибутивная решетка с условием минимальности с наименьшим элементом 1 и наибольшим элементом

0, не являющаяся булевой решеткой. Наряду с числовой прямой R и булеанами, эта решетка - важнейший пример в теории упорядоченных множеств и решеток. Его непустыми конечными подмножествами исчерпываются, с точностью до изоморфизма, все конечные упорядоченные множества.

Пусть L - произвольная булева решетка. Каждый ее элемент а обладает единственным дополнением, которое будем обозначать а'.

Булевы решетки обладают следующими свойствами:

(1) 0N=1, 1N=0.

(2) а"=а.

(3) а # Ь ] Ь' # а' ] а' + Ь = 1 ] аЬ' = 0.

(4) (а + Ь)' = а'Ь', (аЬ)' = а' + Ь' (законы де Моргана).

(5) а + а' =1, аа' = 0.

Упражнение 20. Проверьте эти свойства.

Изобразим диаграммы Хассе трех первых (по

числу элементов) булевых решеток (рис. 4).

В решетке D2 элементы а и а' являются атомами. Атомы а, Ь, с решетки D3 располагаются на втором уровне диаграммы, а их дополнения а', Ь', с' - на третьем уровне.

Докажем теорему Стоуна о строении конечных булевых решеток, являющуюся частным случаем классической теоремы Стоуна о представлении булевых алгебр.

Теорема 3. Любая конечная булева решетка изоморфна булеану B(A), где A - множество всех ее атомов.

Доказательство. Пусть A - множество всех атомов конечной булевой решетки L. Установим изоморфизм между решетками L и B(A), сопоставив каждому элементу x є L подмножество в A: /(х)={а є A: а # x}. Сразу заметим, что f(0)= i и f(1) = A. Покажем, что f является биекцией L на B(A). Возьмем в L элементы x * у.

Тогда одно из соотношений x # у или у # x неверно. Можно считать, что неверно x # у. По свойству (3) булевых решеток xy' * 0. В силу атомности конечной решетки L в ней найдется такой атом a, что a # xy'. Имеем a # x и a # у', откуда a е f(x) и ay = ay'у = a0 = 0. Последнее означает, что a $ f(y). Поэтому f(x) * f(y). Тем самым доказана инъективность отображения f.