7

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

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

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

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

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

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

Доказательство. Пусть f 2= L.

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

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

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

Доказательство. Пусть f 2= L. Тогда многочлен Жегалкина содержит конъюнкцию двух переменных, например x1 и x2, откуда имеем f (x1; : : : ; xn) =

x1x2f1(x3; : : : ; xn)+x1f2(x3; : : : ; xn)+x2f3(x3; : : : ; xn)+f4(x3; : : : ; xn);

причем f1( 3; : : : ; n) = 1 для некоторого ( 3; : : : ; n).

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

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

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

Доказательство. Пусть f 2= L. Тогда многочлен Жегалкина содержит конъюнкцию двух переменных, например x1 и x2, откуда имеем f (x1; : : : ; xn) =

x1x2f1(x3; : : : ; xn)+x1f2(x3; : : : ; xn)+x2f3(x3; : : : ; xn)+f4(x3; : : : ; xn);

причем f1( 3; : : : ; n) = 1 для некоторого ( 3; : : : ; n).Тогда g(x1; x2) = f (x1; x2; 1 : : : ; n) = x1x2 + x1 + x2 + ; и

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

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

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

Доказательство. Пусть f 2= L. Тогда многочлен Жегалкина содержит конъюнкцию двух переменных, например x1 и x2, откуда имеем f (x1; : : : ; xn) =

x1x2f1(x3; : : : ; xn)+x1f2(x3; : : : ; xn)+x2f3(x3; : : : ; xn)+f4(x3; : : : ; xn);

причем f1( 3; : : : ; n) = 1 для некоторого ( 3; : : : ; n).Тогда g(x1; x2) = f (x1; x2; 1 : : : ; n) = x1x2 + x1 + x2 + ; и

g(x1 + ; x2 + ) + + = (x1 + )(x2 + ) + (x1 + )+(x2 + ) + + + = x1x2:

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

Базисы полных классов

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

[ff ; g; p; r g] = F, либо [ff ; g; q; r g] = F.

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

Базисы полных классов

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

[ff ; g; p; r g] = F, либо [ff ; g; q; r g] = F.

Определение. Набор функций C F называется базисом,

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

Базисы полных классов

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

[ff ; g; p; r g] = F, либо [ff ; g; q; r g] = F.

Определение. Набор функций C F называется базисом,

Следствие. Любой базис состоит из не более, чем четырех функций.