Булевы функции от $n$ переменных

Дадим два эквивалентных определения булевой функции.

Определение 1. Функцию $f (x_1, x_2, … , x_n)$ назовем булевой, если она сама и ее аргументы принимают значения 0 и 1.

Определение 2. Булевой функцией $f(x_1, x_2, … , x_n)$ назовем однозначное отображение булева пространства $B^n$ в булево множество $B$, то есть $f : B^n\rightarrow B$.

Пример. Булева функция двух аргументов, принимающая на наборах $01$ и $11$ значение $0$, а на наборах $00$ и $10$ значение $1$:

Определение. Булевы функции равны, $f_1(x_1, …, x_n) = f_2(x_1, …, x_n)$, если на одинаковых наборах они принимают одинаковые значения.

Число булевых функций от $n$ переменных равно $2^ { 2^ { n } } $

Пример 1. Число булевых функций от $n = 1$ переменной равно $2^ { 2^ { n } } = 2^ { 2^ { 1 } } = 2^ { 2 } = 4$. Это $0, 1, x$ и $\bar { x } $

Пример 2. Число булевых функций от $n = 2$ переменных равно $2^ { 2^ { n } } = 2^ { 2^ { 2 } } = 2^ { 4 } = 16$. Они все указаны в таблице

$x_1$	$x_2$	$f_1$	$f_2$	$f_3$	$f_4$	$f_5$	$f_6$	$f_7$	$f_8$	$f_9$	$f_ { 10 } $	$f_ { 11 } $	$f_ { 12 } $	$f_ { 13 } $	$f_ { 14 } $	$f_ { 15 } $	$f_ { 16 } $
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

У некоторых функций есть специальные названия.

$f_1(x_1, x_2) = 0$ - тождественный нуль;

$f_2(x_1, x_2) = x_1\And x_2$ - конъюнкция. Очень часто знак $\And $ опускают и пишут просто $x_1x_2$;

$f_7(x_1, x_2) = x_1\oplus x_2$ - сложение по модулю 2;

$f_8(x_1, x_2) = x_1\vee x_2$ - дезъюнкция;

$f_9(x_1, x_2) = x_1\downarrow x_2$ - стрелка Пирса;

$f_ { 10 } (x_1, x_2) = x_1\equiv x_2$ - эквиваленция;

$f_ { 14 } (x_1, x_2) = x_1\rightarrow x_2$ - импликация;

$f_ { 15 } (x_1, x_2) = x_1|x_2$ - штрих Шеффера;

$f_ { 16 } (x_1, x_2) = 1$ - тождественная единица.