XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 35
Текст из файла (страница 35)
Иными словами, для того чтобы убедиться, что перед нами решетка, достаточно проверить это свойство. Пример 3.1Т. а. Рассмотренный в примере 3.14.б прямоугольник [а, Ь) х ~с, д] есть решетка (см. рис. 3.1), но если мы „срежем" у этого прямоугольника углы и рассмотрим, например, множество точек многоугольника АВИВЕ на рис. 3.2, то это множество уже не будет решеткой, так как, скажем, множество (А, Р) не имеет шЕ, а множество (С, Е11 не имеет гпр.
б. Не является решеткой и конечное упорядоченное множество, диаграмма Хассе которого изображена на рис. 3.3. Здесь впр(а, Ь) = с, но шЕ(а, Ь) не существует. Аналогично 1пЕ(а, е) = с, но впр (а, е) не существует. 221 3.5. Решетки в. Декартаов квадрат множества целых чисел Ут — решетка, где упорядоченные пары целых чисел упорядочиваются аналогично точкам плоскости (см. пример 3.17.а). Относительно этого же отношения порядка решеткой 4 будет и любои ецелочисленныи прямоугольник" [а...Ь] х (с...д], где [тп...п] обозначает множество всех целых чисел р, таких, что тп < р < п (тп < и). Этот „прямоугольник" и графически выглядит как „решетка", что видно на рис. 3.4, на котором изображено множество (1...5] х [1...4].
2 3 4 5 Рве. 3.4 Пример 3.18. На рис. 3.1 прямоугольник (а, Ь] х [с, д] является решеткой с нулем и единицей, причем О = (а, с), 1 = =(Ь, д). Если верхняя полурешетка решетки .С = (Ь, Ч, Л) есть полурешетка с нулем, то этот нуль является наименьшим элементом решетки С.
Тогда ее называют решеткой с нулем, а нуль полурешетки (т', Ч) — кулем решетпки С. Двойственным образом единица нижней полурешетки (т, Л), если она существует, являетсл наибольшим элементом решетки .С. Эту единицу тогда называют единицей решетпки С, а саму решетку — решеткой с единицей.
Таким образом, решетка с нулем имеет нейтральный элемент по операции решеточного объединения (и ее верхняя полу- решетка превращается в моноид), а решетка с единицей имеет нейтральный элемент по операции решеточного пересечения (и моноидом становится уже ее нижняя полурешетка). Кроме того, из теоремы 3.12 следует, что а Л О = О для любого а Е Ь (соответственно аЧ1 = 1 для любого а Е т ), т.е.
выполняются аналоги аннулирующих свойств в симметричных полукольцах. Симметричное полукольцо является примером решетки с нулем и единицей. 222 3. ПОЛУКОЛЬЦА И БУЛЕБЫ АЛГЕБРЫ Рассмотрим теперь вместо отрезка [а, Ь] промежуток А = = (х. "х ( 6) (< означает здесь естественный числовой порядок). Тогда множество А х [с, б] при сохранении того же отношения порядка на Жз, что и в примере 3.17, будет решеткой с единицей, равной (Ь, д). Нуля у этой решетки не будет (если рассматривать, конечно, нерасширенную числовую прямую, точнее, не включать в нее -оо). Если же вместо отрезка [а, Ь] взять также неограниченный промежуток В = (х: х > а), то В х [с, б] будет решеткой с нулем, равным (а) с.
Если опять-таки считать, что элемент +ос не принадлежит Й, то эта решетка не будет иметь единицу. У Рис. 3.6 Рис. З.В В общем случае в решетке не имеет места дистрибутив- ность одной из операций относительно другой. На рис. 3.5 и 3.6 приведены диаграммы Хассе решеток, называемых соответственно ненюнаеоном и днамантом. В каждой ю них ни одна из операций не является дистрибутивной относительно другой. Так, например, в первой ю них а Л (6Ч с) = аЛ 1 = а, но (аЛ6) Ч(аЛс) = ЬЧО=Ь.
Для второй решетки аЛ(ЬЧс) = = аЛ1 = а, тогда как (аЛЬ) Ч(аЛс) =ОЧО= О. Определение 3.6. Решетку Е = (Ь, Ч, Л) называют дис~нрнброиьеноб, если для любых а, Ь, с Е Ь имеют место равенства аЧ(ЬЛс) =(аЧЬ) Л(аЧс), аЛ(ЬЧс) =(аЛЬ)Ч(аЛс). Теперь мы можем дать в терминах решеток характеристику симметричных полуколец и булевых аягебр. 223 Вопросы и залети Теорема 3.14.
Симметричное полукольцо — это дистрибутивная решетка с нулем и единицей. Булеза алгебра — это дистрибутивная решетка с нулем и единицей, в которой для каждого элемента х существует дополнение, т.е. такой элемент х, что х ЧУ = 1 и х Л х = О. Доказательство теоремы 3.14 мы не приводим, так как оно является непосредственным следствием определений 3.3, 3.4 и 3.6. Теория решеток находит многочисленные применения в теории графов и теоретическом программировании. В специальной литературе на базе теории решеток развиты стройная концепция типов данных в языках программирования и теория типов данных', хорошо изложены общая теория решеток" и ее приложения к теории графов"".
Вопросы и задачи 3.1. Проверив аксиомы, убедиться, что алгебры, приведенные в примере 3.3, являдотся полукольцами. 3.2. Выяснить, является ли алгебра ([О, 11, шах, ) полукольцом. 3.3. В полукольце 8(о д) (см. пример 3.3.г) решить систему линейных уравнений хд =0,3хд+О,бхз+0,1хз+0,2, хз — — 0,6хд+ 0,8хз+ 0,4хз+ 0 6, хз = 0,2хд + 0,4хз+ 0,25хз+ 0,1. 3.4.
Привести примеры замкнутых полуколец из 4, 8 и 16 элементов. *Смс Скотт Д. Теории решеток, типы дапиаех и семаитика "Смс Гретппер Г. '"Смс Весшиекеее В.А. 224 3. ПОЛУКОЛЬЦА И БУЛЕВЫ АЛГЕБРЫ Указание: рассмотреть алгебру (2~, О, П, И, М), где множество М конечно. 3.5. Доказать теорему 3.9. 3.6.
Описать однозлементную булеву алгебру. Доказать, что булеза алгебра одноэлементна тогда и только тогда, когда в ней О = 1. З.Т. Доказать, что полукольцо З„, является булевой алгеброй тогда и только тогда, когда т есть произведение попарно различных простых чисел. 3.8. Пусть В = (В, Ч, Л,, О, 1) — булева алгебра. Определим на носителе В операции 9 и . так: х Ю у = (х Л у) Ч (х Л у), х. у = х Л у. Доказать, что Яв = (В, Е,, О, 1) — булево кольцо.
Доказать, что Я.в = Ез. 3.9. Пусть К = (В, Е,, О, 1) — булево кольцо (см. зада; чу 2.12). Определим на его носителе В операции Ч, Л и так: хЧу=хфущху, хЛу=х у, х=хЕ1. Доказать, что Ви = (В, Ч, Л,, О, 1) — булеза алгебра. Пока- зать, что Вх, = В. 3.10. Показать, что для любых булевой алгебры В и булева кольца К (см. задачу 2.12) ??В = К и Вн = В. 3.11. На носителе произвольного (т.е. не обязательно идемпотентного) полукольца о = (з, +,, О, 1) определим бинарное отношение -С так, что х С у с~ (Зз)(у = х+ х).
Является ли зто бинарное отношение порядком или предпорядком? Как интерпретируется зто отношение для кольца? 3.12. Пусть полукольцо о = (Я, +,, О, 1) таково, что в его аддитивном моноиде справедлив закон сокращения, т.е. для Вопросы л эаяачя 225 любых х, р, а Е Я из равенства я+ а = у+ а следует равенство я = р, а также для любых а, Ь Е Я из того, что а+ Ь = О, следует а = Ь = О.
Доказать, что тогда бинарное отношение -С, введенное в задаче 3.11, является порядком. Привести пример такого полукольца. При каких условиях полукольцо с такими свойствами будет идемпотентным? 3.13. Доказать, что в полукольце бинарных отношений на и-элементном множестве итерация любого бинарного отношения равна сумме всех его степеней, начиная с нулевой и кони чая п-й, т.е. р' = 0 р". Доказать, что аналогичное свойство я=о справедливо для полукольца квадратных матриц над полукольцом В.
3.14. Доказать подробно, что метод последовательного исключения неизвестных при решении систем линейных уравнений в замкнутых полукольцах (или в полукольцах с итерацией) действительно дает наименьшее решение системы. У к а э а н и е: воспользоваться методом математической индукции и доказать, что на каждом шаге прямого хода метода Гаусса мы получаем очередную компоненту наименьшего решения; при этом испольэовать непрерывность (и, следовательно, монотонность) операций сложения и умножения. 3.15. Доказать, что идемпотентность решеточных операций вытекает иэ тождеств поглощения.
3.1В. Доказать, что алгебра (А, Ч, Л) является решеткой тогда и только тогда, когда (А, Ч) и (А, Л) — полурешетки,и равенство а = а Л Ь равносильно равенству Ь = а Ч Ь. 3.1Т. Пусть алгебры (А, Л, Ч~) и (А, Л, Чэ) (с одним и тем же носителем) являются решетками. Доказать, что тогда операции Ч~ и Чэ совпадают. 3.18.
Нарисовать диаграммы Хассе всех решеток, состоящих не более чем из шести элементов. 4. АЛГЕБРАИЧ:ЕСКИЕ СИСТЕМЫ При решении многих математических задач (задач дискретной математики, в частности) используютсл более сложные структуры, чем „множества с операциями". Например, изучал множество действительных чисел, мы имеем дело не только с операциями над числами, но и с определенными ошношениями на множестве действительных чисел, такими, как, скажем, естпестпвеннмй числовой порядок. Важейшая структура — упорядоченное множестпво — вообще определяется беэ каких-либо операций. Таким образом, мы приходим к необходимости изучения „множеств с операциями и отношениями", в частности „множеств с отношениями" (примерами которых служат упорядоченное множество, индуктпивное упорядоченное множестпво, множество, на котором задано некоторое отпношение предпорядка, эквиваяентпностаи и т.п.).
Это приводит нас к понятиям „алгебраической системы" и „модели". В этой главе изучаютсл некоторые результаты общей теории алгебраических систем, в том числе обобщаются конструкции, которые были введены в двух предшествующих главах. Материал этой главы будет использован затем в теории графов, булевых функций и языков. 4.1. Модели и алгебры Аляебраическая систпема — это упорядоченная птройка А = (А, й, П), где А — некоторое множество, называемое носитпелем алгебраической системы; й — некоторое множество операций на А, П вЂ” некоторое множество отношений на А. Упорядоченнуто пару (й, П) называют сиенатпурой алгебраической системы.
227 4.1. Модели и алгебры Алгебраическую систему называют конечной, если ее носитель — конечное множество. Обозначая через П("т подмножество всех и-аркыг операций ай, цолучимй= О й1"). Точнотак жеП= Ц П1"1, где П("1— п)0 в)1 подмножество всех и-арныг ошношекий. Алгебраическая система, у которой множество П отношений пусто (П = Я), есть не что иное, как й-алгебра (см.
2). Алгебраическую систему, у которой пусто множество операций (й = Я), называют модалью. Замечание 4.1. Докажем, что и-арная операция на множестве А есть частный случай отношения на этом множестве. Действительно, если ап А" + А — и-ариан операция, то определим (и+ 1)-арное отношение ры С А"+1 так, что кортпеж (а1, ..., а„, Ь) Е ры тогда и только тогда, когда Ь = = ш(а1, ..., а„). Понятно, что это отношение функционально по (и+ 1)-й компокентпе. С учетом этого любая алгебраическая система может рассматриваться как модель.
41 Мы рассмотрели много примеров влгебр (см. 2 и 3). В некоторых вз них были введены отношения, например естпестпвенный порядок полукольца, естпестпвенный порядок булевой алгебры, встпестпвенный порядок решвтпки. Эти отношения разумно ввести в сигнатуру и рассматривать указанные алгебры как алгебраические системы, тем более что указанные отношения определяли важнейшие свойства названных алгебр. Пример 4.1. а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
