Diskretka6

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

Замкнутые классы

Предложение. Классы T0; T1; M; L; S не содержатся друг в друге.

Доказательство (продолжение).

I Класс M: 0; 1; &2 M, но 0 2= T1; S; 1 2= T0; &2= L:

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

Замкнутые классы

Предложение. Классы T0; T1; M; L; S не содержатся друг в друге.

Доказательство (продолжение).

IКласс M: 0; 1; &2 M, но 0 2= T1; S; 1 2= T0; &2= L:

IКласс L: 1; + 2 L, но 1 2= T0; S; + 2= T1; M:

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

Замкнутые классы

Предложение. Классы T0; T1; M; L; S не содержатся друг в друге.

Доказательство (продолжение).

IКласс M: 0; 1; &2 M, но 0 2= T1; S; 1 2= T0; &2= L:

IКласс L: 1; + 2 L, но 1 2= T0; S; + 2= T1; M:

IS: :; d 2 S, где

d(x; y; z) = xy _ yz _ zx = xy + yz + zx:

Тогда но : 2= T0; T1; M; d 2= L:

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

Полные классы

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

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

Полные классы

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

Примеры

If_; &; g; f_; g; f&; g; f1; +; g; fjg; f#g полные классы.

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

Полные классы

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

Примеры

If_; &; g; f_; g; f&; g; f1; +; g; fjg; f#g полные классы.

If0; 1; _; &g; f0; 1; +g неполные классы.

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

Теорема Поста

Теорема. Класс функций C F является полным тогда и только тогда, когда C не содержится в классах T0; T1; M, L,

S:

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

Теорема Поста

Теорема. Класс функций C F является полным тогда и только тогда, когда C не содержится в классах T0; T1; M, L,

S:

Примеры

I f&; :g полный, так как : 2= T0; T1; M; &2= L; S.

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

Теорема Поста

Теорема. Класс функций C F является полным тогда и только тогда, когда C не содержится в классах T0; T1; M, L,

S:

Примеры

If&; :g полный, так как : 2= T0; T1; M; &2= L; S.

If_; :g полный, так как : 2= T0; T1; M; _ 2= L; S.