Конечные булевы алгебры
ТеорияПокажем применение понятия прямого произведения алгебраических систем к теории булевых алгебр. Мы докажем здесь интересный факт, состоящий в том, что мощность любой конечной булевой алгебры есть некоторая степень двойки. Отсюда будет следовать, например, что в конечной булевой алгебре может быть 1, 2, 8, 16, 32, 64 и т.д. элементов, но не может быть, скажем, 100 или 75 элементов. Чтобы доказать сформулированное утверждение о конечных булевых алгебрах, необходимо ввести некоторые вспомогательные определения и доказать некоторые утверждения. Напомним, что мы определили булеву алгебру Вn булевых векторов размерности n (см. пример 3.11). Эта алгебра есть не что иное, как n-я декартова степень двухэлементной булевой алгебры В =({0,1}, ∨, ∧, 0, 1).
Пусть L = {L, ∨, ∧, 0,1} — симметричное полукольцо. Рассмотрим произвольные элементы а, b ∈ L, такие, что а ≤ b. Множество [а, b] = {х: а ≤ х ≤ b} будем называть отрезком, элемент а — левым, а элемент b — правым концом отрезка.
Замечание 4.5. Напомним, что в симметричном полукольце нуль полукольца является наименьшим, а единица полукольца — наибольшим элементом в данном полукольце относительно естественного порядка этого идемпотентного полукольца. Поэтому для любого элемента х симметричного полукольца справедливо неравенство 0 ≤ х ≤ 1, и тем самым все симметричное полукольцо можно рассматривать как отрезок [0,1] симметричного полукольца. #
Любой отрезок [а, Ь] симметричного полукольца замкнут относительно операций ∨ и ∧, но не является, вообще говоря, подполукольцом L, так как не содержит 0 (если а ≠ 0) и не содержит 1 (при b ≠ 1). Но поскольку элемент а будет наименьшим, а элемент b — наибольшим элементом отрезка [а,b], алгебра
([а, b], ∨, ∧, а, b)
будет симметричным полукольцом с нулем а и единицей Ь, которое мы будем обозначать тоже через [а, Ь].
Для произвольно фиксированного элемента а симметричного полукольца L зададим отображение Ѳа, сопоставляющее каждому х ∈ L упорядоченную пару (х ∧ а, х ∨ а) ∈ L2. Так как О≤x∧а≤а и a≤x∨a≤l для любого х ∈ L (в силу свойств симметричного полукольца), то тем самым задано отображение Ѳа носителя полукольца С в декартово произведение отрезков [0,a]×[a,1]:
Ѳa:L→[0,a]×[a,1].
Каждый из отрезков есть симметричное полукольцо. В силу теоремы 4.11 их декартово произведение также является симметричным полукольцом.
Теорема 4,12. Пусть L — носитель симметричного полукольца L = (L, ∨, ∧, 0, 1). Для любого a ∈ L отображение Ѳа есть мономорфизм полукольца L в полукольцо [0,a]×[a,1].
◀Докажем, что Ѳa — гомоморфизм. Имеем Ѳа(0) = (0,а), и эта упорядоченная пара и является наименьшим элементом, т.е. нулем, полукольца [0,a]×[a,1]. Точно так же Ѳа(1) = (a,1) — наибольший элемент, т.е. единица того же полукольца. Далее,
Ѳа(x∨y)=((x∨y)∧a,(x∨y)∨a)= =((x∧a)∨(y∧a),(x∨a)∨(y∨a))=Ѳа(x)Ѳа(y)
Аналогично доказывается, что Ѳа(x∧y)=Ѳа(x)∧Ѳа(y).
Итак, Ѳа — гомоморфизм L в [0,а]×[а,1].
Теперь надо доказать, что Ѳа — инъекция. Для этого нужно показать, что из равенства Ѳа(x) = Ѳа(у) вытекает х = у. Если Ѳа(x) = Ѳа(у), то верны равенства
х∧а = у∧а и х∨а = у∨а,) (4.2)
так как равенство упорядоченных пар означает равенство их одноименных компонент.
Теперь, используя равенства (4.2) и аксиомы симметричного полукольца (см. 3.4), получим
х=х∧(х∨а) = х∧(у∨а)= =(x∧у)∨(х∧а)=(у∧х)∨(у∧а)= =(y∨у)∧(y∨а)∧(x∨y)∧(x∨а)= =y∧(y∨а)∧(x∨y)∧(x∨а)= =y∧(x∨y)∧(y∨a)=y∧(y∨а)=y.
Таким образом, если ва(х) = 0а(у), то х = у, и Ѳa — инъекция.▶
Теорема 4.13. Если симметричное полукольцо
L=(L,∨,∧,0,1)
есть булева алгебра, то для любого а ∈ L полукольца [0,а] и [а,1] тоже булевы алгебры.
◀Поскольку [0,а] и [а,1] — симметричные полукольца, то достаточно доказать, что в каждом из отрезков [0,а] и [а,1] любой элемент имеет дополнение.
Для произвольного u∈[0,а] определим элемент ua равенством ua = u∧а. Докажем, что этот элемент и есть дополнение и в полукольце [0,а]. Для этого, как следует из свойства единственности дополнения в булевой алгебре, достаточно убедиться в том, что ua∨u = a,а ua∧u = 0.
Действительно,
ua∨u=(u∧a)∨u=1∧(a∨u)
Так как u≤а, то а∨u = а, и 1∧(а∨u) = 1∧а=а. Итак, ua∨u = а. Аналогично ua ∧ u = (u ∧ а) ∧ u = 0. Таким образом,ua действительно является дополнением элемента и в полукольце [0,a].
Теперь для произвольного v ∈ [а,1] определим элемент va равенством va = v ∨ а. Как и выше, аналогично доказывается, что va ∨ v = 1, va ∧v = a. Следовательно, элемент va является дополнением v в полукольце [а, 1].
Теорема 4,14. Бели в условиях теоремы 4.12 полукольцо L является булевой алгеброй, то Ѳа — изоморфизм булевых алгебр L и [0,a]×[a,1].
◀В силу теоремы 4.12 достаточно доказать, что Ѳа — эпиморфизм, сохраняющий дополнение, т.е.
1) для любой пары (y,z), где у ≤ a, z ≥ а, существует элемент x∈L, такой, что Ѳа(x) = (y,z);
2) Ѳа(x)=(x∧a,x∨a)=Ѳа(x)
Докажем первое утверждение. Убедимся, что указанный в нем элемент х может быть определен равенством х=y∨(z∧a). Имеем
x∧a = [у ∨ (z ∧ a)]∧а=(у∨г) ∧ (у∨a)∧а= =[(y∨z)∧a]∧(y∨a).
Поскольку у ≤ а ≤ z, то
(у∨z)∧а=(у∧а)∨(z∧а)=у∨а=а.
Следовательно, x∧a = a∧(y∨a) = a∧y = y (так как у ≤ а). Аналогично доказывается, что x ∨ a = z. Таким образом, Ѳа(х) = (у,z).
Второе утверждение следует из того, что элемент x∧а есть дополнение элемента u = х∧а в булевой алгебре [0,a], а элемент x∨а — дополнение элемента v=х∨а в булевой алгебре [а,1].
Действительно, согласно теореме 4.13,
ua = (х∧а)а = (х∧а) ∧ а = =(x∨a)∧a=(x∧a)∨(a∧a)=(x∧a)∨0=x∧a.
Согласно принципу двойственности, va = (x∨a)а=x∨a
Итак,
Ѳа(x)=((x∧a)a,(x∨a)a)=(x∧a,x∨a)=Ѳа(x) ▶
В силу доказанных теорем имеем следующий результат.
Следствие 4.2. Любая булева алгебра изоморфна прямому произведению некоторых двух булевых алгебр. #
Рис. 4.4
Ha рис. 4.4 представлены все возможные способы представления четырехэлементной булевой алгебры (ее элементы обозначены 0,1,а,b) в виде прямого произведения двух двухэлементных булевых алгебр. Эти представления определяются изоморфизмами Ѳа и Ѳb. Изоморфизм Ѳа есть изоморфизм исходной четырехэлеменнои булевой алгебры на декартово произведение ее отрезков [0,а] и [а,1], каждый из которых изоморфен двухэлементной булевой алгебре В. Вместе с тем декартово произведение указанных отрезков дает (см. 4.5) тырехэлементную булеву алгебру, элементами которой служат упорядоченные пары (0,а), (а,a), (а,1) и (0,1), причем пара (0,а) будет нулем, а пара (а,1) — единицей этой булевой алгебры, которая изоморфна исходной. Аналогично рассматривается изоморфизм Ѳb.
Интересно отметить, что могут быть заданы и изоморфизмы Ѳа и Ѳb, но каждый из них определяет тривиальное разложение исходной булевой алгебры в виде ее прямого произведения на одноэлементную булеву алгебру, т.е. в виде [0,1] × [0,0] или в виде [0,1] × [1,1]. Интерес представляют, следовательно, такие изоморфизмы 0а, где элемент а не является ни нулем, ни единицей исходной булевой алгебры.
Теперь, наконец, мы докажем основной результат.
Теорема 4.15. Любая конечная булева алгебра изоморфна булевой алгебре Вn для некоторого n.
◀Доказательство проведем методом математической индукции по числу элементов булевой алгебры A = (А,∨,∧,0,1). Одноэлементная булева алгебра изоморфна нулевой степени алгебры В (см. замечание 4.4). Для самой алгебры В, содержащей два элемента, доказывать нечего.
Пусть утверждение теоремы доказано для всех булевых алгебр с числом элементов, не большим некоторого k ≥ 2. Рассмотрим произвольную булеву алгебру A, содержащую k + 1 элемент, т.е. |А| = k + 1, и пусть a ∈ А. Поскольку число элементов в данной алгебре не меньше трех, то, во-первых, 0≠1 (нуль совпадает с единицей только в одноэлементной булевой алгебре), а во-вторых, можно выбрать элемент а так, что 0 < а < 1 (т.е. а отлично и от нуля и от единицы).
Тогда по теореме 4.14 A ≅ [0,а] × [а,1]. Так как элемент а отличен от единицы алгебры A, то отрезок [0,а] не содержит единицы 1, а так как а≠0, то отрезок [а,1] не содержит нуля алгебры А. Следовательно, число элементов в каждом из отрезков не превышает k.
В соответствии с предположением индукции найдутся такие неотрицательные целые числа r и s, что [0,а]≅Вr, а[а,1] = В8. Поэтому В ≅ Вr × Вs ≅ Вr+s.▶
Следствие 4.3. Мощность конечной булевой алгебры есть некоторая степень двойки.