Полиномы Жегалкина

Элементарная конъюнкция называется монотонной, если она не содержит отрицаний переменных. Константа 1 (т.е. элементарная конъюнкция нулевого ранга) считается монотонной по определению. Выражение вида , где коэффициенты Î{0,1}, называется полиномом Жегалкина (или полиномом по модулю 2). Число r слагаемых полинома называют его длиной. Рассматривается также полином Жегалкина без слагаемых. Такой полином обозначают 0 и считают по определению, что он равен константе 0.

Наибольший из рангов элементарных конъюнкций, входящих в полином, называют степенью этого полинома. Степень полинома 0 считается неопределенной.

Теорема 3.Всякая булева функция единственным образом представима в виде полинома Жегалкина.

Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях.

Опишем методы построения полиномов Жегалкина.

1. Метод неопределенных коэффициентов. Булева функция f(x₁,…,x_n) приравнивается к полиному Жегалкина P(x₁,…,x_n) общего вида с неизвестными 2ⁿ коэффициентами. Затем для каждого ÎBⁿ составляется уравнение f( )=P( ) относительно коэффициентов A_i. Далее решается система из 2ⁿ уравнений относительно неизвестных 2ⁿ коэффициентов A_i. Причем в силу предыдущей теоремы решение всегда существует и единственно.

2. Метод основан на представлении функции в виде формулы над множеством {Ø, &, Ú} с последующей заменой Øx=xÅ1, .

3. Метод, базирующийся на преобразовании вектора значений функции. Над векторами из определяется (индукцией по n) операция Т.

Если n = 1 и , то .
Предположим, что операция Т уже определена для каждого вектора а из , и рассмотрим произвольный вектор а из . Пусть и , . Тогда .

Вектор значений функции f и вектор коэффициентов ее полинома Жегалкина связаны соотношениями и .

Пример 7. Проиллюстрируем эти методы для функции x®y.

1. Метод неопределенных коэффициентов.

x®y=f(x,y)=P(x,y)=a₀₀Åa₁₀xÅa₀₁yÅa₁₁xy.

(00) 1=a₀₀ Þ a₀₀=1.

(01) 1=a₀₀Åa₀₁ Þ a₀₁=0.

(10) 0=a₀₀Åa₁₀ Þ a₁₀=1.

(11) 1=a₀₀Åa₁₀Åa₀₁Åa₁₁ Þ a₁₁=1.

Таким образом, x®y=1ÅxÅxy.

2. .

3. =(1101). Расщепляем этот вектор на вектора длины 2. Выполняем для каждого из них преобразование T. Затем выполняем преобразование T для полученного вектора длины четыре. Результаты вычислений приведены в таблице. Таким образом, =(1,0,1,1) и x®y=1ÅxÅxy.