Алгебраические системы. Решетки

Выше рассматривались алгебры, т.е. множества, на которых заданы операции [19].
Множества, на которых кроме операций заданы отношения, называются алгебраическими системами [19]. Таким образом, алгебры можно считать частным случаем алгебраических систем. Другим частным случаем алгебраических систем являются модели – множества, на которых заданы только отношения.
Рассмотрим пример алгебраической системы, который наиболее часто встречается в теоретической алгебре и ее применениях [19]. Этот пример – решетка.
Рассмотрим алгебраическую систему из множества М, отношения по-рядка (будем обозначать ) и некоторых операций. Говорят, что множество М линейно упорядочено, если любые два элемента находятся в отношении упорядоченности, иначе – частично упорядочено. Для элементов а и b из М их верхней гранью (мажорантой) называется любой элемент сМ такой, что са, сb, а их нижней гранью (минорантой) – любой элемент dМ такой, что dа, db. В общем случае для некоторых элементов а и b верхняя или нижняя грань может не существовать или быть не единственной, причем различные верхние (или нижние) грани могут быть несравнимыми. Во множестве верхних и нижних границ вводится понятие точной верхней (нижней) границы множества.
Такая верхняя граница множества обозначается supМ («супремум»), такая нижняя граница – обозначается infМ («инфинум»).
Частично упорядоченное множество называется решеткой, если у каждой пары его элементов а,b необходимо имеются единственная точная верхняя граница sup(а,b) или пересечение аb и точная нижняя граница inf(а,b) или объединение аb. Здесь операции , пока понимаются как абстрактные операции алгебраической системы и отличаются от теоретико-множественных операций объединения и пересечения. Для алгебры множеств  соответствует ,  соответствует .
Рассмотрим пример частично упорядоченного множества – диаграмму (решетку) Хассе [9], известную с конца XIX века и применяемую в генеалогии для задания родства (рис. 8).

Рис. 8. Диаграмма (решетка) Хассэ для множества всех
подмножеств универсального множества I={y,x,z}

На рис. 8 множество всех подмножеств данного множества упорядочено по отношению включения, а операции объединения и пересечения элементов связаны дистрибутивными законами. Нулем и единицей частично упорядоченного множества называются, соответственно, его наименьший и наибольший элементы, обычно применяются традиционные обозначения 0,1.
Так, на рис. 8 нулем и единицей будут, соответственно, пустое множество  и данное множество (I).
На решетке Хассе обычно не изображаются линии транзитивности и рефлексивности.
В частично упорядоченных множествах с нулем и единицей, вводится операция дополнения элементов.
Элементы а и в частично упорядоченного множества с нулем 0 и еди-ницей 1 называются дополнительными друг для друга, если их пересече-ние равно нулевому элементу 0, а объединение дает единичный элемент 1: аb=0, аb=1.
Так, {y}{x,z}=, {y}{x,z}=I на рис. 8.
Дистрибутивная решетка с отличными друг от друга нулем и едини-цей, в которой каждый элемент имеет дополнение, называется булевой алгеброй.
Пример булевой алгебры – совокупность множества всех подмножеств данного множества и теоретико-множественных операций объединения, пересечения и дополнения, т.е. алгебра Кантора (алгебра множеств), рассмотренная выше. Операции объединения и пересечения являются бинарными (двухместными), а операция дополнения – унар-ной (одноместной).
Далее мы рассмотрим другой пример булевой алгебры – булеву алгебру логических (переключательных) функций.