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

Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо аÎХ, то {а}Í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} не є покриттям множини Х.