Базис булевых функций. Теорема Поста

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

	Сохрание 0,	Сохрание 1,	Самодвойственность, S	Монотонность, M	Линейность, L
			+		+
	+	+		+
	+				+

В таблице знаком «+» обозначено принадлежность функции к данному классу.

Для того чтобы функции составляли базис, по теореме Поста необходимо, чтобы хотя бы одна функция не сохраняла 0, хотя бы одна функция не сохраняла 1, хотя бы одна функция не была самодвойственной, хотя бы одна функция не была монотонной и хотя бы одна функция не была линейной. Из вышеприведенной таблицы видно, что данный набор функций составляет базис. Причем для базиса достаточно первых двух функций, то есть отрицания и дизъюнкции.

Проверим возможность получения из заданной булевой функции f путем суперпозиции некоторой булевой функции . Для этого проверим f на принадлежность классам Поста.

По таблице истинности , следовательно .

, следовательно .

Построим по таблице истинности двойственную функцию , значения которой можно получить из значений функции f с помощью инвертирования (т.е. переписывания в обратном порядке) и поэлементного отрицания.

f

Исходя из таблицы истинности , следовательно .

Рассмотрим два набора и . Согласно лексикографического порядка , но . Поэтому .

Степень полинома Жегалкина для заданной функции f равняется 3, поэтому .

Заданная функция f принадлежит к функционально полному в слабом значении классу, так как она немонотонная и нелинейная. Поэтому добавление констант 0 и 1 в класс позволит получить из f путем суперпозиции любую булеву функцию .