Представление функции в виде полинома Жегалкина
1. Представим любую функцию формулой над { x 1& x 2, Пример 2. (x 1 Надо помнить, что четное число одинаковых слагаемых в сумме по mod 2 дает 0. 2. Метод неопределенных коэффициентов. Он удобен, если функция задана таблицей. Пример 3. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f (x 1, x 2, x 3) = (01101001) = а 0 Å а 1 х 1Å Å а 2 х 2 Å а 3 х 3 Å b 1 x 1 x 2 Å b 2 x 2 x 3 Å b 3 x 1 x 3 Å cx 1 x 2 x 3. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) f (0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим f (0, 0, 0) = а 0, отсюда а 0 = 0. f (0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: f (0, 0, 1) = а 0 Å а 3, т.к. а 0 = 0, отсюда а 3 = 1. Аналогично, f (0, 1, 0) = 1 = а 2, f(0, 1, 1) = 0 = а 2 Å а 3 Å b 2 = b 2 = 0; а 1 = 1; 0 = а 1 Å а 3 Å b 3 = b 3 = 0; 0 = а 1 Å а 2 Å b 1 = b 1 = 0; 1 = 1 Å 1 Å 1 Å c; c = 0; f (x 1, x 2, x 3) = x 1 Å x 2 Å x 3. 3. Многочлен Жегалкина можно получить также с помощью треугольника Паскаля по единицам его левой стороны по таблице следующим образом. Построим многочлен Жегалкина для функции f = (10011110). Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю для двух соседних элементов предыдущей строки. Левая сторона треугольника для функции f содержит шесть единиц. Многочлен Жегалкина будет содержать шесть слагаемых. Первая единица треугольника соответствует набору (000). Первое слагаемое многочлена есть 1. Третья снизу единица в левой стороне треугольника соответсвует набору (101). В качестве слагаемого многочлена берем x 1 x 3. Аналогично для других единиц треугольника. Слева от наборов показаны слагаемые многочлена Жегалкина.
Тогда
|
} и сделаем замену 
(x 2 
