Булеан множини

Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо а Î Х, то { а }Í X. Множина усіх підмножин множини Х називається булеаном, або множиною-степенем множини Х й позначається P(Х) (або В (Х)), тобто P(Х)={ Y | Y Í X }. Якщо, наприклад, А ={ а, b, с }, то P(А)={ А,{ а, b },{ a, c },{ b, c },{ a },{ b },{ c },Æ}.

Теорема 4. Нехай множина Х складається з n елементів. Тоді P(Х) містить 2 ⁿ елементів.

Доведення. Нехай Х ={ х ₁,…, х_n }. Розглянемо такий спосіб подання підмножини Y множини Х. Нехай l_Y = l ₁… l_n – послідовність n нулів та одиниць така, що l_i =1, якщо х_i Î Y, й l_i =0, якщо x_i Ï Y, i Î{1,…, n }. Наприклад, якщо n =5, то підмножина Y ={ x ₂, x ₄, x ₅} множини { х ₁, х ₂, х ₃, х ₄, х ₅} подається у вигляді послідовності l_Y =01011. З іншого боку, кожна послідовність l ₁… l_n з n нулів та одиниць визначає деяку підмножину Y n-елементної множини Х таким чином: якщо l_i =1, то х_i Î Y, а якщо l_i =0, то x_i Ï Y. Наприклад, якщо l_Y =00110, то Y ={ x ₃, x ₄}. Отже, n-елементна множина Х має стільки ж підмножин, скільки існує послідовностей з n нулів та одиниць. Оскільки таких послідовностей 2 ⁿ, то й кількість елементів множини P(Х) теж 2 ⁿ.

Покриття та розбиття множини

Покриттям множини Х називається така сукупність Х ₁,…, Х_k,… підмно-жин множини Х, що Х = Х ₁È…È Х_k È….

Наприклад, множини Х ₁={2,4}, Х ₂={2,3,5}, Х ₃= X ₄={1,2,4} утворюють покриття множини Х ={1,2,3,4,5}, тому що Х ₁Í Х, Х ₂Í Х, Х ₃Í Х, Х ₄Í Х, а також Х = Х ₁È Х ₂È Х ₃È Х ₄. Множини Y ₁={1,2}, Y ₂={2,4}, Y ₃={2,3}, Y ₄={1,2,3} не утворюють покриття множини Х (хоча усі вони є підмножинами Х), тому що Х ≠ Y ₁È Y ₂È Y ₃È Y ₄. Множини Z ₁={1,2,5,6}, Z ₂={2,3,5}, Z ₃={1,4} теж не утворюють покриття множини Х, оскільки не кожна з них є підмножиною множини Х (Z ₁Ë Х).

Розбиттям множини Х називається множина таких непорожніх підмножин множини Х, що попарно не перетинаються й утворюють її покриття.

Наприклад, множина {{1}, {2,3}, {4,6}, {5}} є розбиттям множини Х ={1,2,3,4,5,6}. Множина {{1,4}, {2,3}, {4,6}, {1,5}} не є розбиттям множини Х, оскільки, зокрема, множини {1,4} та {4,6} перетинаються. Множина {{1,4}, {2}, {6}, {3}} також не є розбиттям множини Х, тому що сукупність {1,4}, {2}, {6}, {3} не є покриттям множини Х.