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

Выше рассматривались алгебры, т.е. множества, на которых заданы операции [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.

Дистрибутивная решетка с отличными друг от друга нулем и единицей, в которой каждый элемент имеет дополнение, называется булевой алгеброй.

Пример булевой алгебры – совокупность множества всех подмножеств данного множества и теоретико-множественных операций объединения, пересечения и дополнения, т.е. алгебра Кантора (алгебра множеств), рассмотренная выше. Операции объединения и пересечения являются бинарными (двухместными), а операция дополнения – унарной (одноместной).

Далее мы рассмотрим другой пример булевой алгебры – булеву алгебру логических (переключательных) функций.