БУЛЕАН МНОЖЕСТВА. РАЗБИЕНИЕ МНОЖЕСТВА

Пусть задано непустое множество X. Множество всех подмножеств этого основного множества, включая его само и пустое множество, называется булеаном данного множества и обозначается Р(X) или 2^х. Если X содержит n элементов, то булеан содержит 2 ^п элементов, которыми есть подмножества множества А, собственные и несобственные.

Говорят, что элементы Х₁, Х₂,… Х _п булеана 2^х образуют разбиение множества X, если

(4.2.1)

В этом случае множества Х₁, Х₂,… Х _п называются блоками разбиения множества X.

Правило суммы (лежащее в основе многих комбинаторных вычислений и оценок). Пусть X – конечное множество, , ç X ç- его мощность (число его элементов). Тогда имеет место условие:

ç X ç£ ç Х₁ ç +ç Х₂ ç+…+ç Х _п ç, (4.2.2)

причём равенство достигается, когда Х₁, Х₂,… Х _п образуют разбиение множества X, т.е. удовлетворяют (4.2.1).

 

Задача 4.2.1. Найти булеаны множеств А ={1, 2}; B ={ a, b, c }; C ={1, 2, 3, 4}.

Решение. Р(А) = {{1}, {2}, {1, 2}, {Æ}};

P(B) = {{ a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c }, {Æ}};

P(С) = {{1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}, {Æ}}.

 

Задача 4.2.2. Найти разбиение множеств А ={1, 2}; B ={ a, b, c }; C ={1, 2, 3, 4}.

Решение.

Множество А: Х₁ = {1}, X₂ = {2}; A = X₁ È X₂. Это единственный способ разбиения множества А.

Множество В: первый способ: Х₁ = { a }, X₂ = { b }; X₃ = { c };

второй способ: Х₁ = { a, b }, X₂ = { c };

третийспособ: Х₁ = { a }, X₂ = { b, c }.

Множество С: первый способ: Х₁ = {1}, X₂ = {2}; X₃ = {3}; Х₄ = {4};

второй способ: Х₁ = {1}, X₂ = {2, 3}; X₃ = {4};

третий способ: Х₁ = {1, 2}, X₂ = {2}; X₃ = {3, 4};

четвёртый способ: Х₁ = {1, 2}, X₂ = {3, 4};

пятый способ: Х₁ = {1, 2, 3}, X₂ = {4}; и т.д.

 

Задачи для самостоятельного решения.

1. Найти булеаны следующих множества: А ={1}, B ={3, 5}, C ={7, 8, 10}, D ={ m, n, p, q }. Найти разбиение множеств A, B, C, D.