1 Кубенский А.А. Дискретная математика Глава 1. Множества и отношения Решетки Решетка – это множество M с определенными на нем двумя бинарными операциями и, такими что: 1.a a = a,a a = a 2.a b = b a,a b = b a идемпотентность коммутативность 3.(a b) c = a (b c),(a b) c = a (b c) ассоциативность 4.(a b) a = a, (a b) a = a поглощение Решетка дистрибутивна, если: 5.a (b с) = (a b) (b c), a (b c) = (a b) (a c) дистрибутивность Решетка ограничена, если в ней существуют элементы 0 и 1 такие, что: 6.0 a = 0,1 a = 1 ограниченность Ограниченная решетка называется решеткой с дополнением, если в ней для любого элемента a найдется элемент a' такой, что: 7.a a' = 0,a a' = 1

2 Кубенский А.А. Дискретная математика Глава 1. Множества и отношения. Свойства дополнения в дистрибутивной ограниченной решетке единственность: для данного элемента a существует единственный элемент a'; инволютивность: (a')' = a дополнительность: 1' = 0, 0' = 1 законы де Моргана: (a b)' = a' b', (a b)' = a' b' Если решетка дистрибутивна, то выполняются следующие свойства дополнения: Свойства нуля и единицы: 0 a = a, 1 a = a Действительно, 0 a = (0 a) a = (a 0) a = a, 1 a = (1 a) a = (a 1) a = a Единственность: пусть a' и a'' – два различных дополнения к a. Тогда a' = a' 0 = a' (a a'') = (a' a) (a' a'') = 1 (a' a'') = (a' a'') Аналогично a'' = a'' 0 = a'' (a a') = (a'' a) (a'' a') = 1 (a'' a') = (a' a'') Инволютивность: очевидна, поскольку a' a = 0, a' a = 1 Дополнительность: 1' = 1' 1 = 0; 0' = 0' 0 = 1 Законы де Моргана: Проверяем, что (a b) (a' b') = 1, (a b) (a' b') = 0, (a b) (a' b') = 1, (a b) (a' b') = 0 Например, (a b) (a' b') = (a b a') (a b b') = 1 1 = 1

3 Кубенский А.А. Дискретная математика Глава 1. Множества и отношения. Частичный порядок в решетке Введем отношение порядка на элементах решетки a b, если a b = a Это действительно отношение частичного порядка, так как: Это отношение рефлексивно: a a, так как a a = a Это отношение антисимметрично: если a b и b a, то a = a b = b a = b Это отношение транзитивно: если a b и b с, то a с = (a b) с = a (b с) = a b = a Пусть задано множество с нестрогим порядком, в котором для любых элементов a и b существуют их нижняя и верхняя грани inf(a, b) и sup(a, b) Тогда множество этих элементов образуют решетку относительно операций = inf, = sup Очевидно, что для любых двух элементов такой решетки существуют верхняя и нижняя грани относительно только что введенного отношения порядка : inf(a,b) = a b, sup(a,b) = a b Доказательство (для нижней грани): 1. (a b) b, поскольку (a b b) = (a b) и (a b) a, поскольку (a b a) = (a b) 2. Пусть существует c такое, что (a b) c, c a, c b. Тогда c = c a = (c b) a = a b Наоборот: Таким образом, имеем два равносильных определения решетки: определение через свойства заданных операций и, и определение решетки как частично упорядоченного множества, в котором для каждых двух элементов определены их верхняя и нижняя грань.

4 Кубенский А.А. Дискретная математика Глава 1. Множества и отношения. Булева алгебра Ограниченная дистрибутивная решетка с дополнением называется булевой алгеброй. Минимальная булева алгебра содержит всего два элемента 0 и 1. Операции решетки в этой алгебре принято обозначать символами и, а операцию дополнения – символом. Для булевой алгебры справедлива следующая таблица операций: ab a b a Булеан некоторого множества U – это булева алгебра относительно операций и. Еще пример. Пусть A p – множество всех простых чисел, не превосходящих p. Рассмотрим всевозможные произведения чисел из A p, в которые сомножители входят не более, чем по одному разу. Множество всех таких чисел образует решетку относительно операций НОД и НОК. Число 1 является нулем решетки, произведение всех чисел из A p – ее единицей. Очевидно, что это тоже булева алгебра.