Теорема поста про повноту

Перейдемо до розгляду одного з основних питань алгебри логіки - питання про необхідні і достатні умови повноти. нехай

- довільна система функцій з. Питається, як з'ясувати, буде вона повною чи ні? Відповідь на це питання дає наступна теорема.

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

Доведення. Необхідність. Нехай - повна, тобто. Припустимо, що міститься в одному із зазначених класів - позначимо його через. тобто . Тоді в силу властивостей замикання і замкнутості маємо

.

Звідси. що не так. Необхідність доведена.

Достатність. Нехай цілком не міститься ні в одному із зазначених класів. Тоді з можна виділити підсистему. що містить не більше п'яти функцій, яка володіє цією властивістю. Для цього візьмемо в функції. . . . і покладемо

.

Для доказу достатності переконаємося, що з функцій можна побудувати заперечення і кон'юнкцію. Доказ проведемо в два етапи.

I. Побудова за допомогою функцій. . і констант і заперечення.

Розглянемо функції і. Побудуємо функції одного аргументу:

При зроблених припущеннях

. .

Залежно від того, які значення мають і. можливі чотири варіанти.

В цьому випадку . . В результаті суперпозиції отримуємо константу 1:. Таким чином, заперечення і константи побудовані.

В цьому випадку . . Будуємо. і перший етап закінчений.

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

.

Розглянемо функцію. в якій на місце -го аргументу ставиться. якщо. або. якщо. тоді

.

Звідси слідує що . За допомогою заперечення побудуємо іншу константу.

Отже,. . Скористаємося немонотонної функцією. За лемі 4 з шляхом підстановки констант можна отримати заперечення.

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

.

Розглянемо функцію. Для побудови функції потрібно тільки заперечення, оскільки додаток двійковій константи або нічого не змінює, якщо вона дорівнює 0, або змінює змінну на її заперечення. Наприклад, при. . .

Розкривши дужки, переконуємося, що. Таким чином, кон'юнкція побудована з функцій системи.

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

маємо наступну таблицю: