Diskretka6

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

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

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

Примеры

IКласс всех функций F.

I[C].

IM = [f0; 1; _; &g].

IL = [f0; 1; +g].

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

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

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

Примеры

IКласс всех функций F.

I[C].

IM = [f0; 1; _; &g].

IL = [f0; 1; +g].

IT0 = ff jf (0; : : : ; 0) = 0g:

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

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

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

Примеры

IКласс всех функций F.

I[C].

IM = [f0; 1; _; &g].

IL = [f0; 1; +g].

IT0 = ff jf (0; : : : ; 0) = 0g:

IT1 = ff jf (1; : : : ; 1) = 1g:

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

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

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

Примеры

IКласс всех функций F.

I[C].

IM = [f0; 1; _; &g].

IL = [f0; 1; +g].

IT0 = ff jf (0; : : : ; 0) = 0g:

IT1 = ff jf (1; : : : ; 1) = 1g:

IS = ff jf = f g; где

f (x1; : : : ; xn) = f (x1; : : : ; xn):

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

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

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

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

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

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

Доказательство.

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

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

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

Доказательство.

IКласс T0: &; + 2 T0, но &2= L; S; + 2= T1; M; S; так как x _ y = x _ y = x & y 6= x _ y:

x + y = x + y = 1 + (1 + x) + (1 + y) = x + y 6= x + y:

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

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

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

Доказательство.

IКласс T0: &; + 2 T0, но &2= L; S; + 2= T1; M; S; так как x _ y = x _ y = x & y 6= x _ y:

x + y = x + y = 1 + (1 + x) + (1 + y) = x + y 6= x + y:

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

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

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

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

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

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

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

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