XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 42
Текст из файла (страница 42)
Напомним, что мы определили булеву алгебру В" булевых вектпоров размерностпи и (см. пример 3.11). Эта алгебра есть не что иное, как и-я декартпова стпепень двухэлементпной Булевой алгебра В = ((О, Ц, Ч, Л, О, 1) (см. 4.5). Пусть ь". = (Ь, Ч, Л, О, Ц вЂ” симметпричное полукольцо. Рассмотрим произвольные элементы а, Ь Е Ь, такие, что а < Ь. Множество [а, Ц = (х: а < х < Ь1 будем называть отпрезком, элемент а —.левым, а элемент Ь вЂ” правым концом отпрезка.
Замечание 4.5. Напомним, что в симметричном полукольце нуль полукольца является наименьшим, а единица полукольца — наибольшим элементном в данном полукольце относительно естпестпвенного порядка этого идемпотпентпного полукольца. Поэтому для любого элемента х симметричного полукольца справедливо неравенство О < х < 1, и тем самым все симметричное полукольцо можно рассматривать квк отрезок [0,1] симметричного полукольца. 4.б. Ковечиые булевы аагебры 261 Любой отрезок [а, Ь] симметричного полукольца замкнут относитпельно операций Ч и Л, но не является, вообще говоря, подполунольцом С, так как не содержит 0 (если а ф 0) и не содержит 1 (при Ьу~ 1). Но поскольку элемент а будет наименьшим, а элемент Ь вЂ” наибольшим элементом отрезка [а, Ь], алгебра ([а, Ь], Ч, Л, а, Ь) будет симметричным полукольцом с нулем а и единицей Ь, которое мы будем обозначать тоже через [а, Ь]. Для произвольно фиксированного элемента а симметричного полукольца А".
зададим отображение 6„, сопоставляющее каждому х Е Х упорядоченную пару (х Л а, х Ч а) Е ы~. Так как 0 < хЛа < а и а < хЧа < 1 для любого х Е Х (в силу свойств симметричного полукольца), то тем самым задано отображение 6„носителя полукольца С в декартово произведение отрезков [О, а] х [а, 1]: 6ь: Х ~ [О, а] х [а, 1]. Каждый из отрезков есть симметричное полукольцо. В силу теоремы 4.11 их декартово произведение также является симметричным полукольцом. Теорема 4.12. Пусть Х вЂ” носитель симметричного полукольца Ю = (Х, Ч, Л, О, 1). Для любого а Е Х отображение 6ь есть мономорфизм полукольца .С в полукольцо [О, а] х [а, 1].
~ Докажем, что 9 — гомоморфнзм. Имеем ЩО) = (О, а), и эта упорядоченная пара и является нйименьшим элементом, т.е. нулем, полукольца [О,а] х [а, 1]. Точно так же Щ1) = (а, 1)— наибольший элемент, т.е. единица того же полукольца. Далее, 0 (х Ч у) = ((х Ч у) Л а, (х Ч у) Ч а) = = ((х Л а) Ч (у Л а), (х Ч а) Ч (у Ч а) ) = Щх) Ч Щу). Аналогично доказывается, что 6.(хЛу) =9.(х) ЛЩу). 262 '4. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Итак, 9„— гомоморфизм С в [О, а] х [а, 1].
Теперь надо доказать, что 6~ — инъекция. Для этого нужно показать, что из равенства Щх) = Щу) вытекает х = у. Если 9 (х) = 9„(у), то верны равенства (4.2) х Л а = у Л а и х Ч а = у Ч а, так как равенство упорядоченных пар означает равенство их одноименных компонент. Теперь, используя равенства (4.2) и аксиомы симметричного полукольца (см. 3.4), получим х =хЛ(хЧа) =хЛ(уЧа) = =(хЛу)Ч (хЛа) = (уЛх) Ч(уЛа) = = (уЧу) Л(уЧа) Л(хЧу) Л(хЧа) = = уЛ(уЧа) Л(хЧу) Л(хЧа) = =уЛ(хЧу) Л(уЧа) =уЛ(уЧа) =у.
Таким образом, если 9„(х) = 6~(у), то х = у, и 9„— инъек- ция. ~ Теорема 4.13. Если симметричное полукольцо Ю = (Ь, Ч, Л, О, 1) есть булеза алгебра, то для любого а Е Ь полукольца [О, а) и [а, 1] тоже булевы алгебры. ~ Поскольку [О,а) и [а,1] — симметричные полукольца, то достаточно доказать, что в каждом из отрезков [О,а) и [а,1) любой элемент имеет дополнение. Для произвольного и Е [О,а] определим элемент Б„ равенством Ба = БЛ а. Докажем, что этот элемент и есть дополнение и в полукольце [О,а]. Для этого, как следует из свойства единственности дополнения в булевой алгебре, достаточно убедиться в том, что Б„Чп= а, а Б„Ли= О. 263 4.6. Конечные булавы алгебры Действительно, й Чи = (йЛа) Чи= 1Л(аЧи).
Так как и < а, то а Ч и = а, и 1 Л (а Ч и) = 1 Л а = а. Итак, и, Ч и = = а. Аналогично ил Ли = (иЛа) Ли = О. Таким образом, йе действительно является дополнением элемента и в полукольце [О, а]. Теперь для произвольного е Е «а, 1] определим элемент е равенством ее = еЧа. Как и выше, аналогично доказывается, что ее Ч е = 1, ее Л е = а. Следовательно, элемент ее является дополнением е в полукольце [а, 1]. ~ Теорема 4.14. Если в условиях теоремы 4.12 полукольцо л".
являетсл булевой алгеброй, то йа — иэоморфиэм булевых алгебр л". и [О, а] х [а, 1]. 1 В силу теоремы 4.12 достаточно доказать, что Ое — эаииорФизле, сохраняющий дополнение, т.е. 1) для любой пары (р, я), где р < а, я > а, существует элемент х Е Ь, такой, что 9 (х) = (р,я); 2) 6е(х) =(хЛа, хЧа) =6„(х). Докажем первое утверждение. Убедимся, что указанный в нем элемент х может быть определен равенством х = р Ч (я Л а). Имеем хЛа = [р Ч (яЛа)] Ла = (рря) Л(рЧа) Ла = = [(р Ч я) Л а] Л (р Ч а). Поскольку р < а < я, то (рЧз) Ла = (рда) Ч(яЛа) = рЧа= а.
Следовательно, х Л а = а Л (р Ч а) = а Л р = р (так как р (~ а). Аналогично доказывается, что х Ч а = я. Таким образом, ~ ( )=(р, ). 264 4. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Второе утверждение следует из того, что элемент х Л а есть дополнение элемента и = х Л а в булевой алгебре (О, а], а элемент х Ч а — дополнение элемента о = х Ч а в булевой алгебре (а, 1].
Действительно, согласно теореме 4.13, Иа = (х Л а)а = (хЛ а) Л а = = (хУЕ) Ла= (хЛа) Ч(аЛа) = (УЛа) ЧО =хЛа. Согласно нринцнну двойственности, Еа = ( Итак, а =у'ха. 9~(х) = ((жЛа),(х()а) ) = (хЛа,хна) = Щх). В силу доказанных теорем имеем следующий результат. Следствие 4.2. Любая булеза алгебра изоморфна прямому произведению некоторых двух булевых алгебр.
ф 9, Оь 1 а 1 (а,1) Ь 1 (Ь,1) х а (а,а) (0,1) а х а (Ь, Ь) (О,1) а Ьа О О а (О,а) О Ь (О,Ь) Рис. 4.4 На рис. 4.4 представлены все возможные способы представления четырехэлементной булевой алгебры (ее элементы обозначены О, 1, а, о) в виде прямого произведения двух двух- элементных булевых влгебр. Эти представления определяются изоморфизмами Ва и Вь.
Изоморфизм Ва есть изоморфизм исходной четырехзлеменной булевой алгебры на декартово произведение ее отрезков [О, а] и (а, 1], каждый иэ которых изоморфен двухэлементной булевой алгебре В. Вместе с тем декартово произведение указанных отрезков дает (см. 4.5) четырехэлементную булеву алгебру, элементами которой служат 265 4.6. Кояечаые булевы ыгебры упорядоченные пары (О, а), (а, а), (а, 1) и (О, 1), причем пара (О, а) будет нулем, а пара (а, 1) — единицей этой булевой алгебры, которая изоморфна исходной. Аналогично рассматривается изоморфизм Ом Интересно отметить, что могут быть заданы и изоморфизмы 90 и 91, но каждый из них определяет тривиальное разложение исходной булевой алгебры в виде ее прямого произведения на одноэлементную булеву алгебру, т.е.
в виде [О, Ц х [О, 0] или в виде [О, Ц х [1, Ц. Интерес представляют, следовательно, такие изоморфизмы 6„, где элемент а не является ни нулем, ни единицей исходной булевой алгебры. Теперь, наконец, мы докажем основной результат. Теорема 4.15. Любая конечная булеза алгебра изоморфна булевой алгебре В" для некоторого и. 1 Доказательство проведем методом математической индукции по числу элементов булевой алгебры А = (А, Ч, Л, О, 1).
Одвоэлемевшвая булева аагебра изоморфна нулевой степени алгебры В (см. замечание 4.4). Для самой алгебры В, содержащей два элемента, доказывать нечего. Пусть утверждение теоремы доказано для всех булевых алгебр с числом элементов, не болыпим некоторого я > 2. Рассмотрим произвольную булеву алгебру А, содержащую й+ 1 элемент, т.е. [А[ = Й+ 1, и пусть а е А. Поскольку число элементов в данной алгебре не меньше трех, то, во-первых, 0 -,~ 1 (нуль совпадает с единицей только в одноэлементной булевой алгебре), а во-вторых, можно выбрать элемент а так, что 0 < а < 1 (т.е. а отлично и от нуля и от единицы). Тогда по теореме 4.14 А М [О, а] х [а, Ц. Так как элемент а отличен от единицы алгебры А, то отрезок [О, а] не содержит единицы 1, а так как а ~ О, то отрезок [а, Ц не содержит нуля алгебры А.
Следовательно, число элементов в каждом из отрезков не превьппает й. 266 4. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ В соответствии с предположением индукции найдутся такие неотрицательные целые числа т и в, что (О, а] М В", а ]а, 1] М В'. Поэтому В а) В" х В' в' В"+'. в Следствие 4.3. Мощность конечной булевой алгебры есть некоторая степень двойки. 4.7. Многосортные алгебры Среди всех алгебр, рассмотренных вьппе, несколько особое положение занимает модуль (и, как частный случай, линейное пространство). Модуль был определен как алгебра, в сигнаптуру которой входят бинарная операция сложения и бесконечное (в общем случае) множество унарныя операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
