Студопедия

КАТЕГОРИИ:

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



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

Читайте также:
  1. II закон термодинамики. Теорема Карно-Клаузиуса
  2. II. (Теорема Больцано-Вейерштрасса).
  3. IV. Магическая сила правильной постановки вопросов
  4. А с балкона в полиэтиленовом мешке была занесена земля (примерно 20 кг), поставлена на кровать и залита водой до краев мешка.
  5. А. Поставить реакцию иммобилизации бледных трепонем
  6. Административная ответственность. Виды административных наказаний. Исполнение постановлений по делам об административных правонарушениях.
  7. Аудит расчетов с поставщиками и подрядчиками
  8. Аудит расчетов с поставщиками и покупателями
  9. Б) теория фирмы и транзакционных издержек. Теорема Р.Г.Коуза (1910)
  10. Базисные условия договора поставки.

Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов 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; просмотров: 22; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
L – класс линейных функций. | Составим критериальную таблицу для другой полной системы функций из Р2: {0, 1, x1x2, x1Åx2}.
lektsii.com - Лекции.Ком - 2014-2020 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты