Diskretka6

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

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

Теорема. Класс функций 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.

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

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

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

Теорема. Класс функций 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.

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

Ifjg полный, так как j 2= T0; T1; M; 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.

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

Ifjg полный, так как j 2= T0; T1; M; L; S.

If#g полный, так как # 2= T0; T1; M; 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.

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

Ifjg полный, так как j 2= T0; T1; M; L; S.

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

If0; 1; xy _ yzg неполный, так как f0; 1; xy _ yzg M.

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

Предполные классы

Определение. Неполный замкнутый класс C называется предполным, если не существует неполного замкнутого класса D такого, что C D:

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

Предполные классы

Определение. Неполный замкнутый класс C называется предполным, если не существует неполного замкнутого класса D такого, что C D:

Теорема. Класс C является предполным тогда и только тогда, когда C совпадает с одним из классов T0; T1; M; L; S:

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

Предполные классы

Определение. Неполный замкнутый класс C называется предполным, если не существует неполного замкнутого класса D такого, что C D:

Теорема. Класс C является предполным тогда и только тогда, когда C совпадает с одним из классов T0; T1; M; L; S:

Доказательство. Пусть C предполный.

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

Предполные классы

Определение. Неполный замкнутый класс C называется предполным, если не существует неполного замкнутого класса D такого, что C D:

Теорема. Класс C является предполным тогда и только тогда, когда C совпадает с одним из классов T0; T1; M; L; S:

Доказательство. Пусть C предполный.Так как C не является полным, по теореме Поста C содержится в одном из замкнутых классов D 2 fT0; T1; M; L; S:g.

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

Предполные классы

Определение. Неполный замкнутый класс C называется предполным, если не существует неполного замкнутого класса D такого, что C D:

Теорема. Класс C является предполным тогда и только тогда, когда C совпадает с одним из классов T0; T1; M; L; S:

Доказательство. Пусть C предполный.Так как C не является полным, по теореме Поста C содержится в одном из замкнутых классов D 2 fT0; T1; M; L; S:g. По определению предполного класса имеем C = D:

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

Предполные классы

Доказательство (продолжение) Остается показать, что каждый из классов C 2 fT0; T1; M; L; S:g является предполным.