Глава 18. Решетки

Определения

Решетка — Это множество М С двумя бинарными операциями Ç и È, такими что выполнены следующие условия (аксиомы решетки):

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

А А = A, A A = а;

2. Коммутативность:

А B = B A а B = B а;

3. ассоциативность:

(А B) с = а (B с), (A B) с = A (B с);

4. поглощение:

(A B) а = A, (A B) а = а;

5. Решетка называется Дистрибутивной, Если

A (B с) = (A B) (A с), а (B с) = (А B) (А с).

Если в решетке $0 Î М "А 0 А = 0, то 0 называется нулем (или нижней гранью) решетки. Если в решетке $1 Î М "A 1 A = 1, то 1 называется единицей (или верхней гранью) решетки. Решетка с верхней и нижней гранями называется ограниченной.

В ограниченной решетке элемент А' называется дополнением элемента А, если А а' = 0 и A а' = 1.

Если "A Î M $ A'Î M A A' = 0 & A A' = L, тo ограниченная решетка называется решеткой с дополнением.

Дистрибутивная ограниченная решетка, в которой для каждого элемента суще­ствует дополнение, называется Булевой алгеброй.

Свойства булевой алгебры:

1. A È A = а, а А = а

По определению решетки;

2. A È B = B È а, а B = b А

По определению решетки;

3. A È (B È с) = (A È B) È с, а (B с) = (А B) с

По определению решетки;

4. (А B) È A = A, (A B) а = A

По определению решетки;

5. A È (B с) = (A È B) (A È с), а (B È с) = (А B) È (А с)

По свойству дистрибутивности;

6. A È 1 = 1, а 0 = 0

По свойству ограниченности;

7. A È 0 = A, а 1=а

По следствию из теоремы ограниченности;

8. A" = A

По теореме о свойствах дополнения;

9. (А b)' = a' È b', (A È b)' = А' b'

По теореме о свойствах дополнения;

10. A È A' = 1, а А' = 0

Так как дополнение существует.

Пример

(2M; , È, Ø) — булева алгебра, 1 = U, 0 = Æ.

Упражнения

Привести примеры алгебраических структур и классифицировать их.

< Предыдущая		Следующая >