Полином жегалкина по вектору значений

Полином жегалкина по вектору значений

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

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

Начало. Задана совершенная ДНФ функции 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 и дизъюнкция с исключением aПолином жегалкина по вектору значенийb уже являются полиномами Жегалкина. Полином Жегалкина инверсии a =1Полином жегалкина по вектору значенийa.

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

Полином жегалкина по вектору значений

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

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

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

[ подставим полиномы Жегалкина обратной импликации 1 Полином жегалкина по вектору значенийb Полином жегалкина по вектору значенийab при a=xПолином жегалкина по вектору значенийy, 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, раскрыть скобки и вычеркнуть пары одинаковых слагаемых, то получится полином Жегалкина.

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

Полином жегалкина по вектору значений

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

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

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

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

f(0,0) = c0 Полином жегалкина по вектору значенийc10 Полином жегалкина по вектору значенийc20 Полином жегалкина по вектору значенийc30 0 = c0

f(0,1) = c0 Полином жегалкина по вектору значенийc11 Полином жегалкина по вектору значенийc20 Полином жегалкина по вектору значенийc30 1 = c0 Полином жегалкина по вектору значенийc1

f(1,0) = c0 Полином жегалкина по вектору значенийc10 Полином жегалкина по вектору значенийc21 Полином жегалкина по вектору значенийc31 0 = c0 Полином жегалкина по вектору значенийc2

f(1,1) = c0 Полином жегалкина по вектору значенийc11 Полином жегалкина по вектору значенийc21 Полином жегалкина по вектору значенийc31 1 = c0 Полином жегалкина по вектору значенийc1 Полином жегалкина по вектору значенийc2 Полином жегалкина по вектору значенийc3

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

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

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

Полином жегалкина по вектору значений

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

Содержание
  1. Что нам стоит полином Жегалкина построить…
  2. Метод треугольника Паскаля
  3. Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.
  4. Как пользоваться калькулятором
  5. Видеоинструкция к калькулятору
  6. Используемые символы
  7. Обозначения логических операций
  8. Что умеет калькулятор
  9. Что такое булева функция
  10. Что такое таблица истинности?
  11. Логические операции
  12. Таблица истинности логических операций
  13. Как задать логическую функцию
  14. Способы представления булевой функции
  15. Совершенная дизъюнктивная нормальная форма (ДНФ)
  16. Совершенная конъюнктивная нормальная форма (КНФ)
  17. Алгебраическая нормальная форма (АНФ, полином Жегалкина)
  18. Алгоритм построения СДНФ для булевой функции
  19. Алгоритм построения СКНФ для булевой функции
  20. Алгоритм построения полинома Жегалкина булевой функции
  21. Примеры построения различных представлений логических функций
  22. Построение совершенной дизъюнктивной нормальной формы:
  23. Построение совершенной конъюнктивной нормальной формы:
  24. Построение полинома Жегалкина:
  25. 🎦 Видео

Видео:Полином ЖегалкинаСкачать

Полином Жегалкина

Что нам стоит полином Жегалкина построить…

Думаю, каждый, кто изучал или изучает в университете дискретную математику, знаком с понятием многочлена Жегалкина.

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

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

Расчеты с использованием данных методов часто оказываются громоздкими. По невнимательности допустить ошибку не составляет труда.

Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».

Порядок проведения вычислений проще показать на примере. Далее я буду по шагам показывать, как должен выглядеть расчет на бумаге (или как его удобно проводить).

Видео:A.2.19 Полином ЖегалкинаСкачать

A.2.19 Полином Жегалкина

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

Требуется построить полином Жегалкина для функции f. Для примера, в качестве функции f возьмем функцию голосования Полином жегалкина по вектору значений.

Шаг 1. Строим таблицу значений функции (строки в таблице идут в порядке возрастания двоичных кодов). Таблицу лучше разместить в левой части листа.

Полином жегалкина по вектору значений

Шаг 2. Построение треугольника.

Для этого берем вектор значения функции и выписываем его напротив первой строки таблицы:

Полином жегалкина по вектору значений

Далее заполняем треугольник, складывая попарно соседние значения по модулю 2, результат сложения выписываем ниже.

Полином жегалкина по вектору значений

Продолжаем вычисления, пока в строке не останется лишь одна цифра.

Полином жегалкина по вектору значений

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

Нас интересует левая сторона треугольника (значения выделены жирным):

Полином жегалкина по вектору значений

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

Теперь выпишем для наглядности эти конъюнкции. Конъюнкции выписываем по двоичным наборам в левой части таблицы по следующему принципу: если напротив переменной xi стоит 1, то переменная входит в конъюнкцию; в противном случае переменная отсутствует в конъюнкции. Набору (0,0,0) соответствует константа 1.

Полином жегалкина по вектору значений

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

Для построения полинома нужны только конъюнкции из строк с единицами на левой стороне треугольника.

Полином жегалкина по вектору значений

Это и есть конъюнкции, входящие в состав полинома Жегалкина. Осталось лишь выписать сам полином:
Полином жегалкина по вектору значений

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

Видео:Многочлен полином Жегалкина Метод неопределенных коэффициентов Метод треугольника ПаскаляСкачать

Многочлен полином Жегалкина  Метод неопределенных коэффициентов  Метод треугольника Паскаля

Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.

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

Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина

введите функцию или её вектор

Построено таблиц, форм:

Видео:Полином ЖегалкинаСкачать

Полином Жегалкина

Как пользоваться калькулятором

  1. Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
  2. Укажите действия, которые необходимо выполнить с помощью переключателей
  3. Укажите, требуется ли вывод решения переключателем «С решением»
  4. Нажмите на кнопку «Построить»

Видео:A.2.15 Построение совершенных дизъюнктивной и конъюнктивной нормальных форм (СДНФ и СКНФ)Скачать

A.2.15 Построение совершенных дизъюнктивной и конъюнктивной нормальных форм (СДНФ и СКНФ)

Видеоинструкция к калькулятору

Используемые символы

В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a , x , a1 , B , X , X1 , Y1 , A123 и так далее.

Для записи логических операций можно использовать как обычные символы клавиатуры ( * , + , ! , ^ , -> , = ), так и символы, устоявшиеся в литературе ( ∧ , ∨ , ¬ , ⊕ , → , ≡ ). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите «Показать клавиатуру»), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.

Для смены порядка выполнения операций используются круглые скобки ().

Обозначения логических операций

  • И (AND): & • ∧ *
  • ИЛИ (OR): ∨ +
  • НЕ (NOT): ¬ !
  • Исключающее ИЛИ (XOR): ⊕ ^
  • Импликация: -> → =>
  • Эквивалентность: =

Что умеет калькулятор

  • Строить таблицу истинности по функции
  • Строить таблицу истинности по двоичному вектору
  • Строить совершенную конъюнктивную нормальную форму (СКНФ)
  • Строить совершенную дизъюнктивную нормальную форму (СДНФ)
  • Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
  • Определять принадлежность функции к каждому из пяти классов Поста
  • Строить карту Карно
  • Минимизировать ДНФ и КНФ
  • Искать фиктивные переменные

Видео:СДНФ СКНФ Полином Жегалкина для логических выраженийСкачать

СДНФ СКНФ Полином Жегалкина для логических выражений

Что такое булева функция

Булева функция f(x1, x2, . xn) — это любая функция от n переменных x1, x2, . xn, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1. То есть это правило, по которому произвольному набору нулей и единиц ставится в соответствие значение 0 или 1. Подробнее про булевы функции можно посмотреть на Википедии.

Видео:Многочлен полином Жегалкина Метод неопределенных коэффициентовСкачать

Многочлен полином Жегалкина  Метод неопределенных коэффициентов

Что такое таблица истинности?

Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов. Таблица состоит из n+1 столбцов и 2 n строк, где n — число используемых переменных. В первых n столбцах записываются всевозможные значения аргументов (переменных) функции, а в n+1-ом столбце записываются значения функции, которые она принимает на данном наборе аргументов.

Довольно часто встречается вариант таблицы, в которой число столбцов равно n + число используемых логических операций. В такой таблице также первые n столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.

Видео:Представление в виде Полинома Жегалкина функции заданной в виде СДНФСкачать

Представление в виде Полинома Жегалкина функции заданной в виде СДНФ

Логические операции

Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).

Таблица истинности логических операций

aba ∧ ba ∨ b¬a¬ba → ba = ba ⊕ b
000011110
010110101
100101001
111100110

Видео:Многочлен полином Жегалкина Метод треугольника Паскаля Преобразование формулСкачать

Многочлен полином Жегалкина  Метод треугольника Паскаля  Преобразование формул

Как задать логическую функцию

Есть множество способов задать булеву функцию:

  • таблица истинности
  • характеристические множества
  • вектор значений
  • матрица Грея
  • формулы

Рассмотрим некоторые из них:

Чтобы задать функцию через вектор значений необходимо записать вектор из 2 n нулей и единиц, где n — число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).

Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c

Видео:Полиномы Жегалкина. Замыкание и замкнутые классы. 3 лекцияСкачать

Полиномы Жегалкина. Замыкание и замкнутые классы. 3 лекция

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

С помощью формул можно получать огромное количество разнообразных функций, причём с помощью разных формул можно получить одну и ту же функцию. Иногда бывает весьма полезно узнать, как построить ту или иную функцию, используя лишь небольшой набор заданных операций или используя как можно меньше произвольных операций. Рассмотрим основные способы задания булевых функций:

  • Совершенная дизъюнктивная нормальная форма (СДНФ)
  • Совершенная конъюнктивная нормальная форма (СКНФ)
  • Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Совершенная дизъюнктивная нормальная форма (ДНФ)

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

Например, ДНФ является функция ¬a bc ∨ ¬a ¬b c ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.

Совершенная конъюнктивная нормальная форма (КНФ)

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

Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.

Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.

Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1

Алгоритм построения СДНФ для булевой функции

  1. Построить таблицу истинности для функции
  2. Найти все наборы аргументов, на которых функция принимает значение 1
  3. Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
  4. Объединить все простые конъюнкции с помощью дизъюнкции

Алгоритм построения СКНФ для булевой функции

  1. Построить таблицу истинности для функции
  2. Найти все наборы аргументов, на которых функция принимает значение 0
  3. Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
  4. Объединить все простые дизъюнкции с помощью конъюнкции

Алгоритм построения полинома Жегалкина булевой функции

Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.

  1. Построить таблицу истинности для функции
  2. Добавить новый столбец к таблице истинности и записать в 1, 3, 5. ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6. прибавить по модулю два значения из соответственно 1, 3, 5. строк.
  3. Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10. строк, а к 3, 4, 7, 8, 11, 12. строкам аналогично предыдущему пункту прибавить переписанные значения.
  4. Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
  5. Выписать булевы наборы, на которых значение последнего столбца равно единице
  6. Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.

Видео:Математическая логика и теория алгоритмов 4. Полиномы Жегалкина. ЗамыканиеСкачать

Математическая логика и теория алгоритмов 4. Полиномы Жегалкина. Замыкание

Примеры построения различных представлений логических функций

Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬a b∨ ¬b c∨ca

1. Построим таблицу истинности для функции

abc¬a¬a ∧b¬b¬b ∧c¬a ∧b∨ ¬b ∧cc∧a¬a ∧b∨ ¬b ∧c∨c∧a
0001010000
0011011101
0101100101
0111100101
1000010000
1010011111
1100000000
1110000011

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

Найдём наборы, на которых функция принимает истинное значение:

В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:

Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:

Построение совершенной конъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает ложное значение:

В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:

Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:

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

Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:

abcF1
00000
0011⊕ 01
01011
0111⊕ 10
10000
1011⊕ 01
11000
1111⊕ 01

Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:

abcF12
000000
001111
01011⊕ 01
01110⊕ 11
100000
101111
11000⊕ 00
11111⊕ 10

Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:

abcF123
0000000
0011111
0101111
0111011
100000⊕ 00
101111⊕ 10
110000⊕ 11
111110⊕ 11

Окончательно получим такую таблицу:

abcF123
0000000
0011111
0101111
0111011
1000000
1011110
1100001
1111101

Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):

Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc

Programforyou — это сообщество, в котором Вы можете подтянуть свои знания по программированию, узнать, как эффективно решать те или иные задачи, а также воспользоваться нашими онлайн сервисами.

🎦 Видео

20-2 Полиномы ЖегалкинаСкачать

20-2 Полиномы Жегалкина

Многочлен Жегалкина.Скачать

Многочлен Жегалкина.

Лекция 2. Полином Жегалкина (теоретическая часть)Скачать

Лекция 2. Полином Жегалкина (теоретическая часть)

Алгебра ЖегалкинаСкачать

Алгебра Жегалкина

Лекция по дискретной математике №4. Принцип двойственности. СДНФ, СКНФ. Полином Жигалкина.Скачать

Лекция по дискретной математике №4. Принцип двойственности. СДНФ, СКНФ. Полином Жигалкина.

ДНФ. Импликанты. Полиномы Жегалкина. 2 семинарСкачать

ДНФ. Импликанты. Полиномы Жегалкина. 2 семинар

Полиномы ЖегалкинаСкачать

Полиномы Жегалкина

Старостин М.В. - Теория дискретных функций. Семинары - 4. Булевы функции. Полином ЖегалкинаСкачать

Старостин М.В. -  Теория дискретных функций. Семинары - 4. Булевы функции. Полином Жегалкина

Дискретная математика. Видео 3. Полнота системы функций.Скачать

Дискретная математика. Видео 3. Полнота системы функций.
Поделиться или сохранить к себе: