Решетки, дистрибутивные решетки. Булеан и теорема о числе элементов
множества всевозможных подмножеств заданного множества.
Решетка — это множество М с двумя бинарными операциями
, такими что выполнены следующие условия (аксиомы решетки):1.
идемпотентность:
а 
а = a, a
a
= а; 2. коммутативность:
а
b
= b
а
a
b
= b
a;3.
ассоциативность:
(а 
b) 
с = а 
(b 
с), (а 
b) 
с = а 
(b 
с);4. поглощение:
(о
B)
а = а, (а
b)
a = а;5. Решетка называется
дистрибутивной,
если
a
(b
c)=
(а
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