Булевы функции от 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$. Они все указаны в таблице

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

$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$ - тождественная единица.