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. Теорема Поста о функциональной полноте: