8.4.4. Послаблена функціональна повнота

Систему булевих функцій Qназивають послаблено функціональ­но повною, якщо довільну булеву функцію можна зобразити форму­лою над множиною Q∪{0,1}, тобто суперпозицією констант 0, 1 та функцій із системиQ.

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

Доведення. За наявності констант 0 та 1 маємо функцію, що не зберігає 0 (функція 1), функція, що не зберігає 1 (функція 0) і несамо­двоїста функція (кожна з функцій 0 та 1). Разом з тим, константи 0 і 1 є,очевидно, лінійними і монотонними. Застосування теореми Поста завершує доведення.▲

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

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

Власний замкнений клас називаютьпередповним, якщо він не міститься в жодному замкненому класі, відмінному від самого себе і від класу P₂всіх булевих функцій. Розглянемо тепер декілька сис­тем функцій (див. табл. 8.7).

Таблиця 8.7

		T0	T1	S	M	L
І	0 xy x⊕y⊕z	+ + +	- + +	- - +	+ + -	+ - +
ІІ	1 xy x⊕y⊕z	- + +	+ + +	- - +	+ + -	+ - +
ІІІ		-	-	+	-	-
ІV	0 1 xy	+ - +	- + +	- - -	+ + +	+ + -
V	0 1 x⊕y	+ - +	- + -	- - -	+ + -	+ + +

Обговоримо питання про істотність умов теореми Поста. Всі сис­теми I-V неповні, оскільки для кожної з них у табл. 8.7 є стовпець, який повністю складається з плюсів. Зазначимо, що в кожній системі є точно один такий стовпець і в різних системах ці стовпці різні. Звідси випливає, що в умові теореми Поста не можна відкинути жодного з п'яти класів. Справді, для кожного із класів можна вказати систему функцій, яка є його підмножиною (а отже, неповна), і в якій для кожного із решти чотирьох класів є функція, яка йому не належить.

Теорема 8.20.Жоден із класівТ₀T₁, S, L, Мне міститься в іншому.

Доведення. Якщо який-небудь із перелічених класів містився б в іншому, то у формулюванні теореми Поста цей клас можна було б відкинути, що суперечить попереднім міркуванням. ▲

Теорема 8.21.Будь-який власний замкнений клас є ггідмножиною одного з класівТ₀T₁, S, L, М.

Доведення. Припустимо, що власний замкнений клас Сне є підмножиною жодного з класівТ₀T₁, S, L, М. Отже, Смістить функ­цію. яка не зберігає 0, функцію, яка не зберігає 1, несамодвоїсту функ­цію, немонотонну функцію та нелінійну функцію. Тоді за теоремою 8.17 замикання класу Сдорівнює Р₂ Оскільки Сза умовою замкнений, то С=[С]=Р₂ Суперечність. ▲

Теорема 8.22.Замкнені класи Т₀T₁, S, L, М є передповними і інших перед повних класів немає.

Доведення. За теоремою 8.21 інші замкнені класи не можуть бути передповними. За теоремою 8.20 кожний із п'яти перелічених класів передповний. ▲