Diskretka6
.pdf
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Предполные классы
Доказательство (продолжение) Остается показать, что каждый из классов C 2 fT0; T1; M; L; S:g является предполным. Каждый такой класс не содержится ни в одном другом классе из fT0; T1; M; L; Sg.
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Предполные классы
Доказательство (продолжение) Остается показать, что каждый из классов C 2 fT0; T1; M; L; S:g является предполным. Каждый такой класс не содержится ни в одном другом классе из fT0; T1; M; L; Sg.
Предположим, что имеется неполный замкнутый класс D такой, что C D.
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Предполные классы
Доказательство (продолжение) Остается показать, что каждый из классов C 2 fT0; T1; M; L; S:g является предполным. Каждый такой класс не содержится ни в одном другом классе из fT0; T1; M; L; Sg.
Предположим, что имеется неполный замкнутый класс D такой, что C D. Тогда D не содержится ни в одном из классов из fT0; T1; M; L; S; g кроме C
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Предполные классы
Доказательство (продолжение) Остается показать, что каждый из классов C 2 fT0; T1; M; L; S:g является предполным. Каждый такой класс не содержится ни в одном другом классе из fT0; T1; M; L; Sg.
Предположим, что имеется неполный замкнутый класс D такой, что C D. Тогда D не содержится ни в одном из классов из fT0; T1; M; L; S; g кроме C, и D 6 .C
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Предполные классы
Доказательство (продолжение) Остается показать, что каждый из классов C 2 fT0; T1; M; L; S:g является предполным. Каждый такой класс не содержится ни в одном другом классе из fT0; T1; M; L; Sg.
Предположим, что имеется неполный замкнутый класс D такой, что C D. Тогда D не содержится ни в одном из классов из fT0; T1; M; L; S; g кроме C, и D 6 .CЗначит неполный замкнутый класс D не содержится ни в одном из классов T0; T1; M; L; S
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Предполные классы
Доказательство (продолжение) Остается показать, что каждый из классов C 2 fT0; T1; M; L; S:g является предполным. Каждый такой класс не содержится ни в одном другом классе из fT0; T1; M; L; Sg.
Предположим, что имеется неполный замкнутый класс D такой, что C D. Тогда D не содержится ни в одном из классов из fT0; T1; M; L; S; g кроме C, и D 6 .CЗначит неполный замкнутый класс D не содержится ни в одном из классов T0; T1; M; L; S, что противоречит теореме Поста.
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Лемма о несамопряженной функции
Лемма. Если f 2= S, то 0; 1 2 [ff ; g].
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Лемма о несамопряженной функции
Лемма. Если f 2= S, то 0; 1 2 [ff ; g].
Доказательство. Пусть f 2= S. Тогда существует набор ( 1; : : : ; n) такой, что
f ( 1; : : : ; n) = f ( 1; : : : ; n) 6= f ( 1; : : : ; n):
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Лемма о несамопряженной функции
Лемма. Если f 2= S, то 0; 1 2 [ff ; g].
Доказательство. Пусть f 2= S. Тогда существует набор ( 1; : : : ; n) такой, что
f ( 1; : : : ; n) = f ( 1; : : : ; n) 6= f ( 1; : : : ; n):
Тогда f ( 1; : : : ; n) = f ( 1; : : : ; n).
Замкнутые классы функций Теорема Поста Доказательство теоремы Поста
Лемма о несамопряженной функции
Лемма. Если f 2= S, то 0; 1 2 [ff ; g].
Доказательство. Пусть f 2= S. Тогда существует набор ( 1; : : : ; n) такой, что
f ( 1; : : : ; n) = f ( 1; : : : ; n) 6= f ( 1; : : : ; n):
Тогда f ( 1; : : : ; n) = f ( 1; : : : ; n). Поэтому для формулы g(x) = f (x 1 ; : : : ; x n ) имеем
g(0) = f ( 1; : : : ; n) = f ( 1; : : : ; n) = g(1):