Функции алгебры логики

Функцией алгебры логики переменных (функцией Буля или булевой функцией) называется функция переменных

,

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

Число различных булевых функций переменных равно . В частности, различных булевых функций одной переменной четыре, а различных булевых функций двух переменных шестнадцать. Перечислим эти функции.

Рассмотрим таблицу истинности всех различных булевых функций одной переменной:

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

.

Таблица истинности всех различных булевых функций двух переменных имеет вид:

Этим функциям соответствуют следующие формулы исчисления высказываний:

,

Каждой булевой функции можно сопоставить формулу алгебры высказываний. С этой целью введем обозначение

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

Произвольная булева функция двух переменных представима в виде:

.

Для краткости записи опустим символ конъюнкции: вместо будем писать :

.

Это обозначение совпадает и с содержанием этих операций: значение конъюнкции , на самом деле, совпадает со значением арифметической операции умножения .

Полагая , , , функцию можно представить следующим образом:

.

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