07. Булеан
Множество всех подмножеств множества М называется Булеаном И обозначается 2М:
2М = {А| А
М}
Теорема.Для конечного множества М |2М| = 2|M|
Доказательство:
Индукция по |M|. База: если |M| = 0, то М= Ø и 2Ø = {Ø}. Следовательно,
|2Ø | = |{Ø}| = 1 = 20=2|Ø|.
Индукционный переход: пусть 
M |М| <k→|2М| = 2|M|. Рассмотрим М = {а1,... ,ak},
|М| = k. Положим
M1 = {X 2M |akϵX} иМ2 = {X2м | ak
X}.
Имеем 2M = M1UМ2 и Mi∩М2 = Ø. По индукционному предположению |M1| = 2k-1,
|M2| = 2k-1. Следовательно, |2М| = |M1| + |M2| =2k-1 + 2k-1=2×2k-1 =2k=2М.
Пример. Пусть X = {1,2,3}. Тогда множество всех подмножеств X будет
2X = {0, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, X}.
| < Предыдущая | Следующая > |
|---|
