Теорема Посту про повноту

Для того щоб система функцій була повною, необхідно і достатньо, щоб вона не містилася повністю в жодному з класівT0,T1,L,S,M.

Доказ.Доведемо необхідність цієї умови. Нехай система

Доведемо достатність. НехайF=f0,f1,fL,fm,fs, деf0T0,f1T1,fLL,fsSіfmM. Покажемо, що суперпозицією функцій системиFможна отримати повну системуG= x1&x2,

теорема
>.

g(1) = 0. Тодіg(x) =

теорема
. По лемі про несамовиту функцію суперпозицією над fs,
повноту
> можна отримати одну з констант, наприклад, 0. Тодіf0(0, …, 0) = 1 є інша константа.

В обох випадках отримали обидві константи.

2. По лемі про немонотонну функцію суперпозицією над fm, 0, 1> можна отримати заперечення.

3. По лемі про нелінійну функцію суперпозицією над fL, 1,

повноту
> можна одержати кон'юнкцію. Теорему доведено.

Слідство.Кожен замкнутий клас функцій зР2, що не збігається зР2міститься, принаймні, в одному із замкнутих класівT0,T1,L,S,M. Справді, якщоNне є підмножиноюQ, то [N] =P2, що невірно.