Читать диплом по математике: "Обобщённо булевы решетки" Страница 2

(Назад) (Cкачать работу)

Верхней гранью подмножества Х в упорядоченном множестве Р называется элемент a из Р, больший или равный всех x из X.

Точная верхняя грань подмножества X упорядоченного множества P – это такая его верхняя грань, которая меньше любой другой его верхней грани. Обозначается символом sup X и читается «супремум X».

Согласно аксиоме антисимметричности упорядоченного множества, если точная верхняя грань существует, то она единственна.

Понятия нижней грани и точной нижней грани (которая обозначается inf X и читается «инфинум») определяются двойственно. Также, согласно аксиоме антисимметричности упорядоченного множества, если точная нижняя грань X существует, то она единственна.

Решёткойназывается упорядоченное множество L, в котором любые два элемента x и y имеют точную нижнюю грань, обозначаемую , и точную верхнюю грань, обозначаемую .

Примеры решёток:

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

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

На решётке можно рассматривать две бинарные операции:

- сложение и

- произведение

Эти операции обладают следующими свойствами:

1. ,идемпотентность;

2. ,коммутативность;

3. ,ассоциативность;

4. ,законы поглощения.

ТЕОРЕМА 1.1. Пусть L - множество с двумя бинарными операциями , обладающими свойствами (1) – (4). Тогда отношение(или ) является порядком на L, а возникающее упорядоченное множество оказывается решёткой, причём:и.

Доказательство. Рефлексивность отношениявытекает из свойства (1). Заметим, что оно является следствием свойства (4):

Еслии , то естьи , то в силу свойства (2), получим . Это означает, что отношениеантисимметрично.

Еслии , то применяя свойство (3), получим: , что доказывает транзитивность отношения .

Применяя свойства (3), (1), (2), получим:

,

.

Следовательно,и .

Еслии , то используя свойства (1) – (3), имеем:

, т.е. .

По определению точней верхней грани убедимся, что .

Из свойств (2), (4) вытекает, чтои .

Еслии , то по свойствам (3), (4) получим:

.

Отсюда по свойствам (2) и (4) следует, что

.

Таким образом, . Пусть L решётка, тогда её наибольший элемент 1 характеризуется одним из свойств:

1. .

2. .

Аналогично характеризуется наименьший элемент :

1.

2. .

Решётка L называется дистрибутивной, если для любыхвыполняется:

D1. .

D2. .

В любой решётке тождества D1 и D2 равносильны. Доказательство этого факта содержится в книге [2], стр. 24.

Примеры дистрибутивных решёток:

Множество целых положительных чисел,означает, чтоделит . Это решётка с операциями НОД и НОК. Любая цепь является дистрибутивной решёткой.

ТЕОРЕМА 1.2. Решётка L с 0 и 1 является дистрибутивной тогда и только тогда, когда она не содержит подрешёток вида

Доказательство этой теоремы можно найти в книге [1].

Всюду далее под словом «решётка» понимается произвольная дистрибутивная решётка с 0.

Решётка L называется обобщённой булевой,

Похожие работы