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

 

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

Пример 2. .

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

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

Пример 3. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f(x₁, x₂, x₃) = (01101001) = а_{0 Å}а₁х₁ Åа₂х_{2 Å}а₃х_{3 Å}b₁x₁x_{2 Å}b₂x₂x₃ Å b₃x₁x₃ Å cx₁x₂x₃. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) f(0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим f(0, 0, 0) = а₀, отсюда а₀ = 0. f(0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: f(0, 0, 1) = а_{0 Å}а₃, т.к. а₀ = 0, отсюда а₃ = 1. Аналогично, f(0, 1, 0) = 1 = а₂, f(0, 1, 1) = 0 = а_{2 Å}а_{3 Å}b₂ b₂ = 0; а₁ = 1; 0 = а_{1 Å}а_{3 Å}b₃ b₃ = 0; 0 = а_{1 Å} а_{2 Å}b₁ b₁ = 0; 1 = 1 Å1 Å1 Åc; c = 0; f(x₁, x₂, x₃) = x_{1 Å}x_{2 Å}x₃.

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

 

N	x1x2x3	f	Треугольник Паскаля
x3 x2 x2x3 x1 x1x3 x1x2 x1x2x3			1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0

 

Тогда