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

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

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

Булева 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)\neq 0$, тобто $\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})\neq \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 \leq \beta$, а $f_{M}(\alpha )=1$, $f_{M}(\beta )=1$. Оскільки $\alpha \leq \beta$, то у $\alpha$ є декілька, наприклад, $k$ елементів, які рівні 0, в той час як у $\beta$ ті ж самі елементи рівні 1. Візьмемо набір $\alpha$ та замінимо в ньому перший такий нульовий елемент на 1, отримаємо $\alpha _{1}$: $\alpha \leq \alpha _{1}$, який відрізняється від $\alpha$ тільки одним елементом. Повторюючи цю операцію $k$ разів, отримаємо послідовність наборів $\alpha \leq \alpha _{1}\leq \dots \leq \alpha _{k-1}\leq \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	-	-	-	-	-

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