Понятие булевой функции

Пусть U=U(X₁,X₂,…,X_n) – произвольная формула алгебры высказываний, содержащая n переменных. Оценка переменных такой формулы – это упорядоченная последовательность из 0 и 1 длины n, то есть n-мерный двоичный вектор. Каждой оценке переменных (x₁,x₂,…,x_n)∈{0,1}ⁿ однозначным образом сопоставляется значение истинности u∈{0,1} высказывания, полученного из формулы U после соответствующей подстановки. Таким образом, мы получаем соответствие (x₁,x₂,…,x_n)→u, задающее отображение f_U: {0,1}ⁿ→{0,1}, u=f_U(x₁,x₂,…,x_n). Такие отображения называют булевыми функциями. Непосредственно из определений вытекает, что формулы алгебры высказываний U=U(X₁,X₂,…,X_n) и V=V(X₁,X₂,…,X_n) равносильны в том и только том случае, когда функции f_U и f_V совпадают.

Булевы функции представляют интерес не только в связи с их «логическим» происхождением, но и сами по себе. Оттеняя это обстоятельство, введем следующие определения.

Переменные, пробегающие множество {0,1}, мы будем называть булевыми и обозначать буквами x, y, z, …, x₁, x₂, … . Функция от одной или нескольких булевых переменных, принимающая значение в множестве {0,1}, называется булевой.

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

x₁ x₂ x₃ f(x₁,x₂,x₃)

--------------------------------

0 0 0 1

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 1

1 0 1 1

1 1 0 0

1 1 1 1

Чтобы задать булеву функцию от трех переменных достаточно указать в подобной таблице произвольный столбец из 0 и 1 высоты 8 (по числу наборов значений аргументов), то есть двоичный вектор размерности 8. Число всевозможных таких столбцов равно 2⁸. Значит, и число различных булевых функций от трех переменных конечно и составляет 2⁸. В случае функций от n переменных число строк в таблице равно 2ⁿ , такова же и высота столбца, определяющего функцию. Следовательно, число булевых функций от n переменных равно . С увеличением числа переменных количество булевых функций быстро нарастает. Так, число булевых функций от одной переменной равно 4, от двух переменных – 16, от трех – 256, от четырех – 65536 и т. д. n22