7
.pdfТеорема Поста Доказательство теоремы Поста
Теорема Поста
Определение. Класс функций C F называется полным, если [C] = F.
Теорема. Класс функций C F является полным тогда и только тогда, когда C не содержится в классах T0; T1; M, L,
S:
Теорема Поста Доказательство теоремы Поста
Теорема Поста
Определение. Класс функций C F называется полным, если [C] = F.
Теорема. Класс функций C F является полным тогда и только тогда, когда C не содержится в классах 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):
Теорема Поста Доказательство теоремы Поста
Лемма о несамопряженной функции
Лемма. Если 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):
Таким образом, одна из констант 0; 1 является формулой над 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 ( 1; : : : ; n) = f ( 1; : : : ; n). Поэтому для формулы g(x) = f (x 1 ; : : : ; x n ) имеем
g(0) = f ( 1; : : : ; n) = f ( 1; : : : ; n) = g(1):
Таким образом, одна из констант 0; 1 является формулой над ff ; g. Подставляя ее в отрицание, получим другую константу.
Теорема Поста Доказательство теоремы Поста
Лемма о немонотонной функции
Лемма. Если f 2= M, то 2 [ff ; 0; 1g].
Теорема Поста Доказательство теоремы Поста
Лемма о немонотонной функции
Лемма. Если f 2= M, то 2 [ff ; 0; 1g].
Доказательство. Пусть f 2= M.