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

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

Пример.

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

Решение.

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

Таблица 59

Полином Жегалкина имеет вид: 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.

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

Пример 49.

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

Решение.

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

Таблица 60

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

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