XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 34

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 34)

215 З.б. Решетки Рис. 3.1 Рис. 3.3 б. Если на множестве точек плоскости (на которой задана некоторая декартова система координат и точка рассматривается как упорядоченная пара действительных чисел) определить отношение порядка так, что (х, у) < (и, е) тогда и только тогда, когда х < в и у < е (см. пример 1.17 и рис. 1.11), то множество точек любого прямоугольника [а, 6) х [с, И] (с указанным отношением порядка), согласно теоремам 3.10 и 3.11, есть и верхняя и нижняя полурешетка (рис. 3.1). Если же мы „срежем" у этого прямоугольника углы и рассмотрим, например, множество точек многоугольника АВСВЕг на рис.

3.2, то зто множество не будет ни верхней, ни нижней полурешеткой, так как, скажем, множество (А, г ) не имеет шГ, а множество (С,О) не имеет зир. Если мы „срежем" только один угол, левый нижний или правый верхний, то получим верхнюю или нижнюю полурешетку соответственно. в. На рис. 3.3 изображена диаграмма Хассе множества, не являющегося ни верхней, ни нижней полу- решеткой.

Действительно, множество (И, е) е не имеет точной верхней грани, хотя имеет точную нижнюю грань: шЩ е) = с. Анало- е гично множество (а, е) не имеет точной нижней грани, хотя имеет точную верхнюю грань: епр(а, Ь) =с. Рис. З.З 216 3. ПОЛУКОЛЪЦА и БУЛЕВЫ АЛГЕБРЫ Полурешетка, как полугруппа, может быть моноидом, т.е. может иметь нейтпральный элемент.

Нейтральный элемент верхней полурешетки (я, Ч) называют нулем полуреитетттни и обозначают О, называя при этом саму полурешетку верхней полурешеткой с нулем. Двойственным образом нейтральный элемент нижней полурешетки (Ь, Л) называют единиией по,яурешетпки, используя обозначение 1 и называя эту полурешетку нижней полурешеткой с единицей. Для нуля полурешетки (я, Ч, 0) имеем аЧ 0 = а для всякого а Е Ь, т.е.

нуль полурешетки есть ее наименьший элемента. Двойственным образом единица полурешетки (Ь, Л, 1) есть ее наибольший элемент. Пример 3.15. а. Прямоугольник [а, Ь] х [с,тт] (см. пример 3.14.б и рис. 3.1) — одновременно и нижняя полурешетка с единицей, которой служит точка (6, д), и верхняя полурешетка с нулем, которым является точка (а, с). Прямоугольник со „срезанным" правым верхним углом — нижняя полурешетка, но без единицы полурешетки.

б. Отрезок [а, Ь] С К (при любых его границах) есть одновременно и нижняя полурешетка с единицей, которой является число Ь, и верхняя полурешетка с нулем. Им служит число а. Полуинтервэлы (а, Ь] и [а, 6) суть соответственно нижняя полурешетка с единицей и верхняя полурештка с нулем. Заметим, что одновременно первый полуинтерввл есть верхняя полурешетка, не имеющая нуля, а второй полуинтервал — нижняя полурешетка беэ единицы. Интервал (а, 6) есть одновременно и нижняя и верхняя полу- решетка, но ни та, ни другэл не имеет нейтральных элементов. в. Индунтпивное упорядоченное множество в общем случае не является верхней полурешткой с нулем, хотя и имеет наименьший элемент.

Дело в том, что двухэлементное подмножество этого множества, состоящее из несравнимых элементное, может и не иметь точной верхней грани, поскольку точную верхнюю грань имеет в этом множестве любая неубываюшвя З.е. Решетки 217 последовательность и, как можно показать, любы конечная или счетны цепь. Индуктивное линейно упорядоченное множество является верхней полурешеткой с нулем. Обратное неверно. Так, множе. ство всех неотрицательных вещественных чисел (с естественным числовым порядком) есть верхняя полурешетка с нулем, но ни одна возрастающы последовательность в этом множестве не имеет точной верхней грани. Рассмотренные вьппе примеры показывают, что существуют упорядоченные множества, являющиеся нижней и верхней полурешетками одновременно.

Если такал „связка" полуре. шеток имеет определенные дополнительные свойства, то она называется решеткой. Определение 3.6. Решетка — это алгебра С = (Ь, Ч, Л) с двумя бинарными операциями, такая, что каждая из алгебр (Ь, Ч) и (Ь, Л) является полурешеткой и выполняются следующие епождесепва поглошення: аЧ(аЛЬ) =а, аЛ(аЧЬ) =а. Операции решетки Ч и Л называют решепьочным обьединением и решеепочным пересечением соответственно.

Операции решетки называют также решепьочными операциями. Другими словами, решетка — это алгебра с двумя бинарными операциями, обозначаемыми Ч и Л, такими, что вьшолняютсл тождества а Ч (ЬЧ с) = (а Ч Ь) Ч с, а Л (Ь Л с) = (а Л Ь) Л с, аЧЬ=ЬЧа, аЛЬ=ЬЛа, аЧа=а, аЛа=а, аЧ(аЛЬ) =а, аЛ(аЧЬ) =а. Из определения решетки следует, что всякое симиеепричное полукольцо и, значит, любая булгеа алгебра являются решетками, т.е.

сложение и умножение симметричного полукольца, 218 3. ПОЛУКОЛЬЦА Н БУЛЕВЫ АЛГЕБРЫ равно как и булево объединение и булево пересечение, есть примеры решеточных операций. Тогда и булева алгебра 8А всех подмножеств некоторого множества А, и полукольцо 11„всех делителей натурального числа н — примеры решеток. Приведем пример решетки, не являющейся полукольцом. Пример 3.16. Алгебра ((а, Ь), шах,пйп), носитель которой — открытый интервал на числовой прямой, а операции— взятие наибольшего и наименьшего из двух чисел (относительно естественного числового порядка), есть решетка. Однако отсутствие нейтральных элементов по данным операциям не позволяет считать данную алгебру полукольцом.

ф Заметим, что решеточные операции в общем случае и не дистрибутивны (хотя в только что рассмотренном примере 3.18 дистрибутивность каждой операции относительно другой имеет место). Конкретные примеры недистрибутивных решеток будут приведены ниже. Выясним теперь связь между понятием решетки и понятием упорядоченного множества. Каждая решетка, как следует из определения, есть „связка" двух полурешеток, но априори совсем не очевидно, что естественные порядки этих полурешеток суть взаимно двойственные порядки, т.е. для любых а, Ь е Ь неравенство а ~( 6, равносильное равенству а Ч 6 = Ь, имеет место если и только если а Л 6 = а. Такую связь между решеточными операциями устанавливает следующая теорема.

Теорема 3.12. В любой решетке С = (Ь, Ч, Л) естественный порядок ~ (полурешетки (1, Ч) есть порядок, двойственный к естественному порядку полурешетки (1, Л), т.е. для любых а, Ь Е Ь имеет место равенство а ч Ь = Ь оо а л Ь = а, т.е. аЧЬ=впр1а, Ь) и аЛЬ=|пЕ1а, Ь). ~ Согласно определению естественного порядка полурешетки, для любых а, Ь Е Ь выполняется условие а < Ь ло а Ч 6 = Ь. Мы 3.5. Решетки 219 должны доказать, что двойственный порядок > совпадает с естественным порядком нолурешетки (Ь, Л), т.е.

нужно доказать, чтоа>ЬеэаЛЬ=били, чторавносильно, а<ЬеьаЛЬ=а. Для этого достаточно показать, что а Ч Ь = Ь ЕЬ а Л 6 = а. Имеем: если аЧЬ=Ь, то аЛЬ=аЛ(аЧ6). Согласно второму тождеству поглощения, аЛ(аЧ6) =а, и поэтому аЛЬ=а; если же а Л Ь = а, то с учетом первого тождества поглощения будем иметь аЧ6= (аЛЬ) Ч6= Ь. Итак, естественные порядки полурешеток (о, Л) и (1, Ч) взаимно двойственные. Так как в силу теоремы 3.10 вар (а, Ь) = = аЧ Ь для любых а, Ь Е Ь, то, согласно принцнпу двойственности, шЕ(а, Ь) =аЛЬ.

1ь Обратим внимание на использование тождеств поглощения при доказательстве теоремы 3.12. Именно они делают естественные порядки полурешеток (Ь, Ч) и (Ь, Л) взаимно двойственными. Таким образом, любая решетка Ю = (Ь, Ч, Л) есть в то же время упорядоченное множество (1, <), где отношение порядка < совпадает с естественным порядком полурешетки (Ь, Ч), которве тогда будет верхней полурешеткой. Полурешетка же (1., Л) оказывается (относительно этого же отношения порядка) нижней полурешеткой.

Первую полурешетку поэтому часто нюывают верхней полурешткой решетки,С, а вторую полурешетку — нижней полурешеткой той же самой. решетки. Само же отношение порядка < называют естпестпеенным порядком решетпки Е. Можно доказать утверждение, обратное к теореме 3.12. Теорема 3,13. Любое упорядоченное множество Е = (Ь, ((), в котором всякое двухэлементное подмножество имеет точную верхнюю и точную нижнюю грани, т.е.

для любых а, Ь Е Ь существуют зпр(а, Ь) и шЦа, Ь), является решеткой в смысле определения 3.5, в которой решеточные операции определяются так: а Ч Ь = зпр(а, Ь), а Л Ь = шЦа, 6). 220 3. ПОЛУКОЛЪЦА И БУЛЕВЫ АЛГЕБРЫ При этом естественный порядок решетки (Ь, впр, шЕ) совпада- ет с исходным порядком ((. м То, что каждая из алгебр (Е, апр) и (Е, шЕ) является полурешеткой, равно как и то, что естественный порядок первой полурешетки совпадает с исходным порядком <, а естественный порядок второй полурешетки двойствен к порядку ~(, следует из теорем 3.10 и 3.11. Остается доказать тождества поглощения.

Достаточно доказать одно из них,так как второе будет выполняться в силу принципа двойственности (для упорядоченных множеств). Итак, докажем, что для любых а,Ь Е Ь выполняется равен- ство шЕ(а, впр(а, Ь)) = а. (3.34) Равенство (3.34) следует из того, что для любых элементов с,д Е Е иэ того, что с < д, следует, что с = шЕ(с, а1. Тогда в силу неравенства а < гпр(а, Ь) имеем (3.34). 1ь Важность последнего результата состоит в том, что полурешетку можно задавать как упорядоченное множество с точными верхними и точными нижними гранями для любой пары элементов.

Характеристики

Список файлов книги