Теорема Жегалкина

Каждая функция из может быть представлена в виде полинома Жегалкина единственным образом.

Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:

, s = 0, 1,..., n.

Определение. Функция f (x ₁,..., x_n), полином Жегалкина для которой имеет следующий линейный относительно переменных вид: f = а _{0 Å} а ₁ х _{1 Å} а ₂ х _{2 Å}... Å а_nх_n, называется линейной.

Лемма о нелинейной функции. Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.

Определение: Говорят, что функция f (x ₁,..., x _n) сохраняет константу a Î {0, 1}, если f (a, …, a) = a.

Пример 4. Функция xy сохраняет 0, сохраняет 1. Функция x ® y сохраняет 1 и не сохраняет 0.

Замыкание и замкнутые классы

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

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

Пример 1.

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

2) Множество {1, x _1Å x ₂} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x _{1 Å} x ₂}] = { f (x ₁,..., x_n) = c _{0 Å} c ₁ x _{1 Å} Å c_nx_n }. Действительно, по определению формулы над М, функция f (G ₁, x ₃), где f – есть сумма по модулю 2, G ₁ – функция х _{1 Å} х ₂, будет формулой над М: f (G ₁, x ₃) = (x _{1 Å} x ₂) Å x ₃.

З амечание. В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному:

М – полная система, если [ M ] = P ₂.

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

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

Т ₀ = { f (x ₁,..., x_n | f (0,..., 0) = 0, n = 1, 2,...}.

Примеры функций, входящих в Т ₀: x ₁& x ₂, x _1Ú x ₂, xÎТ ₀и примеры функций из Р₂, не входящих в Т ₀: x ₁| x ₂, x ₁ x ₂, Ï Т ₀.

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

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

T ₁ = { f (x ₁,...) | f (1, 1,...) = 1};

Функции x ₁& x ₂, x _1Ú x ₂, xÎT ₁, х _1Å х ₂, x ₁ x _2Ï T ₁, следовательно Т ₁ – собственное подмножество Р ₂.

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

S = { f (x ₁,...)| f * = f };

Функции x, , x _1Å x _2Å x _3Î S, x ₁& x ₂, x _1Ú x ₂, x _1Å x _2Ï S, следовательно, S – собственное подмножество Р ₂. | S (n)| = .

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

L = { f (x ₁,...)| f = c _0Å c ₁ x _1Å...Å c_nx_n };

Заметим, что тождественная функция принадлежит L и | L (n)| = 2 ^{n +1}.

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

Определение. Набор = (a ₁,..., a _n) предшествует набору = (b₁,..., b _n) и обозначается , если для 1£ i £ n a_i £ b_i, например: = (0010), = (0110), тогда . Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования () является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.

Определение. Функция f (x ₁,..., x_n) называется монотонной, если для двух наборов и , таких что , выполняется f () f ().

Функции 0, 1, x, x ₁& x ₂, x ₁Ú x _{2 Î} M, x ₁¯ x ₂, x _{1 Å} x ₂, x ₁ ~ x _{2 Ï} M.

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

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

	T 0	T 1	L	S	M
x	+	+	+	+	+
	-	-	+	+	-
	+	-	+	-	+
	-	+	+	-	+
x 1 x 2	+	+	-	-	+

A ={ x, , 0, 1, x ₁ x ₂) не является полной системой функций так как всегда есть функции Î Р ₂ не входящие в эти классы.