1.4 Булеан множества

Напомним, что число элементов конечного множества называется мощностью множества и обозначается символом A или Card  A (от английского cardinality - мощность).

Определение. Множество всех подмножеств данного множества называют булеаном множества. Булеан обозначают символом B(A).

Пример. Пусть A = { 1,2,3 }. Перечислить элементы булеана множества A.

B(A)={ ,{ 1 },{ 2 },{ 3},{ 1,2 },{ 1,3 },{ 2,3},{ 1,2,3 } }.

Пример. Пусть A = { 1,2,3,4,...,n }, т.е. |A | = n. Найдем мощность множества B(A).

Для определения CardB(A) воспользуемся биномиальными коэффициентами C_n^k (число сочетаний из n по k)⁴. Перечислим по порядку, начиная с пустого множества, все подмножества множества A:

пустому подмножеству множества A поставим в соответствие число 1 = C_n⁰;

булеан содержит одноэлементные подмножества:

{ 1 },  { 2 },  { 3 },  ...,  {n}.

Число одноэлементных подмножеств равно n = C_n¹;

булеан содержит следующие двухэлементные подмножества:

{ 1,2 },{ 1,3 },{ 1,4 }, ,{ 1,n },{ 2,3 },{ 2,4 }, ,{ 2,n },

{ 3,4 },{ 3,5 }, ,{ 3,n }, ,{ n  2,n  1 },{ n  2,n },{ n  1,n}.

Количество двухэлементных подмножеств равно

n(n  1) 2 = Cn2 ;

продолжая этот подсчет, получим, что булеан содержит C_n³ трехэлементных подмножеств, C_n⁴ четырехэлементных подмножеств и так далее;

наконец, мы отметим, что булеан содержит C_n^{n  1} (n  1)-элементных подмножеств и одно n-элементное подмножество - само множество A, которому мы сопоставим биномиальный коэффициент C_nⁿ = 1.

В результате сумма всех биномиальных коэффициентов покажет нам количество элементов булеана B(A):

2n = (1 + 1)n = Cn0 + Cn1 + Cn2 + ... + Cnn  1 +Cnn     .

Таким образом, для любого множества A, если Card  A = n, то Card B(A)=2ⁿ.