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

Выше рассматривались алгебры, т.е. множества, на которых заданы операции [19].

Множества, на которых кроме операций заданы отношения, называются алгебраическими системами [19]. Таким образом, алгебры можно считать частным случаем алгебраических систем. Другим частным случаем алгебраических систем являются модели – множества, на которых заданы только отношения.

Рассмотрим пример алгебраической системы, который наиболее часто встречается в теоретической алгебре и ее применениях [19]. Этот пример – решетка.

Рассмотрим алгебраическую систему из множества М, отношения порядка (будем обозначать £) и некоторых операций. Говорят, что множество М линейно упорядочено, если любые два элемента находятся в отношении упорядоченности, иначе – частично упорядочено. Для элементов а и b из М их верхней гранью (мажорантой) называется любой элемент сÎ М такой, что с³ а, с³ b, а их нижней гранью (минорантой) – любой элемент dÎ М такой, что d£ а, d£ b. В общем случае для некоторых элементов а и b верхняя или нижняя грань может не существовать или быть не единственной, причем различные верхние (или нижние) грани могут быть несравнимыми. Во множестве верхних и нижних границ вводится понятие точной верхней (нижней) границы множества.

Такая верхняя граница множества обозначается supМ («супремум»), такая нижняя граница – обозначается infМ («инфинум»).

Частично упорядоченное множество называется решеткой, если у каждой пары его элементов а, b необходимо имеются единственная точная верхняя граница sup(а, b) или пересечение аÙ b и точная нижняя граница inf(а, b) или объединение аÚ b. Здесь операции Ù, Ú пока понимаются как абстрактные операции алгебраической системы и отличаются от теоретико-множественных операций объединения и пересечения. Для алгебры множеств Ù соответствует I, Ú соответствует U.

Рассмотрим пример частично упорядоченного множества – диаграмму (решетку) Хассе [9], известную с конца XIX века и применяемую в генеалогии для задания родства (рис. 8).

Рис. 8. Диаграмма (решетка) Хассэ для множества всех

подмножеств универсального множества I={y, x, z}

На рис. 8 множество всех подмножеств данного множества упорядочено по отношению включения, а операции объединения и пересечения элементов связаны дистрибутивными законами. Нулем и единицей частично упорядоченного множества называются, соответственно, его наименьший и наибольший элементы, обычно применяются традиционные обозначения 0, 1.

Так, на рис. 8 нулем и единицей будут, соответственно, пустое множество Æ и данное множество (I).

На решетке Хассе обычно не изображаются линии транзитивности и рефлексивности.

В частично упорядоченных множествах с нулем и единицей, вводится операция дополнения элементов.

Элементы а и в частично упорядоченного множества с нулем 0 и единицей 1 называются дополнительными друг для друга, если их пересечение равно нулевому элементу 0, а объединение дает единичный элемент 1: аÙ b=0, аÚ b=1.

Так, {y}I{x, z}=Æ, {y}U{x, z}=I на рис. 8.

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

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

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