2.2.3.4. Теорема Поста о функциональной полноте

Теорема Поста (признак полноты системы булевых функций). Для того чтобы система булевых функций {f1, …, fm} была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классов T0, T1, L, M, S нашлась хотя бы одна функция fi из системы, не принадлежащая этому классу.

Пример.

Выяснить к каким функционально замкнутым классам принадлежит булева функция f=01001110, используя теорему Поста.

Решение.

Строим таблицу значений и треугольник Паскаля (табл. 59):

Таблица 59

Слагаемые полинома Жегалкина x1 x2 x3 f g Треугольник Паскаля
1 0 0 0 0 0 f = 0 1 0 0 1 1 1 0
x3 0 0 1 1 1 1 1 0 1 0 0 1
x2 0 1 0 0 0 0 1 1 1 0 1
x2x3 0 1 1 0 1 1 0 0 1 1
x1 1 0 0 1 1 1 0 1 0
x1 x3 1 0 1 1 1 1 1 1
x1 x2 1 1 0 1 0 0 0
x1 x2 x3 1 1 1 0 0 0

Полином Жегалкина имеет вид: f = x3 + x2x3 + x1 + x1 x3. f(0, 0, 0) = 0 ? fÎT0; f(1, 1, 1) = 1 ? fÏT1; f(0, 0, 0) = f(1, 1, 1), а наборы (0, 0, 0) и (1, 1, 1) являются противоположными, то f Ï S; так как в полиноме Жегалкина присутствуют слагаемые, представляющие собой конъюнкцию нескольких переменных, то f Ï L; сокращенная ДНФ функции имеет вид: , так как она содержит отрицания, то f Ï M.

Сведем полученные данные:

T0 T1 S L M
f + - - - -

Пример 49.

Доказать полноту системы {+, U, 1}.

Решение.

Введем обозначения: f1 = x1 + x2, f2 = x1 U x2, f3 = 1. Построим единую таблицу для функций (табл. 60).

Таблица 60

Слагаемые х1 х2 f1 = х1+х2 D Паскаля f2 =х1Uх2 D Паскаля f3 =1 D Паскаля
1 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1
х2 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0
х1 2 1 0 1 1 1 1 1 0 1 0 0
х1х2 3 1 1 0 0 1 1 1 0

Полином Жегалкина:

f T0 T1 L M S
f1 + - + - -
f2 + + - + -
f3 - + + + -

Поскольку для каждого из пяти функционально замкнутых классов нашлась функция, не принадлежащая этому классу (в каждом столбце имеется хотя бы один минус), то система булевых функций {+, U, 1} является полной.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 2.2.3.4. Теорема Поста о функциональной полноте:

  1. Система критериев технологичности информатизации
  2. 4.2. Виды функциональных состояний человека
  3. §61. Функциональные ряды
  4. 24(5).1. Пространство целей как множество знаний суггестивной угрозы
  5. Функциональные ряды.
  6. МНОГОЗНАЧНАЯ ЛОГИКА
  7. Теорема 15. Всякая вещь может быть косвенной причиной удовольствия, неудовольствия или желания.
  8. Теорема 17. Если мы воображаем, что вещь, которая обыкновенно причиняет нам неудовольствие, имеет что-либо сходное с другой вещью, обыкновенно причиняющей нам столь же большое удовольствие, то мы будем в одно и то же время и ненавидеть и любить ее.
  9. §6. Функциональные стили в их отношении к выразительности речи
  10. §1.5. Полнота, замкнутость. Теорема Поста о полноте
  11. Важнейшие замкнутые классы
  12. 2.2.3.4. Теорема Поста о функциональной полноте
  13. Функциональные последовательности и ряды