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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \exists \alpha _{1},\dots ,\alpha _{n}:{\hat {f}}(\alpha _{1},\dots ,\alpha _{n})\neq \neg {\hat {f}}(\neg \alpha _{1},\dots ,\neg \alpha _{n})}$.

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

${\displaystyle \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)}$.

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

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

Побудуємо кон’юнкцію за допомогою підстановлення у нелінійну функцію констант та використання заперечення. Нехай ${\displaystyle f_{L}}$ - нелінійна функція. Тоді в її поліномі Жегалкіна існує нелінійний доданок, який містить кон'юнкцію принаймні двох змінних. Нехай, для визначеності, це ${\displaystyle x_{1}}$ та ${\displaystyle x_{2}}$. Тоді:

${\displaystyle 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})}$,

до того ж ${\displaystyle f_{a}(x_{3},\dots ,x_{n})}$ ≠ 0. Відповідно,

${\displaystyle \exists \alpha _{3},\dots ,\alpha _{n}:f_{a}(\alpha _{3},\dots ,\alpha _{n})=1}$.

Нехай ${\displaystyle b=f_{b}(\alpha _{3},\dots ,\alpha _{n}),c=f_{c}(\alpha _{3},\dots ,\alpha _{n}),d=f_{d}(\alpha _{3},\dots ,\alpha _{n})}$ та

${\displaystyle \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}$.

Тоді нехай

${\displaystyle \psi (x_{1},x_{2})=\phi (x_{1}\land c,x_{2}\land b)\oplus (b\land c)\oplus d}$.

Тоді

${\displaystyle \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=}$

${\displaystyle =(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}}$

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

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

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

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

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

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

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

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

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

${\displaystyle {\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=}$

${\displaystyle =(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=}$

${\displaystyle =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=}$

${\displaystyle =xyz\oplus xy\oplus yz\oplus xz\oplus x\oplus 1}$

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

Перевірка на лінійність: ${\displaystyle {\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}$
${\displaystyle C={\bar {x}}\land y}$

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

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

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

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

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

${\displaystyle {\bar {x}}{\bar {y}}z\oplus {\bar {x}}yz\oplus x{\bar {y}}{\bar {z}}\oplus x{\bar {y}}z\oplus xyz=}$

${\displaystyle =(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=}$

${\displaystyle =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=}$

${\displaystyle =x\oplus z\oplus xy\oplus xz\oplus xyz}$

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

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

${\displaystyle {\bar {x}}{\bar {y}}{\bar {z}}\oplus {\bar {x}}yz\oplus x{\bar {y}}{\bar {z}}\oplus x{\bar {y}}z=}$

${\displaystyle =(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=}$

${\displaystyle =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}$
${\displaystyle B={\bar {x}}\lor {\bar {y}}}$

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

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

• Верещагін М., Шень О. Лекции по математической логике и теории алгоритмов. — МЦНМО, 2002.
• Ігошин В. Математическая логика и теория алгоритмов. — Academia, 2008.
• Мальцев А. Алгоритмы и рекурсивные функции. — Москва : Наука, Физматлит, 1986.