Функциональная полнота. Теорема Поста

Функциональный набор логических функций - это такой набор функций, который позволяет любую функцию математической логики описать с помощью функций данного набора.

Теорема Поста. Для того чтобы набор функций {f₁,f₂,……f_n} был функционально полный необходимо и достаточно, чтобы для всего набора функций в целом не выполнялись свойства сохранения нуля, сохранения единицы, линейности, монотонности и самодвойственности.

Полноту набора удобно определять по таблице Поста, в клетках которой ставится знак «+» или «-» в зависимости от того, обладает функция из этого набора тем или иным свойством. В силу теоремы Поста для полноты системы необходимо и достаточно, чтобы в каждом столбце был хотя бы один минус.

ПРИМЕР

Доказать, что набор функций6 дизъюнкция и отрицание является функционально полным.

	T0	T1	L	M	S
	-	-	+	-	+
V	+	+	-	+	-