XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 33
Текст из файла (страница 33)
Свойство 3.3. В симметричном полукольце произведение ху есть точная нижняя грань последовательности (х, у): ху = ш1 (х, у). Свойство 3.4. Для любого элемента х симметричного полукольца имеет место неравенство О < х < 1. ~ Первое неравенство О < х равносильно равенству О+ х = х, верному для любого х. Второе неравенство х < 1 вытекает из четвертого тождества определения 3.3. ~ 208 3. ПОЛУКОЛЪЦА И БУЛЕБЫ АЛГЕБРЫ Таким образом, в симметричном полукольце единица (1) является наибольшим элементом. Определение 3.4.
Булева алеебра — это симметричное полукольцо, в котором для каждого х существует элемент х, называемый дополнением х, такой, что (3.29) х+х= 1, х х=О. (3.30) Обычно сложение в булевой алгебре называют булевым объединением и обозначают Ч, а умножение — булевым пересечением и обозначают Л. Запишем аксиомы булевой алгебры в виде табл. 3.4, объединяя „двойственные пары" (как это мы уже сделали, записывая аксиомы симметричного идемпотентного полукольца).
Таблица 3.4 Рассмотрим некоторые важные свойства булевых алгебр, вытекающие иэ определения. Свойство 3.5 (единственность дополнения). В булевой алгебре для любого х его дополнение х единственное. ~ Пусть для элемента х найдется еще одно такое а, что а Л х = О иаЧх=1. 3.4. Булевм алгебры Имеем а = а Ч О. Воспользовавшись свойством (3.29), получим а = аЧ(хлх).
В силу дистрибутивности и с учетом свойств элемента а имеем а= (аЧх) Л(аЧх) = 1Л(аЧх). С учетом свойств дополнения преобразуем последнее выражение сведующим образом: а= (хчх) Л(аЧх) = (хЛа)Чх. Поскольку хЛа = О, то а = ОЧх = х. Таким образом, элемент а совпадает с дополнением х. ° Свойство 3.6 („симметричностьв операции дополнения). В булевой алгебре выполняется тождество ~ Так как х является дополнением к х, то х Л х = О и х Ч х = 1. В то же время х Л х = О и х Ч х = 1.
В силу единственности дополнения к элементу х имеем х = х. Ь Свойство З.Т. В булевой алгебре верны следующие тождества: хчу=хЛу, хЛу=хчу. (3.31) ч В силу свойств 3.5 и 3.6 для доказательства первого закона достаточно показать, что (х Л у) Ч (х Ч у) = 1 и (х Л у) Л (х Ч у) = =О. Преобразуя выражения в левых частях, получаем (хлу)ч(хЧу) = (хЧхЧу) Л(уЧхЧу)= 1Л1 = 1, (хлу) Л(хЧу) =(хлулх) Ч(хлулу) =ОЧО=О. Первое тождество доказано. Второе тождество следует иэ принципа двойственности. ~ Тождества (3.31) называют законами де Мореона. Единственность дополнения означает, что в булевой алгебре возникает унарная операция — переход от элемента к его дополнению.
Эту операцию можно ввести в сигнатуру алгебры, т.е. рассматривать булеву алгебру как алгебру вида В=(В,ч,л,—,0,1) 210 3. ПОЛУКОЛЬЦА И БУЛЕБЫ АЛГЕБРЫ с двумя бинарными, одной унарной и двуьдя нульарными операциями, такую, что: 1) (В, '>/, Л, О, 1) — симметричное полукольцо; 2) аЧа=1 и аЛа=О (для любого а). Дополнение в булевой алгебре называют булевым до«алке«кем, а все операции булевой алгебры — булевыми окераЧилми. Рассмотрим теперь некоторые примеры булевых алгебр. Пример 3.10. Полукольцо 8 (см. пример 3.2) являетсл булевой алгеброй. Эта булеза алгебра — важнейдпая структура. Мы назовем ее двухэлементной булевой алгеброй и обозначим В. Видно, что в В 0=1, 1=0. Пример 3,11. На множестве (О, 1)" определим структуру булевой алгебры, положив для произвольных о = (од, ..., о„), )3 = фд, ..., Д,) вз (О, Ц", что ст'»'>6 = (а>д д~Дд ... дт д~Д ), стЛфУ=(адЛ)Зд> ..., а»Л>б»)> а (стд» ст>>)> О = (О, ..., 0), 1 = (1, ..., 1).
Можно без труда показать, что все аксиомы булевой алгебры выполняются. Носитель определенной таким образом булевой алгебры называют булевым «убом размерности н, а его элементы — булевыми вектиорами (или булевыми наборами) размерности н. Вектор О называют при этом нулевым булевым ее«тавром или нулевым набором, а вектор 1 — единичнык булевым векпдором или едининнььк набором. Заметим, что случаи н = 0 и н = 1 включаются в эту конструкцию. При и = 1 получаем уже рассмотренную двух- элементную булеву алгебру В, а при и = 0 — так называемую 3.4. Булееы алгебры 211 однозаелеентпную булее у алеебру, в которой О = 1.
Но эта структура малоинтересна. Итак, булевы операции над булевыми векторами выполняются покомпонетно — так же, как сложение векторов или умножение вектора на число в линейной алгебре. Отношение порядка здесь определено также покомпонентно, т.е. для произвольных а = (сем ..., се„), ф = (,о~, ...,,б'„) Е (О, Ц" неравенство а < ~3 означает, что пч < Д, е = 1,н. Так, например, (О, 1, О, О, 1) < (1, 1, О, О, 1), а векторы (О, 1, О, О, 1) и (О, 1, О, О, О) не сравнимы. Пример 3.12.
Полукольцо бл (см. пример 3.3.6) — булеза алгебра, в которой все булевы операции суть не что иное, как обычные теоретико-множественные операции, т.е. булево объединение есть обычное объединение множеств, булево пересечение — пересечение множеств, булево дополнение — дополнение множества. Пример 3.13. а. Рассмотрим полукольцо 2Уе делителей числа 6 с операциями НОК и НОД. Иэ примера 3.9 следует, что зто полукольцо симметричное. Нуль этого полукольца есть число 1, а единица — число 6.
Убедимся, что каждый элемент полукольца имеет дополнение. Начнем с числа 1. Дополнение х должно удовлетворять равенствам 1 Ч х = 6 и 1 Л х = 1. Первое равенство означает, что НОК(1,х) = 6, а второе — НОД(1,х) = = 1. Легко видеть, что х = 1 = 6. Рассуждая аналогично, получим 2 = 3. Следовательно, рассматриваемое полукольцо есть булева алгебра. б. Полукольцо Рш делителей числа 12 не является булевой алгеброй, так как, например, из 2 Ч х = НОК(2,х) = 12 = 1 еле.
дует, что х =12, но 2Л12 =НОД(2,12) = 2е41= 0, и элемент 2 не имеет дополнения. Теория булевых элгебр имеет многочисленные приложения: в математической логике, в теории вероятностей. Она позволяет, в частности, рассматривать с единой точки зрения операции 212 з. 11олукольцл и кулккы ллгккры над множествами, над высказываниями, над случайными собмпьцлми. В этой книге мы используем изложенные здесь факты в главе 6, посвященной булевым функццлм. 3.5. Решетки Напомним, что полурешетпкой называют полугруппу, операццл которой коммупиииивна и идемпопьенпьна.
Таким образом, полурешетка — это алгебра .С = (Ь, Ч), в которой для любых а, Ь, с Е Ь выполнены равенства а Ч (Ь Ч с) = (а Ч Ь) Ч с, аЧЬ=ЬЧа, аЧа=а. В каждой полурешетке может быть определено естественное ошношенце порядка аналогично тому, как это определялось для (идемпотентного) полукольца. По определению полагаем для произвольных а, Ь Е Ь (3.32) а(ЬеьачЬ=Ь. Из определения (3.32) отношения порядка в полурешетке следует, что элемент а Ч 6 есть тонная верхняя грань двухэлементного множества 1а, Ь). Действительно, аЧ(аЧЬ) = (аЧа) ЧЬ=аЧЬ (в силу ассоциативности и идемпотентности операции Ч). Аналогично ЬЧ (а Ч Ь) = а Ч 6 (с использованием и коммутативности операции Ч). Итак, а Ч Ь есть верхняя грань множества 1а, Ь). Полагая, что с есть какгя-то верхняя грань данного множества, вычислим (а Ч Ь) Ч с.
Используя ассоциативность и то, что в силу 6 ( с выполняется равенство 6 Ч с = с, получим (аЧ6) Чс= аЧ (ЬЧс) = ачс. 213 З.о. Решетки Ко так кака <с, то аЧс= с. Итак, (аЧЬ) Чс= с, т.е. аЧЬ< с, и поэтому элемент а Ч Ь есть точная верхняя грань множества (а, Ь). Отношение порядка, определенное в произвольной полуреп1етке согласно условию (3.32), будем называть еспаестпвенным порядком данной пояурешетпки. Таким образом, в полурешетке любое двухэлементное (и, следовательно, любое конечное) подмножество имеет точную верхнюю грань (по естественному порядку полурешетки).
Можно доказать, что имеет место и обратное. Теорема 3.10. Любое упорядоченное множество Ю = = (Ь, <), в котором всякое двухэлементное подмножество имеет точную верхнюю грань, являетсл полурешеткой, естественный порядок которой совпадает с отношением <. 1 Определим операцию Ч так: а Ч Ь = япр(а, Ь). Коммутативность и идемпотентность операции Ч следует сразу из определения точной верхней грани множества.
Действительно, а Ч а = вар(а, а) = впр (а) = а, и так как (а, Ь) = (Ь, а), то а Ч Ь = вар (а, Ь) = вар (Ь, а) = 6 Ч а. Докажем ассоциативность операции Ч. Для этого нужно показать, что для произвольных а, 6, с е Ь имеет место равенство япр(епр(а, Ь), с) = впр(а, впр(6, с)). (3.33) Обозначим левую часть равенства (3.33) через 4, а правую — через с~э. Элемент 4 является точной верхней гранью множества, элементы которого суть впр(а,Ь) и с. Поэтому 4 > впр(а,6) и д1 > с. Из первого неравенства следует, что 41 > а ид1 >Ь. Тогда, поскольку д1 >Ьи 4 >с, то д1 есть верхняя грань множества (Ь, с), т.е.
Ы1 > впр(Ь, с). Так как д1 > а, то д1 > епр(а, впр(Ь, с)) = дг. Аналогично доказывается, что дг > дм т.е. д1 = дз, что и требовалось доказать. Поскольку для любых элементов а, 6 упорядоченного множества (о, <) согласно условию теоремы соотношение а < 6 214 3. ПОЛУКОЛЬЦА И БУЛЕВЫ АЛГЕБРЫ эквивалентно тому, что аир(а, Ь) = Ь, то исходное отношение порядка < совпадает с естественным порядком полурешетки (Ь, аир). ° Из принципа двойственности для упорядоченных множеств следует, что точны верхняя (нижняя) грань любого подмножества упорядоченного множества (1, <) является одновременно точной нижней (верхней) гранью этого подмножества в смысле двойсшвенного порядка >.
Отсюда получаем утверждение, двойственное теореме 3.10. Теорема 3.11. Любое упорядоченное множество С = (Ь, <), в котором всякое двухэлементное подмножество имеет точную нижнюю грань, является полурешеткой, причем естественнъй порядок этой полурешетки является порядком, двойственным к исходному порядку <. М Доказательство дословно повторяет доказательство теоре- мы 3.10, но операция Л полурешетки определяется так: аЛЬ= ш1(а, Ь). Полурешетку (Ь, аир), определенную теоремой 3.10, называют верхней полурешетноб, а полурешетку (1, ш1), определяемую теоремой 3.11, — ннхсней полурешепькой Замечание 3.3.
Обратим внимание на то, что понятия „верхний" и „нижний" имеют смысл относительно фиксированного отношения порядка и при переходе к двойственному порядку „верх" превращается в „ннз" и наоборот. Пример 3.14. а. Отрезок [а, Ь] числовой прямой (с естественным числовым порядком), согласно теоремам 3.10 и 3.11, является и верхней и нижней полурешеткой. Более того, поскольку на числовой прямой любое двухэлементное подмножество имеет как точную верхнюю, так и точную нижнюю грань, то любое подмножество множества действительных чисел Ж (в частности, само Й) является и верхней и нижней полурешеткой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
