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

Булева 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}$).