Истинным является высказывание многочленом жегалкина

Обновлено: 22.12.2024

Полином (многочлен) Жегалкина представляет собой полином, коэффициентами которого являются числа $0$ или $1$, причем в качестве операций умножения и сложения выступают соответственно конъюнкция и сумма по модулю $2$. Например, для булевой функции $f\left(x_1,\ x_2,\ x_3\right)$ от трех переменных $x_1,\ x_2,\ x_3$ полином Жегалкина будет иметь следующий вид:

$$f\left(x_1,\ x_2,\ x_3\right)=a_0\bigoplus a_1x_1\bigoplus a_2x_2\bigoplus a_3x_3\bigoplus a_x_1x_2\bigoplus a_x_1x_3\bigoplus a_x_2x_3\bigoplus a_x_1x_2x_3.$$

Коэффициенты $a_0,\ a_1,\ \dots ,\ a_\in \left\$, то есть могут принимать значения либо $0$, либо $1$ в зависимости от того, какое значение принимает булева функция $f\left(x_1,\ x_2,\ x_3\right)$ на том или ином наборе значений переменных.

С помощью полинома Жегалкина можно представить любую булеву функцию, причем единственных образом. Поэтому можно сказать, что полином Жегалкина является еще одним способом представления булевых функций в алгебре операций $\bigoplus $ — суммы по модулю $2$, $\cdot $ — конъюнкции и константы $1$.

Операция $\bigoplus $ имеет и другие названия: сумма Жегалкина, неравнозначность, исключающее ИЛИ-НЕ. Иногда, для удобства ее обозначения используют привычную запись сложения $+$, но не стоит путать с дизъюнкцией и, тем более, с обычной арифметической операцией сложения. Таблица истинности данной операции имеет вид:

Сумма $x\bigoplus y$ принимает истинное значение тогда и только тогда, когда истинно одно и только одно составляющее высказывание. Если сравнить таблицы истинности основных логических операций, то можно заметить, что $x\bigoplus y=\overline$. То есть операция сумма Жегалкина $\bigoplus $ есть отрицание эквиваленции.

Для двух введенных операций $\bigoplus ,\ \cdot $ (суммы по модулю 2 и конъюнкции) выполняются все логические законы:

Коммутативность: $x\bigoplus y=y\bigoplus x$;
Ассоциативность: $\left(x\bigoplus y\right)\bigoplus z=x\bigoplus \left(y\bigoplus z\right)$, то есть результат $x\bigoplus y\bigoplus z$ не зависит от расстановки скобок;
Дистрибутивность: $x\left(y\bigoplus z\right)=xy\bigoplus xz$;
$x\bigoplus x=0$;
$0\bigoplus x=x$;
$\overline=x\bigoplus 1$.

Для построения полинома Жегалкина можно использовать различные методы:

Метод неопределенных коэффициентов;
Метод треугольника Паскаля;
Преобразование ДНФ;
Преобразование СДНФ.

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

Найдем полином Жегалкина для функции $f\left(x_1,\ x_2,\ x_3\right)=\left(x_1x_2\vee x_3\right)\to <\overline>_2$, используя метод неопределенных коэффициентов. Для этого сначала необходимо построить таблицу истинности данной булевой функции $f\left(x_1,\ x_2,\ x_3\right)$.

$\begin<|c|c|>
\hline
x_1 & x_2 & x_3 & x_1x_2 & x_1x_2\vee x_3 & f\left(x_1,\ x_2,\ x_3\right)=\left(x_1x_2\vee x_3\right)\to <\overline>_2 \\
0 & 0 & 0 & 0 & 0 & 1 \\
\hline
0 & 0 & 1 & 0 & 1 & 1 \\
\hline
0 & 1 & 0 & 0 & 0 & 1 \\
\hline
0 & 1 & 1 & 0 & 1 & 0 \\
\hline
1 & 0 & 0 & 0 & 0 & 1 \\
\hline
1 & 0 & 1 & 0 & 1 & 1 \\
\hline
1 & 1 & 0 & 1 & 1 & 0 \\
\hline
1 & 1 & 1 & 1 & 1 & 0 \\
\hline
\end$

Общий вид полинома Жегалкина для функции $f\left(x_1,\ x_2,\ x_3\right)$ трех переменных $x_1,\ x_2,\ x_3$:

$$f\left(x_1,\ x_2,\ x_3\right)=a_0\bigoplus a_1x_1\bigoplus a_2x_2\bigoplus a_3x_3\bigoplus a_x_1x_2\bigoplus a_x_1x_3\bigoplus a_x_2x_3\bigoplus a_x_1x_2x_3.$$

Последовательно подставляем наборы значений переменных и находим коэффициенты $a_0,\ a_1,\ \dots ,\ a_$.

$f\left(0,\ 0,\ 0\right)=a_0=1;$

$f\left(0,\ 0,\ 1\right)=a_0\bigoplus a_3=1\Rightarrow 1\bigoplus a_3=1\Rightarrow a_3=0;$

$f\left(0,\ 1,\ 0\right)=a_0\bigoplus a_2=1\Rightarrow 1\bigoplus a_2=1\Rightarrow a_2=0;$

$f\left(0,\ 1,\ 1\right)=a_0\bigoplus a_2\bigoplus a_3\bigoplus a_=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus a_=0\Rightarrow 1\bigoplus a_=0\Rightarrow a_=1;$

$f\left(1,\ 0,\ 0\right)=a_0\bigoplus a_1=1\Rightarrow 1\bigoplus a_1=1\Rightarrow a_1=0.$

$f\left(1,\ 0,\ 1\right)=a_0\bigoplus a_1\bigoplus a_3\bigoplus a_=1\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus a_=1\Rightarrow 1\bigoplus a_=1\Rightarrow a_=0;$

$f\left(1,\ 1,\ 0\right)=a_0\bigoplus a_1\bigoplus a_2\bigoplus a_=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus a_=0\Rightarrow 1\bigoplus a_=0\Rightarrow a_=1;$

$f\left(1,\ 1,\ 1\right)=a_0\bigoplus a_1\bigoplus a_2\bigoplus a_3\bigoplus a_\bigoplus a_\bigoplus a_\bigoplus a_=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus 0\bigoplus 1\bigoplus 0\bigoplus 1\bigoplus a_=0\Rightarrow 1\bigoplus a_=0\Rightarrow a_=1;$

Подставляя найденные коэффициенты, получаем полином Жегалкина:

$$f\left(x_1,\ x_2,\ x_3\right)=1\bigoplus x_1x_2\bigoplus x_2x_3\bigoplus x_1x_2x_3.$$

Метод треугольника Паскаля

Построим полином Жегалкина для функции из предыдущего метода, используя треугольник Паскаля.

Поясним, как заполняется треугольник Паскаля. Верхняя строка треугольника задает вектор значений булевой функции $f=\left(11101100\right)$. В каждой строке, начиная со второй, любой элемент такого треугольника вычисляется как сумма по модулю $2$ двух соседних элементов предыдущей строки. Так, элементы второй строки: $1\bigoplus 1=0,\ 1\bigoplus 1=0,\ 1\bigoplus 0=1,\ 0\bigoplus 1=1,\ 1\bigoplus 1=0,\ 1\bigoplus 0=1,\ 0\bigoplus 0=0$. Аналогично вычисляются элементы других строк.

Левой стороне треугольника Паскаля соответствуют наборы значений переменных исходной функции $f\left(x_1,\ x_2,\ x_3\right)$. Соединяя знаком конъюнкции переменные, значения которых в наборе равны $1$, мы получим слагаемое в полиноме Жегалкина. Набору $\left(000\right)$ соответствует $1$, набору $\left(001\right)$ соответствует $x_3$, и т.д.

Поскольку единицам левой стороны треугольника соответствуют слагаемые $1,\ x_2x_3,\ x_1x_2,\ x_1x_2x_3$, то полином Жегалкина:

$$f\left(x_1,\ x_2,\ x_3\right)=1\bigoplus x_2x_3\bigoplus x_1x_2\bigoplus x_1x_2x_3.$$

Преобразование ДНФ

Используя основные законы алгебры логики, приведем сначала данную функцию к ДНФ.

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

Заменяем каждое отрицание $\overline=1\bigoplus x$ и применяем написанные выше логические законы, получаем:

$\overline<<\overline<<\overline>_1<\overline>_3>x>_2>=1\bigoplus <\overline<<\overline>_1<\overline>_3>x>_2=1\bigoplus \left(1\bigoplus \left(1\bigoplus x_1\right)\left(1\bigoplus x_3\right)\right)x_2=1\bigoplus \left(1\bigoplus 1\bigoplus x_3\bigoplus x_1\bigoplus x_1x_3\right)x_2=1\bigoplus \left(x_3\bigoplus x_1\bigoplus x_1x_3\right)x_2=1\bigoplus x_2x_3\bigoplus x_1x_2\bigoplus x_1x_2x_3$ — полином Жегалкина.

Преобразование СДНФ

Для построения СДНФ по таблице истинности выбираем наборы, на которых функция $f$ принимает значение, равное 1. Если значение переменной в этом наборе равно 0, то она берется с отрицанием, если значение переменной равно 1, то переменная берется без отрицание. Соединив знаком конъюнкции переменные соответствующего набора, получим элементарную конъюнкцию. Тогда дизъюнкция всех таких элементарных конъюнкций есть СДНФ.

Чтобы построить полином Жегалкина через СДНФ, необходимо исключить операции дизъюнкции и отрицания, затем раскрыть скобки.

$f\left(x_1,\ x_2,\ x_3\right)=<\overline>_1<\overline>_2<\overline>_3\bigoplus <\overline>_1<\overline>_2x_3\bigoplus <\overline>_1x_2<\overline>_3\bigoplus x_1<\overline>_2<\overline>_3\bigoplus x_1<\overline>_2x_3=\left(1\bigoplus x_1\right)\left(1\bigoplus x_2\right)\left(1\bigoplus x_3\right)\bigoplus \left(1\bigoplus x_1\right)\left(1\bigoplus x_2\right)x_3\bigoplus \left(1\bigoplus x_1\right)x_2\left(1\bigoplus x_3\right)\bigoplus x_1\left(1\bigoplus x_2\right)\left(1\bigoplus x_3\right)\bigoplus x_1\left(1\bigoplus x_2\right)x_3=1\bigoplus x_3\bigoplus x_2\bigoplus x_2x_3\bigoplus x_1\bigoplus x_1x_3\bigoplus x_1x_2\bigoplus x_1x_2x_3\bigoplus x_3\bigoplus x_2x_3\bigoplus x_1x_3\bigoplus x_1x_2x_3\bigoplus x_2\bigoplus x_2x_3\bigoplus x_1x_2\bigoplus x_1x_2x_3\bigoplus x_1\bigoplus x_1x_3\bigoplus x_1x_2\bigoplus x_1x_2x_3\bigoplus x_1x_3\bigoplus x_1x_2x_3=1\bigoplus x_2x_3\bigoplus x_1x_2\bigoplus x_1x_2x_3$ — полином Жегалкина.

Читайте также: