Пусть f(x₁, ..., x _n)ÎP₂, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как {x₁&x₂, x₁Åx₂, 0, 1} полна в Р₂. В силу свойства x& (yÅz) = xyÅ xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х ^, х ^, ..., х , соединенных знаком Å. Такой полином называется полиномом Жегалкина.

Общий вид полинома Жегалкина

где , s = 0, 1, ..., n, причем при s = 0 получаем свободный член а₀.

Представление функции в виде полинома Жегалкина

1. Представим любую функцию формулой над {x₁&x₂, } и сделаем замену . Этот способ удобен, если функция задана формулой.

Пример 16. (x₁ (x₂ x₃))(x₁ Ú x₂) x₃ = ( Ú Ú x₃)(x₁ Ú x₂) x₃ =

Надо помнить, что четное число одинаковых слагаемых в сумме по mod2 дает 0.

2. Метод неопределенных коэффициентов. Он удобен, если функция задана таблицей.

Пример 17. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f(x₁, x₂, x₃) = = (01101001) = а₀Åа₁х₁Åа₂х₂Åа₃х₃Åb₁x₁x₂Åb₂x₂x₃Åb₃x₁x₃Åcx₁x₂x₃.

Затем находим коэффициенты, используя значения функции на всех наборах. f(0, 0, 0) = 0, с другой стороны, подставив набор (0, 0, 0) в полином, получим f(0, 0, 0) = а₀, отсюда а₀ = 0. f(0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим f(0,0,1) = а₀ Å а₃, так как а₀ = 0, отсюда а₃ = 1. Aналогично f (0, 1, 0) = 1 =а₂, f(0, 1, 1) = 0 = = а₂ Å а₃ Å b₂ = b₂ = 0; а₁ = 1; 0 = а₁ Å а₃ Å b₃ = b₃ = 0; 0 = а₁ Åа₂ Å b₁ = = b₁ = 0; 1 = 1 Å 1 Å 1 Å c; c = 0; f(x₁, x₂, x₃) = x₁ Å x₂ Å x₃.

3. Многочлен Жегалкина можно получить также с помощью треугольника Паскаля по единицам его левой стороны по таблице следующим образом. Построим многочлен Жегалкина для функции

F = (10011110). Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю для двух соседних элементов предыдущей строки. Левая сторона треугольника для функции f содержит шесть единиц. Многочлен Жегалкина будет содержать шесть слагаемых. Первая единица треугольника соответствует набору (000). Первое слагаемое многочлена есть 1. Третья снизу единица в левой стороне треугольника соответствует набору (101). В качестве слагаемого многочлена берем x₁x₃. Aналогично для других единиц треугольника. Cлева от наборов показаны слагаемые многочлена Жегалкина (табл. 3.20).

Таблица 3.20

Тогда

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

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

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

.

Доказательство. Любая функция из  может быть представлена формулой над {x₁&x₂, x₁Åx₂, 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции  от  переменных. Мы знаем, что всего таких функций, т. е. их таблиц истинности, . Подсчитаем число различных полиномов Жегалкина от  переменных. Число наборов  равно числу всех подмножеств множества , сюда входит и пустое множество (если ). Число подмножеств множества из  элементов равно , а так как каждый набор входит с коэффициентом , принимающим два значения: 0 или 1, то число всевозможных полиномов будет . Так как каждому полиному соответствует единственная функция, число функций от  переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.

Определение. Функция , полином Жегалкина для которой имеет следующий линейный относительно переменных вид:

f = а₀Å а₁х₁Å а₂х₂Å ... Åа_n х_n называется линейной.