Решетки, дистрибутивные решетки. Булеан и теорема о числе элементов множества всевозможных подмножеств заданного множества.
Решетка — это множество М с двумя бинарными операциями , такими что выполнены следующие условия (аксиомы решетки):
1. идемпотентность:
а а = a, aa = а;
2. коммутативность:
аb = bа ab = ba;
3. ассоциативность:
(а b) с = а (b с), (а b) с = а (b с);
4. поглощение:
(оB) а = а, (аb) a = а;
5. Решетка называется дистрибутивной, если
a(bc)= (аb) (ас), а (bс) = (аb) (ас).
Булеан и теорема о числе элементов множества всевозможных подмножеств;
Множество всех подмножеств множества М называется булеаном и обозначается 2м:
ТЕОРЕМА Для конечного множества М .
Доказательство;
Индукция по |M|. База: если |M |=0, то и . Следовательно, .
Индукционный переход: пусть . Рассмотрим .
Положим M1:=и M2:= .
Имеем 2M= M1 M2 и M1 M2=. По индукционному предположению |M1|=2k-1, |M2|=2k-1. Следовательно, |2M|=|M1|+|M2|=2k-1+2k-1=.
Пересечение, объединение и разность подмножеств множества U (универсума) являются подмножествами множества U. Множество всех подмножеств множества U с операциями пересечения, объединения, разности и дополнения образует алгебру подмножеств множества U