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

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

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

Таблиця 8.7

		T0	T1	S	M	L
І	xy x⊕ y⊕ z	+ + +	- + +	- - +	+ + -	+ - +
ІІ	xy x⊕ y⊕ z	- + +	+ + +	- - +	+ + -	+ - +
ІІІ		-	-	+	-	-
ІV	xy	+ - +	- + +	- - -	+ + +	+ + -
V	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 кожний із п'яти перелічених класів передповний. ▲