5. Алгебра Буля. Основные законы.

Равносильности 3 – ей группы говорят о том ,что алгебра логики обладает коммутативными и ассоциативными законами относительно операций конъюнкции и дизъюнкции и дизъюнктивным законом конъюнкции относительно дизъюнкции, эти же законы имеют место и в алгебре чисел. Поэтому над формулами алгебры логики можно производить те же преобразования, которые производятся в алгебре чисел (раскрытие скобок, заключение в скобки, вынесение за скобки общего множителя).

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

Рассмотрим непустое множество М элементов любой природы {p, q, r, …}, в котором определены отношение “=” (равно) и три операции: “+” (сложение), (умножение) и “ – “ (отрицание), подчиняющиеся следующим аксиомам:

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

p + q = q + p, .

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

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

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

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

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

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

Такое множество М называется булевой алгеброй.

Если под основными элементами p, q, r, … подразумевать высказывания, под операциями “+”, , “ – “ дизъюнкцию, конъюнкцию, отрицание соответственно, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей 1, 2 и 3 групп, все аксиомы булевой алгебры выполняются.

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

Алгебра логики является интерпретацией булевой алгебры. Алгебра Буля имеет и другие интерпретации. Например, если под основными элементами p, q, r, …множества М подразумевать множества под операциями “+”, , “ – “ объединение, пересечение, дополнение соответственно, а под знаком равенства – знак равенства множеств, в котором все аксиомы алгебры Буля выполняются.

Среди обычных интерпретаций алгебры Буля имеются интерпретация и технического характера.

6. Булевы функции

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

Например, формула является функцией трех переменных f (p, q, r). Особенностью этой функции является то обстоятельство, что ее аргументы принимают одно из двух значений: 0 или 1, и при этом функция может принимать одно из двух значений: 0 или 1.

Определение. Функцией алгебры логики n переменных или функцией Буля называется функция n переменных, где каждая переменная принимает два значения 0 и 1, и при этом функция может принимать только одно из двух значений: 0 или 1.

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

Выясним, каково число функций n переменных. Очевидно, каждую функцию алгебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности, которая будет содержать строк. Следовательно, каждая функция n переменных принимает значений, состоящих из нулей и единиц. Таким образом, функция n переменных полностью определяется набором значений из нулей и единиц, длины равно . Значит, число различных функций алгебры логики n переменных равно .