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

Читатель должен сам подключиться к построению решетки произ­ведения относительно L1 и L2. Рассматривая (4.30) и (4.31), можно, например, написать

(4.34)

(4.35)

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

Следует указать на важный частный случай, когда L1 и L2 — пол­ностью упорядоченные множества; тогда L = L1 × L2 образует век­торную решетку.

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

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

(4.36)

(4.37)

Pис. 4.16

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

Pис. 4.17

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

На рис. 4.17 мы изобразили нижнюю (а) и верхнюю (б) полу­решетки, и, как можно заметить, целиком изображенное на рис. 4.16

упорядоченное множество не является ни нижней, ни верхней полу­решеткой.

Порядковая функция частично упорядоченного множества. Ранее

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

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

Рис. 4.18 Рис.4.19

Рис.4.20 .

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

1.—ассоциативность для *; (4.38)

—существование единицы е для *; (4.39) — существование обратного элемента для всех Хi; (4.40)

—коммутативность операции *; (4.41)

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

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

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

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

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

Рис. 4.21

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

Хi, Xj, Хk L

(4.45-4.46)

(4.47-4.48) (4.49-4.50)

(4.51-4.52)

(4.53)

(4.54)

(4.55)

(4.56)

(4.57)

(4.58)

(4.59)

(5.60-4.61)

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

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

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

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

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

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

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

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

Следовательно, множество LE само наделено структурой кольца и называется булевым кольцом. Можно показать, что в этом кольце, если Е={0, 1}, то соответствуют дизъюнктивной сумме ф, а — пересечению ∩ .

4.5. Обобщение понятия нечеткого подмножества

Сначала рассмотрим частные примеры.

Пример 1. Предположим, что

L= {0, α, β, 1}, (5.1)

Е = {А, В}. (5.2)

Предположим, также, что L имеет струк­туру булевой решетки (т. е. дистрибутивной и с дополнением), подобную той, которая пред - ∆ставлена на рис. 5.1.

Pис. 5.1

Для операций ∆ и результаты для L можно видеть на матрицах (5.3) и (5.4).

(5.3)

(5.4)

Исследуем свойства LE. Положим

(5 5)

(5.6)

(5.7)

(5.8)

Положим

(5 9) (5.10)

Поскольку L имеет структуру булевой решетки, то для операций ∆ и выполняются следующие свойства: ассоциативность, коммута­тивность, идемпотентность, поглощение, дистрибутивность ∆ относи­тельно и наоборот, существование единственного дополнения для каждого элемента L.

Теперь исследуем свойства LE. Легко видеть, чтоассоциатив­на, поскольку ассоциативна ∆. Аналогичноассоциативна в силу ассоциативности . Tаким же образом легко доказать коммутативность, идемпотентность и поглощение