Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 7

Решетка А дистрибутивна тогда и только тогда, когда в каждом интервале У решетки А любые два свлэанных в У элемента равны. Этот критерий можно выразить в более удобной для вычислений форме, если найти структуру подрешеток, наличие которых выводит решетку нз класса дистрибутивных. Введем понятие дедекиндовых (модулярных) решеток.

Решетка А называется дедекиндовой тогда и только тогда, когда (Чт;,т.,тьбА, т <ть)((т;0ту)Пть=т Пть0т). Критерий дедекнндовости решетки. Решетка А дедекиндава тогда и только тогда, когда она не содержит падрешетки, иэаморфной решетке А (рис. 1.12, а).

Решетка А содержит олин элемент нулевой высоты, два элемента единичной высоты и по одному элементу, высота которых 2 и 3. Используя критерий модулярности решеток, сформулируем критерий дистрибутивности в более удобной для вычислений форме: решетка дистрибутивна тогда и только тогда, когда она не содержит подрешетки, иэоморфной А, т. е. лвллетсл дедекиндовой, и не содержит подрешетки, иэоморфной падрешетке Ае (рис.

1.12,6). Решетка Ае содержит три цепи длины 2, состоящие из одного элемента нулевой высоты, трех Рес. 1.12 элементов единичной высоты и одного элемента высоты 2. Решетка А, задаваемая диаграммой Хассе Н (см. рис. 1.10, б), является не только дедекиндовой, но и дистрибутивной. В решетке А со структурными нулем и единицей, в которой каждый элемент т обладает дополнением т, можно считать задакной унарную одноместную операцию 11(т) = т.

Решетка А называется решеткой с дополнениеми, если она обладает структурным нулем и такой унарной операцией Ят) = т, что т=т, (1 6) т; 0 Впу — тв П ту, (1 6) тПт= О. (1.7) Согласно (1.6) и (1.6) одна из операций О, П может быть выражена через другую. Следовательно, решетку с дополнениями можно определить как алгебру, сигнатура которой состоит из 0, Отметим некоторые следствия тождеств (1.6) — (1.7). Имеем О < т для всех т б М; следовательно, О П т = О. Если положить 1 = О, а О П т О и О 0 т = т подставить в (1.6), то получим 1 П т = т, 1 0 т = 1. Следовательно, 1 — наибольший элемент решетки, т.

е. является структурной единицей. Согласно тождествам (1.7) и (1.6) т 0 т = 1. Дистрибутивная решетка с дополнениями называется булевой алгеброй. Изоморфиэмом и между алгебрами А1 — — (М1, 51) и Аз = = (Мэ, Яэ) называется такое взаимно однозначное соответствие между элементами носителей и сигнатур, что Л(таю таа> ° ° о таь а) = таь н н Ц(Л)(О(гпаа)о 11(таа)о ° ' о Вво(таь В)) = Ввв(таь)о тпатбМ1, О(тат)бМ2, у=1,2,,Й, Л651о 9(Л)без Алгебры, между которыми существует изоморфизм, называются изоморфными. Все законы алгебры А1 справедливы и в изоморфной ей алгебре Аэ. Теорема 1.2 (Стоун).

Булева алгебра иэоморфна алгебре .Кантора. Для рассматриваемых алгебр имеется следующий изоморфизм: а0Ьн М,ОМь, аПЬн М,ПМь, она~„ где в левых частях выражений стоят теоретико.решетчатые, в правых — теоретико-множественные операции. Эти операции имеют одно и то же написание, поэтому, чтобы их различать, аргументы теоретико-решетчатых операций будем обозначать малыми буквами, а аргументы теоретико-множественных операций — большими буквами латинского алфавита. 2 В. В. Горавтвв 35 1 1.4.

Решстпяа 34 15 Рис. 1.14 Рис. 1.13 Таблица 1.3 Оперзцяя иересечевяя (сг п,В) Операция иересечеввя (сг П,0) Таблица 1.4 Операция допалпепяя (сг) 60 12 15 20 10 1 2 1 1 1 1 1 2 1 2 3 3 1 1 2 1 1 4 1 4 1 2 1 5 5 1 1 6 3 2 2 5 10 1 2 1 2 10 10 10 10 12 12 3 4 12 15 3 15 5 1 1 20 10 4 5 20 б 15 10 10 1 2 1 2 10 50 12 15 20 10 1 2 Гл. 1. Осиоеы мяогосорагных ммолсесше На рис. 1.13 изобранена дистрибутивная решетка с дополнениями, з которой результаты действия теоретико-решетчатьпс операций объединения, пересечения и дополнения определены в табл. 1.2-1.4. Таблица 1.2 Операция ебъедипеиия (сг Ц )у) Элементам а я а соответствуют максимально (з смысле длины соединшощей их цепи) удаленные вершины диаграммы Хассе.

Рассмотрим еше один пример решетки, обрааозапной бинарным опюшением делвмостп Втг в множестве целых чисел (1, 2, 3,4, 5, б, 10, 12, 15, 20, 30, 60); (а, Ь) б Взэ с+ геэс(Ь/а) = О, где гезу(Ь/а) — остаток от целочисленного деленна Ь на а. Отношение дслвмости Взе рефлексивно: гезт(а/а) = 0; аитисвмметрично: гевс(Ь/а) = 0 -+ гааз (а/Ь) уь 0 (таас(а/Ь) = а), ггвс (Ь/а) = гает(а/Ь) ++ а = Ь; травзитнано: геас(Ь/а) = Оуспнт(с/а) = О -+ гезз(с/а) = О.

Следозателыю, отвошешге Взг является атяошеиием частичкой упорядочекности. Диаграмма Хассе, определаощая это отношение, представлена на рнс. 1.14. Для вандой вары элементов диаграэяеы Хассе нмеется наиболъшая винная грань (табл. 1.5) и яавмеиьшая верхняя грань (табл. 1.5). В диаграмме имеются структурный нуль (чясло 1) н структурная едвшща (число 60). Имеет зн вандый элемент доволневие (табл. 1.7)7 Нет, мммеиты 2, б, 10, 30, зошедюяе в пересечение носителей диаграмм Н, н Нм ве нмеют дополнений: Н = ((1, 2, 3, 5, б, 10, 15, 30), < ), Нь = ((2, 4, б, 10, 12, 20, 30, 60], < ). Следовательно, диаграмма Хассе (рис.

1.14) ведает двстрнбутиввую решетку беа дополнений, так вав оиа не содернит подрешеток, вэоморфпых А,„и Аз (см. рвс. 1.12); ври этом структурное объединение двух элементов опредглает наименьшее общее кратное соответствующих чисел, а структурное вересеченпе— навболъший общий делитель. Таблица 1.5 Гл. 1. Основы многосортлных множеств 36 11.5. Модель.

Алгеб о ошмошениб 37 Таблица 1.6 Операция ебьадяиеиия (ст ы 13) 20 30 20 30 12 15 12 15 60 10 1 2 1 2 10 10 20 30 12 30 10 60 2 2 60 30 20 60 12 15 12 60 3 б 4 4 15 12 12 12 2О 60 10 20 5 10 20 30 30 60 60 ЗО 12 12 30 20 30 60 30 10 30 60 10 20 10 10 10 60 60 60 60 12 60 12 12 12 12 15 15 60 30 60 30 20 60 60 15 60 60 15 30 20 20 20 20 20 20 60 60 30 ЗО ЗО 30 ЗО 60 ЗО 60 60 60 60 60 60 60 Таблица 1.7 Операция дапелпепил (Щ и 1 2 3 4 5 6 10 12 15 20 30 60 60 пьт 20 15 12 пст пст 5 4 3 пот 1 Если после замены дуг на цепи соответствующей длины диаграмма Хассе Н, преобразуется в диаграмму, изоморфную диаграмме Нь, то диаграммы Н, и Нь называр ются гомеаморбтными. Теорема 1.3. Диаграмма Хассе Н не определяетп решетку, если она содержити поддиаграмму, гомеоморутную Н, (рис.

1.15). Доказательство. Очевидно, что элементы ст и Д не имеют наибольшей нижней грани, элементы у и о — наименьшей верхней грани. 3 1.5. Модель. Алгебра отношений Аналогично бинарному отношению определим и-арное отношение.

Декартово произведение и равных между собой множеств М называется и-й степенью М" множества М. Под и-арным отношением Т в множестве М понимается подмножество Т его п-й степени Т С М". Если элементы т;„т;„..., т;„принадлежат М и (т;„т;„..., т;„) Е Т, то говорят, что элементы находятся в отношений Т. Любое и-арное отношение может бып задано в виде списка, элементами которого являются последовательности (кортежи), определяемые этим отношением. Рассмотрим свойство симметричности и-арных отношений, позволяющее эффективно использовать п-арные отношения при формализации многих практических задач.

Симмепьричным называется и-арное отношение Т в множестве М такое, что если (т;„ т;„ ..., тп;„) Е Т, то и любая последовательность (тт„ т „ ..., т „), полученная из (тй, т;„ ..., тп;„) перестановкой элементов, также находится в отношении Т: (т „т „..., т „) Е Т. По существу и-арное отношение, обладающее свойством симметричности, задает подмножества, которые состоят из и элементов, — подмножества мошности п.

В дальнейшем и-арное отношение, обладаюшее свойством симметричности, будем называть Я-ричным отношением (Я-отпношением или словесныи отношением). Элементы множества М, в котором определено Я-отношение, будем называть буквами, а подмножества, определяемые Я-отношением, будем называть словами и обозначать р;.

Задавать Я-отношение можно более удобными способами: матрицей инцидентности и модельным графом (мографом). Матрииеб иниидентпноспьи () = (д;у) называется двумерная матрица, каждому столбцу которой взаимно однозначно соответствует буква, строке — слово, определяемое Я-отношением, и ) 1, т)Е(ь;, ббш1О, )Ур;, Например, 3-ьтношепие в множестве М = (о, и, о, р, с, ы), определяюшее словат = (с,о,р), т = (р, и, с), тть =(с,ы,р), тта =(о, с, о), с вомошью матрицы инцидеитности ст можно аьлать следующим абрагом: а и а т с и 0 0 1 1 1 0 1Ую01О11О 0 0 0 1 1 1 1 0 1 0 1 0 Если отношение Я определяет подмножество М', М' С М', то число в будем называть степенью отпношения Я. Задать Я-отношение произвольной степени с помощью графа, носитель которого совпадает с множеством букв, нельзя (см.