Курсовая работа: Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста

Приклад. Система функцій {} є функціонально повною, але система функцій {} не є функціонально повна.

Якщо у функціонально повній системі є функції константи «0» чи константи «1», то вона послаблено функціонально повна.

Приклад. Система функцій {}, що поповнена константою одиниці , тобто {{},1}, є послаблено функціонально повна.

Максимальна кількість булевих функцій у базисі – 4.

Деколи кажуть про систему функцій повну в деякому класі, а також про базис цього класу. Наприкад, систему {} можна назвати базисом класу лінійних функцій.

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

Приклад. Мінімально повний базис є {}, але система {} не є мінімально повним базисом.

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

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

1. - замкнутість щодо заміни змінних;

2. - замкнутість щодо суперпозиції.

В 1941 році Еміль Пост надав повний опис замкнених класів, який назвали решіткою Поста.

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

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

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 Інші важливі замкнені класи