Теорема Поста о полноте

Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T ₀, T ₁, L, S, M.

Следствие. Всякий замкнутый класс функций из Р ₂, не совпадающий с Р ₂ содержится, по крайней мере, в одном из замкнутых классов T ₀, T ₁, L, S, M.

1. Покажем, что система функций { f ₁ = x ₁ x ₂, f ₂ =0, f ₃ =1, f ₄ = x ₁Å x ₂Å x ₃} полна в Р ₂. Составим таблицу, которая называется критериальной:

2.

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

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, { f ₂, f ₃, f ₄}Î L, { f ₁, f ₃, f ₄}Î T ₁, { f ₁, f ₂, f ₄}Î T ₀, { f ₁, f ₂, f ₃}Î M.

2 Мы знаем, что система { x ₁| x ₂} – полна в Р ₂. Составим для нее критериальная таблица? x ₁| x ₂= = x ₁ x ₂Å1.

3. Составим критериальную таблицу для другой полной системы функций из Р₂: из Р₂: {0, 1, x ₁ x ₂, x ₁Å x ₂}.

Согласно критериальной таблице, полной является и система {0, 1, x ₁ x ₂, x ₁Å x ₂}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где а равны 0, если члены х х ... х , в полиноме отсутствуют.

4. Выясним, полна ли система . Составим критериальную таблицу, очевидно . Чтобы показать, что , достаточно найти одну функцию и . Возьмем , удовлетворяющую требуемым условиям. Если f S \ T ₀, то f (0,..., 0) = 1, f (1,..., 1)=0, следовательно, f M, f T ₁. Рассмотрим функцию h = x ₁ x ₂ x ₂ x ₃ x ₁ x ₃=1, набор ее значений (11101000), h S \ T ₀, но h L. Следовательно, критериальная таблица имеет вид:

	Т 0	Т 1	L	M	S
L T 1	-	+	+	-	-
S \ T 0	-	-	-	+	-

и А – полная система функций.

Определение. Система функций { f ₁,..., f_s,...} называется базисом в Р ₂,если она полна в Р ₂, но любая ее подсистема не будет полной. Например, система функций { x ₁& x ₂, 0, 1, x ₁ x ₂ x ₃} – базис.

Рассмотрим набор функций f, g и h, представленный в следующей таблице:

Таблица 1

Функция f, очевидно, не сохраняет 0 и 1, но является самодвойственной. Функция g(X₁,X₂,X₃)= 1+X₁+X₂ + X₁ * X₃ + X₁ * X₂ * X₃ является несамодвойственной, немонотонной и нелинейной. По лемме 5.1 получаем, что , функция , а функция . Подставив X₂=0 в g получим g₃(X₁,X₃)= g(X₁,0,X₃)= 1 + X₁ + X₁ * X₃. Тогда . Таким образом, мы с помощью f и g сумели выразить обе функции полной системы и, следовательно, система функций {f, g } полная.

Не нашли, что искали? Воспользуйтесь поиском: