Булева функцыя

Булева функцыя — гэта функцыя, якая працуе з лікамі з мноства двух аб’ектаў, звычайна $B=\{0,1\}$.

Адметным для такіх функцый з’яўляецца тое, што іх агульная колькасць заўсёды канцатковая і залежыць ад колькасці аргументаў функцыі. Але гэта не значыць што іх мала, наадварот, колькасць розных функцый залежыць ад колькасці аргументаў $n$ як $2^{2^{n}}$.

Прыклады

Розных булевых функцый без аргументаў існуе $2^{2^{0}}=2$, вось яны:

1. Выхад заўсёды 0. Звычайна запісваецца проста $0$.
2. Выхад заўсёды 1. Звычайна запісваецца проста $1$.

Для аднаго аргумента $x$ можна пабудаваць $2^{2^{1}}=4$ функцыі:

1. $0$.
2. Выхад паўтарае значэнне аргумента: калі аргумент 0, то выхад 0, калі аргумент 1 то выхад 1. Запісвацца як $x$.
3. Выхад адмаўляе аргумент: калі аргумент 0, то выхад 1, калі аргумент 1 то выхад 0. Звычайна запісвацца як $-x$.
4. $1$.

Для двух аргументаў $(x,y)$ існуе $2^{2^{2}}=16$ функцый. Іх зручна пералічыць у выглядзе табліцы:

$f(x,y)$

$\arg x$	$\arg y$	$0$	$-(x+y)$	$x*-y$	$-y$	$-x*y$	$-x$	$x*-y+-x*y$	$-(x*y)$	$x*y$	$-x*-y+x*y$	$x$	$-(-x*y)$	$y$	$-(x*-y)$	$x+y$	$1$
0	0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

Для трох аргументаў $2^{2^{3}}=256$ функцый. Іх няма патрэбы пералічваць, бо яны выражаюцца праз базіс папярэдніх $\{-x,x*y,x+y\}$. Функцыі большых памераў таксама выражаюцца праз гэты базіс згодна з крытэрыем Поста. Насамрэч гэты базіс дазваляе будаваць функцыі любых памераў для іншых тыпаў функцый.

Функцыі $x*y$ і $x+y$ спалучаюцца між сабой правіламі дэ Моргана:

1. $x*y=-(-x+-y)$
2. $x+y=-(-x*-y)$

Будаванне функцый з адвольнай колькасцю аргументаў вывучае тэорыя камбінацыйных схем.