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

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

Пример 2. (x ₁ (x ₂ x ₃))(x ₁ Ú x ₂) x ₃ = (x ₁Ú x ₂ Ú x ₃)(x ₁ Ú x ₂) x ₃ = (` x <sub>1</sub> x <sub>2</sub> Ú x <sub>1</sub> x <sub>3</sub> Ú x <sub>1</sub> x <sub>2</sub> Ú x <sub>2</sub> Ú x <sub>2</sub> x <sub>3</sub>) x <sub>3</sub> = (` x ₁ x ₃ Ú x ₂) x ₃ = x ₁ x ₃ x ₂ x ₃ = ((x ₁ x ₃Å1) x ₂Å1) x ₃ = x ₁ x ₂ x ₃Å x ₂ x ₃Å x ₃.

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

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

Пример 3. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f (x ₁, x ₂, x ₃) = (01101001) = а ₀ Å а ₁ х ₁Å Å а ₂ х ₂ Å а ₃ х ₃ Å b ₁ x ₁ x ₂ Å 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, отсюда а ₃ = 1. Аналогично, 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 ₃. Аналогично для других единиц треугольника. Слева от наборов показаны слагаемые многочлена Жегалкина.

	N	x 1 x 2 x 3	f	Треугольник Паскаля
x 3 x 2 x 2 x 3 x 1 x 1 x 3 x 1 x 2 x 1 x 2 x 3			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

Тогда

Дата добавления: 2014-12-27