Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста (стр. 4 из 5)

Особливо важливими замкнутими класами є так звані передповні класи.

алгебра логіка функція теорема поста

2.4 Передповні класи

Визначення. Нехай

. називається передповним класом, якщо

1.

;

2.

.

Теорема 10. В

передповними є лише такі 5 класів:

Доведення

1. Покажемо спочатку, щожоден з цих п’яти класів не міститься в іншому. Для цього достатньо для кожного з цих п’яти класів вказати чотири функції, що належать цьому класу, але що не належать іншим чотирьом

	0			0
	1			1
	1	0		0
	1	0		0

2. Доведемо, що всі класи – T₀, T₁, L, S, Mє передповними. Дійсно, нехай

і . Тоді системи немає в жодному із класів Поста. Отже, система – повна і – передповний клас.

3. Нехай

- передповний клас

Тоді

Якщо

, то

Жоден з передповних класів не міститься повністю в об'єднанні чотирьох інших класів; довільний замкнутий клас, відмінний від P₂, повністю міститься хоча б в одному з п'яти передповних класів.

Таблиця №3

Хиба	Істина	Заперечення	Кон'юнкція, AND	Диз'юнкція, OR	Виключна диз'юнкція XOR	Еквівалентність, XNOR	Імплікація	Заперечення імплікації	Штрих Шеффера, NAND	Стрілка Пірса, NOR
Т0	•	•	•	•	•
Т1	•	•	•	•	•
S	•
M	•	•	•	•
L	•	•	•	•	•

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

Щоб вибрати базис для класу потрібно, щоб таблиця з їхніх стовпців в кожному рядку (крім рядка цього класу) містила хоча б одну порожню клітинку.

2.5 Інші важливі замкнені класи

1. Клас кон'юнкцій K, що є замиканням множини операцій {

}. Він представляє собою множину функцій виду .

2. Клас диз'юнкцій D, що є замиканням множини операцій {

}. Він представляє собою множину функцій виду .

3. Клас U функцій одної змінної, що містить тільки константи, заперечення та селектор (функцію, що тотожна одній зі своїх змінних).

4. Клас

функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна нулю, знайдеться змінна, яка теж рівна нулю на всіх цих наборах.

5. Клас

функцій, для яких виконується умова .

6. Клас

функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна 1, знайдеться змінна, яка теж рівна 1 на всіх цих наборах.

7. Клас

функцій, для яких виконується умова .

В 1941 році Еміль Пост показав, що довільний замкнутий клас є перетином скінченної кількості вищеописаних класів. Також Пост встановив, що довільний замкнутий клас може бути породжений скінченним базисом.

Властивості:

1. Перетин замкнутих класів є замкнутим класом.

2. Об'єднання замкнутих класів може не бути замкнутим класом.

3. Доповнення замкнутого класа булевих функцій до множини всіх булевих функцій P₂ не є замкнутим класом.

Розділ 3. Теорема Поста

Лема 2(про несамодвоїсту функцію.) [1, ст. 10]. З будь-якої несамодвоїстої функції алгебри логіки

, підставляючи замість усіх змінних функції і , можна отримати .

Доведення

Нехай

Тоді

Побудуємо функцію

так:

Дійсно

і

Зауважимо, що підстановка задовольняє умові теореми, так

як

Лемy доведенo.

Лема 3(про немонотонну функцію.) [1, ст. 11]. З будь-якої немонотонної функції алгебри логіки

, підставляючи замість усіх змінних функції , можна отримати функцію

Доведення

Нехай

. Тоді існують такі набори і , що (тобто і ) і . Виділимо ті розряди наборів , в яких вони відрізняються. Очевидно, в наборі ці розряди

рівні 0, а в наборі

. Розглянемо послідовність наборів таких, що , де виходить з заміною одного з нулів, розташованого в одній з позицій , на одиницю (при цьому набори і - сусідні).