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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. \phi(1)=1. В цьому випадку формула реалізує 1.
2. \phi(1)=0. Тоді формула \phi реалізує заперечення. В цьому випадку розглянемо несамодвоїсту функцію \hat f. Маємо:
\exists \alpha_1,\dots,\alpha_n : \hat f(\alpha_1,\dots,\alpha_n)\ne\neg \hat f(\neg\alpha_1,\dots,\neg\alpha_n).
Відповідно,\hat f(\alpha_1,\dots,\alpha_n) = \hat f(\neg\alpha_1,\dots,\neg\alpha_n). Нехай тепер \psi(x) = \hat f(x^{\alpha_1},\dots,x^{\alpha_n}). Тоді:
\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).

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

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


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

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),

до того ж f_a(x_3,\dots,x_n) ≠ 0. Відповідно,

\exists \alpha_3,\dots,\alpha_n : f_a(\alpha_3,\dots,\alpha_n) = 1.

Нехай b = f_b(\alpha_3,\dots,\alpha_n), c = f_c(\alpha_3,\dots,\alpha_n), d = f_d(\alpha_3,\dots,\alpha_n) та

\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.

Тоді нехай

\psi(x_1, x_2) = \phi(x_1 \land c, x_2 \land b) \oplus (b \land c) \oplus d.

Тоді

\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 =
= (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

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

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

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

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

Розглянемо формулу F=x \to y ́

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

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

x V
0 1
1 0

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

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

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

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

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

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

x y z \bar y  x \land \bar y 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

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

 \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=
= (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 =
 = 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 =
 = xyz \oplus xy \oplus yz \oplus xz \oplus x \oplus 1

 B =  (x \oplus y) \leftrightarrow (x \land \bar z)

x y z \bar z x \oplus y x \land \bar 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

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

x y \bar x C
0 0 1 0
0 1 1 1
1 0 0 0
1 1 0 0

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

Т0 Т1 M S L
F - + - - -
B - + - - -
C + - - - -

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

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

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

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

x y z \bar x \bar x \lor y 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

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

\bar x \bar y  z \oplus \bar x yz \oplus x \bar y \bar z \oplus x \bar y z \oplus xyz =
= (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 =
= 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 =
= x \oplus z \oplus xy \oplus xz \oplus xyz

P=(x \leftrightarrow y) \oplus (x \lor z)

x y z x \leftrightarrow y x \lor 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

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

\bar x \bar y \bar z \oplus \bar x yz \oplus x \bar y \bar z \oplus x \bar y z =
= (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 =

=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
B= \bar x \lor \bar y

x y \bar x \bar y B
0 0 1 1 1
0 1 0 1 1
1 0 0 1 1
1 1 0 0 0

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

T0 T1 M S L
F + + - - -
P - - - - -
B - - - - -

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