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

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

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

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

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

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

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

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

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

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

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

Критерій

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

Доведення

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

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

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

$\mathrm{\exists }{\alpha }_1,\dots ,{\alpha }_n:\hat{f}({\alpha }_1,\dots ,{\alpha }_n)\ne \mathrm{\neg }\hat{f}(\mathrm{\neg }{\alpha }_1,\dots ,\mathrm{\neg }{\alpha }_n)$.

Відповідно,$\hat{f}({\alpha }_1,\dots ,{\alpha }_n)=\hat{f}(\mathrm{\neg }{\alpha }_1,\dots ,\mathrm{\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$ реалізує нуль, а тому $\varphi (\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)=\mathrm{\neg }{x}_j$.

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

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

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

$\mathrm{\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)$ та

$\varphi (x_1,x_2)=f_L(x_1,x_2,{\alpha }_3,\dots ,{\alpha }_n)=(x_1\wedge x_2)\oplus (x_1\wedge b)\oplus (x_2\wedge c)\oplus d$.

Тоді нехай

$\psi (x_1,x_2)=\varphi (x_1\wedge c,x_2\wedge b)\oplus (b\wedge c)\oplus d$.

Тоді

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

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

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

Приклади

Приклад 1

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

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

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

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

x	V
0	1
1	0

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

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

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

Приклад 2

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

Розглянемо $F=(x\wedge \overline{y})\to z$

x	y	z	$\overline{y}$	$x\wedge \overline{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

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

$\overline{x}\overline{y}\overline{z}\oplus \overline{x}\overline{y}z\oplus \overline{x}y\overline{z}\oplus \overline{x}yz\oplus x\overline{y}z\oplus xy\overline{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\wedge \overline{z})$

x	y	z	$\overline{z}$	$x\oplus y$	$x\wedge \overline{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

Перевірка на лінійність: $\overline{x}\overline{y}\overline{z}\oplus \overline{x}\overline{y}z\oplus x\overline{y}\overline{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=\overline{x}\wedge y$

x	y	$\overline{x}$	C
0	0	1	0
0	1	1	1
1	0	0	0
1	1	0	0

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

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

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

Приклад 3

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

Розглянемо $F=(\overline{x}\vee y)\to z$

x	y	z	$\overline{x}$	$\overline{x}\vee 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

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

$\overline{x}\overline{y}z\oplus \overline{x}yz\oplus x\overline{y}\overline{z}\oplus x\overline{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\vee z)$

x	y	z	$x\leftrightarrow y$	$x\vee 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

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

$\overline{x}\overline{y}\overline{z}\oplus \overline{x}yz\oplus x\overline{y}\overline{z}\oplus x\overline{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=\overline{x}\vee \overline{y}$

x	y	$\overline{x}$	$\overline{y}$	B
0	0	1	1	1
0	1	0	1	1
1	0	0	1	1
1	1	0	0	0

Перевіримо на лінійність: $\overline{x}\overline{y}\oplus \overline{x}y\oplus x\overline{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	-	-	-	-	-

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