Треугольник паскаля полином жегалкина

Полином Жегалкина — многочлен над полем Z 2 <displaystyle mathbb _<2>> , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).

Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина [1] .

Полином Жегалкина представляет собой сумму по модулю два попарно различных произведений неинвертированных переменных, где ни в одном произведении ни одна переменная не встречается больше одного раза, а также (если необходимо) константы 1 [1] . Формально полином Жегалкина можно представить в виде

P ( X 1 , … , X n ) = a ⊕ a 1 X 1 ⊕ a 2 X 2 ⊕ ⋯ ⊕ a n X n ⊕ a 12 X 1 X 2 ⊕ a 13 X 1 X 3 ⊕ … ⊕ a 1 … n X 1 … X n , <displaystyle P(X_<1>,dots ,X_)=aoplus a_<1>X_<1>oplus a_<2>X_<2>oplus dots oplus a_X_oplus a_<12>X_<1>X_<2>oplus a_<13>X_<1>X_<3>oplus ldots oplus a_<1dots n>X_<1>dots X_,> a , … , a 1 … n ∈ < 0 , 1 >, <displaystyle a,ldots ,a_<1ldots n>in <0,1>,>

или в более формализованном виде как

P = a ⊕ ⨁ 1 ⩽ i 1 … i k ⩽ n k ∈ 1 , n ¯ a i 1 , … , i k ∧ x i 1 ∧ … ∧ x i k , a , a i 1 , … , i k ∈ < 0 , 1 >. <displaystyle P=aoplus igoplus _<egin1leqslant i_ <1>

Примеры полиномов Жегалкина:

P = B ⊕ A B , <displaystyle P=Boplus AB,> P = X ⊕ Y Z ⊕ A B X ⊕ A B D Y Z , <displaystyle P=Xoplus YZoplus ABXoplus ABDYZ,> P = 1 ⊕ A ⊕ A B D . <displaystyle P=1oplus Aoplus ABD.>

Содержание

Предпосылки [ править | править код ]

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:

  1. Хотя бы одна функция, не сохраняющая 0.
  2. Хотя бы одна функция, не сохраняющая 1.
  3. Хотя бы одна нелинейная функция.
  4. Хотя бы одна немонотонная функция.
  5. Хотя бы одна несамодвойственная функция.

Этому требованию отвечает, в частности, система функций ⟨ ∧ , ⊕ , 1 ⟩ <displaystyle <igl langle >wedge ,oplus ,1<igr
angle >> (конъюнкция, сложение по модулю два, константа 1). На её основе и строятся полиномы Жегалкина.

Существование и единственность представления [ править | править код ]

По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от n переменных 2 2 n <displaystyle 2^<2^>> штук. При этом конъюнкций вида x i 1 … x i k <displaystyle x_<1>>ldots x_>> существует ровно 2 n , так как из n возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует 2 2 n <displaystyle 2^<2^>> различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.

Представление функции в виде полинома Жегалкина [ править | править код ]

С помощью эквивалентных преобразований ДНФ [ править | править код ]

По сравнению с ДНФ в полиноме Жегалкина отсутствуют операции ИЛИ и НЕ. Таким образом, полином Жегалкина можно получить из ДНФ, выразив операции ИЛИ и НЕ через операции сложение по модулю два, и константу 1. Для этого применяются следующие соотношения:

A ∨ B = A ⊕ B ⊕ A B , <displaystyle Avee B=Aoplus Boplus AB,> A ¯ = A ⊕ 1. <displaystyle <overline >=Aoplus 1.>

Ниже приведён пример преобразования ДНФ в полином Жегалкина:

X Y ∨ X ¯ Y ¯ = X Y ⊕ X ¯ Y ¯ ⊕ X Y X ¯ Y ¯ = X Y ⊕ X ¯ Y ¯ = X Y ⊕ ( X ⊕ 1 ) ( Y ⊕ 1 ) = <displaystyle XYvee <overline >,<overline >=XYoplus <overline >,<overline >oplus XY<overline >,<overline >=XYoplus <overline >,<overline >=XYoplus (Xoplus 1)(Yoplus 1)=> = X Y ⊕ X Y ⊕ X ⊕ Y ⊕ 1 = X ⊕ Y ⊕ 1. <displaystyle quad =XYoplus XYoplus Xoplus Yoplus 1=Xoplus Yoplus 1.>

При преобразованиях использованы соотношения

A ⊕ A = 0 , <displaystyle Aoplus A=0,> ( A ⊕ B ) C = A C ⊕ B C . <displaystyle (Aoplus B)C=ACoplus BC.>

С помощью эквивалентных преобразований СДНФ [ править | править код ]

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

При преобразовании СДНФ в полином Жегалкина достаточно заменить все дизъюнкции на операции сложение по модулю два и избавиться от инверсий при помощи эквивалентного преобразования

A ¯ = A ⊕ 1. <displaystyle <overline >=Aoplus 1.>

С помощью карты Карно [ править | править код ]

Логическая функция трёх переменных P ( A , B , C ) <displaystyle P(A,B,C)> , представленная в виде карты Карно, преобразуется в полином Жегалкина следующими шагами:

  • Рассматриваем все ячейки карты Карно в порядке возрастания количества единиц в их кодах. Для функции трёх переменных последовательность ячеек будет 000 — 100 — 010 — 001 — 110 — 101 — 011 — 111. Каждой ячейке карты Карно сопоставляем член полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1.
  • Если в рассматриваемой ячейке находится 0, переходим к следующей ячейке.
  • Если в рассматриваемой ячейке находится 1, добавляем в полином Жегалкина соответствующий член, инвертируем в карте Карно все ячейки, где этот член равен 1, и переходим к следующей ячейке. Например, если при рассмотрении ячейки 110 в ней оказывается единица, то в полином Жегалкина добавляется член AB и инвертируются все ячейки карты Карно, где A = 1 и B = 1. Если единице равна ячейка 000, то в полином Жегалкина добавляется член 1 и инвертируется вся карта Карно.
  • Процесс преобразования можно считать законченным, когда после очередной инверсии все ячейки карты Карно становятся нулевыми.
Читайте также:  Электромеханический этап развития вычислительной техники

Метод треугольника [ править | править код ]

Метод треугольника (часто ошибочно [ источник не указан 640 дней ] называемый методом треугольника Паскаля) позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

  • Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000…00 до 111…11.
  • Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
  • Ячейка в каждом последующем столбце получается путём суммирования по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
  • Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
  • Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т. д.
  • Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

Метод треугольника основан на теореме, предложенной В. П. Супруном, не связанной напрямую с треугольником Паскаля. В 1985 году метод двоичного треугольника было предложено использовать для преобразования вектора значений совершенной дизъюнктивной нормальной формы в вектор коэффициентов полинома Жегалкина для произвольной симметрической булевой функции. В 1987 году метод был расширен для произвольной булевой функции. Отметим, что метод треугольника позволяет строить полином Рида — Маллера [en] с отрицательной поляризацией как для симметрических функций, так и для произвольных [ источник не указан 640 дней ] .

Метод Паскаля [ править | править код ]

Наиболее экономным с точки зрения объёма вычислений и целесообразным для построения полинома Жегалкина вручную является метод Паскаля.

Строим таблицу, состоящую из 2 N столбцов и N + 1 строк, где N — количество переменных в функции. В верхней строке таблицы размещаем вектор значений функции, то есть последний столбец таблицы истинности.

Каждую строку полученной таблицы разбиваем на блоки (чёрные линии на рисунке). В первой строке блок занимает одну клетку, во второй строке — две, в третьей — четыре, в четвёртой — восемь и т. д. Каждому блоку в некоторой строке, который мы будем называть «нижний блок», всегда соответствует ровно два блока в предыдущей строке. Будем называть их «левый верхний блок» и «правый верхний блок».

Построение начинается со второй строки. Содержимое левых верхних блоков без изменения переносится в соответствующие клетки нижнего блока (зелёные стрелки на рисунке). Затем над правым верхним и левым верхним блоками побитно производится операция «сложение по модулю два», и полученный результат переносится в соответствующие клетки правой части нижнего блока (красные стрелки на рисунке). Эта операция проводится со всеми строками сверху вниз и со всеми блоками в каждой строке. После окончания построения в нижней строке оказывается строка чисел, которая является коэффициентами полинома Жегалкина, записанными в той же последовательности, что и в описанном выше методе треугольника.

Метод суммирования [ править | править код ]

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

Предположим для примера, что нужно найти коэффициент при конъюнкции xz для функции трёх переменных f(x, y, z). В этой конъюнкции отсутствует переменная y. Найдём входные наборы, в которых переменная y принимает нулевое значение. Это наборы 0, 1, 4, 5 (000, 001, 100, 101). Тогда коэффициент при конъюнкции xz равен

a 5 = f 0 ⊕ f 1 ⊕ f 4 ⊕ f 5 = f ( 0 , 0 , 0 ) ⊕ f ( 0 , 0 , 1 ) ⊕ f ( 1 , 0 , 0 ) ⊕ f ( 1 , 0 , 1 ) . <displaystyle a_<5>=f_<0>oplus f_<1>oplus f_<4>oplus f_<5>=f(0,0,0)oplus f(0,0,1)oplus f(1,0,0)oplus f(1,0,1).>

Поскольку с свободном члене отсутствуют все переменные, то

a 0 = f 0 . <displaystyle a_<0>=f_<0>.>

Для члена, куда входят все переменные, в сумму входят все значения функции:

a N − 1 = f 0 + f 1 + f 2 + … + f N − 2 + f N − 1 . <displaystyle a_=f_<0>+f_<1>+f_<2>+ldots +f_+f_.>

Представим графически коэффициенты полинома Жегалкина как суммы по модулю 2 значений функций в некоторых точках. Для этого построим квадратную таблицу, где каждый столбец представляет собой значение функции в одной из точек, а строка — коэффициент полинома Жегалкина. Точка на пересечении некоторого столбца и строки означает, что значение функции в данной точке входит в сумму для данного коэффициента полинома (см. рисунок). Назовём эту таблицу TN, где N — число переменных функции.

Существует закономерность, которая позволяет получить таблицу для функции N переменных, имея таблицу для функции N − 1 переменных. Новая таблица TN+1 компонуется как матрица 2 × 2 таблиц TN, причём правый верхний блок матрицы очищается.

Похожие темы научных работ по математике , автор научной работы — Алехина М. А., Пичугина П. Г.

Текст научной работы на тему «Об одном методе построения полинома Жегалкина»

Алехина М.А., Пичугина П.Г. ОБ ОДНОМ МЕТОДЕ ПОСТРОЕНИЯ ПОЛИНОМА ЖЕГАЛКИНА

Читайте также:  Термины связанные с космосом

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

Преобразование произвольной формулы алгебры логики: сначала строим дизъюнктивную нормальную форму (ДНФ) или конъюнктивную нормальную форму (КНФ), а затем — полином Жегалкина, используя известные соотношения

x = x ©1, x v y = xy = (x © 1)(y © 1) ©1 = xy © x © y . (1)

Метод неопределенных коэффициентов состоит в следующем: записываем булеву функцию в виде полинома Жегалкина с неопределенными коэффициентами. Приравниваем значения функции к значениям полинома на соответствующих наборах переменных и находим неизвестные коэффициенты.

3) На значениях исходной функции f (x, x2. xn) = (f, f2, f. fn ) , строим треугольник Паскаля, складывая каждый раз соответствующие значения функции по модулю 2. Тогда числа на левой стороне полученного треугольника определяют коэффициенты полинома Жегалкина при монотонных конъюнкциях, соответствующих наборам переменных. Напомним, что элементарная конъюнкция называется монотонной, если она не содержит отрицаний переменных. Константа 1 (т. е. элементарная конъюнкция нулевого ранга) считается

по определению монотонной конъюнкцией.

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

f (x,y,z) = (x v y)(y v xz) .

Преобразуем логическую формулу (xvy)(y v xz) , используя формулы (1):

(x v y)(y v xz) = (xy © x © y)((y ©1)xz © (y ©1) © xz) = (xy © x © yXyZ © xz © y ©1© xz) =

= (xy © x © y)(xyz © y ©1) = xyxyz © xyy © xy © xxyz © xy © x © yxyz © yy © y = xyz © xy © x .

Таким образом, полином Жегалкина P(x, y, z) для данной функции имеет вид P(x, y, z) = xyz © xy © x . Теперь построим его методом неопределенных коэффициентов. Для этого запишем нашу функцию в виде многочлена с неопределенными коэффициентами:

f (x, y, z) = Axyz © Bxy © Cxz © Dyz © Ex © Fy © Gz © H , (2)

где A, B, C, D, E, F, G, H e<0,1>.

Таблица истинности нашей функции выглядит следующим образом:

x У z x V y y xz y V xz f = (x V y)( y V xz)

0 0 0 0 1 0 1 0

0 0 1 0 1 0 1 0

0 1 0 1 0 0 0 0

0 1 1 1 0 0 0 0

1 0 0 1 1 0 1 1

1 0 1 1 1 1 1 1

1 1 0 1 0 0 0 0

1 1 1 1 0 1 1 1

Чтобы определить неизвестные коэффициенты, подставим соответствующие значения переменных в правую и левую части формулы (2) и получим систему:

В 0 Р 0 в 0 Н = 0

С 0 Е 0 в 0 Н = 1

В 0 Е 0 ^ 0 Н = 0

А 0 В 0 С 0 В 0 Е 0 ^ 0 в 0 Н = 0

Решая систему, находим коэффициенты:

В = 0 Е = 1 С = 0 В = 1 А = 1

Подставляя найденные значения А, В, С, В, Е, В, О, Н в формулу (2), получим полином Жегалкина того же вида, что и в первом случае: /(х,у,’£) = (хVу)(уVх£) = ху.z©ху©х .

Для реализации третьего метода, зададим исходную функцию набором ее значений /(х,у,г) = (00001101) . На строке значений функции построим треугольник Паскаля, складывая попарно по модулю 2 соседние значения фун кции:

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

Сравнивая предложенные методы построения полинома Жегалкина, студенты (да и преподаватели тоже) отдают предпочтение последнему методу, обосновывая выбор быстротой получения результата и простотой алгоритма построения треугольника Паскаля. Изучая соответствующую данной тематике научную и научнометодическую литературу, мы не нашли строгого доказательства построения полинома Жегалкина с использованием треугольника Паскаля. Поэтому предлагаем свое доказательство для функций двух, трех и четырех переменных (исходя из тех соображений, что на практических занятиях со студентами другие случаи, как правило, не рассматриваются), т. е. п =2, 3, 4.

п=2. Проведем доказательство для булевой функции двух переменных /(х,х2) . Полином Жегалкина для

этой функции в общем виде будет выглядеть следующим образом: / (х, х2) = ахх ® ах ® ах ® аА , (3)

где а1 е <0,1>, I = 1,4 . Таблица истинности данной функции имеет вид:

Значения функции / (1=1,2,3,4) можно определить, подставляя в соотношение (3) всевозможные набо-

ры значений переменных:

Решая систему относительно а,а,а,а, получим:

а4 = А а3 = /1 0 /2 а2 = /1 0 /3

а1 = Л 0 /20 /30 /4

Покажем, что эти коэффициенты совпадают со значениями на левой стороне треугольника Паскаля, построенного для функции /(х,х2) , заданной набором значений ї= (/,/2,/,/) .

Видим, что числа на левой стороне треугольника в точности определяет коэффициенты полинома Жегалкина, найденные при решении системы (см. соотношения (4)).

п=3. Теперь возьмем функцию трех переменных / (х, х2, х3) и представим ее полином Жегалкина с неопределенными коэффициентами а е <0,1>, I = 1,8 :

/(х, х2, х) = аххх ® ахх ® ахх ® ахх ® ах ® ах ® ах ® а • (5)

Строим таблицу истинности исходной функции:

Полином (многочлен) Жегалкина представляет собой полином, коэффициентами которого являются числа $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>$.

$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$ — полином Жегалкина.

Оцените статью
Добавить комментарий

Adblock
detector