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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Постановка задачі[ред.ред. код]

Булева n-арна функція, це функція , де  — булева множина.

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

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

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

Замкнені класи[ред.ред. код]

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

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

Критерій[ред.ред. код]

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

Доведення[ред.ред. код]

Необхідність умови випливає з функціональної замкненості та неповноти классів монотонних, лінійних, самодвоїстих функцій та функції, які зберігають 0 та 1. Для доведення достатності необхідно показати, що за допомогою функцій, які не належать деяким з класів , , можна побудувати деяку повну систему функцій. Прикладом повної системи є заперечення та кон'юнкція. Дійсно довільна булева функція може бути представлена у вигляді ДДНФ, тобто у вигляді кон'юнкції, диз'юнкції та заперечення. Відповідна система є функціонально повною. Можна виключити з неї диз'юнкцію так що вона буде представлена як суперпозиція та : .
Спочатку побудуємо константи. Почнемо з константи 1. Нехай , де - функція, що не зберігає нуль. Тоді , тобто . Можливі два випадки:

1. . В цьому випадку формула реалізує 1.
2. . Тоді формула реалізує заперечення. В цьому випадку розглянемо несамодвоїсту функцію . Маємо:
.
Відповідно,. Нехай тепер . Тоді:
.

Таким чином, , звідки або . Якщо , то ми побудували константу 1. В іншому випадку реалізує нуль, а тому . Константа 0 будується аналогічно, тільки замість треба брати - функцію, що не зберігає 1.

За допомогою немонотонної функції підстановкою в неї констант можна побудувати заперечення. Нехай - немонотонна функція. Тоді існують набори та , такі, що переслідує , тобто , а , . Оскільки , то у є декілька, наприклад, елементів, які рівні 0, в той час як у ті ж самі елементи рівні 1. Візьмемо набір та замінимо в ньому перший такий нульовий елемент на 1, отримаємо : , який відрізняється від тільки одним елементом. Повторюючи цю операцію разів, отримаємо послідовність наборів , в якій кожні два сусідніх набори відрізняються один від одного тільки одним елементом. В цьому ланцюжку знайдуться два таких набори , що та . Нехай ці набори відрізняються -м (значення змінної ), а решта елементів однакові. Підставимо у ці значення. Тоді отримаємо функцію , яка залежить тільки від . Тоді , . Звідси, маємо, що .

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

,

до того ж ≠ 0. Відповідно,

.

Нехай та

.

Тоді нехай

.

Тоді

(функцію можна виразити за допомогою ).

Приклади[ред.ред. код]

Приклад 1[ред.ред. код]

Перевірити повноту системи

Розглянемо формулу

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

Розглянемо формулу

x V
0 1
1 0

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

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

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

Приклад 2[ред.ред. код]

Перевірити на повноту систему:

Розглянемо

x y z 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

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

x y 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

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

x y 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 + - - - -

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

Приклад 3[ред.ред. код]

Перевірити на повноту систему

Розглянемо

x y z 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

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

x y 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

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


x y 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 - - - - -

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