Полином жегалкина через сднф

Рассмотрим алгоритмы построения полинома Жегалкина булевой функции, заданной различными способами, а именно: совершенной ДНФ, произвольной ДНФ, формулой и таблицей истинности.

Алгоритм построения полинома Жегалкина по СовДНФ (основан на доказательстве теоремы о существовании полинома Жегалкина).

Начало. Задана совершенная ДНФ функции f(x1, …, xn).

Шаг 1. Заменяем каждый символ дизъюнкции на символ дизюнкции с исключением.

Шаг 2. Заменяем каждую переменную с инверсией x равносильной формулой x 1.

Шаг 3. Раскрываем скобки.

Шаг 4. Вычеркиваем из формулы пары одинаковых слагаемых.

Конец. Получен полином Жегалкина функции f(x1, …, xn).

Пример. Найдем полином Жегалкина мажоритарной булевой функции по ее совершенной ДНФ.

Алгоритм построения полинома Жегалкина по ДНФ (основан на равносильности K1 K2= K1 K2 K1K2).

Начало. Задана произвольная ДНФ функции f(x1, …, xn).

Шаг 1. Разбиваем ДНФ на пары конъюнкций, предпочтительно ортогональных (если число конъюнкций нечетно, одна из них остается без пары).

Шаг 2. Заменяем дизъюнкцию каждой пары конъюнкций K1 K2 формулой K1 K2 K1K2 или формулой K1 K2, если K1 и K2 ортогональны.

Шаг 3. В полученной формуле находим очередную дизъюнкцию A1 A2и заменяем ее формулой A1 A2 A1A2. Повторяем шаг 3 до тех пор, пока это возможно.

Шаг 4. Заменяем каждую переменную с инверсией x равносильной формулой x 1.

Шаг 5. Раскрываем скобки.

Шаг 6. Вычеркиваем из формулы пары одинаковых слагаемых.

Конец. Получен полином Жегалкина функции f(x1, …, xn).

Пример. Найдем полином Жегалкина мажоритарной функции по ДНФ.

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

Способ 1 основан на предварительном преобразовании формулы в ДНФ (любым известным нам способом). Затем ДНФ преобразуется в полином Жегалкина по только что изученному алгоритму.

Примеры. Получим полиномы Жегалкина двух элементарных булевых функций: импликации и эквивалентности, представив их предварительно кратчайшими ДНФ.

Аналогично можно получить полиномы Жегалкина всех элементарных булевых функций (оставим читателю их вывод).

Константы 0 и 1, тождественная функция, а также конъюнкция ab и дизъюнкция с исключением ab уже являются полиномами Жегалкина. Полином Жегалкина инверсии a =1a.

Заметим, что некоторые из приведенных полиномов могут быть получены гораздо проще, в частности,

Способ 2. Если булева функций задана произвольной формулой, то ее полином Жегалкина можно получить подстановкой в формулу вместо элементарных булевых функций их полиномов.

Пример. Найдем полином Жегалкина мажоритарной функции, заданной формулой:

[ подставим в формулу полином Жегалкина штриха Шеффера 1 ab при a=(xy) z, b=x y ]

[ подставим полиномы Жегалкина обратной импликации 1 b ab при a=xy, b=z и импликации 1 a ab при a=x, b= y ]

[ подставим полином Жегалкина эквивалентности 1 x y, раскроем скобки, и вычеркнем появившиеся при этом пары одинаковых слагаемых ]

[заменим инверсию ее полиномом Жегалкина, раскроем скобки и вычеркнем пары одинаковых слагаемых ]

Полином, естественно, совпадает с полученными ранее по совершенной и произвольной ДНФ.

Способ 3. Если булева функций задана произвольной формулой, то ее полином Жегалкина можно получить, используя специальное разложение функции.

Определение. Разложением Дэвио называется следующее разложение булевой функции f(x1, …, xn по переменной xi:

Разложение Дэвио непосредственно следует из разложения Шеннона, если учесть, что слагаемые в последнем ортогональны, и что x i=xi 1.

Пример. Найдем разложение Дэвио по переменной x мажоритарной булевой функции, заданной формулой.

Для получения полинома Жегалкина необходимо продолжить разложение подформул, не являющихся дизъюнкцией с исключением элементарных конъюнкций, пока не получится формула над <,, – >. Если в такой формуле заменить инверсии x на x 1, раскрыть скобки и вычеркнуть пары одинаковых слагаемых, то получится полином Жегалкина.

Читайте также:  Zte blade a6 max обзор

Пример. Продолжив предыдущий пример, получим полином Жегалкина мажоритарной функции. Для этого разложим подформулы (y z) / y и y z по переменной y:

Полином Жегалкина, естественно, совпадает с полученными ранее.

Алгоритм построения полинома Жегалкина по таблице истинности (основан на методе неопределенных коэффициентов).

Продемонстрируем идею метода на примере произвольной булевой функции двух аргументов f(x,y). Представим ее полиномом Жегалкина в форме с коэффициентами

Подставив в данное равенство наборы значений аргументов, получим систему из четырех линейных уравнений с четырьмя неизвестными коэффициентами: c, c1 c2, c3.

f(0,0) = c c10 c20 c30 0 = c

f(0,1) = c c11 c20 c30 1 = c c1

f(1,0) = c c10 c21 c31 0 = c c2

f(1,1) = c c11 c21 c31 1 = c c1 c2 c3

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

В общем случае для функции n аргументов получается система треугольного вида из 2 n линейных уравнений с 2 n неизвестными – коэффициентами полинома Жегалкина.

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

Из первого уравнения следует, что c=0. Из второго и третьего уравнений следует, что c1=0 и c2=0, значит, c1z и c2y тождественно равны нулю. Из четвертого уравнения получаем c3=1, значит, надо вычислять значения конъюнкции c3yz в остальных уравнениях. Аналогично получаем c4=0, c5=1, c6=1 и c7=0. Найден вектор коэффициентов полинома Жегалкина мажоритарной функции π=00010110, и сам полином P=yz xz xy, который, естественно, совпадает с полученными ранее. •

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

Самый простой метод построения совершенной дизъюнктивной и конъюнктивной нормальных форм — с помощью таблиц истинности. Для перехода к ДНФ и КНФ используют методы эквивалентных преобразований, правила де Моргана, свойства поглощения, правило Блейка и т.п.

Полином Жегалкина может быть построен как с помощью последовательных преобразований, так и по таблице истинности (метод неопределенных коэффициентов).

Все эти примеры разобраны ниже. Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.

Другие примеры решений о булевых функциях:

Задачи и решения о представлении булевых функций

Нормальные формы (КНФ, СКНФ, ДНФ и СДНФ): примеры решений

Задача 1. Привести к КНФ и СКНФ.

$$((((A o B) o ar A) o ar B) o ar C).$$

Задача 2. С помощью эквивалентных преобразований построить д.н.ф. функции:

$$f(x)=(overlinex_2 oplus x_3) cdot (x_1 x_3 o x_2) $$

Задача 3. Используя СКНФ, найдите наиболее простую формулу алгебры высказываний от четырех переменных, принимающую значение 0 на следующих наборах значений переменных, и только на них:

Задача 4. Привести данные выражения к ДНФ, пользуясь правилами де Моргана. Если возможно, сократить ДНФ, используя свойство поглощения и правило Блейка.

Многочлен Жегалкина: примеры решений

Задача 5. Представив функцию формулой над множеством связок $<&, ->$, преобразовать затем полученную формулу в полином Жегалкина функции $f(x)$ (используя эквивалентности):

$$f(x) = (x_1 vee x_2) cdot (x_2 | x_3)$$

Задача 6. Задана булева функция: $$ f(x_1, x_2, x_3) = overline vee ((x_1 wedge overline ) | overline<(x_2 | overline )>$$ А) Построить таблицу истинности, найти двоичную форму булевой функции и привести ее к СДНФ и СКНФ.
Б) Найти многочлен Жегалкина.

Читайте также:  Теория вероятности хотя бы одно событие

Задача 7. Для заданной логической функции перейти к полиному Жегалкина.

Решение задач на заказ

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

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

$$fleft(x_1, x_2, x_3
ight)=a_0igoplus a_1x_1igoplus a_2x_2igoplus a_3x_3igoplus a_<12>x_1x_2igoplus a_<13>x_1x_3igoplus a_<23>x_2x_3igoplus a_<123>x_1x_2x_3.$$

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

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

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

$$egin<|c|c|>
hline
x & y & xigoplus y \
hline
0 & 0 & 0 \
hline
0 & 1 & 1 \
hline
1 & 0 & 1 \
hline
1 & 1 & 0 \
hline
end
$$

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

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

  1. Коммутативность: $xigoplus y=yigoplus x$;
  2. Ассоциативность: $left(xigoplus y
    ight)igoplus z=xigoplus left(yigoplus z
    ight)$, то есть результат $xigoplus yigoplus z$ не зависит от расстановки скобок;
  3. Дистрибутивность: $xleft(yigoplus z
    ight)=xyigoplus xz$;
  4. $xigoplus x=0$;
  5. $0igoplus x=x$;
  6. $overline=xigoplus 1$.

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

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

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

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

$egin<|c|c|>
hline
x_1 & x_2 & x_3 & x_1x_2 & x_1x_2vee x_3 & fleft(x_1, x_2, x_3
ight)=left(x_1x_2vee x_3
ight) o <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
$

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

$$fleft(x_1, x_2, x_3
ight)=a_0igoplus a_1x_1igoplus a_2x_2igoplus a_3x_3igoplus a_<12>x_1x_2igoplus a_<13>x_1x_3igoplus a_<23>x_2x_3igoplus a_<123>x_1x_2x_3.$$

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

Читайте также:  Trojan win32 miner как удалить

$fleft(0, 0, 0
ight)=a_0=1;$

$fleft(0, 0, 1
ight)=a_0igoplus a_3=1Rightarrow 1igoplus a_3=1Rightarrow a_3=0;$

$fleft(0, 1, 0
ight)=a_0igoplus a_2=1Rightarrow 1igoplus a_2=1Rightarrow a_2=0;$

$fleft(0, 1, 1
ight)=a_0igoplus a_2igoplus a_3igoplus a_<23>=0Rightarrow 1igoplus 0igoplus 0igoplus a_<23>=0Rightarrow 1igoplus a_<23>=0Rightarrow a_<23>=1;$

$fleft(1, 0, 0
ight)=a_0igoplus a_1=1Rightarrow 1igoplus a_1=1Rightarrow a_1=0.$

$fleft(1, 0, 1
ight)=a_0igoplus a_1igoplus a_3igoplus a_<13>=1Rightarrow 1igoplus 0igoplus 0igoplus a_<13>=1Rightarrow 1igoplus a_<13>=1Rightarrow a_<13>=0;$

$fleft(1, 1, 0
ight)=a_0igoplus a_1igoplus a_2igoplus a_<12>=0Rightarrow 1igoplus 0igoplus 0igoplus a_<12>=0Rightarrow 1igoplus a_<12>=0Rightarrow a_<12>=1;$

$fleft(1, 1, 1
ight)=a_0igoplus a_1igoplus a_2igoplus a_3igoplus a_<12>igoplus a_<13>igoplus a_<23>igoplus a_<123>=0Rightarrow 1igoplus 0igoplus 0igoplus 0igoplus 1igoplus 0igoplus 1igoplus a_<123>=0Rightarrow 1igoplus a_<123>=0Rightarrow a_<123>=1;$

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

$$fleft(x_1, x_2, x_3
ight)=1igoplus x_1x_2igoplus x_2x_3igoplus x_1x_2x_3.$$

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

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

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

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

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

$$fleft(x_1, x_2, x_3
ight)=1igoplus x_2x_3igoplus x_1x_2igoplus x_1x_2x_3.$$

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

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

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

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

$overline<<overline<<overline>_1<overline>_3>x>_2>=1igoplus <overline<<overline>_1<overline>_3>x>_2=1igoplus left(1igoplus left(1igoplus x_1
ight)left(1igoplus x_3
ight)
ight)x_2=1igoplus left(1igoplus 1igoplus x_3igoplus x_1igoplus x_1x_3
ight)x_2=1igoplus left(x_3igoplus x_1igoplus x_1x_3
ight)x_2=1igoplus x_2x_3igoplus x_1x_2igoplus x_1x_2x_3$ — полином Жегалкина.

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

$egin<|c|c|>
hline
x_1 & x_2 & x_3 & fleft(x_1, x_2, x_3
ight) \
hline
0 & 0 & 0 & 1 \
hline
0 & 0 & 1 & 1 \
hline
0 & 1 & 0 & 1 \
hline
0 & 1 & 1 & 0 \
hline
1 & 0 & 0 & 1 \
hline
1 & 0 & 1 & 1 \
hline
1 & 1 & 0 & 0 \
hline
1 & 1 & 1 & 0 \
hline
end
$

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

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

$fleft(x_1, x_2, x_3
ight)=<overline>_1<overline>_2<overline>_3igoplus <overline>_1<overline>_2x_3igoplus <overline>_1x_2<overline>_3igoplus x_1<overline>_2<overline>_3igoplus x_1<overline>_2x_3=left(1igoplus x_1
ight)left(1igoplus x_2
ight)left(1igoplus x_3
ight)igoplus left(1igoplus x_1
ight)left(1igoplus x_2
ight)x_3igoplus left(1igoplus x_1
ight)x_2left(1igoplus x_3
ight)igoplus x_1left(1igoplus x_2
ight)left(1igoplus x_3
ight)igoplus x_1left(1igoplus x_2
ight)x_3=1igoplus x_3igoplus x_2igoplus x_2x_3igoplus x_1igoplus x_1x_3igoplus x_1x_2igoplus x_1x_2x_3igoplus x_3igoplus x_2x_3igoplus x_1x_3igoplus x_1x_2x_3igoplus x_2igoplus x_2x_3igoplus x_1x_2igoplus x_1x_2x_3igoplus x_1igoplus x_1x_3igoplus x_1x_2igoplus x_1x_2x_3igoplus x_1x_3igoplus x_1x_2x_3=1igoplus x_2x_3igoplus x_1x_2igoplus x_1x_2x_3$ — полином Жегалкина.