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

Определение:

Формула вида

[math]\displaystyle{ \alpha_0 \oplus \alpha_1 x_1 \oplus \alpha_2 x_2 \oplus ... \oplus \alpha_n x_n \oplus \alpha_{12} x_1 x_2 \oplus ... \oplus \alpha_{12...n} x_1 x_2 ... x_n, }[/math] где $x_1,...,x_n$ — логические переменные, а $\alpha_0, \alpha_1, ..., \alpha_{12...n}$ — логические константы,

называется полиномом Жегалкина.

Замечание

Для удобства будем также использовать следующую запись: [math]\displaystyle{ \bigoplus_{I\subseteq \{1,...,n\}} \alpha(I) \bigwedge_{i\in I} x_i }[/math].

Пример

$1 \oplus x_1 \oplus x_2 x_3$ — полином Жегалкина. Здесь $n=3$, $\alpha_0=\alpha_1=\alpha_{23}=1$, а $\alpha_2=\alpha_3=\alpha_{12}=\alpha_{13}=\alpha_{123}=0$.

Рис. 1. В полиноме Жегалкина есть коэффициент при каждом мономе: для [math]\displaystyle{ n=3 }[/math] их [math]\displaystyle{ 2^3=8 }[/math]. В примере [math]\displaystyle{ f=1\oplus x\oplus yz }[/math] ненулевые только [math]\displaystyle{ \alpha_0 }[/math], [math]\displaystyle{ \alpha_1 }[/math] и [math]\displaystyle{ \alpha_{23} }[/math].

Утверждение:

Пусть $f(x_1,...,x_n)\in P_2$. Тогда функция $f$ может быть представлена полиномом Жегалкина, причем единственным образом.

Доказательство:

Для начала докажем существование такого представления для функции. Прежде всего заметим, что произвольная функция представима в виде формулы $\mathcal U_1$ над $\{\neg, \vee, \wedge\}$: если \mbox{$f\neq 0$}, ее можно представить в виде СДНФ, а $f=0$ представим как \mbox{$f= x\wedge\overline x$}.

Воспользуемся законом де Моргана $x\vee y = \overline{\overline x\wedge \overline y}$ и заменим все дизъюнкции в формуле $\mathcal U_1$ на конъюнкции и отрицание. Получим представление функции $f(x_1,...,x_n)$ в виде формулы $\mathcal U_2$ над системой элементарных функций $\{\neg, \wedge\}$. Заменим в формуле $\mathcal U_2$ все отрицания на сложение по модулю два согласно тождеству $\overline x=1\oplus x$. Раскроем все скобки, пользуясь дистрибутивностью $\wedge$ относительно $\oplus$, и получим формулу вида [math]\displaystyle{ \alpha_0 \oplus \alpha_1 x_1 \oplus \alpha_2 x_2 \oplus ... \oplus \alpha_n x_n \oplus \alpha_{12} x_1 x_2 \oplus ... \oplus \alpha_{12...n} x_1 x_2 ... x_n, }[/math].

Теперь докажем единственность. Пусть [math]\displaystyle{ f(x_1,...,x_n)=\bigoplus_{I\subseteq \{1,...,n\}} \alpha(I) \bigwedge_{i\in I} x_i = \bigoplus_{I\subseteq \{1,...,n\}} \beta(I) \bigwedge_{i\in I} x_i }[/math]. — два различных полинома Жегалкина для функции $f$. Полиномы различны, когда отличаются наборы их коэффициентов $\alpha$ и $\beta$.

Выберем $I^*\subseteq \{1,...,n\}$ такой, что [math]\displaystyle{ \alpha(I^*)\neq\beta(I^*) }[/math] и $\alpha(I) = \beta(I)$ для любого [math]\displaystyle{ I\subset I^* }[/math].

Поскольку наборы коэффициентов $\alpha$ и $\beta$ не совпадают, существует такое множество индексов $I_0$, что $\alpha(I_0)\neq\beta(I_0)$.

Мы можем найти искомое $I^*$, начав с $I_0$ и последовательно удаляя индексы, если указанное свойство не выполняется. Так, если для набора индексов $I_k$ существует $I\subset I_k$: $\alpha(I)\neq \beta(I)$, то выбираем $I_{k+1}=I$ и так далее, пока не получим $I_l$ с искомыми свойствами.

Пусть [math]\displaystyle{ \sigma_i = \left\{ \begin{array}{ll} 1, & i\in I^*,\\ 0, & i\notin I^*, \end{array} \right. \quad i=\overline{1,n}. }[/math]

Тогда [math]\displaystyle{ f(\sigma_1, ..., \sigma_n)= \bigoplus_{I\subseteq \{1,...,n\}} \alpha(I) \bigwedge_{i\in I} \sigma_i= \bigoplus_{I\subseteq I^*} \alpha(I)= \bigoplus_{I\subset I^*} \alpha(I) \oplus \alpha(I^*) }[/math] и в то же время [math]\displaystyle{ f(\sigma_1, ..., \sigma_n)= \bigoplus_{I\subseteq \{1,...,n\}} \beta(I) \bigwedge_{i\in I} \sigma_i= \bigoplus_{I\subseteq I^*} \beta(I)= \bigoplus_{I\subset I^*} \beta(I) \oplus \beta(I^*). }[/math]

Таким образом, [math]\displaystyle{ \bigoplus_{I\subset I^*} \alpha(I) \oplus \alpha(I^*)= \bigoplus_{I\subset I^*} \beta(I) \oplus \beta(I^*) \quad\Longrightarrow\quad \alpha(I^*)=\beta(I^*). }[/math] Противоречие с нашим исходным предположением о $I^*$ доказывает утверждение.

[math]\displaystyle{ \blacksquare }[/math]

Рис. 2. Идея единственности: выбираем минимальное [math]\displaystyle{ I^* }[/math] с [math]\displaystyle{ \alpha(I^*)\neq\beta(I^*) }[/math] и подставляем [math]\displaystyle{ \sigma }[/math] — индикатор [math]\displaystyle{ I^* }[/math]. Мономы вне [math]\displaystyle{ I^* }[/math] обнуляются, на собственных подмножествах коэффициенты совпадают, поэтому остаётся [math]\displaystyle{ \alpha(I^*)=\beta(I^*) }[/math] — противоречие.

Замечание

Полином Жегалкина является формулой над $\{0,1,\wedge,\oplus\}$.

0 нам требуется для задания тождественно нулевой функции.

Для остальных случаев нам будет достаточно функций $1,\wedge,\oplus$.

Пример

Рассмотрим функцию $f$, заданную формулой $f(x, y, z)=\overline{xy\supset z}\vee xy$.

Представим ее с помощью формулы над $\{\neg, \wedge\}$. [math]\displaystyle{ xy\supset z= \overline {xy}\vee z = \overline{xy\wedge \overline z}, }[/math]

[math]\displaystyle{ \overline{xy\supset z}\vee xy = \overline{(xy\supset z)\wedge \overline{xy}}= \overline{\overline{xy\wedge \overline z}\wedge \overline{xy}} }[/math] Теперь избавимся от отрицаний и раскроем скобки. [math]\displaystyle{ \overline{\overline{xy\wedge \overline z}\wedge \overline{xy}}= 1\oplus ((1\oplus (xy\wedge (1\oplus z)))\wedge (1\oplus xy))= }[/math] [math]\displaystyle{ =1\oplus 1\oplus xy \oplus (xy\wedge (1\oplus z)) \oplus (xy\wedge (1\oplus z))xy= }[/math] [math]\displaystyle{ =xy \oplus (xy\wedge (1\oplus z)) \oplus(xy\wedge (1\oplus z)) = xy. }[/math]

Таким образом, единственным ненулевым коэффициентом полинома Жегалкина для функции $f$

оказался $\alpha_{12}$ и сам полином имеет вид $f(x,y,z)=xy$.

Для построения полинома Жегалкина есть и более удобный способ — метод неопределенных коэффициентов. Предположим, что функция $f(x_1, ..., x_n)$ задана таблицей значений для всех наборов аргументов. Нам известен общий вид полинома Жегалкина для $f$ $\bigoplus_{I\subseteq \{1,...,n\}} \alpha(I) \bigwedge_{i\in I} x_i$ и требуется только вычислить коэффициенты $\alpha(I)$.

Проходя по всей таблице значений для $f$ будем приравнивать общий вид полинома и известное значение функции на данном наборе, тем самым последовательно вычисляя коэффициенты $\alpha$.

$f(0,...,0) = \bigoplus_{I\subseteq \{1,...,n\}} \alpha(I) \bigwedge_{i\in I} 0 = \alpha(\varnothing).$ Отсюда имеем первый коэффициент: $\alpha(\varnothing) = f(0,...,0)$.

$f(0,..,0,1) = \alpha(\varnothing) \oplus \alpha(\{n\}) \wedge 1$. Таким образом, [math]\displaystyle{ \alpha(\{n\}) = f(0,...,0,1)\oplus \alpha(\varnothing) =f(0,...,0,1) \oplus f(0,...,0,0). }[/math]

$f(0,...,0,1,0) = \alpha(\varnothing) \oplus \alpha(\{n-1\}) \wedge 1$ и [math]\displaystyle{ \alpha(\{n-1\}) = f(0,...,0,1,0)\oplus \alpha(\varnothing) =f(0,...,0,1,0) \oplus f(0,...,0,0,0). }[/math]

$f(0,...,0,1,1) = \alpha(\varnothing) \oplus \alpha(\{n-1\}) \oplus \alpha(\{n\}) \oplus \alpha(\{n-1,n\})$ и, следовательно, [math]\displaystyle{ \alpha(\{n-1,n\}) = f(0,...,0,1,1) \oplus \alpha(\varnothing) \oplus \alpha(\{n-1\}) \oplus \alpha(\{n\}) = }[/math] [math]\displaystyle{ = f(0,...,0,1,1) \oplus f(0,...,0,0,0) \oplus f(0,...,0,1,0) \oplus }[/math] [math]\displaystyle{ \oplus f(0,...,0,0,0) \oplus f(0,...,0,1) \oplus f(0,...,0,0) = }[/math] [math]\displaystyle{ = f(0,...,0,1,1) \oplus f(0,...,0,1,0) \oplus f(0,...,0,0,1) \oplus f(0,...,0,0,0) }[/math]

Продолжая этот процесс мы сможем вычислить все коэффициенты и тем самым получим полином Жегалкина для функции $f$.

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

Пример

Построим полином Жегалкина для функции $f(x, y, z)=\overline{xy\supset z}\vee xy$ с помощью метода неопределенных коэффициентов.

В общем виде полином для функции от трех переменных выглядит следующим образом: [math]\displaystyle{ f(x,y,z) = \alpha_0 \oplus \alpha_1 x \oplus \alpha_2 y \oplus \alpha_3 z \oplus \alpha_{1,2} xy \oplus \alpha_{1,3} x z \oplus \alpha_{2,3} y z \oplus \alpha_{1,2,3} x y z. }[/math]

Переберем все возможные наборы аргументов.

[math]\displaystyle{ \begin{array}{lcl} f(0,0,0) = 0 = \alpha_0 & \Rightarrow & \alpha_0 = 0,\\ f(0,0,1) = 0 = \alpha_0\oplus \alpha_3 & \Rightarrow & \alpha_3 = 0,\\ f(0,1,0) = 0 = \alpha_0 \oplus \alpha_2 & \Rightarrow & \alpha_2 = 0,\\ f(0,1,1) = 0 = \alpha_0 \oplus \alpha_2 \oplus \alpha_3 \oplus \alpha_{2,3} & \Rightarrow & \alpha_{2,3} = 0,\\ f(1,0,0) = 0 = \alpha_0 \oplus \alpha_1 & \Rightarrow & \alpha_1 = 0,\\ f(1,0,1) = 0 = \alpha_0 \oplus \alpha_1 \oplus \alpha_3 \oplus \alpha_{1,3} & \Rightarrow & \alpha_{1,3} = 0,\\ f(1,1,0) = 1 = \alpha_0 \oplus \alpha_1 \oplus \alpha_2 \oplus \alpha_{1,2} & \Rightarrow & \alpha_{1,2} = 1,\\ f(1,1,1) = 1 = \alpha_0 \oplus \alpha_1 \oplus \alpha_2 \oplus \alpha_3 \oplus \alpha_{1,2} \oplus\\ \oplus \alpha_{1,3} \oplus \alpha_{2,3} \oplus \alpha_{1,2,3} & \Rightarrow & \alpha_{1,2,3} = 0. \end{array} }[/math]

Полином Жегалкина имеет вид $f(x,y,z)=xy$.

Пример

Рассмотрим еще один пример использования метода неопределенных коэффициентов.

Пусть $f(x, y, z)=xy\vee xz \vee yz$.

[math]\displaystyle{ \begin{array}{lcl} f(0,0,0) = 0 = \alpha_0 & \Rightarrow & \alpha_0 = 0,\\ f(0,0,1) = 0 = \alpha_0\oplus \alpha_3 & \Rightarrow & \alpha_3 = 0,\\ f(0,1,0) = 0 = \alpha_0 \oplus \alpha_2 & \Rightarrow & \alpha_2 = 0,\\ f(0,1,1) = 1 = \alpha_0 \oplus \alpha_2 \oplus \alpha_3 \oplus \alpha_{2,3} & \Rightarrow & \alpha_{2,3} = 1,\\ f(1,0,0) = 0 = \alpha_0 \oplus \alpha_1 & \Rightarrow & \alpha_1 = 0,\\ f(1,0,1) = 1 = \alpha_0 \oplus \alpha_1 \oplus \alpha_3 \oplus \alpha_{1,3} & \Rightarrow & \alpha_{1,3} = 1,\\ f(1,1,0) = 1 = \alpha_0 \oplus \alpha_1 \oplus \alpha_2 \oplus \alpha_{1,2} & \Rightarrow & \alpha_{1,2} = 1,\\ f(1,1,1) = 1 = \alpha_0 \oplus \alpha_1 \oplus \alpha_2 \oplus \alpha_3 \oplus \alpha_{1,2} \oplus\\ \oplus \alpha_{1,3} \oplus \alpha_{2,3} \oplus \alpha_{1,2,3} & \Rightarrow & \alpha_{1,2,3} = 0. \end{array} }[/math]

Следовательно, полином Жегалкина для функции $f$ будет иметь вид

$f(x,y,z) = xy\oplus xz\oplus yz.$

Конспект: Дискретная математика