Представить функцию в виде полинома жегалкина

Представить функцию в виде полинома жегалкина

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

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

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

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

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

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

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

Задача 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 дней.

Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина
  1. Услуги проектирования
  2. Алгебра логики [Ф.Г. Кораблёв]
  3. Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина

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

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

Полином Жегалкина представляет собой сумму по модулю два произведений неинвертированных переменных, а также < если необходимо >константы

Формально полином Жегалкина можно представить в виде

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

$P = a oplus igoplus_ < egin < c >1leq i_1 Примеры полиномов Жегалкина:

  • $ P = B oplus AB;$
  • $ P = X oplus YZ oplus ABX oplus ABDYZ;$
  • $ P = 1 oplus A oplus ABD.$

Полнота

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

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

Исходя из этого, система функций $igllangle wedge, oplus, 1 igr
angle$ является полной:

$x_0$ $x_1$ $dots$ $x_n$ $1$ $land$ $oplus$
$0$ $0$ $dots$ $0$ $1$ $0$ $0$
$1$ $0$ $dots$ $0$ $1$ $0$ $1$
$vdots$ $vdots$ $vdots$ $vdots$ $vdots$ $vdots$ $vdots$
$1$ $1$ $dots$ $1$ $1$ $1$ $0$
. . . сохраняет 0 $0$ $1$ $1$
. . . сохраняет 1 $1$ $1$ $0$
. . . самодвойственная $0$ $0$ $0$
. . . монотонная $1$ $1$ $0$
. . . линейная $1$ $0$ $1$

На основе этой системы и строятся полиномы Жегалкина.

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

Теорема Жегалкина: Каждая булева функция единственным образом представляется в виде полинома Жегалкина.

Заметим, что различных булевых функций от $n$ переменных $2^ < 2^n >$ штук. При этом конъюнкций вида $x_ < i_1 >ldots x_ < i_k >$ существует ровно $2^n$, так как из $n$ возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит $0$ или $1$, то есть существует $2^ < 2^n >$ различных полиномов Жегалкина от $n$ переменных.

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

Построение полинома Жегалкина

Существует несколько способов построения полинома Жегалкина.

По таблице истинности

Пусть для функции $f(x_1,x_2,dots,x_n)$ задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что $ a oplus 1 = ar < a >$, а $ a oplus 0 = a$. За каждую подстановку находим только один коэффициент.

Читайте также:  Как напечатать этикетки на принтере

Пример: Дана функция $f(x_1,x_2,x_3,x_4)$ и её таблица истинности:

$x_1$ $x_2$ $x_3$ $x_4$ $f(x_1,x_2,x_3,x_4)$
1
1
1 1
1
1 1
1 1 1
1 1 1
1 1
1 1
1 1
1 1 1 1
1 1 1
1 1 1
1 1 1 1
1 1 1 1

Построим для неё полином Жегалкина:

$f(x_1,x_2,x_3,x_4) = a_ < 0000 >oplus a_ < 1000 >x_1 oplus a_ < 0100 >x_2 oplus a_ < 0010 >x_3 oplus a_ < 0001 >x_4 oplus a_ < 1100 >x_1 x_2 oplus a_ < 1010 >x_1 x_3 oplus a_ < 1001 >x_1 x_4 oplus \ oplus a_ < 0110 >x_2 x_3 oplus a_ < 0101 >x_2 x_4 oplus a_ < 0011 >x_3 x_4 oplus a_ < 1110 >x_1 x_2 x_3 oplus a_ < 1101 >x_1 x_2 x_4 oplus \ oplus a_ < 1011 >x_1 x_3 x_4 oplus a_ < 0111 >x_2 x_3 x_4 oplus a_ < 1111 >x_1 x_2 x_3 x_4$

Так как $f(0,0,0,0) = 0$, то $a_ < 0000 >= 0$.

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

$f(1,0,0,0) = a_ < 0000 >oplus a_ < 1000 >= 1 Rightarrow a_ < 1000 >= 1$

$f(0,1,0,0) = a_ < 0000 >oplus a_ < 0100 >= 0 Rightarrow a_ < 0100 >= 0$

$f(0,0,1,0) = a_ < 0000 >oplus a_ < 0010 >= 0 Rightarrow a_ < 0010 >= 0$

$f(0,0,0,1) = a_ < 0000 >oplus a_ < 0001 >= 0 Rightarrow a_ < 0001 >= 0$

$f(1,1,0,0) = a_ < 0000 >oplus a_ < 1000 >oplus a_ < 0100 >oplus a_ < 1100 >= 1 Rightarrow a_ < 1100 >= 0$

$f(1,0,1,0) = a_ < 0000 >oplus a_ < 1000 >oplus a_ < 0100 >oplus a_ < 1010 >= 0 Rightarrow a_ < 1010 >= 1$

$f(1,0,0,1) = a_ < 0000 >oplus a_ < 1000 >oplus a_ < 0100 >oplus a_ < 1001 >= 0 Rightarrow a_ < 1001 >= 1$

$f(0,1,1,0) = a_ < 0000 >oplus a_ < 0100 >oplus a_ < 0010 >oplus a_ < 0110 >= 1 Rightarrow a_ < 0110 >= 1$

$f(0,1,0,1) = a_ < 0000 >oplus a_ < 0100 >oplus a_ < 0001 >oplus a_ < 0101 >= 0 Rightarrow a_ < 0101 >= 0$

$f(0,0,1,1) = a_ < 0000 >oplus a_ < 0010 >oplus a_ < 0001 >oplus a_ < 0011 >= 0 Rightarrow a_ < 0011 >= 0$

$f(1,1,1,0) = a_ < 0000 >oplus a_ < 1000 >oplus a_ < 0100 >oplus a_ < 0010 >oplus a_ < 1100 >oplus a_ < 1010 >oplus a_ < 0110 >oplus a_ < 1110 >= 1 Rightarrow a_ < 1110 >= 0$

$f(1,1,0,1) = a_ < 0000 >oplus a_ < 1000 >oplus a_ < 0100 >oplus a_ < 0001 >oplus a_ < 1100 >oplus a_ < 1001 >oplus a_ < 0101 >oplus a_ < 1101 >= 0 Rightarrow a_ < 1101 >= 0$

$f(1,0,1,1) = a_ < 0000 >oplus a_ < 1000 >oplus a_ < 0010 >oplus a_ < 0001 >oplus a_ < 1010 >oplus a_ < 1001 >oplus a_ < 0011 >oplus a_ < 1011 >= 1 Rightarrow a_ < 1011 >= 0$

$f(0,1,1,1) = a_ < 0000 >oplus a_ < 0100 >oplus a_ < 0010 >oplus a_ < 0001 >oplus a_ < 0110 >oplus a_ < 0101 >oplus a_ < 0011 >oplus a_ < 0111 >= 0 Rightarrow a_ < 0111 >= 1$

$f(1,1,1,1) = a_ < 0000 >oplus a_ < 1000 >oplus a_ < 0100 >oplus a_ < 0010 >oplus a_ < 0001 >oplus a_ < 1100 >oplus a_ < 1010 >oplus a_ < 1001 >oplus a_ < 0110 >oplus a_ < 0101 >oplus a_ < 0011 >oplus \ oplus a_ < 1110 >oplus a_ < 1101 >oplus a_ < 1011 >oplus a_ < 0111 >oplus a_ < 1111 >= 0 Rightarrow a_ < 1111 >= 1$

Таким образом, полином Жегалкина выглядит так:

$f(x_1,x_2,x_3,x_4) = x_1 oplus x_1 x_3 oplus x_1 x_4 oplus x_2 x_3 oplus x_2 x_3 x_4 oplus x_1 x_2 x_3 x_4$

Преобразование дизъюнктивной нормальной формы

Этот способ основан на том, что $ X oplus 1 = ar < X >$. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю < так как $ X oplus X = 0 $ >, а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу: $ A lor B = AB oplus A oplus B $ $ (1) $.

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

Пример: Дана функция в ДНФ $ f(x_1,x_2,x_3,x_4) = (x_1 land x_2 land
eg x_3 land x_4) lor (
eg x_1 land
eg x_4) lor (x_1 land x_2) lor x_2 $, построим полином Жегалкина.

Запишем функцию так:

$f(x_1,x_2,x_3,x_4) = x_1 x_2
eg x_3 x_4 +
eg x_1
eg x_4 + x_1 x_2 + x_2$;

Сгруппируем слагаемые и воспользуемся преобразованием (1):

$f(x_1,x_2,x_3,x_4) = (x_1 x_2
eg x_3 x_4 oplus
eg x_1
eg x_4 oplus x_1 x_2
eg x_3 x_4
eg x_1
eg x_4) + (x_1 x_2 oplus x_2 oplus oplus x_1 x_2 x_2)$

Воспользуемся свойствами конъюнкции $A land A = A$ и $
eg A land A = 0$, а также тем, что $A oplus A = 0$, и упростим выражение:

$f(x_1,x_2,x_3,x_4) = (x_1 x_2
eg x_3 x_4 oplus
eg x_1
eg x_4) + x_2$

Читайте также:  Как добавить звук на динамиках

Ещё раз воспользуемся преобразованием (1):

$f(x_1,x_2,x_3,x_4) = x_1 x_2
eg x_3 x_4 oplus
eg x_1
eg x_4 oplus x_2 oplus (x_1 x_2
eg x_3 x_4 oplus
eg x_1
eg x_4) x_2$

Раскроем скобку по алгебраическим правилам:

$f(x_1,x_2,x_3,x_4) = x_1 x_2
eg x_3 x_4 oplus
eg x_1
eg x_4 oplus x_2 oplus x_1 x_2 x_2
eg x_3 x_4 oplus
eg x_1 x_2
eg x_4$

Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ:

$f(x_1,x_2,x_3,x_4) =
eg x_1
eg x_4 oplus x_2 oplus
eg x_1 x_2
eg x_4$

Заменим отрицание на прибавление $1$:

$f(x_1,x_2,x_3,x_4) = (x_1 oplus 1) (x_4 oplus 1) oplus x_2 oplus (x_1 oplus 1) x_2 (x_4 oplus 1)$

$f(x_1,x_2,x_3,x_4) = x_1 x_4 oplus x_1 oplus x_4 oplus 1 oplus x_2 oplus x_1 x_2 x_4 oplus x_1 x_2 oplus x_2 x_4 oplus x_2$

Выкинем парные слагаемые и получим окончательную формулу:

$f(x_1,x_2,x_3,x_4) = x_1 x_2 x_4 oplus x_1 x_2 oplus x_1 x_4 oplus x_2 x_4 oplus x_1 oplus x_4 oplus 1$

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

Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

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

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

Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных $P(A,B,C)$ показан на рисунке.

Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца $»P»$ таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.

Таким образом, в первом столбце сверху записан коэффициент $ a_0 = P(0,0,0) $,

во втором — $ a_1 = P(0,0,0) oplus P(0,0,1) $,

в третьем — $ a_2 = P(0,0,0) oplus P(0,0,1) oplus P(0,0,1) oplus P(0,1,0) = P(0,0,0) oplus P(0,1,0) $,

$ a_3 = P(0,0,0) oplus P(0,0,1) oplus P(0,0,1) oplus P(0,0,1) oplus P(0,1,0) oplus P(0,1,0) oplus P(0,1,0) oplus P(0,1,1) = \ = P(0,0,0) oplus P(0,1,0) oplus P(0,1,0) oplus P(0,1,1), $

и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.

Преобразование Мёбиуса

Пусть задана булева функция $f: B^n
ightarrow B, ;; B= < 0; 1 >$. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.

Пусть $ i = (i_1, i_2, .. i_n), ;; i_k in < 0 ; 1 >$, и введем обозначение $ x ^ < i_k >sim left[egin < matrix >x,;; i_k=1 1, ;; i_k=0end < matrix >
ight. $

Тогда полином Жегалкина можно записать как: $ f(x) = igopluslimits_i alpha_i cdot x_1^ < i_1 >cdot x_2^ < i_2 >cdot$$dots$$cdot x_n^ < i_n >$, где $alpha_i in < 0; 1 >$.

Множество коэффициентов $ < alpha _i >$ можно рассматривать как функцию $alpha$, заданной на множестве индексов $ i = (i_1, i_2, dots i_n)$, то есть $alpha: i mapsto alpha_i$.

Очевидно, функцию $ f $ можно записать и следующим образом: $ f(x) = igoplus limits_i alpha_i cdot [x_1 , ; $ если $ ;; i_1] cdot [x_2 , ; $ если $ ;; i_2] cdot$$dots$$cdot [x_n , ; $ если $ ;; i_n]$.

Тут запись $[x_k , ; $ если $ ; i_k]$ означает, что элелемент $ x_k $ присутствует в соответствующем члене полинома только если $ i_k = 1 $. Тогда если для какого-то $x$, $i succ x$* ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет. Отсюда ясно, что $ f(x) = igoplus limits_ < i preceq x >alpha_i $ $ (2) $ Найдем отображение $ f mapsto alpha$ < То есть такое, которое по заданной функции вычисляет значения всех коэффициентов >.

$*$ $i succ x$ обозначает, что $x$ "меньше" $i$ как последовательность бит

Теорема: Пусть задана функция $ f $. Тогда функцию $ alpha_x $ можно найти по формуле: $alpha_x = igoplus limits_ < jpreceq x >f(j)$ (3)

Докажем при помощи индукции по количеству единиц в векторе $ x $ < иначе говоря, по сумме $x_1+x_2+dots +x_n$ >и для удобства обозначим это количество единиц < сумму >$ wt(x) $.

1) База: если $ x = 0 $, то, очевидно $ f(0) = alpha_0 $

2) Пускай теорема справедлива для всех сумм $wt(x) Огравление $Rightarrow $

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

Читайте также:  Как обновить юнити 3д

С помощью полинома Жегалкина можно представить любую булеву функцию, причем единственных образом. Поэтому можно сказать, что полином Жегалкина является еще одним способом представления булевых функций в алгебре операций $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$ — полином Жегалкина.

Ссылка на основную публикацию
Почему не запускается игра spin tires
Некоторые игроки наблюдают проблемы в игре Spintires: MudRunner (2017). У игроков в Spintires: MudRunner (2017) - игра тормозит, низкий ФПС(FPS),...
Портал госуслуг нижний новгород регистрация
Зарегистрироваться на госуслугах и создать свой личный кабинет для доступна ко всем услугам официального сайта. Доступ к порталу открыт для...
Портал госуслуг йошкар ола личный кабинет
Для пользования государственными услугами в режиме онлайн следует перейти на официальный портал Госуслуги.ру. Далее вам предложат зарегистрироваться в системе. В...
Почему не запускается тайм вивер
TeamViewer — очень полезная и функциональная программа. Иногда пользователи сталкиваются с тем, что она перестает запускаться непонятно почему. Что делать...
Adblock detector