Diskretka6

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

Лемма о несамопряженной функции

Лемма. Если 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= S, то 0; 1 2 [ff ; g].

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

Лемма о несамопряженной функции

Лемма. Если f 2= S, то 0; 1 2 [ff ; g].

Пример. Пусть f (x; y; z) = x _ yz. Имеем

0 f (1; 0; 0) = f (0; 1; 1) 6= f (0; 1; 1) = 1:

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

Лемма о несамопряженной функции

Рассмотрим формулу g(x) = f (x; x; x).

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

Лемма о несамопряженной функции

Рассмотрим формулу g(x) = f (x; x; x).

g(0) = f (1; 0; 0) = 1; g(1) = f (0; 1; 1) = 1

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

Лемма о несамопряженной функции

Рассмотрим формулу g(x) = f (x; x; x).

g(0) = f (1; 0; 0) = 1; g(1) = f (0; 1; 1) = 1

Таким образом, константа 1 является формулой над ff ; g.

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

Лемма о несамопряженной функции

Рассмотрим формулу g(x) = f (x; x; x).

g(0) = f (1; 0; 0) = 1; g(1) = f (0; 1; 1) = 1

Таким образом, константа 1 является формулой над ff ; g. Константа 0 совпадает с формулой g(x) = f (x; x; x).