Критерій Поста — одна з центральних теорем математичної логіки, описує необхідні та достатні умови функціональної повноти множини булевих функцій. Був сформульований американським математиком Емілем Постом в 1921. Отже, для того щоб наша система була повною, необхідно і достатньо, щоб вона містила хоча б одну нелінійну функцію, хоча б одну несамодвоїсту, хоча б одну немонотонну, хоча б одну неафінну, хоча б одну функцію, яка не зберігатиме нуль та хоча б одну функцію, що не зберігає одиницю.
Булева n-арна функція, це функція
, де
— булева множина.
Кількість n-арних булевих функцій дорівнює
, а загалом, існує нескінченна кількість булевих функцій.
Довільна булева функція може бути представлена у вигляді:
Тому природним є питання: чи є функціонально повною деяка множина функцій?
Ідея теореми Поста в тому, щоб розглядати множину всіх булевих функцій як алгебру відносно операції суперпозиції, її називають алгеброю Поста. Підалгебрами цієї алгебри є всі замкнені класи булевих функцій.
Основними в теоремі Поста є 5 замкнених класів що називаються передповними класами.
Множина булевих функцій є функціонально повною тоді і тільки тоді, коли вона не міститься повністю ні в одному з передповних класів.
Необхідність умови випливає з функціональної замкненості та неповноти классів монотонних, лінійних, самодвоїстих функцій та функції, які зберігають 0 та 1. Для доведення достатності необхідно показати, що за допомогою функцій, які не належать деяким з класів
,
, можна побудувати деяку повну систему функцій. Прикладом повної системи є заперечення та кон'юнкція. Дійсно довільна булева функція може бути представлена у вигляді ДДНФ, тобто у вигляді кон'юнкції, диз'юнкції та заперечення. Відповідна система є функціонально повною. Можна виключити з неї диз'юнкцію так що вона буде представлена як суперпозиція
та
:
.
Спочатку побудуємо константи. Почнемо з константи 1. Нехай
, де
- функція, що не зберігає нуль. Тоді
, тобто
. Можливі два випадки:
- 1.
. В цьому випадку формула реалізує 1.
- 2.
. Тоді формула
реалізує заперечення. В цьому випадку розглянемо несамодвоїсту функцію
. Маємо:
.
- Відповідно,
. Нехай тепер
. Тоді:
.
Таким чином,
, звідки
або
. Якщо
, то ми побудували константу 1. В іншому випадку
реалізує нуль, а тому
.
Константа 0 будується аналогічно, тільки замість
треба брати
- функцію, що не зберігає 1.
За допомогою немонотонної функції підстановкою в неї констант можна побудувати заперечення. Нехай
- немонотонна функція. Тоді існують набори
та
, такі, що
переслідує
, тобто
, а
,
. Оскільки
, то у
є декілька, наприклад,
елементів, які рівні 0, в той час як у
ті ж самі елементи рівні 1. Візьмемо набір
та замінимо в ньому перший такий нульовий елемент на 1, отримаємо
:
, який відрізняється від
тільки одним елементом. Повторюючи цю операцію
разів, отримаємо послідовність наборів
, в якій кожні два сусідніх набори відрізняються один від одного тільки одним елементом. В цьому ланцюжку знайдуться два таких набори
, що
та
. Нехай ці набори відрізняються
-м (значення змінної
), а решта елементів однакові. Підставимо у
ці значення. Тоді отримаємо функцію
, яка залежить тільки від
. Тоді
,
. Звідси, маємо, що
.
Побудуємо кон’юнкцію за допомогою підстановки у нелінійну функцію констант та використання заперечення. Нехай
- нелінійна функція. Тоді в її поліномі Жегалкіна існує нелінійний доданок, який містить кон'юнкцію принаймні двох змінних. Нехай, для визначеності, це
та
. Тоді:
,
до того ж
≠ 0. Відповідно,
.
Нехай
та
.
Тоді нехай
.
Тоді
![{\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=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b98e411e6168e3a2a94d3f6dd5e79e3b7dc22d47)
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b0f108eddd6d44e30fbd56ec0336f0023630385)
(функцію
можна виразити за допомогою
).
Перевірити повноту системи
Розглянемо формулу
х |
y |
F
|
0 |
0 |
1
|
0 |
1 |
1
|
1 |
0 |
0
|
1 |
1 |
1
|
Розглянемо формулу
Побудуємо таблицю Поста( якщо функція входить у функціонально замкнений клас, то в таблиці Поста у відповідній комірці ставиться знак "+", інакше - "-"
|
Т0 |
Т1 |
S |
M |
L
|
F |
- |
+ |
- |
- |
-
|
V |
- |
- |
- |
- |
+
|
Система є повною.
Перевірити на повноту систему:
Розглянемо
x |
y |
z |
![{\displaystyle {\bar {y}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b298744237368f34e61ff7dc90b34016a7037af) |
![{\displaystyle x\land {\bar {y}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c15d5fae7a3ba2680b0c2e3df55a23736a17186) |
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
|
Перевірка на лінійність:
![{\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=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d8df07bc8ab55938bc6d0ca42e769537a9d7edd)
![{\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=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12099f1b5d778447079e61024a08d481e5be45ee)
![{\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=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85f1ae69e0e77635d8fb28643daaa65cf730ee91)
![{\displaystyle =xyz\oplus xy\oplus yz\oplus xz\oplus x\oplus 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abebd721ce97a632e2ae632c42f017cc6dc9e493)
x |
y |
z |
![{\displaystyle {\bar {z}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52dd0599595d539f7d757ec21da6c6e6ac3ad427) |
![{\displaystyle x\oplus y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10fc94462e7622639c0c464161a1f0c8fc057999) |
![{\displaystyle x\land {\bar {z}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6ceff91e43e5789b76072da29dcd23e5e1f280f) |
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
|
Перевірка на лінійність:
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aac5a75b06da6e9ca1509b8f4acafafd8f5d9384)
x |
y |
![{\displaystyle {\bar {x}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/466e03e1c9533b4dab1b9949dad393883f385d80) |
C
|
0 |
0 |
1 |
0
|
0 |
1 |
1 |
1
|
1 |
0 |
0 |
0
|
1 |
1 |
0 |
0
|
Перевірка на лінійність:
|
Т0 |
Т1 |
M |
S |
L
|
F |
- |
+ |
- |
- |
-
|
B |
- |
+ |
- |
- |
-
|
C |
+ |
- |
- |
- |
-
|
Отже система є повною.
Перевірити на повноту систему
Розглянемо
x |
y |
z |
![{\displaystyle {\bar {x}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/466e03e1c9533b4dab1b9949dad393883f385d80) |
![{\displaystyle {\bar {x}}\lor y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cfd33e98cc142319d4b0a21884db47466d4861b) |
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
|
Перевіримо на лінійність:
![{\displaystyle {\bar {x}}{\bar {y}}z\oplus {\bar {x}}yz\oplus x{\bar {y}}{\bar {z}}\oplus x{\bar {y}}z\oplus xyz=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79366d04d1c1e2a3519a36407c4a712012b93623)
![{\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=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23a4815dfaff10555ca856a049efab53869896f5)
![{\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=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/585c8472a3bf4751f59526be5592f3b402809c8d)
![{\displaystyle =x\oplus z\oplus xy\oplus xz\oplus xyz}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1fa22bab779e2af737415a6ac967df33f604759)
x |
y |
z |
![{\displaystyle x\leftrightarrow y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/339073a2ad68a02cc97cbb40c8c1488ac9e485fe) |
![{\displaystyle x\lor z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3c4ea2020619887570ca25e9d4f958ce6f90df2) |
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
|
Перевіримо на лінійність:
![{\displaystyle {\bar {x}}{\bar {y}}{\bar {z}}\oplus {\bar {x}}yz\oplus x{\bar {y}}{\bar {z}}\oplus x{\bar {y}}z=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b64b569603675f077a766313dff3d0af18195c0d)
![{\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=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8be86dbedeccc881bcd5910a0b6fddcac05c13b)
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ea0f25df2cc62c8633f56932bf55d20aee687bf)
x |
y |
![{\displaystyle {\bar {x}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/466e03e1c9533b4dab1b9949dad393883f385d80) |
![{\displaystyle {\bar {y}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b298744237368f34e61ff7dc90b34016a7037af) |
B
|
0 |
0 |
1 |
1 |
1
|
0 |
1 |
0 |
1 |
1
|
1 |
0 |
0 |
1 |
1
|
1 |
1 |
0 |
0 |
0
|
Перевіримо на лінійність:
|
T0 |
T1 |
M |
S |
L
|
F |
+ |
+ |
- |
- |
-
|
P |
- |
- |
- |
- |
-
|
B |
- |
- |
- |
- |
-
|
Отже, система - повна.