Аксиоматика и свойства алгебры логики

Алгебру логики можно представить как множество логических переменных (т.е. таких переменных, каждая из которых может принимать значения из множества – в дальнейшем слово «логические» будем опускать) и двух констант 0 («ложь») и 1 («истина»), для всех элементов которого определено отношение эквивалентности (другие термины: равнозначность, тождественность), обозначаемое символом «=» (другие символы: «», «», «») и три основные операции: сложение («ИЛИ», объединение, дизъюнкция), обозначаемое символом «+» («»), умножение («И», пересечение, конъюнкция), обозначаемое символом «×» («», «&», отсутствие символа), отрицание («НЕ», инверсия), обозначаемое символом «–» («ù», «!»).

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

Для всех переменных отношение эквивалентности удовлетворяет следующим свойствам:

если то (симметричность);

если и , то (транзитивность).

Определения операций сложения и умножения приведены в табл. 1.1, определение операции отрицания – в табл. 1.2.

Таблица 1.1 Таблица 1.2

		+	×

Из табл. 1.1 видно, что сумма переменных равна 1, когда значение хотя бы одной переменной равно 1, а произведение равно 1, когда значения всех переменных равны 1.

Непосредственно из данных определений следуют все перечисленные свойства:

(нулевые константы);

(единичные константы);

(отрицание);

(двойное отрицание);

(идемпотентность);

(коммутативность);

(ассоциативность);

(дистрибутивность).

Докажем второе свойство дистрибутивности:

= [по первому свойству дистрибутивности] = = = [по второму свойству идемпотентности] = = [по первому свойству дистрибутивности и свойствам единичных констант] = = [аналогично] = = .

При доказательстве этого свойства дважды использовалось следующее тождество:

(поглощение).

Из первого свойства дистрибутивности и первого свойства отрицания следует

(склеивание).

Возможность перехода между операциями сложения и умножения определяется следующими законами:

(правила де Моргана).

Благодаря ассоциативности можно обобщить свойства идемпотентности на произвольное количество переменных:

.

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

Реализуя свойство склеивания для двух первых слагаемых, из данного выражения получаем:

Последовательно используя свойства поглощения и идемпотентности, можно записать:

Подставляя в наше выражение, получаем:

Попарно склеивая второе слагаемое с четвертым, а третье с пятым, окончательно получаем:

Докажем часто используемое в алгебре логики тождество:

Применяя свойства склеивания и идемпотентности, можно записать:

В результате получаем:

Заменяя везде в доказанном тождестве на , получаем:

В табл. 1.3 приведены некоторые дополнительные операции, представимые через операции сложения, умножения и отрицания.

Таблица 1.3

Название операции	Обозначение	Представление через операции «И», «ИЛИ», «НЕ»	Смысл
сумма по модулю 2 (исключающее “ИЛИ”			или , но не и одновременно
штрих Шеффера (антиконъюнкция)			не , или не
стрелка Пирса (антидизъюнкция)			ни , ни
следование (импликация)			или не , или и одновременно
эквивалентность (двойная импликация)			или не и не одновременно, или и одновременно
разность (запрет)			, но не

Рассмотрим некоторые свойства дополнительных операций.

Для суммы по модулю два легко доказать справедливость следующих соотношений:

Операции штрих Шеффера и стрелка Пирса являются универсальными, так как с их помощью можно выразить операции «И», «ИЛИ», «НЕ»: