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

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

Страница 6

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.

Страницы: 1 2 3 4 5 6 7

Смотрите также:

Самомассаж рук и упражнения на сцепление пальцев рук
Самомассаж. 1. Левая рука поглаживает правую руку от кончиков пальцев к запястью. Затем также правой рукой помассировав левую. 2. Кисти рук лежат на краю стола. Ладонями ребенок проводит по ребру стола таким образом, чтобы вся ладонь последовательно промассировалась. 3. Кисти сжаты в кулаки. Кулако ...

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

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

Приёмы и методы запоминания

Приёмы и методы запоминания

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

Категории

Copyright © 2019 - All Rights Reserved - www.newlypedagog.ru