Определение. Пусть M Í Р₂. Замыканием М называется множество всех функций из P₂ , которые можно выразить формулами над М. Замыкание М обозначается [M].

Определение. Множество функций М называется замкнутым классом, если [M]=M.

Замечание. В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному: М – полная система, если [M] = P₂.

Пример 18.

1) P₂ – замкнутый класс.

2) A = {f(x₁, ..., x _n)|f(1, 1, ..., 1) = 0} – незамкнутый класс.

Возьмем формулу над этим множеством. Пусть f, g₁, ..., g _nÎA, т. е. f(1, 1, ..., 1) = 0, g₁(1, 1, ..., 1) = 0, тогда f(g₁, ..., g _n)Î[A]. Посмотрим, принадлежит ли функция f(g₁, ..., g _n) множеству А.

f(g₁(1, ..., 1), g₂(1, ..., 1), ..., g _n(1, ..., 1) = f(0, ..., 0)), но f(0, ..., 0) не обязано быть равным 0.

Пусть, например, g(x₁, x₂) = x₁ Å x₂, , т. е.  и . Построим формулу , рассмотрим функцию  на наборе , т. е. формула не входит в А и А – незамкнутый класс.

Важнейшие замкнутые классы в Р₂

1) Т ₀ – класс функций, сохраняющих константу 0

Т₀ = { f(x₁, ..., x _n)|f(0, ..., 0) = 0}. Покажем, что Т₀ является собственным подмножеством Р₂, т. е. Т₀ ¹ Æ и Т₀ Ì  (не совпадает с Р₂). Для этого достаточно привести примеры функций, входящих в Т₀, и примеры функций из Р₂, не входящих в Т₀: x₁&x₂, x₁Úx₂, xÎТ₀  и x₁|x₂, x₁ x₂, ÏТ₀. Покажем далее, что [Т₀] = Т₀. Вложение Т₀Í [Т₀] очевидно, так как по определению формулы любая функция из Т₀ является формулой над Т₀ и, следовательно, принадлежит [Т₀]. Покажем, что [Т₀]ÍТ₀. Для этого надо показать, что = f(f₁, ..., f _m)Î Т₀, если все функции f, f₁, f₂, f₃, ..., f _mÎТ₀. Надо заметить, что в формуле в качестве функции  могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т₀, поэтому достаточно показать, что если Ф = f (f₁, ..., f _m)Î [Т₀], то Ф(0, ..., 0). Действительно, Ф = f (f₁(0, ..., 0), (0, ..., 0), ... , ) = f (0, ..., 0) = 0, так как все функции .

Таким образом .

Число функций, зависящих от n переменных и принадлежащих Т₀, будет равно

2) T₁ – класс функций, сохраняющих константу 1

T₁ = {f(x₁, ...) |f(1, 1, ...) = 1}; x₁&x₂, x₁Úx₂, xÎT₁, х₁Åх₂, x₁ x₂ÏT₁, следовательно, Т₁ – собственное подмножество Р₂

Покажем, что [T₁]Í T₁, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т₁, достаточно показать Ф = f(f₁, ..., f _n)ÎT₁, если f, f₁, ..., f _nÎT₁. Найдем Ф(1, ..., 1) = f( f₁(1, ..., 1), ..., f _n(1, ..., 1)) = f(1, ..., 1) = 1, следовательно, Ф = f(f₁, ..., f _n)ÎT₁, отсюда следует [T₁] = T₁.

3) S – класс самодвойственных функций

S = {f(x₁, ...)|f* = f }; x, , x₁Åx₂Åx₃ÎS, x₁&x₂, x₁Úx₂, x₁Åx₂ÏS, следовательно, S – собственное подмножество Р₂. |S(n)| = . Покажем, что [S]ÍS. Ф = f (f₁, ... ,f _n) Î [S], если f, f₁, ... , f _nÎS, покажем, что ФÎS. По принципу двойственности, Ф* = f*(f₁*, ..., f _n*) = f(f₁, ... , f _n) = Ф, отсюда S – замкнутый класс.

4) L – класс линейных функций

L = {f(x₁, ...)|f = c₀Åc₁x₁Å...Åc _n x _n}; очевидно, L¹ Æ, с другой стороны L¹ P₂, так как x₁&x₂ÏL. Заметим, что тождественная функция принадлежит L и |L(n)| = 2ⁿ⁺¹. Покажем, что [L]ÍL. Рассмотрим Ф = f (f₁, ..., f _m), где f, f₁, ..., f _mÎL. Тогда Ф = а₀Åа₁(с₁₀Åс₁₁х₁Å Å...Åc_1n x _n1)Åa₂(c₂₀ Åc₂₁x₁ Åc₂₂x₂Å...Åc_2n x _n2)Å...Åa _m(c _m0Åc _m1x₁Å...Åc _mn x _nm) =

= в₀Åв₁х₁Å...Åв _n х _n , следовательно ФÎL.

5) М – класс монотонных функций

Определение. Набор = (a₁, ..., a_n) предшествует набору = (b₁, ..., b_n ) и обозначается , если для , например:  = (0010), = (0110), тогда .

Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования ( ) является отношением порядка на множестве наборов длины n. Множество таких наборов будет частично упорядоченным множеством по отношению к операции предшествования.

Определение. Функция f(x ₁ , ..., x_n) называется монотонной, если для любых двух наборов и , таких что , выполняется f( ) f( ). Функции 0, 1, x, x₁&x₂, x ₁ Ú x₂Î M, x₁Åx₂, x₁~x₂Ï M.

Для числа монотонных функций, зависящих от n переменных, существуют оценки сверху и снизу, но точное число сосчитать не удается. Покажем, что М – замкнутый класс. Рассмотрим функцию ФÎ[M], Ф = f(f₁, ..., f _m), где f, f₁, ..., f _mÎM, причем можем считать, что все они зависят от n переменных. Пусть набор  = (a₁, ..., a_n),

  = (b₁, ..., b_n) и   . Рассмотрим

Ф(a₁, ..., a_n) = f (f₁(a₁, ..., a_n), …, f _m(a₁, ..., a_n)),

Ф(b₁, ..., b_n) = f (f₁(b₁, ..., b_n), ..., f _m(b₁, ..., b_n));

, тогда набор (f₁( ), ..., f _m( )) , и так как , то , то есть Ф = f (f₁, ..., ) – монотонная функция.

Классы T₀, T₁, L, S, M пересекаются, но не совпадают, что видно из табл. 3.21, где «+» означает, что функция принадлежит данному классу и «–» – не принадлежит.

Таблица 3.21

	T0	T1	L	S	M
x	+	+	+	+	+
	–	–	+	+	–
0	+	–	+	–	+
1	–	+	+	–	+
x1x2	+	+	–	–	+

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

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

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

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

Таблица 3.22

Из табл. 3.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 (табл. 3.23).

Таблица 3.23

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

Таблица 3.24

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

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

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

Если , то f (0, ..., 0) = 1, f (1, ..., 1)=0, следовательно, , f T₁. Рассмотрим функцию h = x₁x₂ x₂x₃ x₁x₃ = 1, набор ее значений (11101000), , но . Cледовательно, критериальная таблица имеет вид (табл. 3.25) и А – полная система функций.

Таблица 3.25

	Т0	Т1	L	M	S
L T1	–	+	+	–	–
S\T0	–	–	–	+	–

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