Теорема Поста

Существует метод проверки полноты системы, называемый теоремой Поста. Она основывается на выделении пяти классов Поста булевых функций:

класс функций сохраняющих 0

,

класс функций сохраняющих 1

,

класс самодвойственных функций

,

класс монотонных функций

, где подразумевается стандартный порядок булевой алгебры (при котором существуют и несравнимые элементы!),

класс линейных функций

, т.е. функция представима в виде полинома Жегалкина первой степени.

Можно доказать, что все эти классы являются замкнутыми, т.е. любая комбинация функций из одного класса остаётся в том же классе.

Теорема (Поста):система булевых функций полна тогда и только тогда, когда она целиком не лежит ни в одном из классов Поста.теорема Поста, которая гласит: для того чтобы система функций была базисной, необходимо и достаточно, чтобы она включала в себя хотя бы одну функцию, не принадлежащую 0, 1, 2, 3 и 4 классам

Рассмотрим пример: . Необходимо проверить полноту системы.

Функция принимает следующие значения:. Проверка принадлежности первых четырёх классов поста может быть проведена очень быстро. Для проверки линейности построим представление данных функций в виде полинома Жегалкина:

Поучается, что нелинейна.

Поучается, что нелинейна.

Принадлежность классам Поста обобщим в таблице:

Система функций является полной, более того, полной является уже система.Выразим стандартный базисчерез функцию. Воспользуемся тем, чтоне сохраняет ни 0, ни 1, значит:

Так как -- несамодвойственна, выразим константы через отрицание. Для этого найдём такой вектор, что. Видно, что это выполняется при. Значит,. Тогда 0 можно получить с помощью отрицания.

-- нелинейна, выразим коньюнкцию из полинома Жегалкина этой функции. Можно получить, что . Тогда

откуда .