02.2. Многочлен Жегалкина и действительный многочлен двоичной функции

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

.

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

,

Где .

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

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

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

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

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

Пример 2.14.

;

=.

Двоичные функции можно также задавать многочленами, в которых используются операции сложения, вычитания и умножения действительных чисел. Так, непосредственно проверкой убеждаемся, что

Поскольку каждую двоичную функцию можно задать своим многочленом Жегалкина, СДНФ или СКНФ, то, заменив все используемые в этих формулах операции на их выражения (по приведенным выше формулам) и, раскрыв затем скобки, получаем для всякой двоичной функции эквивалентную запись в виде некоторого действительного многочлена. Вместе с тем, можно заметить, что такая запись неоднозначна. Например, функцию можно представить действительными многочленами вида:

Перечисленные многочлены при и принимают значения 1 и 0 соответственно. Все многочлены в этом примере обладают той особенностью, что они содержат степени переменной , в то же время для двоичных переменных очевидны равенства:

Если отказаться от использования переменных в степенях выше первой, то неоднозначность представления двоичных функций можно исключить.

Теорема 2.15. Любая двоичная функция однозначно представляется в виде следующего действительного многочлена:

,

Все коэффициенты которого являются целыми числами.

Доказательство. Полностью аналогично тому, которое было приведено в теореме 2.12. Необходимо только заменить операцию «» на «+».

Ниже, говоря «действительный многочлен», будем всюду иметь в виду определенный в теореме 2.15 многочлен .

< Предыдущая		Следующая >