В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 16
Текст из файла (страница 16)
Так, например, при r = 2M (4) =1 42 · 1 + 22 · (−1) + 21 · 0 = 3.4Решетки. Пусть (P, 6) — некоторое частично упорядоченное множество и X ⊆ P.Определение 1.4.14. Верхней гранью множества X называется элемент (если он существует) a ∈ P такой, что∀x ∈ X ⇒ x 6 a. По двойственности определяется нижняя грань множества X. Точной верхней гранью множестваX называется наименьшая из верхних граней supX (если такая существует). По двойственности определяется точнаянижняя грань inf X множества X.Определение 1.4.15.
Частично упорядоченное множество (P, 6) называется полной решеткой, если у любого множества X ⊆ P существуют sup X и inf X. Если у каждого X ⊆ P существует sup X, то (P, 6) называется верхней полурешеткой, если же у каждого X ⊆ P существует inf X, то (P, 6) называется нижней полурешеткой.Определение 1.4.16.
Частично упорядоченное множество (P, 6) называется решеткой, если у любых x, y ∈ P сущеdefdefствуют sup {x, y} = x ∨ y и inf {x, y} = x ∧ y.Замечание. Если (P, 6) — решетка, то для любых x1 , . . . , xn ∈ P существуютsup {x1 , . . . , xn } = x1 ∨ · · · ∨ xnиinf {x1 , . . . , xn } = x1 ∧ · · · ∧ xn .Примером неполной решетки может выступать частично упорядоченное множество натуральных чисел по делимости (N, |).
Легко видеть, что в нем множество X = N не имеет верхних граней вообще, следовательно, не имеет и точнойверхней грани.Введенные выше обозначения точной верхней и точной нижней граней пар элементов решетки можно рассматривать как операцию над элементами исходного частичного порядка. Легко доказать, что выполняется простой законассоциативности, например, для точной верхней грани:(x ∨ y) ∨ z = x ∨ (y ∨ z) .Действительно, пусть x ∨ y = a и b = a ∨ z. Предположим, что x ∨ (y ∨ z) = b1 < b.
Но тогда x 6 b1 , y ∨ z 6 b1 ⇒ y 6 b1 ,причем b1 является верхней гранью как для x, так и для y. Тогда a 6 b1 , но b 6 a, откуда получаем противоречие спредположением b 6 b1 .Решеткой является множествоM (d1 , . . . , dn ) = (x1 , . . . , xn ) 0 6 xi 6 di , xi , di ∈ Z, i = 1, n ,причем (x1 , . . . , xn ) 6 (y1 , . . . , yn ) ⇔ xi 6 yi ∀ i = 1, n.
Множество, состоящее из линейных подпространств пространстваR3 (начало координат, три координатных оси, три координатных плоскости и все R3 ) также представляет собой решетку, причем изоморфную B3 . Частично упорядоченное по включению множество всех подгрупп (включая тривиальные— пустую и саму группу) некоторой конечной группы G является также решеткой.
При этом точной верхней граньюмножества является наименьшая группа, содержащая все группы это множества, а точной нижней гранью — пересечение всех групп множества. Замкнутые классы функций k-значной логики (k > 2) также образуют решетку. По аналогиис группой точной верхней гранью множества классов выступает наименьший класс, всех их содержащий, а точнойнижней гранью множества классов является их пересечение. При k = 2 решетка замкнутых классов в Pk называетсярешеткой Поста.Очевидным образом выполняются следующие пять свойств:1. x ∧ x = x, x ∨ x = x — идемпотентность,2. x ∧ y = y ∧ x, x ∨ y = y ∨ x — коммутативность,551.4.
ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВА3. (x ∧ y) ∧ z = x ∧ (y ∧ z) , (x ∨ y) ∨ z = x ∨ (y ∨ z) — ассоциативность,4. x ∧ (x ∨ y) = x ∨ (x ∧ y) = x — поглощение,5. x ≤ y ⇐⇒ x = x ∧ y и y = x ∨ y — совместимость,6. свойство дистрибутивности, которое, вообще говоря, выполняется не всегда:(a) x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) и(b) x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z).Таким образом, можно перейти к рассмотрению алгебры (P, ∨, ∧), соотносящейся с частичным порядком (P, 6) согласносвойству 5.Определение 1.4.17. Подрешеткой решетки (P, ∨, ∧) называется решетка (Q, ∨, wedge), где Q ⊆ P замкнутая относительно операций взятия точной верхней и точной нижней граней в исходной решетке (P, ∨, ∧).Чтобы подчеркнуть важность последнего требования приведем пример решетки U, носитель которой является подмножеством решетки B3 , однако, U не является подрешеткой B3 согласно введенному определению.v `c@@@x c`y c`z c`@@@@@``@`inf {x, y} @@@c`wB3Uv `c@x `cy c`@@@c`w@@z c`Действительно, x, y ∈ U, но inf {x, y} ∈/ U.Примером множества, не являющегося решеткой служит частично упорядоченное множество, заданное диаграммойХассе: элементы x, y не имеют верхней грани вообще, а значит и точной верхней грани.x `@y`@@@@`@``@@`Определение 1.4.18.
Если для любых трех элементов x, y, z решетки выполняются условия 6a и 6b, то решетка называется дистрибутивной.Примерами дистрибутивных решеток являются Bn , упорядоченный стандартным образом и (N, |). Примераминедистрибутивных решеток являются пентагон и решетка U, рассмотренная в качестве контрпримера подрешетки.v ∨` w@x ∨` zAy c`Ax `c@ @`y∧zAz A`cu `c@@@v c`w@c`@@@`u∧v = u∧wДействительно, в пентагоне:x ∨ (y ∧ z) = x 6= y = (x ∨ y) ∧ (x ∨ z) ,в решетке U:u ∧ (v ∨ w) = u 6= 0 = (u ∧ v) ∨ (u ∧ w) .Справедлив некий аналог теоремы Понтрягина-Куратовского: решетка является дистрибутивной тогда и только тогда,когда она не содержит в качестве подрешеток пентагона и U.
Используя это утверждение, можно показать, например, что частично упорядоченное по подразбиениям множество разбиений конечного множества является решеткой,которая не дистрибутивна, если только исходное множество содержит не менее трех элементов.56ГЛАВА 1. КОМБИНАТОРИКАЛюбая решетка с конечным носителем является полной. Элемент p решетки L называется неприводимым, есливыполняется импликацияp = x ∨ y =⇒ p = x или p = y.Исключим по определению из множества неприводимых элементов наименьший (несмотря на то, что вышеприведеннаяимпликация для него выполняется).
На языке диаграмм Хассе из вершины, соответствующей неприводимому элементу,выходит вниз не более одного ребра: в противном случае он являлся бы точной верхней гранью двух непосредственнопредшествующих ему элементов. Согласно определению любой элемент частично упорядоченного множества являетсялибо неприводимым, либо приводимым, поэтому для произвольного элемента a частично упорядоченного множествадопустимо представление его в виде точной верхней грани неприводимых элементов a = p1 ∨ p2 ∨ · · · ∨ ps .
Если длялюбого i = 1, s ⇒ a 6= p1 ∨ p2 ∨ · · · ∨ pi−1 ∨ pi+1 ∨ · · · ∨ ps , то такое разложение называется несократимым. В этом случаеочевидно, что множество неприводимых элементов {pi }si=1 образует антицепь. Разложением для нуля будем считатьсам нуль: 0 = 0.Лемма 1.4.1. Пусть p — неприводимый элемент дистрибутивной решетки L иp6n_ai .i=1Тогда найдется такое 1 6 i 6 n, что p 6 ai . Док-во. Из условия ясно, что для p справедливо представление!p = p∧n_aii=1=n_(p ∧ ai ) .i=1Поскольку все p ∧ ai 6 p, должно найтись такое i, что выполнится в точности равенство p ∧ ai = p. В этом случае поопределению точной нижней грани и выполнится p 6 ai .Лемма доказана.Лемма 1.4.2 (Биркгоф). Несократимое разложение на неприводимые элементы для любого элемента a ∈ L(L — дистрибутивная решетка) однозначно с точностью до порядка неприводимых элементов, участвующих в разложении.
Док-во. Пусть найдутся два несократимых разложения некоторого элемента a ∈ L на неприводимые элементы:a = p1 ∨ p2 ∨ · · · ∨ ps = q1 ∨ q2 ∨ · · · ∨ qr .Из вида разложений следует, что∀ i = 1, s ⇒ pi 6 a =r_qi =⇒ ∃ j : pi 6 q j ,аналогично ∃ k : q j 6 pk =⇒ pi 6 q j 6 pk .i=1Учитывая то, что элементы несократимого разложения на неприводимые элементы лежат на антицепи, получим pi =q j = pk . Проведя эти рассуждения сначала для всех pi , а затем для всех q j , убедимся, что оба разложения состоят изодних и тех же неприводимых элементов и могут различаться лишь их порядком.Лемма доказана.Монотонная булева функция на частично упорядоченном множестве может быть задана следующим образом: выделяется произвольная максимальная по включению антицепь, выше которой функция определяется единицей, а наней и ниже — нулем.
По двойственности можно определить антимонотонную функцию. Это определение понадобитсянам в дальнейшем при кодировании дистрибутивных решеток. Предварим это следующим примером. Пусть частичноупорядоченное множество задается диаграммой Хассе.f`ce `@@c `cd c`@@b c``afc`@c` c@c` d@@c`b1.4. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВА57Выделим из этого множества подмножество всех неприводимые элементов — в данном случае это {b, c, d, f }. Неприводимые элементы находятся между собой в отношении частичного порядка, определяющемся в свою очередь своей диаграммой Хассе, представленной справа.
Новый частичный порядок, образованный неприводимыми элементами можно упорядоченным образом покрыть цепями. Сделать это можно разными способами: например, пользуясь теоремойДилуорса, покрыть числом цепей, равным ширине множества (в этом случае число цепей минимально), а можно тривиально: каждый неприводимый элемент объявить самостоятельной цепью (в этом случае число цепей максимально).Пусть уже имеется упорядоченное покрытие цепями C1 , .
. . ,Cn длин `1 , . . . , `n соответственно. Пронумеруем элементыCi по порядку числами от 1 до `i для i = 1, n. Теперь каждому элементу исходной дистрибутивной решетки поставим всоответствие набор чисел (k1 , . . . , kn ), где ki для i = 1, n — номер неприводимого элемента с i-ой цепи, участвующего внесократимом разложении элемента на неприводимые элементы (ki 6 `i ). В случае, если ни один элемент с цепи Ci неучаствует в несократимом разложении на неприводимые элементы данного элемента частично упорядоченного множества, положим ki = 0. Таким образом, для данного покрытия цепями происходит вложение дистрибутивной решетки вn-мерный параллелепипед с целочисленными координатами:P → ([0, `1 ] ∩ Z) × ([0, `2 ] ∩ Z) × · · · × ([0, `i ] ∩ Z) × · · · × ([0, `n ] ∩ Z) .Рассмотрим тривиальное покрытие множества неприводимых элементов, объявив каждый элемент самостоятельной цепью.
В этом случае установится соответствие между всеми элементами исходного частично упорядоченного множества и наборами из нулей и единиц длины 4:a −→ (0, 0, 0, 0)b −→ (1, 0, 0, 0)c −→ (1, 1, 0, 0)d −→ (1, 0, 1, 0)e −→ (1, 1, 1, 0)f −→ (1, 1, 1, 1)Это соответствие проинтерпретируем как вложение исходной дистрибутивной решетки в четырехмерный единичныйкуб B4 :c` f@` ` ` @`c@ e@@ d` ` @` ` @c` @c` c@ @@@`@` @`c`@ b@c` aРассмотрим другое упорядоченное покрытие цепями, число которых равно ширине решетки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
