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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так, { y } ∩ {х, z } = 0, {у} ∪ {х, z } = I на рис. 8.

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

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

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

Задание множеств конституентами

Формула алгебры множеств, представляющая собой пересечение, в которое входят по одному разу все множества (со знаками дополнения или без дополнений) на данном универсуме, называется конституентой единицы. Формула, представляющая собой объединение, в которое входят по одному разу все множества (со знаками дополнения или без дополнений) на данном универсуме, называется конституентой нуля. Каждое множество, за исключением пустого, может быть задано объединением конституент единицы. Каждое множество, за исключением универсального, может быть задано пересечением конституент нуля. Рассмотрим задание множества путем указания его конституент единицы. Пусть на некотором универсуме рассматриваются два взаимно пересекающихся множества: А и В.

Зададим их графически с помощью диаграмм Эйлера (рис. 9).

Рис. 9. Диаграмма Эйлера для двух взаимно пересекающихся
множеств А и В на универсуме I

Тогда каждый из четырех сегментов (четырех «кусочков») этой диаграммы может быть закодирован конституентой, содержащей символы А и В:

В таком случае заданное множество можно закодировать, двоичным кодом в соответствии с тем, входят ли в него указанные конституенты (табл. 4):

Таблица 4

Задание множества А двоичным числом

Множество А закодировано двоичным числом 1100. Этому двоичному числу соответствует десятичное число 12.

При таком задании множеств легко выполняются операции над ними. Например, получим пересечение множества № 12 и множества № 5. Результатом будет множество № 4. Действительно, результат пересечения — множество, в котором при его двоичном представлении имеются единицы в разрядах, соответствующих совпадениям единиц в исходных множествах (табл. 5).

Таблица 5

⇐ Предыдущая 5 6 7 8 91011 12 13 14 Следующая ⇒