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

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

.

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

,

где .

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

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

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

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

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

Пример 2.14.

;

=.

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

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

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

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

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

,

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

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

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

2.3. Теорема о разложении в ряд Фурье

Сопоставим каждому двоичному вектору линейную двоичную функцию(сокращенно ()), и определим функции:

Например, векторам исоответствуют функции

и

соответственно.

Всего имеется функций вида. Как показывает следующая лемма, они образуют ортогональную систему функций.

Лемма 2.16. Для любых векторов справедливы равенства:

Доказательство. Сначала заметим, что

Поскольку линейная функция припринимает значение 0 ровно. Теперь

Отсюда и следует утверждение леммы.

Теорема 2.17 (о разложении в ряд Фурье). Для всякой двоичной функции имеется единственное разложение вида: , где коэффициентыявляются рациональными числами. При этом значения коэффициентов определяются равенствами

.

Доказательство. Докажем сначала, что указанная сумма представляет функцию . Имеем:

поскольку в последней сумме будет только одно нулевое слагаемое при y = x.

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

Отсюда . Так какb — произвольный вектор из , получаем требуемое утверждение.

Определение 2.18. Коэффициенты ,, называются коэффициентами Фурье функции.

Л е к ц и я 3