Теорема Поста о полнотеДля того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T 0, T 1, L, S, M. Доказательство. Докажем необходимость этого условия. Пусть система N = { f 1, f 2,... fs,...} полна в Р 2, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T 0, T 1, L, S, M. Докажем от противного, пусть N Í Q, очевидно, [ N ] Í [ Q ] = Q, но [ N ] = P 2, т.к. N – полна в Р 2, отсюда Р 2= Q, но это не так. Необходимость доказана. Докажем достаточность. Пусть F = { f 0, f 1, fL, fm, fs }, где f 0Ï T 0, f 1Ï T 1, fL Ï L, fs Ï S и fm Ï M. Покажем, что суперпозицией функций системы F можно получить полную систему G = { x 1& x 2, 1. Пусть g (x) = f 0(x, …, x). Тогда g (0) = f (0, …, 0) = 1. Далее возможны два случая: g (1) = 1. Тогда g (x) º 1. Функция h (x) = f 1(g (x), …, g (x)) = f 1(1, …, 1) = 0, т.е. h (x) º 0. Получили константы 0 и 1; g(1) = 0. Тогда g (x) = В обоих случаях получили обе константы. 2. По лемме о немонотонной функции суперпозицией над { fm, 0, 1} можно получить отрицание. 3. По лемме о нелинейной функции суперпозицией над { fL, 1, Следствие. Всякий замкнутый класс функций из Р 2, не совпадающий с Р 2 содержится, по крайней мере, в одном из замкнутых классов T 0, T 1, L, S, M. Действительно, если N не является подмножеством Q, то [ N ] = P 2, что неверно.
|
}.
} можно получить конъюнкцию. Теорема доказана.
