Примеры использования теоремы Поста

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

	Т 0	Т 1	L	M	S
x 1 x 2	+	+	-	+	-
	+	-	+	+	-
	-	+	+	+	-
x 1Å x 2Å x 3	+	+	+	-	+

x 1 x 2 x 3	x 1Å x 2Å x 3
0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

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

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

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

	Т 0	Т 1	L	M	S
x 1| x 2	-	-	-	-	-

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

	Т 0	Т 1	L	M	S
	+	-	+	+	-
	-	+	+	+	-
x 1 x 2	+	+	-	+	-
x 1Å x 2	+	-	+	-	-

Согласно критериальной таблице, полной является и система {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 ₃} – базис.

Дата добавления: 2014-01-04