На головну

Теорема Поста про повноту

  1. I.4.6) Постанови государя.
  2. Put (set) the book on the shelf.- Поставьтекнігу на
  3. Z. Прочитайте наступні слова і поєднання слів 1-2 рази про себе, потім вголос і постарайтеся запам'ятати їх.
  4. Аксіома Больцано-Вейєрштрасса і теорема про стягують системі відрізків
  5. Алгоритм проведення біопроби (реакція нейтралізації на мишах) при діагностиці газової гангрени. Мета постановки цієї реакції для визначення виду збудника.
  6. Алгоритм проведення біопроби (реакція нейтралізації на мишах) при діагностиці правця. Мета постановки цієї реакції для лабораторного діагнозу правця.
  7. альтернативне зіставлення

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

Доведення. Доведемо необхідність його запровадження. нехай система

N = {f1, f2, ...fs, ...} Повна в Р2, Покажемо, що тоді вона не лежить цілком в Q, Де через Q позначимо будь-який з класів T0, T1, L, S, M. Доведемо від противного, нехай N I Q, Очевидно, [N] I [Q] = Q, Але [N] = P2, Тому що N - Повна в Р2, звідси Р2=Q, але це не так. Необхідність доведена.

Доведемо достатність. нехай F = {f0, f1, fL, fm, fs}, Де f0IT0, f1IT1, fLIL, fsIS и fmIM. Покажемо, що суперпозицией функцій системи 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, Що невірно.



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   Наступна

Елементи математичної логіки. | Приклад 2. | Приклад 4. | Деякі властивості елементарних функцій | принцип подвійності | Лемма про несамодвойственной функції | Теорема про розкладання функції по змінним | повні системи | Теорема про достатність чотирьох функцій. | можливість розв'язання |

© um.co.ua - учбові матеріали та реферати