Дискретно-непрерывная математика (стр. 28 )

подмножества H, если h < х для всехВерхняя граница х

подмножества H называется его верхней гранью или супремом, если для любой верхней границы у подмножества Н. Это записывается через х = sup H или Понятие нижней границы

и инфимума определяется аналогично (двойственным образом) и инфимум записывается через inf Н или

Ч. у. множество называется решеткой, если для всех

существуют Решетка L называется

полной, если существуют для любого подмножества

Приведем два важных свойства ч. у. множеств: 1) линейно упорядоченное множество с sup и inf образует (дистрибутивную) решетку; 2) пусть есть множество всех подмножеств

множества Е, упорядоченное отношением включения Тогда есть (булева) решетка.

Однако во многих случаях предпочтительней охарактеризовать решетку как алгебру Тогда все понятия и

методы универсальной алгебры были бы применимы к решеткам. В этом случае частичный порядок ≤ вводится так: означает

Непустое множество L с двумя бинарными операциями на L называется решеткой, если L удовлетворяет следующим тож­дествам:

(Заметим, что пара тождеств (I) выводима из остальных.)

Обратим внимание, что единственными аксиомами, связы­вающими верхнюю полурешеткус нижней полурешеткой являются аксиомы поглощения (IV). Непустое множество L называется квази-решеткой [Plonka 1967], если выполняются только тождества

(I) - (III).

Решетка L называется дистрибутивной, если выполняются законы дистрибутивности:

(Один из законов дистрибутивности выводим из остальных тождеств.)

Дистрибутивные решетки лежат в основе большинства хорошо известных многозначных логик. Специально дистрибутивным решеткам посвящена монография [Balbes and Dwinger 1974].

Дистрибутивные решетки L называются решетками Де Моргана [Moisil 1935], или дистрибутивными решетками с инволюцией {distributive i-lattices) [Kahnan 1958], если для одноместной операции ~ выполняются тождества

Решетка L с двумя нульарными операциями 0 и 1 называется ограниченной:

Ограниченные решетки иногда называются алгебрами.

( Вопрос здесь чисто терминологтческий, поскольку решетка есть алгебра с двумя бинарными операциями, которые удовлетворяют тождествам (I) - (IV). Тем не менее, Г. Гретцер [Гретцер 1982] вводит это различие.)

Соот­ветственно ограниченные дистрибутивные решетки с отрицанием Де Моргана (тождества VI - VIII) называются алгебрами Де Моргана {Balbes and Dwinger 1974]. Алгебры Де Моргана (решетки Де Моргана), в которой операция ~ удовлетворяет условию

называются алгебрами Клини (решетками Клини) [Kahnan 1958].

О характеристическом тождестве, превращающем алгебру де Моргана в алгебру Клини, см. ниже в разделе 9.2. Условие (закон) Клини является довольно-таки сильным свойством и не имеет места, например, в четырехзначной логике Белнапа (см. ниже раздел 5.4.4).

4.4.1. Булевы алгебры

В ограниченной решетке L элемент у называется дополнением х, если В этом случае элемент у обозначают ~х.

Булевой алгеброй называется дистрибутивная решетка с допол­нениями. Можно показать, что в булевой решетке каждый элемент имеет единственное дополнение. Имеется большое число различных (эквивалентных) систем тождеств, определяющих класс булевых алгебр.

Например, алгебра называется булевой

алгеброй, если есть ограниченная дистрибутивная

решетка и выполняются следующие два тождества для операции дополнения:

и

Понятно, что булева алгебра является также алгеброй де Мор­гана и Клини, поскольку все условия для последних выполняются в булевой алгебре.

Примеры. 1) Алгебра классических истинностных значений. Двухэлементная структура с

операциями, определенными посредством истинностных таблиц, является булевой алгеброй. Другими словами, алгебра является простейшей моделью булевой алгебры,

2) Алгебра подмножеств. Пусть есть множество всех

подмножеств некоторого множества U. Для определим —X как дополнение U\X множества X, а для X и Y из пусть обозначает обычное теоретико-множественное

объединение множеств X и Y, а обозначает теоретико-

множественное пересечение множеств Х и Y. Тогда <

оказывается булевой алгеброй. Роль 0 играет пустое множество , а 1 есть U.

Классическим и одним из наиболее важных результатов в теории булевых алгебр стала Теорема представления Стоуна

[Stone 1936]: Любая булева алгебра изоморфна алгебре подмножеств подходящего множества.

Таким образом, булевы алгебры полностью сводятся к алгебрам подмножеств. Например, для конечных булевых алгебр: если есть любая булева алгебра, то

существует определенное множество U и множество В всех подмножеств U, замкнутое относительно булевых операций, такое, что алгебра изоморфна булевой алгебре

Другая теорема представления утверждает: каждая булева алгебра изоморфна подалгебре прямого произведения двухэле­ментной булевой алгебры или в другой формулировке: каждая булева алгебра изоморфна подпрямому произведению двухэле­ментной булевой алгебры

Алгебры Буля, явившись результатом исследований Г. Буля в области законов правильных рассуждений (1847 г.), нашли самое широкое применение в логико-математических исследованиях, в области инженерии контактно-релейных схем, компьютерных наук, аксиоматической теории множеств, теории моделей и в других областях науки и математики. Хорошее введение в теорию булевых алгебр имеется в [Вwris and Sankappanavar 1981]. См. также [Владимиров 1969]. Популярное изложение имеется в [Яглом 1980], где рассматриваются также конечные булевы алгебры. Имеется трехтомный справочник по булевым алгебрам [Mcw/c (ed), 1989].

4.4.2. Другие "логические" алгебры

Особое место в исследовании многозначных логик занимают алгебры Гейтинга. Пусть L - решетка с 0, тогда элемент называется псевдодополнением элемента если и

влечет за собой Любой элемент не может иметь

более одного псевдодополнения. Обобщение понятия псевдо­дополнения ведет к понятию относительного псевдодополнения. Пусть L - непустое множество и Элемент называется