СВ в 20:09, 24 октября 2026

2026-10-24T20:09:47Z

← Предыдущая		Версия 20:09, 24 октября 2026
Строка 237:		Строка 237:
	$f(x,y,z) = xy\oplus xz\oplus yz.$		$f(x,y,z) = xy\oplus xz\oplus yz.$
	}}		}}

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

СВ: Новая страница: «{{Определение |definition= Формула вида $\alpha_0 \oplus \alpha_1 x_1 \oplus \alpha_2 x_2 \oplus ... \oplus \alpha_n x_n \oplus \alpha...»$

2026-10-24T20:09:30Z

Новая страница: «{{Определение |definition= Формула вида <math> \alpha_0 \oplus \alpha_1 x_1 \oplus \alpha_2 x_2 \oplus ... \oplus \alpha_n x_n \oplus \alpha...»

Новая страница

{{Определение
|definition=
Формула вида
<math>
\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}$ {{---}} логические константы,
называется полиномом Жегалкина.
}}
{{Замечание
|content=Для удобства будем также использовать следующую запись:
<math>\bigoplus_{I\subseteq \{1,...,n\}} \alpha(I) \bigwedge_{i\in I} x_i</math>.
}}
{{Пример
|content=$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$.
}}

[[Файл:p38-01-monomial-coefficients.svg|frame|none|900px|alt=Восемь мономов для трёх переменных с коэффициентами; в примере f = 1 ⊕ x ⊕ yz ненулевые только три|Рис. 1. В полиноме Жегалкина есть коэффициент при каждом мономе: для <math>n=3</math> их <math>2^3=8</math>. В примере <math>f=1\oplus x\oplus yz</math> ненулевые только <math>\alpha_0</math>, <math>\alpha_1</math> и <math>\alpha_{23}</math>.]]

{{Утверждение
|statement=Пусть $f(x_1,...,x_n)\in P_2$.
Тогда функция $f$ может быть представлена полиномом Жегалкина, причем единственным образом.
|proof=Для начала докажем существование такого представления для функции.
Прежде всего заметим, что произвольная функция представима в виде формулы
$\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>
\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>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>\alpha(I^*)\neq\beta(I^*)</math> и $\alpha(I) = \beta(I)$ для любого <math>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>
\sigma_i = \left\{
\begin{array}{ll}
1, & i\in I^*,\\
0, & i\notin I^*,
\end{array}
\right.
\quad
i=\overline{1,n}.
</math>

Тогда
<math>
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>
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>
\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^*$ доказывает утверждение.
}}

[[Файл:p38-02-uniqueness-minimal-set.svg|frame|none|900px|alt=Подстановка σ = (1,1,0) при I* = {1,2}: мономы с z обнуляются, равные коэффициенты сокращаются, остаётся α12 = β12|Рис. 2. Идея единственности: выбираем минимальное <math>I^*</math> с <math>\alpha(I^*)\neq\beta(I^*)</math> и подставляем <math>\sigma</math> — индикатор <math>I^*</math>. Мономы вне <math>I^*</math> обнуляются, на собственных подмножествах коэффициенты совпадают, поэтому остаётся <math>\alpha(I^*)=\beta(I^*)</math> — противоречие.]]

{{Замечание
|content=
Полином Жегалкина является формулой над $\{0,1,\wedge,\oplus\}$.
0 нам требуется для задания тождественно нулевой функции.
Для остальных случаев нам будет достаточно функций $1,\wedge,\oplus$.
}}
{{Пример
|content=Рассмотрим функцию $f$, заданную формулой $f(x, y, z)=\overline{xy\supset z}\vee xy$.
Представим ее с помощью формулы над $\{\neg, \wedge\}$.
<math>
xy\supset z= \overline {xy}\vee z = \overline{xy\wedge \overline z},
</math>

<math>
\overline{xy\supset z}\vee xy = \overline{(xy\supset z)\wedge \overline{xy}}=
\overline{\overline{xy\wedge \overline z}\wedge \overline{xy}}
</math>
Теперь избавимся от отрицаний и раскроем скобки.
<math>
\overline{\overline{xy\wedge \overline z}\wedge \overline{xy}}=
1\oplus ((1\oplus (xy\wedge (1\oplus z)))\wedge (1\oplus xy))=
</math>
<math>
=1\oplus 1\oplus xy \oplus (xy\wedge (1\oplus z)) \oplus (xy\wedge (1\oplus z))xy=
</math>
<math>
=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>
\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>
\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>
\alpha(\{n-1,n\}) = f(0,...,0,1,1) \oplus
\alpha(\varnothing) \oplus \alpha(\{n-1\}) \oplus \alpha(\{n\})
=
</math>
<math>
=
f(0,...,0,1,1) \oplus f(0,...,0,0,0) \oplus f(0,...,0,1,0)
\oplus
</math>
<math>
\oplus f(0,...,0,0,0) \oplus f(0,...,0,1) \oplus f(0,...,0,0)
=
</math>
<math>
=
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$.

[[Файл:p38-03-triangular-system.svg|frame|none|900px|alt=Матрица активных мономов для наборов 000–111: точки образуют треугольник, диагональ — новые коэффициенты|Рис. 3. Почему метод неопределённых коэффициентов решается строка за строкой: на каждом наборе активные мономы образуют треугольник, и ровно один из них — новый. Диагональ соответствует коэффициенту, который находится на этом шаге.]]

{{Пример
|content=
Построим полином Жегалкина для функции $f(x, y, z)=\overline{xy\supset z}\vee xy$ с помощью метода неопределенных коэффициентов.
В общем виде полином для функции от трех переменных выглядит следующим образом:
<math>
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>
\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$.
}}
{{Пример
|content=
Рассмотрим еще один пример использования метода неопределенных коэффициентов.
Пусть $f(x, y, z)=xy\vee xz \vee yz$.

<math>
\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.$
}}

Полином Жегалкина - История изменений

СВ в 20:09, 24 октября 2026

СВ: Новая страница: «{{Определение |definition= Формула вида \alpha_0 \oplus \alpha_1 x_1 \oplus \alpha_2 x_2 \oplus ... \oplus \alpha_n x_n \oplus \alpha...»

СВ: Новая страница: «{{Определение |definition= Формула вида $\alpha_0 \oplus \alpha_1 x_1 \oplus \alpha_2 x_2 \oplus ... \oplus \alpha_n x_n \oplus \alpha...»$