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

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

Таблица 22

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

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

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

Таблица 23

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

Таблица 24

Согласно критериальной таблице, полной является и система

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

Пример 22. Выясним, полна ли система . Составим критериальную таблицу. Очевидно, . Чтобы показать, что , достаточно найти одну функцию и . Возьмем , удовлетворяющую требуемым условиям.

Если 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. Следовательно, критериальная таблица имеет вид (табл. 25) и А – полная система функций.

Таблица 25

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

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