19.2: Булеві алгебри

Давайте розберемо приклад набору потужності,\({\mathcal P}(X)\text{,}\) набору\(X\) більш уважно. Набір потужності - це решітка, яка впорядковується включенням. За визначенням набору потужності найбільшим елементом\({\mathcal P}(X)\) є\(X\) сам по собі, а найменший елемент -\(\emptyset\text{,}\) порожній набір. Для будь-якого набору\(A\) в\({\mathcal P}(X)\text{,}\) ми знаємо, що\(A \cap X = A\) і\(A \cup \emptyset = A\text{.}\) Це пропонує наступне визначення для решіток. Елемент\(I\) у poset\(X\) є найбільшим елементом, якщо\(a \preceq I\) для всіх\(a \in X\text{.}\) Елемент\(O\) є найменшим елементом\(X\) if\(O \preceq a\) for all\(a \in X\text{.}\)

Нехай\(A\) буде\({\mathcal P}(X)\text{.}\) згадати, що доповнення\(A\) є

\[ A' = X \setminus A = \{ x : x \in X \text{ and } x \notin A \}\text{.} \nonumber \]

Ми знаємо, що\(A \cup A' = X\) і\(A \cap A' = \emptyset\text{.}\) ми можемо узагальнити цей приклад для решіток. Решітка\(L\) з найбільшим елементом\(I\) і найменшим елементом\(O\) доповнюється, якщо для кожного\(a \in L\text{,}\) існує\(a'\) така, що\(a \vee a' = I\) і\(a \wedge a' = O\text{.}\)

У решітці\(L\text{,}\) бінарні операції\(\wedge\) задовольняють\(\vee\) і комутативні та асоціативні закони; однак вони не повинні задовольняти розподільному закону

\[ a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ); \nonumber \]

проте в\({\mathcal P}(X)\) розподільному законі задовольняється, оскільки

\[ A \cap ( B \cup C ) = (A \cap B ) \cup ( A \cap C ) \nonumber \]

бо\(A, B, C \in {\mathcal P}(X)\text{.}\) Ми скажемо, що решітка\(L\) є розподільною, якщо дотримується наступний розподільний закон:

\[ a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ) \nonumber \]

для всіх\(a, b, c \in L\text{.}\)

Теорема\(19.15\)

Решітка\(L\) є розподільною, якщо і тільки якщо

\[ a \vee ( b \wedge c ) = ( a \vee b ) \wedge ( a \vee c ) \nonumber \]

для всіх\(a, b, c \in L\text{.}\)

Доказ

Припустимо, що\(L\) це розподільна решітка.

\ begin {align*} a\ vee (b\ клин c) & = [a\ vee (a\ клин c)]\ vee (b\ клин c)\\ & = a\ vee [(a\ клин c)\ vee (b\ клин c)]\\ & = a\ vee [(c\ клин a)\ vee (c\ клин b)]\\ & = a\ vee [c\ клин (a\ vee b)]\\ & = a\ vee [(a\ vee b)\ клин c]\\ & = [(a\ vee b)\ клин a]\ vee [(a\ vee b)\ клин c]\\ & = (a\ vee b)\ клин (a\ vee c)\ текст {.} \ end {вирівнювати*}

Зворотне випливає безпосередньо з принципу подвійності.

Булева алгебра - це решітка\(B\) з найбільшим елементом\(I\) і найменшим елементом,\(O\) таким як\(B\) розподільним, так і доповненим. Набір степенів\(X\text{,}\)\({\mathcal P}(X)\text{,}\) є нашим прототипом для булевої алгебри. Як з'ясовується, це також одна з найважливіших булевих алгебр. Наступна теорема дозволяє охарактеризувати булеві алгебри з точки зору бінарних відносин\(\vee\) і\(\wedge\) без згадки про те, що булева алгебра є помножиною.

Теорема\(19.16\)

Набір\(B\) є булевою алгеброю тоді і тільки тоді, коли існують бінарні операції\(\vee\) і\(\wedge\) на\(B\) задоволення наступних аксіом.

1. \(a \vee b = b \vee a\)і\(a \wedge b = b \wedge a\) для\(a, b \in B\text{.}\)

2. \(a \vee ( b \vee c) = (a \vee b) \vee c\)і\(a \wedge ( b \wedge c) = (a \wedge b) \wedge c\) для\(a, b, c \in B\text{.}\)

3. \(a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c )\)і\(a \vee ( b \wedge c ) = (a \vee b ) \wedge ( a \vee c )\) для\(a, b, c \in B\text{.}\)

4. Існують елементи\(I\) і\(O\) такі, що\(a \vee O = a\) і\(a \wedge I = a\) для всіх\(a \in B\text{.}\)
5. Для кожного\(a \in B\) існує\(a' \in B\) таке, що\(a \vee a' = I\) і\(a \wedge a' = O\text{.}\)

Доказ

\(B\)Дозволяти бути множиною задовольняє (1) — (5) в теоремі. Один з ідемпотентних законів задовольняється, оскільки

\ begin {align*} a & = a\ vee O\\ & = a\ vee (a\ клин a')\\ & = (a\ vee a)\ клин (a\ vee a')\\ & = (a\ vee a)\ клин I\\ & = a\ vee a\ text {.} \ end {вирівнювати*}

Зауважте, що

\[ I \vee b = (b \vee b' ) \vee b = (b' \vee b ) \vee b = b' \vee (b \vee b) = b' \vee b = I\text{.} \nonumber \]

Отже, перший з двох законів поглинання дотримується, оскільки

\ begin {align*} a\ vee (a\ клин b) & = (a\ клин I)\ vee (a\ клин b)\\ & = a\ клин (I\ vee b)\\ & = a\ клин I\\ & = a\ text {.} \ end {вирівнювати*}

Інші ідемпотентні та поглинання закони доведені аналогічно. Оскільки\(B\) також задовольняє (1) — (3), умови теореми\(19.14\) виконуються; отже,\(B\) повинна бути решітка. Умова (4) говорить нам, що\(B\) це розподільна решітка.

Бо,\(a \in B\text{,}\)\(O \vee a = a\text{;}\) отже,\(O \preceq a\) і\(O\) є найменшим елементом в\(B\text{.}\) Щоб показати, що\(I\) це найбільший елемент в\(B\text{,}\) ми спочатку покажемо, що\(a \vee b = b\) еквівалентно\(a \wedge b = a\text{.}\) Оскільки\(a \vee I = a\) для всіх,\(a \in B\text{,}\) використовуючи закони поглинання, ми можемо визначити що

\[ a \vee I =(a \wedge I) \vee I = I \vee ( I \wedge a) = I \nonumber \]

або\(a \preceq I\) для всіх\(a\) в\(B\text{.}\) Нарешті, оскільки ми знаємо, що\(B\) доповнюється (5),\(B\) повинна бути булева алгебра.

І навпаки, припустимо, що\(B\) це булева алгебра. \(I\)\(O\)Дозволяти і бути найбільшим і найменшим елементами\(B\text{,}\) відповідно. Якщо ми визначаємо\(a \vee b\) і\(a \wedge b\) як найменші верхні та найбільші нижні межі,\(\{ a, b\}\text{,}\) то\(B\) це булева алгебра за теоремою\(19.14\), теоремою\(19.15\) та нашою гіпотезою.

Багато інших ідентичностей зберігаються в булевих алгебрах. Деякі з цих ідентичностей перераховані в наступній теоремі.

Теорема\(19.17\)

\(B\)Дозволяти булева алгебра. Тоді

1. \(a \vee I = I\)і\(a \wedge O = O\) для всіх\(a \in B\text{.}\)

2. Якщо\(a \vee b = a \vee c\) і\(a \wedge b = a \wedge c\) для\(a, b, c \in B\text{,}\) того\(b = c\text{.}\)

3. Якщо\(a \vee b = I\) і\(a \wedge b = O\text{,}\) тоді\(b = a'\text{.}\)
4. \((a')'=a\)для всіх\(a \in B\text{.}\)
5. \(I' = O\)і\(O' = I\text{.}\)
6. \((a \vee b)' = a' \wedge b'\)і\((a \wedge b)' = a' \vee b'\) (Закони Де Моргана).

Доказ

Доведемо тільки (2). Решта ідентичності залишають як вправи. Бо\(a \vee b = a \vee c\) і у\(a \wedge b = a \wedge c\text{,}\) нас є

\ почати {вирівнювати*} b & = b\ vee (b\ клин а)\\ & = b\ vee (a\ клин b)\\ & = b\ vee (а\ клин c)\\ & = (b\ vee a)\ клин (b\ vee c)\\ & = (a\ vee b)\ клин (b\ vee c)\\ & = vee c)\ клин (b\ vee c)\\ & = (c\ vee a)\ клин (c\ vee b)\\ & = c\ vee (а\ клин б)\\ & = c\ vee (а\ клин c)\\ & = c\ vee (c\ клин а)\\ & = c\ text {.} \ end {вирівнювати*}

Скінченні булеві алгебри

Булева алгебра - це скінченна булева алгебра, якщо вона містить скінченну кількість елементів у вигляді множини. Кінцеві булеві алгебри особливо приємні, оскільки ми можемо класифікувати їх аж до ізоморфізму.

\(C\)Дозволяти\(B\) і бути булеві алгебри. Біоб'єктивна карта\(\phi : B \rightarrow C\) - це ізоморфізм булевих алгебр, якщо

\ begin {align*}\ phi (a\ vee b) & =\ phi (a)\ vee\ phi (b)\\\ phi (a\ клин b) & =\ phi (a)\ клин\ фі (б)\ кінець {align*}

для всіх\(a\) і\(b\) в\(B\text{.}\)

Ми покажемо, що будь-яка скінченна булева алгебра є ізоморфною до булевої алгебри, отриманої шляхом прийняття набору степеней деякого скінченного множини\(X\text{.}\) Нам знадобиться кілька лем і визначень, перш ніж ми доведемо цей результат. \(B\)Дозволяти кінцева булева алгебра. Елемент\(a \in B\) є атомом\(B\) якщо\(a \neq O\) і\(a \wedge b = a\) для всіх\(b \in B\) з\(b \neq O\text{.}\) еквівалентно,\(a\) є атомом,\(B\) якщо немає\(b \in B\) з\(b \neq O\) відмінним від\(a\) такого, що\(O \preceq b \preceq a\text{.}\)

Лемма\(19.18\)

\(B\)Дозволяти кінцева булева алгебра. Якщо\(b\) є елементом\(B\) з,\(b \neq O\text{,}\) то є атом\(a\) в\(B\) такому, що\(a \preceq b\text{.}\)

Доказ

Якщо\(b\) це атом, нехай в\(a =b\text{.}\) іншому випадку, вибрати елемент\(b_1\text{,}\) не дорівнює\(O\) або\(b\text{,}\) такий, що\(b_1 \preceq b\text{.}\) Ми гарантуємо, що це можливо, оскільки\(b\) це не атом. Якщо\(b_1\) це атом, то ми закінчили. Якщо ні, вибрати\(b_2\text{,}\) не дорівнює\(O\) або\(b_1\text{,}\) такий, що\(b_2 \preceq b_1\text{.}\) Знову ж таки, якщо\(b_2\) це атом, нехай\(a = b_2\text{.}\) Продовжуючи цей процес, ми можемо отримати ланцюг

\[ O \preceq \cdots \preceq b_3 \preceq b_2 \preceq b_1 \preceq b\text{.} \nonumber \]

Оскільки\(B\) є кінцевою булевою алгеброю, цей ланцюжок повинен бути кінцевим. Тобто для деяких\(k\text{,}\)\(b_k\) це атом. Нехай\(a = b_k\text{.}\)

Лемма\(19.19\)

\(b\)Дозволяти\(a\) і бути атомами в скінченній булевій алгебрі\(B\) такі, що\(a \neq b\text{.}\) Тоді\(a \wedge b = O\text{.}\)

Доказ

Оскільки\(a \wedge b\) є найбільшою нижньою межею,\(a\) і\(b\text{,}\) ми знаємо, що\(a \wedge b \preceq a\text{.}\) Отже,\(a \wedge b = a\) або\(a \wedge b = O\text{.}\) Однак, якщо\(a \wedge b = a\text{,}\) тоді\(a \preceq b\) або або\(a = O\text{.}\) В будь-якому випадку ми маємо протиріччя, тому що\(a\) і\(b\) є обидва атоми; отже, \(a \wedge b = O\text{.}\)

Лемма\(19.20\)

\(B\)Дозволяти Булева алгебра і\(a, b \in B\text{.}\) Наступні твердження еквівалентні.

1. \(a \preceq b\text{.}\)
2. \(a \wedge b' = O\text{.}\)
3. \(a' \vee b = I\text{.}\)

Доказ

(1)\(\Rightarrow\) (2). Якщо\(a \preceq b\text{,}\) тоді\(a \vee b = b\text{.}\) Тому,

\ begin {align*} a\ клин b' & = a\ клин (a\ vee b) '\\ & = a\ клин (a'\ клин b')\\ & = (a\ клин a')\ клин b'\\ & = O\ клин b\\ & = O\ text {.} \ end {вирівнювати*}

(2)\(\Rightarrow\) (3). Якщо\(a \wedge b' = O\text{,}\) тоді\(a' \vee b = (a \wedge b')' = O' = I\text{.}\)

(3)\(\Rightarrow\) (1). Якщо\(a' \vee b = I\text{,}\) тоді

\ begin {align*} a & = a\ клин (a'\ vee b)\\ & = (a\ клин a')\ vee (a\ клин b)\\ & = O\ vee (a\ клин b)\\ & = a\ клин b\ текст {.} \ end {вирівнювати*}

Таким чином,\(a \preceq b\text{.}\)

Лемма\(19.21\)

\(B\)Дозволяти бути булева алгебра\(b\) і і\(c\) бути елементи в\(B\) такий, що\(b \not\preceq c\text{.}\) Тоді існує атом\(a \in B\) такий, що\(a \preceq b\) і\(a \not\preceq c\text{.}\)

Доказ

За Лемма\(19.20\),\(b \wedge c' \neq O\text{.}\) Отже, існує\(a\) такий атом, що\(a \preceq b \wedge c'\text{.}\) Отже,\(a \preceq b\) і\(a \not\preceq c\text{.}\)

Лемма\(19.22\)

Нехай\(b \in B\) і\(a_1, \ldots, a_n\) бути атоми\(B\) таких, що\(a_i \preceq b\text{.}\) Тоді\(b = a_1 \vee \cdots \vee a_n\text{.}\) Крім того, якщо\(a, a_1, \ldots, a_n\) атоми\(B\) таких, що\(a \preceq b\text{,}\)\(a_i \preceq b\text{,}\) а\(b = a \vee a_1 \vee \cdots \vee a_n\text{,}\) потім\(a = a_i\) для деяких\(i = 1, \ldots, n\text{.}\)

Доказ

Нехай\(b_1 = a_1 \vee \cdots \vee a_n\text{.}\) Оскільки\(a_i \preceq b\) для кожного\(i\text{,}\) ми знаємо, що\(b_1 \preceq b\text{.}\) Якщо ми можемо показати, що\(b \preceq b_1\text{,}\) тоді лема вірна антисиметрії. Припустимо,\(b \not\preceq b_1\text{.}\) тоді існує атом\(a\) такий, що\(a \preceq b\) і\(a \not\preceq b_1\text{.}\) Оскільки\(a\) є атом, і\(a \preceq b\text{,}\) ми можемо зробити висновок, що\(a = a_i\) для деяких\(a_i\text{.}\) Однак це неможливо,\(a \preceq b_1\text{.}\) тому що\(b \preceq b_1\text{.}\)

Тепер припустимо, що\(b = a_1 \vee \cdots \vee a_n\text{.}\) If\(a\) є атомом менше, ніж\(b\text{,}\)

\[ a = a \wedge b = a \wedge( a_1 \vee \cdots \vee a_n ) = (a \wedge a_1) \vee \cdots \vee ( a \wedge a_n )\text{.} \nonumber \]

Але кожен термін є\(O\) або\(a\) з\(a \wedge a_i\) відбувається тільки для одного\(a_i\text{.}\) Отже, по Лемма\(19.19\),\(a = a_i\) для деяких\(i\text{.}\)

Теорема\(19.23\)

\(B\)Дозволяти кінцева булева алгебра. Тоді існує безліч\(X\) таких, що\(B\) є ізоморфним до\({\mathcal P}(X)\text{.}\)

Доказ

Ми покажемо, що\(B\) є ізоморфним,\({\mathcal P}(X)\text{,}\) де\(X\) знаходиться набір атомів\(B\text{.}\) Let\(a \in B\text{.}\) By Lemma\(19.22\), ми можемо писати\(a\) однозначно, як\(a = a_1 \vee \cdots \vee a_n\) для\(a_1, \ldots, a_n \in X\text{.}\) Отже, ми можемо визначити карту\(\phi : B \rightarrow {\mathcal P}(X)\) по

\[ \phi(a) = \phi( a_1 \vee \cdots \vee a_n ) = \{a_1, \ldots, a_n \}\text{.} \nonumber \]

Зрозуміло,\(\phi\) це на.

Тепер нехай\(a = a_1 \vee \cdots \vee a_n\) і\(b = b_1 \vee \cdots \vee b_m\) бути елементами в\(B\text{,}\) де кожен\(a_i\) і кожен\(b_i\) є атомом. Якщо\(\phi(a) = \phi(b)\text{,}\) потім\(\{a_1, \ldots, a_n \} = \{b_1, \ldots, b_m \}\) і,\(a = b\text{.}\) отже,\(\phi\) є ін'єкційним.

З'єднання\(a\) і\(b\) зберігається\(\phi\) з тих пір

\ почати {align*}\ phi (a\ vee b) & =\ фі (a_1\ vee\ cdots\ vee a_n\ vee b_1\ vee\ cdots\ vee\ vee b_m)\\ & =\ {a_1,\ ldots, a_n, b_1,\ ldots, b_m\}\\ & =\\ a_1,\ ldots, a_n\}\ чашка\ {b_1,\ ldots, b_m\}\\ & =\ фі (a_1\ ве\ cdots\ ве a_n)\ чашка\ фі (b_1\ клин\ cdots\ vee b_m)\\ & =\ phi (a) \ чашка\ фі (b)\ текст {.} \ end {вирівнювати*}

Аналогічно,\(\phi( a \wedge b ) = \phi(a) \cap \phi(b)\text{.}\)

Ми залишаємо доказ наступного слідства як вправу.

Слідство\(19.24\)

Порядок будь-якої скінченної булевої алгебри повинен бути\(2^n\) для деякого натурального числа\(n\text{.}\)