54. Обзор некоторых основных структур

Решетка. Пусть - упорядоченное множество. Предположим, что для каждой пары обычных подмножеств множества существует один и только один элемент - нижняя граница и аналогично существует один и только один элемент - верхняя граница ; в этом случае говорят, что - решетка или сетчатое множество.

Введем обозначения:

для нижней границы ,

для верхней границы .

Тогда определение решетки можно записать в виде

(54.1)

(символ означает «существует одно и только одно»).

Операции и можно также рассматривать как отображения в , которые каждой паре , ставят в соответствие элемент и элемент .

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

Пример. На рис. 54.1,а приведен пример решетки. На рис. 54.1,б изображена диаграмма максимальных цепей, или диаграмма Хассе. Имеем

. (54.10)

Можно проверить, что

(54.11)

В качестве упражнения читатель должен проверить свойства (54.2)-(54.9).

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

. (54.12)

Рис. 54.1.

Таким образом, в этом упорядоченном множестве имеется три цепи, которые определены как максимальные, поскольку ни одна из них не может быть частью другой цепи упорядоченного множества.

Неориентированный обычный граф, составленный из максимальных цепей, называется диаграммой максимальных цепей или диаграммой Хассе; для нашего примера такая диаграмма изображена на рис. 54.1,б.

Другие примеры. Вполне упорядоченное множество является решеткой.

Пусть - вполне упорядоченное множество, а следовательно, и решетка; тогда - тоже решетка; аналогично - тоже решетки, но при это лишь частично упорядоченные множества. Если вернуться к рис. 6.1-6.6, то на них мы увидим решетки, представленные их диаграммами Хассе.

Контрпримеры. На рис. 54.2 приведены три примера, показывающие с помощью диаграммы Хассе, что понятие отношения порядка не равносильно понятию решетки. Так, диаграмма на рис. 54.2,а не представляет собой решетку. Действительно, есть нижняя граница , но и тоже; следовательно, существует по крайней мере одна пара элементов, имеющая не единственную нижнюю границу. Диаграмма на рис. 54.2,б тоже не решетка, поскольку, например, пара не имеет верхней границы. Аналогично диаграмма на рис. 54.2,в не представляет собой решетку. Выпишем максимальные цепи этих трех отношений порядка в явном виде:

(54.13)

Теперь кратко опишем несколько важных классов решеток.

Модулярная решетка. Говорят, что решетка модулярная, если для трех произвольных элементов имеем

, (54.14)

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

Так, решетка на рис. 54.3 модулярная. Проверим это для , и . Имеем

, (54.15)

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

, (54.16)

. (54.17)

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

Рис. 54.3.

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

(54.18)

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

Рис. 54.4.

Например,

(54.19)

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

Прежде чем перейти к другим типам решеток, напомним, что такое подрешетка. Рассмотрим решетку и пусть , где - подмножество, упорядоченное индуцированным порядком. Если , , и , то есть подрешетка .

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

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

Пусть элемент есть нижняя граница всей решетки , а элемент - верхняя граница той же самой решетки. Тогда элемент называется дополнением элемента , если

, (54.20)

. (54.21)

Дополнение элемента обозначается . Дополнение , если оно существует, не обязательно единственное.

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

, или , или ; , , , . (54.22)

Рис. 54.5.

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

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

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

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

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

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

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

Рис. 54.6.

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

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

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

, (54.23)

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

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

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

Векторная решетка. Пусть есть множеств, каждое из которых вполне упорядочено отношением . Произведение множеств упорядочено и образует решетку, называемую векторной решеткой, а отношение порядка на ней является отношением доминирования [см. (4.3) и (4.4)].

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

, , . (54.26)

Рис. 54.7.

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

Лексикографическая векторная решетка. Это такая векторная решетка, которая сводится к полному порядку, например, такому, который используется в словаре (откуда произошло название). Рассмотрим следующее отношение доминирования: -ка доминирует -ку в том и только в том случае, когда первые элементов (произвольно отсчитанные слева) двух -ок равны, а -й элемент первого набора больше (для рассматриваемого отношения), чем -й элемент второго. Таким образом получаем полный порядок.

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

Рис. 54.8.

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

. (54.27)

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

, (54.28)

, (54.29)

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

Рис. 54.9.

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

для решетки

; (54.30)

для решетки

, . (54.31)

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

, (54.32)

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

Таким образом, произведение упорядочено, и можно установить, что для этой структуры выполняются соотношения (54.4)-(54.11).

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

, (54.33)

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

Читатель должен сам подключиться к построению решетки произведения относительно и . Рассматривая (54.30) и (54.31), можно, например, написать

, (54.34)

и т.д. (54.35)

Нужно каждую пару сравнить со всеми другими; это довольно длительный процесс. Обработку можно упростить, сравнивая друг с другом максимальные цепи (54.30) и (54.31).

Следует указать на важный частный случай, когда и - полностью упорядоченные множества; тогда образует векторную решетку.

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

Частично упорядоченное множество, не образующее решетку. Конечно, не все частично упорядоченные множества образуют решетку (например, изображенное на рис. 54.10). Очевидно, что

, (54.36)

. (54.37)

Рис. 54.10.

Если для любого обычного подмножества его верхняя граница принадлежит , то говорят, что есть верхняя полу решетка. (рис. 54.11,б).

Рис. 54.11.

Аналогично, если речь идет о нижней границе, то говорят, что есть нижняя полурешетка (рис. 54.11,а). Решетка является одновременно и нижней и верхней полурешеткой.

На рис. 54.11 мы изобразили нижнюю (а) и верхнюю (б) полурешетки, и, как можно заметить, целиком изображенное на рис. 54.10 упорядоченное множество не является ни нижней, ни верхней полурешеткой.

Порядковая функция частично упорядоченного множества. В § 24 мы определили понятие порядковой функции для любого графа без контуров. Если известно, что граф представляет частичный порядок, определен на конечном множестве и не имеет контуров, то определение его уровней может оказаться очень полезным; они облегчают анализ и синтез отношений порядка. Порядковую функцию можно установить непосредственно с помощью диаграммы Хассе, или диаграммы максимальных цепей.

На рис. 54.12-54.14 видно, как определить уровни для некоторых отношений порядка (решеток или нет) с помощью их представлений в виде диаграммы Хассе.

Рис. 54.12.

Рис. 54.13.

Рис. 54.14.

Структура кольца. Рассмотрим множество , наделенное двумя внутренними законами и , такими, что для всех

1. - ассоциативность для ; (54.38)

- существование единицы для ; (54.39)

- существование обратного элемента для всех ; (54.40)

- коммутативность операции ; (54.41)

2. - ассоциативность операции ; (54.42)

3. - дистрибутивность слева (54.43)

и справа относительно . (54.44)

Говорят, что имеет структуру кольца или что -кольцо. Если закон к тому же коммутативный, то говорят, что кольцо коммутативное.

Рис. 54.15 дает пример структуры кольца, где - единица.

Рис. 54.15.

Булева решетка и булево кольцо. Булева решетка - это дистрибутивная решетка с дополнением. Можно проверить, что для всех

; (54.53)

; (54.54)

; (54.55)

; (54.56)

; (54.57)

; (54.58)

; (54.59)

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

Можно убедиться, что для любых имеют место свойства:

1. - ассоциативность операции , (54.62)

- существование единицы для , (54.63)

- существование обратного элемента, которым будет само множество , (54.64)

- коммутативность для . (54.65)

2. - ассоциативность для . (54.66)

Следовательно, множество само наделено структурой кольца и называется булевым кольцом. Можно показать, что в этом кольце, если , то соответствуют дизъюнктивной сумме , а - пересечению .