7

Теорема Поста Доказательство теоремы Поста

Лемма о немонотонной функции

Лемма. Если f 2= M, то 2 [ff ; 0; 1g].

Доказательство. Пусть f 2= M.Тогда существует наборы

( 1; : : : ; n) ( 1; : : : n) такие, что f ( 1; : : : ; n) = 1 и f ( 1; : : : n) = 0:

Теорема Поста Доказательство теоремы Поста

Лемма о немонотонной функции

Лемма. Если f 2= M, то 2 [ff ; 0; 1g].

Доказательство. Пусть f 2= M.Тогда существует наборы

( 1; : : : ; n) ( 1; : : : n) такие, что f ( 1; : : : ; n) = 1 и f ( 1; : : : n) = 0: Определим формулы

Теорема Поста Доказательство теоремы Поста

Лемма о немонотонной функции

Лемма. Если f 2= M, то 2 [ff ; 0; 1g].

Доказательство. Пусть f 2= M.Тогда существует наборы

( 1; : : : ; n) ( 1; : : : n) такие, что f ( 1; : : : ; n) = 1 и f ( 1; : : : n) = 0: Определим формулы

8

>0; если i = i = 0;

<

gi (x) = 1; если i = i = 1;

>

:x; если i = 0 и i = 1:

Тогда gi (0) = i и gi (1) = i для всех i = 1; n.

Теорема Поста Доказательство теоремы Поста

Лемма о немонотонной функции

Лемма. Если f 2= M, то 2 [ff ; 0; 1g].

Доказательство. Пусть f 2= M.Тогда существует наборы

( 1; : : : ; n) ( 1; : : : n) такие, что f ( 1; : : : ; n) = 1 и f ( 1; : : : n) = 0: Определим формулы

8

>0; если i = i = 0;

<

gi (x) = 1; если i = i = 1;

>

:x; если i = 0 и i = 1:

Тогда gi (0) = i и gi (1) = i для всех i = 1; n. Поэтому для формулы h(x) = f (g0(x); : : : ; gn(x)) имеем h(0) = 1 и

h(1) = 0, то есть h(x) = x:

Теорема Поста Доказательство теоремы Поста

Лемма для T0 и T1

Лемма. Если f 2= T0 и g 2= T1, то либо 2 [ff ; gg], либо

0; 1 2 [ff ; gg].

Теорема Поста Доказательство теоремы Поста

Лемма для T0 и T1

Лемма. Если f 2= T0 и g 2= T1, то либо 2 [ff ; gg], либо

0; 1 2 [ff ; gg].

Доказательство. Имеем f (0; : : : ; 0) = 1 и g(1; : : : ; 1) = 0.

Теорема Поста Доказательство теоремы Поста

Лемма для T0 и T1

Лемма. Если f 2= T0 и g 2= T1, то либо 2 [ff ; gg], либо

0; 1 2 [ff ; gg].

Доказательство. Имеем f (0; : : : ; 0) = 1 и g(1; : : : ; 1) = 0. Если f (1; : : : ; 1) = 0, то f (x; : : : ; x) = x и лемма доказана.

Теорема Поста Доказательство теоремы Поста

Лемма для T0 и T1

Лемма. Если f 2= T0 и g 2= T1, то либо 2 [ff ; gg], либо

0; 1 2 [ff ; gg].

Доказательство. Имеем f (0; : : : ; 0) = 1 и g(1; : : : ; 1) = 0. Если f (1; : : : ; 1) = 0, то f (x; : : : ; x) = x и лемма доказана. Пусть теперь f (1; : : : ; 1) = 1. Тогда f (x; : : : ; x) = 1 и, следовательно, 1 2 [ff ; gg].

Теорема Поста Доказательство теоремы Поста

Лемма для T0 и T1

Лемма. Если f 2= T0 и g 2= T1, то либо 2 [ff ; gg], либо

0; 1 2 [ff ; gg].

Доказательство. Имеем f (0; : : : ; 0) = 1 и g(1; : : : ; 1) = 0. Если f (1; : : : ; 1) = 0, то f (x; : : : ; x) = x и лемма доказана. Пусть теперь f (1; : : : ; 1) = 1. Тогда f (x; : : : ; x) = 1 и, следовательно, 1 2 [ff ; gg].

Остается показать, что 0 2 [ff ; gg]:

g(f (x; : : : ; x); : : : ; f (x; : : : ; x)) = g(1; : : : ; 1) = 0:

Теорема Поста Доказательство теоремы Поста

Лемма для T0 и T1

Лемма. Если f 2= T0 и g 2= T1, то либо 2 [ff ; gg], либо

0; 1 2 [ff ; gg].

Доказательство. Имеем f (0; : : : ; 0) = 1 и g(1; : : : ; 1) = 0. Если f (1; : : : ; 1) = 0, то f (x; : : : ; x) = x и лемма доказана. Пусть теперь f (1; : : : ; 1) = 1. Тогда f (x; : : : ; x) = 1 и, следовательно, 1 2 [ff ; gg].

Остается показать, что 0 2 [ff ; gg]:

g(f (x; : : : ; x); : : : ; f (x; : : : ; x)) = g(1; : : : ; 1) = 0:

Следствие. Если f 2= T0, g 2= T1, p 2= S и q 2= M, то либо

; 0; 1 2 [ff ; g; pg], либо ; 0; 1 2 [ff ; g; qg].