Дискретно-непрерывная математика (стр. 53 )

Пусть L — вполне упорядоченное множество, а следовательно, и

решетка; тогда L × L—тоже решетка; аналогично—

тоже решетки, но при r> 1 это лишь частично упорядоченные мно­жества. На рис. 4.2—4.7 мы видим решетки, представленные их диаграммами Хассе.

Рис. 4.2 Рис. 4.3

Рис. 4.4 Рис. 4.5

I

Рис 4.6 Рис. 4.7

Контрпримеры (Контрпримеры опровергают утверждение, что любой порядок представ­ляет собой решетку.) На рис. 4.8 приведены три примера, показыва­ющие с помощью диаграммы Хассе, что понятие отношения порядка не равносильно понятию решетки.

Рис. 4.8

Так, диаграмма на рис. 4. 8, а не представляет собой решетку. Действительно, С есть нижняя граница {D, Е}, но и В тоже; следовательно, существует по крайней мере одна пара элементов, имеющая не единственную нижнюю границу. Диаг­рамма на рис. 4.8, б тоже не решетка, поскольку, например, пара {D, Е} не имеет верхней границы. Аналогично диаграмма на рис. 4.8, в не представляет собой решетку. Выпишем максимальные цепи этих трех отношений порядка в явном виде:

(4,13)

Теперь кратко опишем несколько важных классов решеток Модулярная решетка. Говорят, что решетка L модулярная, если для трех произвольных элементов Х1, Х2, Х3 L имеем

(4.14)

где символобозначает отношение порядка на решетке.

Так, решетка на рис. 4.9 модулярная.

Рис. 4.9

Проверим это для А, В и С. Имеем

(4.15)

а также, выбирая произвольно еще один элемент, например В,

(4.16)

(4.17)

Свойство (4.14) аналогично проверяется для других троек.

Дистрибутивная решетка. Говорят, что решетка L дистрибутивная, если удовлетворяются условия

(4.18)

Можно проверить, что эти условия действительно удовлетворяются для всех 20 троек элементов на рис. 4.10. Например,

(4.19)

Рис. 4.10

Можно показать, что любая дистрибутивная решетка модулярная.

Прежде чем перейти к другим типам решеток, напомним, что такое

подрешетка. Рассмотрим решетку L и пусть А L, где А — подмно-

жество, упорядоченное индуцированным порядком. Если

то А есть подрешетка L.

Можно доказать, что любая подрешетка L' дистрибутивной решет­ки L дистрибутивна.

Решетка с дополнениями. Сначала определим, что такое дополне­ние элемента решетки.

Пусть элемент О есть нижняя граница всей решетки L, а элемент U — верхняя граница той же самой решетки. Тогда элемент Хj назы­вается дополнением элемента если

(54.20) (4.21)

Дополнение элемента Xi обозначается Дополнение Xi, если

оно существует, не обязательно единственное.

На рис. 4.11 каждый элемент имеет дополнение:

(4.22)

Pис. 4.11

Говорят, что L — решетка с дополнениями, если

1) она обладает единственным элементоми единствен-

ным элементом

2) каждый Хi L обладает по крайней мере одним дополнением в L.

Как легко видеть на рис. 4.11 изображена решетка с дополнениями.

Можно показать, что в дистрибутивной решетке, если дополнение элемента Хi существует, то оно единственное.

Дистрибутивная решетка с дополнениями, или булева решетка. Ре­шетка, которая одновременно и дистрибутивная и с дополнениями, называется булевой.

Можно проверить, что решетка на рис. 4.12 действительно булева.

Рис. 4.12

Перечислим несколько свойств булевых решеток:

1) для каждого элемента существует одно и только одно дополнение;

2) для каждого Xі имеем

(4.23)

3) выполняются следующие соотношения:

(4.24-4.25)

(теоремы де Моргана);

4) каждая конечная булева решетка изоморфна решетке множе­ства всех подмножеств относительно включения и наоборот.

Векторная решетка. Пусть А, В, ..., S есть п множеств, каждое из которых вполне упорядочено отношением . Произведение множеств А × В ×... × S упорядочено и образует решетку, называемую век­торной решеткой, а отношение порядка на ней является отношением доминирования.

На рис. 4.13 изображена векторная решетка, образованная про­изведением множеств

(4.26)

Рис. 4.13

Подчеркнем важное свойство: за исключением очевидного случая булевой векторной решетки, каждая векторная решетка дистрибутив­на, но не имеет дополнений.

Лексикографическая векторная решетка. Это такая векторная ре­шетка, которая сводится к полному порядку, например, такому, который используется в словаре (откуда произошло название). Рас­смотрим следующее отношение доминирования: п-ка (Аi, Вj, ..., St) доминирует п-ку (Аi', Вj', ..., St') в том и только в том случае, когда первые r элементов (произвольно отсчитанные слева) двух п-ок равны, а (r + 1) й элемент первого набора больше (для рассматри­ваемого отношения), чем (r + 1)-й элемент второго. Таким образом получаем полный порядок.

На рис. 4.14 представлены две лексикографические решетки.

Рис. 4.14

Произведения решеток. Пусть L1 и L2 — две решетки; тогда произ­ведение этих двух множеств снова решетка. Другими словами,

(L1 — решетка и L2 — решетка) (L1 × L2 — решетка). (4.27)

Рассмотрим пример. Пусть имеем

(4.28)

(4.29)

решетчатые структуры которых представлены на рис. 4.15, а и б со­ответственно.

Рис. 4.15

Укажем максимальные цепи:

для решетки L1

(4.30)

для решетки L2

(4.31)

Рассмотрим две упорядоченные пары Если (Xi′, Yj′) доминирует (Xi, Yj), то пишут

(4.32)

где обозначает отношение доминирования.

Таким образом, произведение L1 × L2 упорядочено, и можно устано­вить, что для этой структуры выполняются соотношения (4.4)— (4.11).

Чтобы построить решетку

(4.33)

надо сравнить друг с другом все упорядоченные пары (Xi, Yj) и опре­делить, какая из них доминирует другие. Это дает максимальные цепи решеткии позволяет определить решетку произведения.