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

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

Теорема Поста. Для того чтобы набор функций f(x ₁, …, x _n) был функционально полным, необходимо и достаточно, чтобы для всего набора функций в целом не выполнялось свойство сохранения нуля, сохранения единицы, линейность, монотонность и самодвойственность. Полноту набора функций удобно определять по таблице Поста, в котором знаком + или – обозначаются функции, принадлежащие (+) или не принадлежащие (-) к одному из этих классов.

В силу теоремы Поста, для полноты системы необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один минус.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1.

F={f₁,f₂}

	P0	P1	L	M	S
f1	+	+	-	+	+
f2	-	+	-	-	-

Решение. Так как f₁ и f₂ ÎР₁, следовательно, {f₁,f₂} не является полной.

Задача 2. Выяснить, является ли система функций f₁=x®1 и f₂=(x«)®x полной.

Решение. f₁=x®1º1

x	f

f₂=(x«)®x

x	y	x«	f

Составим таблицу Поста

	P0	P1	L	M	S
f1	-	+	+	+	+
f2	-	+	-	-	-

f₂=(x«)®x

= Многочлен Жегалкина второй степени линейностью не обладает, так как таблица содержит столбец со всеми плюсами, то исходная система булевых функций по теореме Поста не является полной.