Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Конечные булевы алгебры

Конечные булевы алгебры


Покажем применение понятия прямого произведения алгебраических систем к теории булевых алгебр. Мы докажем здесь интересный факт, состоящий в том, что мощность любой конечной булевой алгебры есть некоторая степень двойки. Отсюда будет следовать, например, что в конечной булевой алгебре может быть 1, 2, 8, 16, 32, 64 и т.д. элементов, но не может быть, скажем, 100 или 75 элементов. Чтобы доказать сформулированное утверждение о конечных булевых алгебрах, необходимо ввести некоторые вспомогательные определения и доказать некоторые утверждения. Напомним, что мы определили булеву алгебру [math]\mathbb{B}^n[/math] булевых векторов размерности [math]n[/math] (см. пример 3.11). Эта алгебра есть не что иное, как n-я декартова степень двухэлементной булевой алгебры


[math]\mathbb{B}= \bigl(\{0,1\},\lor,\land,0,1\bigr).[/math]

Пусть [math]\mathcal{L}=\{L,\lor,\land,\bold{0},\bold{1}\}[/math] — симметричное полукольцо. Рассмотрим произвольные элементы [math]a,b\in L[/math], такие, что [math]a\leqslant b[/math]. Множество [math][a,b]=\{x\colon\, a\leqslant x\leqslant b\}[/math] будем называть отрезком, элемент [math]a[/math] — левым, а элемент [math]b[/math] — правым концом отрезка.


Замечание 4.5. Напомним, что в симметричном полукольце нуль полукольца является наименьшим, а единица полукольца — наибольшим элементом в данном полукольце относительно естественного порядка этого идемпотентного полукольца. Поэтому для любого элемента х симметричного полукольца справедливо неравенство [math]\bold{0}\leqslant x\leqslant \bold{1}[/math], и тем самым все симметричное полукольцо можно рассматривать как отрезок [math][\bold{0};\bold{1}][/math] симметричного полукольца.


Любой отрезок [math][a,b][/math] симметричного полукольца замкнут относительно операций [math]\lor[/math] и [math]\land[/math], но не является, вообще говоря, подполукольцом [math]\mathcal{L}[/math], так как не содержит [math]\bold{0}[/math] (если [math]a\ne \bold{0}[/math]) и не содержит [math]\bold{1}[/math] (при [math]b\ne\bold{1}[/math]). Но поскольку элемент [math]a[/math] будет наименьшим, а элемент [math]b[/math] — наибольшим элементом отрезка [math][a,b][/math], алгебра


[math]\bigl([a,b],~\lor,~ \land,~ a,~b\bigr)[/math]

будет симметричным полукольцом с нулем [math]a[/math] и единицей [math]b[/math], которое мы будем обозначать тоже через [math][a,b][/math].


Для произвольно фиксированного элемента а симметричного полукольца [math]\mathcal{L}[/math] зададим отображение [math]\Theta_{a}[/math], сопоставляющее каждому [math]x\in L[/math] упорядоченную пару [math](x\land a,\,x\lor a)\in L^2[/math]. Так как [math]\bold{0}\leqslant x\land a \leqslant a[/math] и [math]a\leqslant x\lor a\leqslant \bold{1}[/math] для любого [math]x\in L[/math] (в силу свойств симметричного полукольца), то тем самым задано отображение [math]\Theta_{a}[/math] носителя полукольца [math]\mathcal{L}[/math] в декартово произведение отрезков [math][\bold{0},a]\times[a,\bold{1}]:[/math]


[math]\Theta_{a}\colon\, L\to [\bold{0},a]\times[a,\bold{1}].[/math]

Каждый из отрезков есть симметричное полукольцо. В силу теоремы 4.11 их декартово произведение также является симметричным полукольцом.




Теорема 4.12. Пусть [math]L[/math] — носитель симметричного полукольца [math]\mathcal{L}=(L,\lor,\land,\bold{0},\bold{1})[/math]. Для любого [math]a\in L[/math] отображение [math]\Theta_{a}[/math] есть мономорфизм полукольца [math]\mathcal{L}[/math] в полукольцо [math][\bold{0},a]\times[a,\bold{1}][/math].


Докажем, что [math]\Theta_{a}[/math] — гомоморфизм. Имеем [math]\Theta_{a}(\bold{0})= (\bold{0},a)[/math], и эта упорядоченная пара и является наименьшим элементом, т.е. нулем, полукольца [math][\bold{0},a]\times[a,\bold{1}][/math]. Точно так же [math]\Theta_{a}(\bold{1})= (a,\bold{1})[/math] — наибольший элемент, т.е. единица того же полукольца. Далее,


[math]\begin{aligned} \Theta_a(x\lor y)&= \bigl((x\lor y)\land a,\, (x\lor y)\lor a\bigr)=\\[2pt] &=\bigl((x\land a)\lor (y\land a),\, (x\lor a)\lor (y\lor a)\bigr)=\\[2pt] &=\Theta_{a}(x)\lor \Theta_{a}(y). \end{aligned}[/math]

Аналогично доказывается, что [math]\Theta_{a}(x\land y)= \Theta_{a}(x)\land \Theta_{a}(y)[/math]


Итак, [math]\Theta_{a}[/math] — гомоморфизм [math]\mathcal{L}[/math] в [math][\bold{0},a]\times [a,\bold{1}][/math].


Теперь надо доказать, что [math]\Theta_{a}[/math] — инъекция. Для этого нужно показать, что из равенства [math]\Theta_{a}(x)= \Theta_{a}(y)[/math] вытекает [math]x=y[/math]. Если [math]\Theta_{a}(x)= \Theta_{a}(y)[/math], то верны равенства


[math]x\land a=y\land a,\qquad x\lor a=y\lor a,[/math]
(4.2)

так как равенство упорядоченных пар означает равенство их одноименных компонент.

Теперь, используя равенства (4.2) и аксиомы симметричного полукольца, получим


[math]\begin{aligned} x&= x\land (x\lor a)= x\land (y\lor a)= (x\land y)\lor (x\land a)= (y\land x)\lor (y\land a)=\\[2pt] &= (y\lor y)\land (y\lor a)\land (x\lor y)\land (x\lor a)= y\land (y\lor a)\land (x\lor y)\land (x\lor a)=\\[2pt] &= y\land (x\lor y)\land (y\lor a)= y\land (y\lor a)=y. \end{aligned}[/math]

Таким образом, если [math]\Theta_{a}(x)=\Theta_{a}(y)[/math], то [math]x=y[/math], и [math]\Theta_{a}[/math] — инъекция.




Теорема 4.13. Если симметричное полукольцо [math]\mathcal{L}= (L,\lor, \land, \bold{0}, \bold{1})[/math] есть булева алгебра, то для любого [math]a\in L[/math] полукольца [math][\bold{0},a][/math] и [math][a,\bold{1}][/math] тоже булевы алгебры.


Поскольку [math][\bold{0},a][/math] и [math][a,\bold{1}][/math] — симметричные полукольца, то достаточно доказать, что в каждом из отрезков [math][\bold{0},a][/math] и [math][a,\bold{1}][/math] любой элемент имеет дополнение.


Для произвольного [math]u\in[\bold{0},a][/math] определим элемент [math]\overline{u}_{a}[/math] равенством [math]\overline{u}_{a}=\overline{u}\land a[/math]. Докажем, что этот элемент и есть дополнение и в полукольце [math][\bold{0},a][/math]. Для этого, как следует из свойства единственности дополнения в булевой алгебре, достаточно убедиться в том, что [math]\overline{u}_{a}\lor u=a[/math], а [math]\overline{u}_{a}\land u=\bold{0}[/math].


Действительно, [math]\overline{u}_{a}\land u= (\overline{u}\land a)\lor u=\bold{1}\land (a\lor u)[/math].


Так как [math]u\leqslant a[/math], то [math]a\lor u=a[/math], и [math]\bold{1}\land (a\lor u)=\bold{1}\land a=a[/math]. Итак, [math]\overline{u}_{a}\land u=a[/math]. Аналогично [math]\overline{u}_{a}\land u= (\overline{u}\land a)\land u=\bold{0}[/math]. Таким образом, [math]\overline{u}_{a}[/math] действительно является дополнением элемента и в полукольце [math][\bold{0},a][/math].


Теперь для произвольного [math]v\in[a,\bold{1}][/math] определим элемент [math]\overline{v}^{a}[/math] равенством [math]\overline{v}^{a}=\overline{v}\lor a[/math]. Как и выше, аналогично доказывается, что [math]\overline{v}^{a}\lor v=\bold{1},[/math] [math]\overline{v}^{a}\land v=a[/math]. Следовательно, элемент [math]\overline{v}^{a}[/math] является дополнением [math]v[/math] в полукольце [math][a,\bold{1}][/math].




Теорема 4.14. Если в условиях теоремы 4.12 полукольцо [math]\overline{L}[/math] является булевой алгеброй, то [math]\Theta_{a}[/math] — изоморфизм булевых алгебр [math]\mathcal{L}[/math] и [math][\bold{0,a]\times[a,\bold{1}][/math].


В силу теоремы 4.12 достаточно доказать, что [math]\Theta_{a}[/math] — эпиморфизм, сохраняющий дополнение, т.е.


1) для любой пары [math](y,z)[/math], где [math]y\leqslant a,~ z\geqslant a[/math], существует элемент [math]x\in L[/math], такой, что [math]\Theta_{a}(x)=(y,z)[/math];
2) [math]\Theta_{a}(\overline{x})= (\overline{x}\land a,\, \overline{x}\lor a)= \overline{\Theta_{a}(x)}[/math].

Докажем первое утверждение. Убедимся, что указанный в нем элемент [math]x[/math] может быть определен равенством [math]x=y\lor (z\land \overline{a})[/math]. Имеем


[math]x\land a= \bigl[y\lor (z\land \overline{a})\bigr]= (y\lor z)\land (y\lor \overline{a})\land a= \bigl[(y\lor z)\land a\bigr]\land (y\lor \overline{a}).[/math]

Поскольку [math]y\leqslant a\leqslant z[/math], то [math](y\lor z)\land a= (y\land a)\lor (z\land a)= y\lor a=a[/math]. Следовательно, [math]x\land a=a\land (y\lor \overline{a})= a\land y=y[/math] (так как [math]y\leqslant a[/math]). Аналогично доказывается, что [math]x\lor a=z[/math]. Таким образом, [math]\Theta_{a}(x)=(y,z)[/math].


Второе утверждение следует из того, что элемент [math]\overline{x}\land a[/math] есть дополнение элемента [math]u=x\land a[/math] в булевой алгебре [math][\bold{0},a][/math], а элемент [math]\overline{x}\lor a[/math] — дополнение элемента [math]v=x\lor a[/math] в булевой алгебре [math][a,\bold{1}][/math].


Действительно, согласно теореме 4.13, имеем


[math]\overline{u}_{a}= \overline{x\land a}\land a= (\overline{x}\lor \overline{a})\land a= (\overline{x}\land a)\lor (\overline{a}\land a)= (\overline{x}\land a)\lor \bold{0}= \overline{x}\land a\,.[/math]

Согласно принципу двойственности, [math]\overline{v}^{a}= (\overline{x\lor a})^{a}=\overline{x}\lor a\,.[/math]. Итак,


[math]\overline{\Theta_{a}(x)}= \bigl((\overline{x\land a})_{a},(\overline{x\lor a})^a\bigr)= (\overline{x}\land a, \overline{x}\lor a)= \Theta_{a}(\overline{a}).[/math]



Изоморфность булевой алгебры прямому произведению двух булевых алгебр


В силу доказанных теорем имеем следующий результат.


Следствие 4.2. Любая булева алгебра изоморфна прямому произведению некоторых двух булевых алгебр.


На рис. 4.4 представлены все возможные способы представления четырехэлементной булевой алгебры (ее элементы обозначены [math]\bold{0},\,\bold{1},\,a,\,b[/math]) в виде прямого произведения двух двухэлементных булевых алгебр. Эти представления определяются изоморфизмами [math]\Theta_{a}[/math] и [math]\Theta_{b}[/math]. Изоморфизм [math]\Theta_{a}[/math] есть изоморфизм исходной четырехэлементной булевой алгебры на декартово произведение ее отрезков [math][\bold{0},a][/math] и [math][a,\bold{1}][/math], каждый из которых изоморфен двухэлементной булевой алгебре [math]\mathbb{B}[/math]. Вместе с тем декартово произведение указанных отрезков дает четырехэлементную булеву алгебру, элементами которой служат упорядоченные пары [math](\bold{0},a),\,(a,a),\,(a,\bold{1})[/math] и [math](\bold{0},\bold{1})[/math], причем пара [math](\bold{0},a)[/math] будет нулем, а пара [math](a,\bold{1})[/math] — единицей этой булевой алгебры, которая изоморфна исходной. Аналогично рассматривается изоморфизм [math]\Theta_{b}[/math].


Все возможные способы представления четырехэлементной булевой алгебры (ее элементы обозначены 0,1,a,b) в виде прямого произведения двух двухэлементных булевых алгебр

Интересно отметить, что могут быть заданы и изоморфизмы [math]\Theta_{\bold{0}}[/math] и [math]\Theta_{\bold{1}}[/math], но каждый из них определяет тривиальное разложение исходной булевой алгебры в виде ее прямого произведения на одноэлементную булеву алгебру, т.е. в виде [math][\bold{0},\bold{1}]\times [\bold{0},\bold{0}][/math] или в виде [math][\bold{0},\bold{1}]\times [\bold{1},\bold{1}][/math]. Интерес представляют, следовательно, такие изоморфизмы [math]\Theta_{a}[/math], где элемент [math]a[/math] не является ни нулем, ни единицей исходной булевой алгебры.


Теперь, наконец, мы докажем основной результат.




Теорема 4.15. Любая конечная булева алгебра изоморфна булевой алгебре [math]\mathbb{B}^n[/math] для некоторого [math]n[/math].


Доказательство проведем методом математической индукции по числу элементов булевой алгебры [math]\mathcal{A}=(A,\lor,\land,\bold{0},\bold{1})[/math]. Одноэлементная булева алгебра изоморфна нулевой степени алгебры [math]\mathbb{B}[/math] (см. замечание 4.4). Для самой алгебры [math]\mathbb{B}[/math], содержащей два элемента, доказывать нечего.


Пусть утверждение теоремы доказано для всех булевых алгебр с числом элементов, не большим некоторого [math]k\geqslant 2[/math]. Рассмотрим произвольную булеву алгебру [math]\mathcal{A}[/math], содержащую [math]k+1[/math] элемент, т.е. [math]|A|=k+1[/math], и пусть [math]a\in A[/math]. Поскольку число элементов в данной алгебре не меньше трех, то, во-первых, [math]\bold{0}\ne \bold{1}[/math] (нуль совпадает с единицей только в одноэлементной булевой алгебре), а во-вторых, можно выбрать элемент [math]a[/math] так, что [math]\bold{0}<a<\bold{1}[/math] (т.е. [math]a[/math] отлично и от нуля и от единицы).


Тогда по теореме 4.14 [math]\mathcal{A}\cong [\bold{0},a]\times [a,\bold{1}][/math]. Так как элемент а отличен от единицы алгебры [math]\mathcal{A}[/math], то отрезок [math][\bold{0},a][/math] не содержит единицы [math]\bold{1}[/math], а так как [math]a\ne\bold{0}[/math], то отрезок [math][a,\bold{1}][/math] не содержит нуля алгебры [math]\mathcal{A}[/math]. Следовательно, число элементов в каждом из отрезков не превышает [math]k[/math].


В соответствии с предположением индукции найдутся такие неотрицательные целые числа [math]r[/math] и [math]s[/math], что [math][\bold{0},a]\cong \mathbb{B}^r[/math], а [math][a,\bold{1}]\cong \mathbb{B}^s[/math]. Поэтому [math]\mathcal{B}\cong \mathbb{B}^r\times \mathbb{B}^s\cong \mathbb{B}^{r+s}[/math].


Следствие 4.3. Мощность конечной булевой алгебры есть некоторая степень двойки.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved