Булевой алгеброй в узком смысле называется множество {0, 1} с двумя бинарными и одной унарной операцией

{ 0, 1} ; Ъ, &,` х ; m = (2, 2, 1).

Дизъюнкция Ъ (операция "ИЛИ") иногда называется логическим сложением, что неверно, так как она мало похожа на обычное сложение. Поэтому не следует заменять знак дизъюнкции на знак “плюс”. Дизъюнкция двух и большего числа аргументов обращается в нуль только в том случае, когда все аргументы имеют значение нуль. В противном случае она равна единице.

Инверсия ` х (операция "НЕ х") выполняется одновременно над всем выражением, записанным под чертой, как унарная операция.

Свойства операций булевой алгебры, как и любой конечной алгебры, можно выразить с помощью таблиц Кэли (табл. 8.1, 8.2, 8.3). Ввиду связи булевой алгебры с математической логикой, о чем будет сказано дальше, эти таблицы издавна принято называть таблицами истинности. Для удобства пользования такими таблицами в них включают переменную х и инверсию ` х.

А₁ : ассоциативность дизьюнкции и конъюнкции

aЪ (bЪ c) = (aЪ b)Ъ c; a(bc) = (ab)c;

А₂ : коммутативность дизъюнкции и конъюнкции

aЪ b = bЪ a; ab = ba;

А₃ : существование нейтральных элементов для дизъюнкции и конъюнкции

aЪ 0 = 0Ъ a = a; a&1 = 1& a = a;

А₅ : дистрибутивность конъюнкции относительно дизъюнкции

a(bЪ c) = abЪ ac.

А₆ : закон исключенного третьего (вместо аксиомы о существовании противоположного элемента) а Ъ `а = 1;

А₇ : закон противоречия (вместо аксиомы о существовании обратного элемента)  а &`а = 0;

А₈ : дистрибутивность дизьюнкции относительно конъюнкции

аЪ bc = (aЪ b)(aЪ c);

А₉ : замкнутость множества { 0, 1} относительно инверсии: `0 = 1; `1 = 0.

Исходя из этих аксиом, можно вывести как теоремы некоторые удобные для практического применения правила. Для примера докажем правило: х&0 = 0 (конъюнкция любой переменной с нулем равна нулю). Запишем левую часть доказываемого правила: х & 0 = ... ; ввиду нейтральности 0 для дизъюнкции перепишем так: х & 0 Ъ 0=…; согласно закона противоречия заменим нуль: х & 0 Ъ х & `х=… Ввиду дистрибутивности конъюнкции относительно дизъюнкции вынесем переменную х за скобки: ... = х ( х Ъ 0) = ... ; далее, ввиду нейтральности нуля для дизъюнкции, преобразуем к виду: ... = х & `х = ... ; наконец, вследствие закона противоречия получим: ... = 0. Примерно таким же путем можно доказать и другие правила, применяемые при практической работе с булевой алгеброй:

аЪ а = а; а & а = а;

а Ъ ab = a; a(aЪ b) = a;

-правило склеивания

abЪ a` b = a; (aЪ b)(aЪ ` b) = a;

С другой стороны, булева алгебра связана, во всяком случае, исторически, с логикой. Логика - древняя наука, рассматривающая категории истинности, выводимые путем рассуждений из некоторых известных предпосылок. Классическая логика двузначна, она признает только две категории: истиннно (1) или ложно (0). В своем развитии она часто наталкивалась на противоречия, которые не удавалось разрешить путем рассуждений. Подобные противоречия назывались парадоксами. Например: "Некто заявляет, что он лжет. Если он при этом говорит правду, то выходит, что он солгал. Если же он действительно лжет, то выходит, что он сказал правду". Логика научилась избавляться от парадоксов только после создания специального формального аппарата, называемого исчислением высказываний. Это стало возможным лишь после изобретения булевой алгебры (Джордж Буль 1848 г.).

Булевой алгеброй в широком смысле или алгеброй логики называют множество {0, 1} с любыми сигнатурами, способными заменить сигнатуру (Ъ , &, ` х ). В частности это: исчисление Гильберта с сигнатурой (® , ` х ), алгебра Жегалкина с операциями (Е , &, 0, 1) и др. Операция а ® b (импликация) равна нулю только в том случае, если а = 1, b = 0. Она выражает рассуждение: "Если а - истинно, то должно быть истинно и b", или : "Истинность а влечет истинность b". Равенство нулю результата операции а ® b означает ошибочность этого рассуждения при а = 1 и b = 0.

f(a,b,c,d) = abc` d Ъ a` b` cd Ъ abcd.

СДНФ может быть упрощена до минимальной ДНФ, представляющей интерес для последующей аппаратной реализации. Минимальная ДНФ, равносильная первоначальному представлению функции, тоже состоит из элементарных конъюнкций, соединенных знаком Ъ , но теперь такие члены содержат наименьшее возможное количество букв, да и число членов тоже минимально.

Заметим, что применяемые в булевой алгебре равенства имеют мало общего с равенствами, используемыми в обычной алгебре. В обычной алгебре они обычно выражают уравнения. Например, мы приравниваем двучлен bx + c нулю, а затем отыскиваем корень уравнения bx + с = 0, т.е. такое значение переменной х, которое превращает уравнение в тождество. Можно сказать, что, составляя уравнение, мы тем самым неявно задаем х. Неявное задание функций типично для обычной алгебры. Уравнение

x²/a² + y²/b² + z²/c² = 1

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

В булевой алгебре это невозможно. Нельзя, например, разрешить равенство (а Ъ b)& c = 1 относительно переменной а. Из данного выражения вытекает только, что с = 1 и, кроме того, либо а, либо b равно единице, либо и то и другое вместе.

aЪ b = c; (aЪ b) Ъ 1 = c Ъ 1; 1 = 1.

0Ъ 0 = 0 на 0 Е 0Е 0& 0 = 0,

0Ъ 1 = 1 на 0 Е 1Е 0&1 = 1,

1Ъ 0 = 1 на 1Е 0Е 1&0 = 1,

1Ъ 1 = 1 на 1Е 1Е 1&1 = 1.

В общем виде: a Ъ b = a Е b Е a & b; ` x = x Е 1.

Таблица 8.5

Таблицы Кэли (табл. 8.4 и 8.5) для операций Е и & после проделанной замены показывают наличие коммутативной аддитивной группы и мультипликативной полугруппы с единицей. Итак, булева алгебра (в широком смысле) оказалась коммутативным кольцом с единицей, тогда, как алгебра действительных чисел является полем. Именно отсутствие обратного элемента для мультипликативной операции делает булеву алгебру столь непохожей на обычную.

Содержание