Абстрактное определение булевых алгебр

 

Определение.Множество элементов B с заданным на нем двуместными операциями Ù и Ú (конъюнкцией и дизъюнкцией) и одноместной операцией Ø (отрицанием) называется булевой алгеброй, если выполнены следующие аксиомы (f, g, h - произвольные элементы множества):

fÙg = gÙf, fÚg = gÚf (коммутативность);

(fÙg)Ùh = fÙ(gÙh), (fÚg)Úh = fÚ(gÚh) (ассоциативность);

fÙf = f, fÚf = f (идемпотентность);

fÙ(gÚf) = f, fÚ(gÙf) = f (законы поглощения);

fÙ(gÚh) = (fÙg)Ú(fÙh), fÚ(gÙh) = (fÚg)Ù(fÚh) (дистрибутивность);

Ø(Øf) = f (закон инволюции);

Ø(fÙg) = Øf Ú Øg, Ø(fÚg) = Øf Ù Øg (законы де Моргана);

fÙ(gÚØg) = f, fÚ(gÙØg) = f (законы нейтральности).

Из перечисленных законов можно вывести, что для произвольных f, g справедливы равенства fÙØf = gÙØg и fÚØf = gÚØg. Например, в силу законов нейтральности и коммутативности имеем

fÙØf = (fÙØf)Ú(gÙØg) =(gÙØg)Ú(fÙØf) = gÙØg.

Если обозначить fÙØf через Î и fÚØf через Ë, то выполняются равенства

ØË =Î , ØÎ = Ë ,

fÙË = f, fÙÎ = Î ,

fÚË = Ë , fÚÎ = f.

Булева алгебра называется вырожденной, если Î и Ë совпадают; в таком случае ввиду равенств f = fÙË = fÙÎ = Î она не содержит никаких других элементов, а значит состоит ровно из одного элемента. Всякая невырожденная булева алгебра - а только такие и будут рассматриваться в дальнейшем - содержит два нейтральных элемента: Î (нулевой элемент) и Ë (единичный элемент).

Из fÙg = Ë следует, что f = g = Ë . Действительно, f = fÚ(fÙg) = fÚË = Ë . Этот факт называют неразложимостью нейтрального элемента Ë.

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

К счастью, это не так. Сейчас укажем некоторые модели - конкретные примеры булевых алгебр.

Двоичная модель

Наиболее простая из булевых алгебр ( и вместе с тем одна из наиболее важных для компьютерной науки) содержит только два (нейтральных) элемента и операции на ней вводятся с помощью следующих таблиц значений.

 

Ù	Ë	Î
Ë	Ë	Î
Î	Î	Î

 

Ú	Ë	Î
Ë	Ë	Ë
Î	Ë	Î

 

	Ë	Î
Ø	Î	Ë