Основные законы булевой алгебры

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

• отрицание (обозначается НЕ (NOT), черта над переменной (например, ), символ «»);

• логическое умножение (конъюнкция) (обозначается И (AND), &, );

• логическое сложение (дизъюнкция) (обозначается ИЛИ (OR), , +).

Для представления любой логической функции в виде формулы используются:

• символы основных операций отрицания, конъюнкции и дизъюнкции;

• буквы типа х, у, z, ... для обозначения переменных (включая буквы с индексами);

• константы 0 и 1;

• пара символов ( ), которые называются скобками.

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

Формулами булевой алгебры являются:

• булевы переменные х, у, z, ...;

• константы 0 и 1;

• выражения вида (АВ), (AB), , где А и В являются формулами.

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

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

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

Таблица 4

Основные законы булевой алгебры

Законы и правила	Дизъюнкция	Конъюнкция
1. Закон двойного отрицания
2. Закон коммутативности	х1х2 = х2х1	х1х2 = х2х1
3. Закон ассоциативности	х1(х2х3) = (х1х2)х3	х1(х2х3) = (х1х2)х3
4. Закон дистрибутивности	х1(х2х3) = х1х2х1х3	х1х2х3 = (х1х2)(х1х3)
5. Правила де-Моргана
6. Правила операций с константами 0 и 1
	х0 = х; х1 = 1	х0 = 0; х1 = х
7. Правила операций с переменной и ее инверсией
8. Закон поглощения	х1х1х2 = х1	х1(х1х2) = х1
9. Закон идемпотентности	хх…х = х	хх…х = х

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

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

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

.