Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




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

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

N = {f1, f2, ...fs, ...} полна в Р2, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T0, T1, L, S, M. Докажем от противного, пусть N Í Q, очевидно, [N] Í [Q] = Q, но [N] = P2, т.к. N – полна в Р2, отсюда Р2=Q, но это не так. Необходимость доказана.

Докажем достаточность. Пусть F = {f0, f1, fL, fm, fs}, где f0ÏT0, f1ÏT1, fLÏL, fsÏS и fmÏM. Покажем, что суперпозицией функций системы F можно получить полную систему G = {x1&x2, }.

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

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

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

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

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

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

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


Поделиться:

Дата добавления: 2014-11-13; просмотров: 106; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты