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

Докажем дистрибутивность и существование дополнений.

(5.11) Положим

(5.12)

Убедимся, что

(5.13)

аналогично

(5.14)

Таким образом, LE так же, как и L, обладает структурой булевой решетки, и эта структура изображена на рис. 5.2.

Рис. 5. 2

Пример 2. Пусть опять

(5.15)

Е = {А, В}. (5.16)

Пусть теперь структура L представляет собой решетку, состоя­щую из единственной цепи (рис. 5. 3).

Рис. 5.3

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

(5.17)

(5.18)

Структура множества L обладает следующими свойствами: ассоциа­тивностью, коммутативностью, идемпотентностью, поглощением,

дистрибутивностью относительно ∆ и .

Легко проверить, что LE обладает теми же свойствами, а струк­тура LE — также векторная решетка (рис. 5.4).

Рис. 5.4

Пример 3. Пусть

(5.19)

Е ={А, В}. (5.20)

Структура L представляет собой нижнюю полурешетку (см, рис. 5.5), и поэтому можно определить только ∆.

Рис. 5.5

Имеем

(5.21)

В LE выполняются следующие свойства операции ∆: ассоциативность для ∆, коммутативность для ∆, идемпотентность для ∆; таким обра­зом, LE имеет структуру нижней полурешетки (см. рис. 5.6).

Рис. 5.6

Если в этом примере изменить структуру L, а именно, поменять местами верх и низ на рис. 5.5, то для LE получим верхнюю полуре­шетку.

Пример 4. Пусть

(5.22)

Е = {А, В}. (5.23)

Структура L, показанная на рис. 5.7, не полурешетка.

Рис. 5.7

В ней для некоторых упорядоченных пар уже не существует ни нижней, ни верх­ней границы. Структуру LE можно определить для отношения доми­нирования; эта структура изображена на рис. 5.8.

Рис. 5.8

Замечание. Обычно граф, представляющий отношение, называют конфигурацией. Таким образом, решетку можно рассматривать как конфигурацию, то же самое можно сказать о полурешетке и в конце концов, следовательно, о любом графе, представляющем отношение. Однако, как мы видели, решетка также представляет структуру для операций ∆ и , а полурешетка — структуру для одной из операций

∆ или . Графы, соответствующие диаграммам Хассе на рис. 5.7 и 5.8, представляют собой конфигурации, а не структуры по крайней. мере для ∆ или (и) .

Случай, когда L имеет конфигурацию предпорядка. Если структу­ра L имеет конфигурацию обычного предпорядка (в смысле обычной теории графов), то мы знаем, что в этом предпорядке можно опреде - лить множество классов эквивалетности и тогда эти классы сами с со­бой образуют (частичный или полный) порядок. Именно так мы будем поступать в случае, когда L имеет конфигурацию обычного предпо­рядка.

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

(5.24)

Е = {А, В}. (5.25)

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

Рис. 55.9

На рис. 5.10 мы выделили четыре класса эквивалентности этого предпорядка, на рис 5.11 показан порядок на этих классах, на рис. 5.12— макси­мальные цепи этого порядка.

Рис. 5.10

Рис. 5.11 Рис. 5.12

Отметим, что классы образуют верхнюю иолурешетку.

Изучая состав классов эквивалентности на рис. 5.10, замечаем, что

(5.26)

Для упрощения записи каждому* классу эквивалентности поста­вим в соответствие по одному представителю

(5.26')

которые и будем использовать для представления классов.

Верхнюю полурешетку L можно представить с помощью следующе­го отношения:

(5.27)

На рис. 5.13 изображена верхняя полурешетка LE, где ху — представитель класса.

Рис. 5.13

В этой верхней полурешетке имеется 16 классов эквивалентности. Выпишем для примера класс αβ:

(5.28)

Очевидно, что 64 элемента LE разбиваются на классы эквивалент­ности следующим образом:

(5.29)

Таким образом, LE — обычный предпорядок, содержащий 16 клас­сов эквивалентности.

Случай, когда L имеет сгруктуру кольца. Пусть

(5.30)

(5.31)

Если положим

(5.32)

(5.33)

где х1, х2, у1, у2 L и А, В Е, то

(5.34) (5.35)

Для LE мы получаем структуру кольца, представленную в явном виде в (5.36) и (5.37), где запись типа ху использована для обозна­чения

{(А|х), (В|у)}:

(5.36)

(5.37)

Замечание. Интересно сравнить кольцо (5.30) и (5.31) с булевым кольцом (5.3) и (5.4). Используем обозначения (5.30) и (5.31) для (5.3) и (5.4) и сравним их на рис. 5.14.

Pис. 5.14

Кольцо из примера (5.30) и (5.31) — это (см. левый рисунок) кольцо с операциями сложения и умножения по модулю 4 (чтобы убедиться в этом, достаточно положить с= 0, α = 1, β = 2 и γ = 3), а правый рисунок иллюстрирует по­строение булева кольца на множе­стве {e, α, β, γ }.

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

Перенесение свойств. После всего, что мы изложили в данном парагра­фе, легко доказать, что

L—обычный предпорядок LE— обычный предпорядок, (5.38)

L — обычный порядок LE — обычный порядок, (5.39)

L— нижняя полурешетка LE—нижняя полурешетка, (5.40)

L — верхняя полурешетка LE — верхняя полурешетка, (5.41)

L — решетка LE — решетка, (5.42)

L — кольцо LE — кольцо. (5.43)

Эти свойства следует добавить к тем, которые уже были определе­ны в (3.16)—( 3.18), помня, что любой ассоциативный для L закон * индуцирует ассоциативный закон для LE; аналогично, если закон