Труды КНЦ вып.7 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып.2 4/2011(7))

(знак <=> здесь означает "равносильно"). Далее приведем формальное опре­ деление решетки через операции О , (в некоторых источниках эти операции обозначаются, как л и v соответственно. Алгебра <В, П, и > , где В - непустое множество элементов решетки, а П , и - двухместные операции ( пересечение и объединение), называется решеткой, если для всех a, b, с из B выполняются следующие требования: 1) замкнутость : множество В содержит а ГлЬ, a U 6; 2) свойства идемпотентности : а гл а = a, a U а = а; 3) коммутативные законы, а Г\Ь = b П а, а U b = Ь U а; 4) ассоциативные законы, а П ф П с) = (а П Ь) П с, a U {b U с) = (а U b) U с; 5) законы поглощения : a (а Г\ Ь) = а, а Г\ (a 'U Ь) = а . Решетка называется дистрибутивной, если соблюдается хотя бы один из следующих законов: 6) законы дистрибутивности : а П ф U с) = (а П 6) U (а П с), а U (6 П с) = (а U с) П (а и с). Решетка называется ограниченной, если: 7) 0 е В {нуль или нижняя грань решетки) и 1 е В (единица или верхняя грань решетки) такие, что для. а е В выполняется ОП я = 0, 1 и а = 1 , a u O = a, а Г \ \ = а. Решетки сами по себе часто встречаются в разных прикладных задачах, но еще важнее то, что понятие решетки непосредственно приводит нас к понятию булевой алгебры, значение которой для основ современной двоичной компьютерной техники трудно переоценить. Алгебра <В, О, >, где есть одноместная операция ( дополнение ), называется булевой алгеброй (булевой решеткой), если в B, помимо условий 1 - 7, выполняются следующее условие: 8 ) Для каждого элемента а множество B содержит элемент а (дополнение элемента а) такой, что a U а = 1 , а П а = 0 . Другими словами, булева алгебра является дистрибутивной ограниченной решеткой, в которой для каждого элемента существует дополнение. Большой список литературы по различным вариантам аксиоматических определений булевой алгебры приведен в [ 8 ]. К булевым алгебрам относятся: 1) алгебра множеств (алгебра Кантора, алгебра классов, алгебра подмножеств, алгебра частей множества) <Р{М), ГЛ, LJ. >, причем М (универсум) - верхняя грань, 0 - нижняя грань, cz - естественный частичный порядок, P(M) - булеан (множество всех подмножеств) множества M ; 2) алгебра Буля (алгебра логики, алгебра высказываний, алгебра В2) <{ 0 , 1 }, л , v , —I >, причем 1 - верхняя грань, 0 - нижняя грань. Своеобразным эталоном в классе булевых алгебр является алгебра множеств, о чем свидетельствует следующая теорема. 114