Двоичной функции

Многочлен Жегалкина и действительный многочлен

Будем рассматривать формулы над классом

.

Определение 2.11. Многочленом Жегалкина (приведенным многочленом) называется представление двоичной функции формулой вида:

,

где .

Теорема 2.12. Для каждой двоичной функции существует единственный многочлен Жегалкина.

Доказательство. Покажем, что по таблице функции однозначно определяются коэффициенты её многочлена Жегалкина. Воспользуемся методом неопределенных коэффициентов. Будем последовательно вычислять значения искомого многочлена на наборе из одних нулей, затем на наборе с одной единицей, затем — с двумя, и т.д. В результате получим систему:

Из первого уравнения находим , из второго , …, из (n + + 1)-го — , из (n + 2)-го — , …, из последнего — . Теорема доказана.

Определение 2.13. Конъюнкции , входящие в многочлен Жегалкина, называются одночленами. Степенью одночлена называется число входящих в него переменных (ранг конъюнкции). Степенью нелинейности (порядком) многочлена Жегалкина функции (обозначается ) называют максимальную из степеней входящих в него многочленов.

Многочлен Жегалкина можно вычислять исходя из ДНФ или СДНФ функции , выразив операции «дизъюнкция» и «отрицание» через операции «конъюнкция» и «сложение по модулю два»:

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