Критерій Поста

Критерій Поста — одна з центральних теорем математичної логіки, описує необхідні та достатні умови функціональної повноти множини булевих функцій. Був сформульований американським математиком Емілем Постом в 1941. Отже, для того щоб наша система була повною, необхідно і достатньо, щоб вона містила хоча б одну нелінійну функцію, хоча б одну несамодвоїсту, хоча б одну немонотонну, хоча б одну функцію, яка не зберігатиме нуль та хоча б одну функцію, що не зберігає одиницю.

Постановка задачі

Булева n-арна функція, це функція $~B^n \to B$, де $~B=\{0,1\}$ — булева множина.

Кількість n-арних булевих функцій дорівнює $2^{2^n}$, а загалом, існує нескінченна кількість булевих функцій.

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

• ДНФ (використовується такий набір операцій: кон'юнкція ($\land$), диз'юнкція ($\lor$), заперечення ($\neg$));
• поліному Жегалкіна.

Тому природнім є питання: чи є функціонально повною деяка множина функцій?

Замкнені класи

Ідея теореми Поста в тому, щоб розглядати множину всіх булевих функцій як алгебру відносно операції суперпозиції, її називають алгеброю Поста. Підалгебрами цієї алгебри є всі замкнені класи булевих функцій.

Основними в теоремі Поста є 5 замкнених класів що називаються передповними класами.

Критерій

Множина булевих функцій є функціонально повною тоді і тільки тоді, коли вона не міститься повністю ні в одному з передповних класів.

Доведення

Необхідність умови випливає з функціональної замкненості та неповноти классів монотонних, лінійних, самодвоїстих функцій та функції, які зберігають 0 та 1. Для доведення достатності необхідно показати, що за допомогою функцій, які не належать деяким з класів $T_0$, $T_1, M, L, S$, можна побудувати деяку повну систему функцій. Прикладом повної системи є заперечення та кон'юнкція. Дійсно довільна булева функція може бути представлена у вигляді ДДНФ, тобто у вигляді кон'юнкції, диз'юнкції та заперечення. Відповідна система є функціонально повною. Можна виключити з неї диз'юнкцію так що вона буде представлена як суперпозиція $\land$ та $\neg$: $x \land y=\overline {(\bar x \land \bar y)}$.
Спочатку побудуємо константи. Почнемо з константи 1. Нехай $\phi(0)=f_0(x,...x)$, де $f_0$ - функція, що не зберігає нуль. Тоді $\phi(0)=f_0(0,...0)\ne0$, тобто $\phi(0)=1$. Можливі два випадки:

1. $\phi(1)=1$. В цьому випадку формула реалізує 1.

2. $\phi(1)=0$. Тоді формула $\phi$ реалізує заперечення. В цьому випадку розглянемо несамодвоїсту функцію $\hat f$. Маємо:

$\exists \alpha_1,\dots,\alpha_n : \hat f(\alpha_1,\dots,\alpha_n)\ne\neg \hat f(\neg\alpha_1,\dots,\neg\alpha_n)$.

Відповідно,$\hat f(\alpha_1,\dots,\alpha_n) = \hat f(\neg\alpha_1,\dots,\neg\alpha_n)$. Нехай тепер $\psi(x) = \hat f(x^{\alpha_1},\dots,x^{\alpha_n})$. Тоді:

$\psi(0) = \hat f(0^{\alpha_1},\dots,0^{\alpha_n}) = \hat f(\alpha^1,\dots,\alpha^n) = \hat f(1^{\alpha_1},\dots,1^{\alpha_n})=\psi(1)$.

Таким чином, $\psi(0) = \psi(1)$, звідки $\psi = 1$ або $\psi = 0$. Якщо $\psi = 1$, то ми побудували константу 1. В іншому випадку $\psi$ реалізує нуль, а тому $\phi(\psi(x)) = 1$. Константа 0 будується аналогічно, тільки замість $f_0$ треба брати $f_1$ - функцію, що не зберігає 1.

За допомогою немонотонної функції підстановкою в неї констант можна побудувати заперечення. Нехай $f_M$ - немонотонна функція. Тоді існують набори $\alpha$ та $\beta$, такі, що $\alpha$ переслідує $\beta$, тобто $\alpha\le\beta$, а $f_M(\alpha) = 1$, $f_M(\beta) = 1$. Оскільки $\alpha\le\beta$, то у $\alpha$ є декілька, наприклад, $k$ елементів, які рівні 0, в той час як у $\beta$ ті ж самі елементи рівні 1. Візьмемо набір $\alpha$ та замінимо в ньому перший такий нульовий елемент на 1, отримаємо $\alpha_1$: $\alpha\le\alpha_1$, який відрізняється від $\alpha$ тільки одним елементом. Повторюючи цю операцію $k$ разів, отримаємо послідовність наборів $\alpha\le\alpha_1\le\dots\le\alpha_{k-1}\le\beta$, в якій кожні два сусідніх набори відрізняються один від одного тільки одним елементом. В цьому ланцюжку знайдуться два таких набори $\alpha^i, \alpha^{i+1}$, що $f_M(\alpha^i) = 1$ та $f_M(\alpha^{i+1}) = 1$. Нехай ці набори відрізняються $j$-м (значення змінної $x_j$), а решта елементів однакові. Підставимо у $f_M$ ці значення. Тоді отримаємо функцію $f_M(\alpha_1^i, \dots, \alpha_{j-1}^i, x_j, \alpha_{j+1}^i, \alpha_n^i = \omega(x_j)$, яка залежить тільки від $x_j$. Тоді $\omega(0) = \omega(\alpha_j^i) = f(\alpha^i) = 1$, $\omega(1) = \omega(\alpha_j^{i+1}) = f(\alpha^{i+1}) = 0$. Звідси, маємо, що $\omega(x_j) = \neg x_j$.

Побудуємо кон’юнкцію за допомогою підстановки у нелінійну функцію констант та використання заперечення. Нехай $f_L$ - нелінійна функція. Тоді в її поліномі Жегалкіна існує нелінійний доданок, який містить кон'юнкцію принаймні двох змінних. Нехай, для визначеності, це $x_1$ та $x_2$. Тоді:

$f_L = (x_1 \land x_2 \land f_a(x_3,\dots,x_n)) \oplus (x_1 \land f_b(x_3,\dots,x_n)) \oplus (x_2 \land f_c(x_3,\dots,x_n)) \oplus f_d(x_3,\dots,x_n)$,

до того ж $f_a(x_3,\dots,x_n)$ ≠ 0. Відповідно,

$\exists \alpha_3,\dots,\alpha_n : f_a(\alpha_3,\dots,\alpha_n) = 1$.

Нехай $b = f_b(\alpha_3,\dots,\alpha_n), c = f_c(\alpha_3,\dots,\alpha_n), d = f_d(\alpha_3,\dots,\alpha_n)$ та

$\phi(x_1, x_2) = f_L(x_1, x_2, \alpha_3,\dots,\alpha_n) = (x_1 \land x_2) \oplus (x_1 \land b) \oplus (x_2 \land c) \oplus d$.

Тоді нехай

$\psi(x_1, x_2) = \phi(x_1 \land c, x_2 \land b) \oplus (b \land c) \oplus d$.

Тоді

$\psi(x_1, x_2) = (x_1 \oplus c) \land (x_2 \oplus b) \oplus b \land (x_1 \oplus c) \oplus c \land (x_2 \oplus b) \oplus d \oplus (b \land c) \oplus d =$

$= (x_1 \land x_2) \oplus (x_2 \land c) \oplus (x_1 \land b) \oplus (c \land b) \oplus (x_1 \land b) \oplus (x_2 \land c) \oplus (c \land b) \oplus (c \land b) \oplus (c \land b) \oplus d \oplus d = x_1 \land x_2$

(функцію $x \oplus \alpha$ можна виразити за допомогою $x \oplus 1 = \bar x, x \oplus 0 = x$).

Приклади

Приклад 1

Перевірити повноту системи
${x \to y,\bar x}$

Розглянемо формулу $F=x \to y$ ́

х	y	F
0	0	1
0	1	1
1	0	0
1	1	1

Розглянемо формулу $V=\bar x$

x	V
0	1
1	0

Побудуємо таблицю Поста( якщо функція входить у функціонально замкнений клас, то в таблиці Поста у відповідній комірці ставиться знак "+", інакше - "-"

	Т0	Т1	S	M	L
F	-	+	-	-	-
V	-	-	-	-	+

Система є повною.

Приклад 2

Перевірити на повноту систему:
$(x \land \bar y ) \to z, (x \oplus y) \leftrightarrow (x \land \bar z), \bar x \land y$

Розглянемо $F = (x \land \bar y ) \to z$

x	y	z	$\bar y$	$x \land \bar y$	F
0	0	0	1	0	1
0	0	1	1	0	1
0	1	0	0	0	1
0	1	1	0	0	1
1	0	0	1	1	0
1	0	1	1	1	1
1	1	0	0	0	1
1	1	1	0	0	1

Перевірка на лінійність:

$\bar x \bar y \bar z \oplus \bar x \bar y z \oplus \bar x y \bar z \oplus \bar x yz \oplus x \bar y z \oplus xy \bar z \oplus xyz=$

$= (x \oplus 1)(y \oplus 1)(z \oplus 1) \oplus (x \oplus 1)(y \oplus 1)z \oplus (x \oplus 1)y(z \oplus 1) \oplus (x \oplus 1)yz \oplus x(y \oplus 1)z \oplus xy(z \oplus 1) \oplus xyz =$

$= xyz \oplus xy \oplus xz \oplus yz \oplus x \oplus y \oplus z \oplus 1 \oplus xyz \oplus xz \oplus yz \oplus z \oplus xyz \oplus xy \oplus yz \oplus y \oplus xyz \oplus yz \oplus xyz \oplus xz \oplus xyz \oplus xy \oplus xyz =$

$= xyz \oplus xy \oplus yz \oplus xz \oplus x \oplus 1$

$B = (x \oplus y) \leftrightarrow (x \land \bar z)$

x	y	z	$\bar z$	$x \oplus y$	$x \land \bar z$	B
0	0	0	1	0	0	1
0	0	1	0	0	0	1
0	1	0	1	1	0	0
0	1	1	0	1	0	0
1	0	0	1	1	1	1
1	0	1	0	1	0	0
1	1	0	1	0	1	0
1	1	1	0	0	0	1

Перевірка на лінійність: $\bar x \bar y \bar z \oplus \bar x \bar y z \oplus x \bar y \bar z \oplus xyz= xyz \oplus xy \oplus yz \oplus xz \oplus x \oplus y \oplus z \oplus 1 \oplus xyz \oplus xz \oplus yz \oplus z \oplus xyz \oplus xy \oplus xz \oplus x \oplus xyz = xz \oplus y \oplus 1$
$C= \bar x \land y$

x	y	$\bar x$	C
0	0	1	0
0	1	1	1
1	0	0	0
1	1	0	0

Перевірка на лінійність: $\bar x y=xy \oplus y$

	Т0	Т1	M	S	L
F	-	+	-	-	-
B	-	+	-	-	-
C	+	-	-	-	-

Отже система є повною.

Приклад 3

Перевірити на повноту систему
${(\bar x \lor y) \to z, (x \leftrightarrow y) \oplus (x \lor z), \bar x \lor \bar y}$

Розглянемо $F =(\bar x \lor y) \to z$

x	y	z	$\bar x$	$\bar x \lor y$	F
0	0	0	1	1	0
0	0	1	1	1	1
0	1	0	1	1	0
0	1	1	1	1	1
1	0	0	0	0	1
1	0	1	0	0	1
1	1	0	0	1	0
1	1	1	0	1	1

Перевіримо на лінійність:

$\bar x \bar y z \oplus \bar x yz \oplus x \bar y \bar z \oplus x \bar y z \oplus xyz =$

$= (x \oplus 1)(y \oplus 1)z \oplus (x \oplus 1)yz \oplus x(y \oplus 1)(z \oplus 1) \oplus x(y \oplus 1)z \oplus xyz =$

$= xyz \oplus xz \oplus yz \oplus z \oplus xyz \oplus yz \oplus xyz \oplus xy \oplus xz \oplus x \oplus xyz \oplus xz \oplus xyz =$

$= x \oplus z \oplus xy \oplus xz \oplus xyz$

$P=(x \leftrightarrow y) \oplus (x \lor z)$

x	y	z	$x \leftrightarrow y$	$x \lor z$	P
0	0	0	1	0	1
0	0	1	1	1	0
0	1	0	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	0	1	0	1	1
1	1	0	1	1	0
1	1	1	1	1	0

Перевіримо на лінійність:

$\bar x \bar y \bar z \oplus \bar x yz \oplus x \bar y \bar z \oplus x \bar y z =$

$= (x \oplus 1)(y \oplus 1)(z \oplus 1) \oplus (x \oplus 1)yz \oplus x(y \oplus 1)(z \oplus 1) \oplus x(y \oplus 1)z =$

$=xyz \oplus xy \oplus yz \oplus xz \oplus x \oplus y \oplus z \oplus 1 \oplus xyz \oplus yz \oplus xyz \oplus xy \oplus xz \oplus x \oplus xyz \oplus xz = xz \oplus y \oplus z \oplus 1$
$B= \bar x \lor \bar y$

x	y	$\bar x$	$\bar y$	B
0	0	1	1	1
0	1	0	1	1
1	0	0	1	1
1	1	0	0	0

Перевіримо на лінійність: $\bar x \bar y \oplus \bar x y \oplus x \bar y = (x \oplus 1)(y \oplus 1) \oplus (x \oplus 1)y \oplus x(y \oplus 1) = xy \oplus x \oplus y \oplus 1 \oplus xy \oplus x \oplus xy \oplus y =xy \oplus 1$

	T0	T1	M	S	L
F	+	+	-	-	-
P	-	-	-	-	-
B	-	-	-	-	-

Отже, система - повна.