Решетки

Определения

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

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

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

Пример

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

Дата добавления: 2014-12-27