Обобщённо булевы решетки

дипломная работа

2.2. Основная теорема

(1)

Пусть - обобщённая булева решётка. Определим бинарные операции на B, полагая и обозначая через относительное дополнение элемента в интервале . Тогда - булево кольцо, т.е. (ассоциативное) кольцо, удовлетворяющее тождеству (а следовательно и тождествам , ).

(2) Пусть - булево кольцо. Определим бинарные операции и на , полагая, что и . Тогда - обобщённая булева решётка.

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

(1) Покажем, что - кольцо.

Напомним определение. Кольцо - это непустое множество с заданными на нём двумя бинарными операциями , которые удовлетворяют следующим аксиомам:

1. Коммутативность сложения: выполняется ;

2. Ассоциативность сложения: выполняется ;

3. Существование нуля, т.е. , ;

4. Существование противоположного элемента, т.е. , , ;

5. Ассоциативность умножения: , ;

6. Закон дистрибутивности.

Проверим, выполняются ли аксиомы кольца:

1. Относительным дополнением до элемента будет элемент , а относительным дополнением элемент . В силу того, что , а так же единственности дополнения имеем .

2. Покажем, что .

Рассмотрим все возможные группы вариантов:

1) Пусть , тогда (Далее везде под элементом x будем понимать сумму ).

Аналогично получаем в случаях , , , и . Заметим, что когда один из элементов равен нулю (например, c), то получаем тривиальные варианты (a+b=a+b).

2) Пусть , а элемент c не сравним с ними. Возможны следующие варианты:

Нетрудно заметить, что во всех этих случаях , кроме того:

если c=a+b, то (a+b)+c=0=a+(b+c);

если c=0, то получаем тривиальный вариант.

Вариант, когда c равен наибольшему элементу решётки d, мы уже рассматривали.

Если c=b, то (a+b)+c=(a+b)+b=a и a+(b+c)=a+(b+b)=a.

Если c=a, то (a+b)+c=(a+b)+a=b и a+(b+c)=a+(b+a)=b.

Аналогично для случаев , , , и .

3) Под элементами нижнего уровня будем понимать элементы , , , , , , , , т.е. те элементы 4-х мерного куба, которые образуют нижний трёхмерный куб.

Под элементами верхнего уровня будем понимать элементы , , , , , , , , т.е. те элементы 4-х мерного куба, которые образуют верхний трёхмерный куб.

Под фразой «элемент верхнего уровня, полученный из элемента нижнего уровня сдвигом по соответствующему ребру» будем понимать элемент верхнего уровня.

Пусть a, b, c несравнимы. Рассмотрим следующие варианты: и .

Пусть . Заметим, что это возможно только в случаях, когда принадлежат нижнему уровню, причём лежат на позициях элементов (рис. 1). Либо a, b остаются на своих позициях, элемент c сдвигается на верхний уровень по соответствующему ребру (рис. 2). Либо элемент a остаётся на своей позиции, элементы b, c сдвигаются на верхний уровень по соответствующему ребру (рис 3).

Нетрудно заметить, что во всех этих случаях .

Пусть , здесь так же .

Таким образом мы рассмотрели все основные группы вариантов расположения элементов a, b, c и во всех этих случаях ассоциативность сложения выполняется.

3. Рассмотрим в решётке элемент , к нему существует относительное дополнение до элемента , т.е. и . Учитывая, что в решётке и , имеем следующее: и . Отсюда .

4. Рассмотрим относительное дополнение элемента до , это элемент . Таким образом: и . Учитывая, что в решётке выполняются тождества и имеем следующее: и . Отсюда .

5. Так как в решётке выполняется ассоциативность , а так же имея , то .

6. Докажем дистрибутивность или что то же самое

(*).

Докажем, что дополнения левой и правой частей выражения (*) до верхней грани совпадают.

Нетрудно заметить, что дополнением правой части выражения (*) до элемента будет являться элемент .

Покажем это:

, по определению относительного дополнения элемента (), где за приняли элемент , а элемент за .

, по определению относительного дополнения элемента () , где за приняли элемент , а элемент за .

Покажем, что и для левой части (*) элемент будет являться относительным дополнением до верхней грани :

, т.к. .

Мы показали, что дополнения элементов и до верхней грани совпадают, следовательно, в силу единственности дополнения . А значит и , т.е. дистрибутивность доказана.

Таким образом, для все аксиомы кольца выполняются.

Заметим, что выполняется в силу того, что , а в решётке .

Также выполняется , потому что .

Таким образом, - булево кольцо.

Доказательство (2). Частичную упорядоченность имеем исходя из того, что исходное булево кольцо - частично упорядоченное множество. Кроме того - решётка, т.к. существуют sup(x,y) и inf(x,y), заданные соответствующими правилами: и .

Покажем, что решётка дистрибутивна, т.е. что выполняется тождество (*)

Рассмотрим левую часть выражения (*):

.

Рассмотрим правую часть выражения (*):

,

т.о. тождество верно, т.е. решётка является дистрибутивной.

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

Рассмотрим элемент булева кольца (в решётке лежит соответствующий ему элемент), заметим, что

и .

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

Таким образом, будет являться дистрибутивной решёткой с относительными дополнениями (обобщённой булевой).

Делись добром ;)