Учебник по дискретной математике

Оглавление
n1.doc (26 стр.)
Скачать

Задачи

1. Доказать, что пересечение любых двух замкнутых классов замкнуто.

2. Доказать, что объединение двух замкнутых классов не всегда замкнуто.

Теорема Поста о полноте

Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T₀, T₁, L, S, M.

Доказательство. Докажем необходимость этого условия. Пусть система

N = {f₁, f₂, ...f_s, ...} полна в Р₂, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T₀, T₁, L, S, M. Докажем от противного, пусть N Q, очевидно, [N] [Q] = Q, но [N] = P₂, т.к. N – полна в Р₂, отсюда Р₂=Q, но это не так. Необходимость доказана.

Докажем достаточность. Пусть F = {f₀, f₁, f_L, f_m, f_s}, где f₀T₀, f₁T₁, f_LL, f_sS и f_mM. Покажем, что суперпозицией функций системы F можно получить полную систему G = {x₁&x₂, }.

1. Пусть g(x) = f₀(x, …, x). Тогда g(0) = f( 0, …, 0) = 1. Далее возможны два случая:

g(1) = 1. Тогда g(x)  1. Функция h(x) = f₁(g(x), …, g(x)) = f₁(1, …, 1) = 0, т.е. h(x)  0. Получили константы 0 и 1;

g(1) = 0. Тогда g(x) =. По лемме о несамодвойственной функции суперпозицией над {f_s, } можно получить одну из констант, например, 0. Тогда f₀(0, …, 0) = 1 есть другая константа.

В обоих случаях получили обе константы.

2. По лемме о немонотонной функции суперпозицией над {f_m, 0, 1} можно получить отрицание.

3. По лемме о нелинейной функции суперпозицией над {f_L, 1, } можно получить конъюнкцию. Теорема доказана.

Следствие. Всякий замкнутый класс функций из Р₂, не совпадающий с Р₂ содержится, по крайней мере, в одном из замкнутых классов T₀, T₁, L, S, M. Действительно, если N не является подмножеством Q, то [N] = P₂, что неверно.