Т. А. Сливина математическая логика и теория алгоритмов

§ 3. Алгебра Буля. Функции Буля. Представление произвольной
функции алгебры логики в виде формулы алгебры логики


Рассмотрим непустое множество М элементов любой природы {x, y, z, …}, в котором определены отношение «=» и три операции «+», «∙» и «–» (отрицание), подчиняющиеся следующим аксиомам:

Коммутативные законы

х + y = y + x,
x ∙ y = y ∙ x.

Ассоциативные законы

х + (y + z) = (x + y) + z,
x ∙ (y ∙ z) = (x ∙ y) ∙ z.

Дистрибутивные законы

(x + y) ∙ z = (x ∙ z) + (y ∙ z),
(x ∙ y) + z = (x + z) ∙ (y + z).

Законы идемпотентности

х + x = x,
х ∙ x = x.

Закон двойного отрицания

Законы де-Моргана

Законы поглощения

х + (y ∙ x) = x,
х ∙ (у + x) = x.
Такое множество М называется булевой алгеброй.
Если под основными элементами x, y, z, … подразумевать высказывания, под операциями «+», «∙» и «–» дизьюнкцию, коньюнкцию и отрицание, а знак равенства рассматривать как знак равносильности, то как следует из равносильностей 1-ой, 2-ой и 3-ей групп, все аксиомы булевой алгебры выполняются.
Интерпритацией называется соответствие переменных объектов из некоторого множества и знаков операций – операциям, при котором будут выполняться заданные аксиомы.


Пример.
1) алгебра логики высказываний является интерпретацией булевой алгебры (x, y, z, … – высказывания и операции «=», «+», «∙», «–», соответствующие – равносильности, дизьюнкции, коньюнкции, отрицанию);
2) алгебра множеств – также является интерпретацией булевой алгебры
(x, y, z, … – множества и операции «=», «+», «∙», «–», соответствующие равенству множеств, объединению, пересечению и дополнению множеств).
Среди различных интерпретаций булевой алгебры имеются интерпретации технического характера в области современной автоматики (релейно-контактные схемы).
Как уже отмечалось, значение формулы алгебры логики высказываний полностью зависит от значений входящих в эту формулу высказываний. Поэтому формула алгебры логики высказываний является функцией входящих в нее элементарных высказываний.


Пример.
Формула ( ) является функцией трех переменных f (x, y, z). Особенность этой функции состоит в том, что ее переменные принимают – лишь два значения 0 и 1, при этом значение функции тоже может быть только 0 и 1.
Функцией Буля n переменных называется функция, где каждая переменная принимает два значения 0 и 1, при этом функция может принимать только одно из двух значений 0 или 1.
Замечание. Тождественно ложные и тождественно истинные формулы представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию.
Каждая функция алгебры логики высказываний также как и формула задается таблицей истинности, которая будет содержать 2ⁿ строк. А число различных функций n переменных будет равно
Выпишем все функции одной и двух переменных.
Таблица истинности для различных функций одной переменной имеет следующий вид:

x

f1(x)

f2(x)