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м | akX}.

Имеем 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}.

Яндекс.Метрика