Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов 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) = . По лемме о несамодвойственной функции суперпозицией над { fs, } можно получить одну из констант, например, 0. Тогда f 0(0, …, 0) = 1 есть другая константа.

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

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

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

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





Дата публикования: 2014-10-20; Прочитано: 384 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...