Главная особенность этих многочленов состоит в том, что любую булеву функцию можно представить полиномом Жегалкина, причем единственным образом.
Чаще всего для построения полиномов Жегалкина студентам предлагаются два метода построения таких полиномов: метод неопределенных коэффициентов и метод эквивалентных преобразований.
Расчеты с использованием данных методов часто оказываются громоздкими. По невнимательности допустить ошибку не составляет труда.
Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».
Порядок проведения вычислений проще показать на примере. Далее я буду по шагам показывать, как должен выглядеть расчет на бумаге (или как его удобно проводить).
Метод треугольника Паскаля
Требуется построить полином Жегалкина для функции f. Для примера, в качестве функции f возьмем функцию голосования
Шаг 1. Строим таблицу значений функции (строки в таблице идут в порядке возрастания двоичных кодов). Таблицу лучше разместить в левой части листа.
Шаг 2. Построение треугольника.
Для этого берем вектор значения функции и выписываем его напротив первой строки таблицы:
Далее заполняем треугольник, складывая попарно соседние значения по модулю 2, результат сложения выписываем ниже.
Продолжаем вычисления, пока в строке не останется лишь одна цифра.
Шаг 3. Построение полинома Жегалкина.
Нас интересует левая сторона треугольника (значения выделены жирным):
Числа на левой стороне (выделены жирным шрифтом) треугольника есть коэффициенты полинома при монотонных конъюнкциях, соответствующих наборам значений переменных.
Теперь выпишем для наглядности эти конъюнкции. Конъюнкции выписываем по двоичным наборам в левой части таблицы по следующему принципу: если напротив переменной xi стоит 1, то переменная входит в конъюнкцию; в противном случае переменная отсутствует в конъюнкции. Набору (0,0,0) соответствует константа 1.
Если принцип получения конъюнкций понятен, то столбец с ними можно (даже лучше) не выписывать, а сразу переходить к построению полинома.
Для построения полинома нужны только конъюнкции из строк с единицами на левой стороне треугольника.
Это и есть конъюнкции, входящие в состав полинома Жегалкина. Осталось лишь выписать сам полином:
Если переменных в функции не 3, а 4 или больше, то метод работает без изменений, только увеличатся размеры таблиц. Тем не менее, в отличие от метода неопределенных коэффициентов, расчеты можно без особых усилий выполнить на листе бумаги.
Литература
К сожалению, мне не удалось найти и посмотреть источник, указанный в Википедии:
В.П. Супрун Табличный метод полиномиального разложения булевых функций // Кибернетика. — 1987. — № 1. — С. 116-117.
Комментарии (19)
dcc0
19.01.2016 20:51+4Читал про полином Жегалкина, не знал про метод Треугольника Паскаля.
Вот это видео еще в своем время пролило лучик света в мою гуманитарную голову:
https://www.youtube.com/watch?v=UWy4--GyO4c
Спасибо. Перечитаю еще потом.
PavelSandovin
19.01.2016 22:25+1Еще в детстве читал про полином Жегалкина, но до сих пор не знаю: есть ли у него какое-либо практическое применение? Зачем представлять булеву функцию в этой форме?
dcc0
19.01.2016 23:19+1Сказанное мной ниже в качестве предположения.
Классическая математика оперирует объектами или реально существующими, или абстрактными, т.е. занимается именно исчислением объектов, и тут на помощь приходит программирование, — операндов.
Не знаю правильно ли будет сказано — булева алгебра — скажу луше — абстрактная — смещает акцент от исчисления оперндов к исчислению операторов.
Далее, снова в качестве предположения, полином Жегалкина может сократить проведение теста над длинным формальным высказыванием на предмет его истинности. Делаю это утверждению из того, чтоб было сказано про единственность таблицы истинности для одной функции. А из этого делаю вывод, что можно использовать полином для составления «тестов истинности» логики программ.
Morozov_5F
19.01.2016 23:22Просто исходя из логических сображений — мы получаем полином над кольцом Z2, что позволяет нам строить, к примеру, матрицы этой функции (по аналогии с матрицами квадратичной формы; не знаю, как их назвать в случае булевой алгебры :) ) Возможно, это, как и в случае «обыкновенных» многочленов может дать что-то интересное.
Morozov_5F
19.01.2016 23:28Добавляя себя, возможно, это (представление в виде матриц) позволит намного легче исследовать именно нелинейные системы, состоящие из булевых многочленов, опять же, исходя из аналогии с «обыкновенными» многочленами. Опять же, это лишь мои домыслы и я, честн говоря, не уверен в их правдивости.
DolphinSoft
20.01.2016 02:19+2Как было сказано выше, это азы дискретной математики.
Как следствие, практическое применение очень объемно в программировании: компиляторы, логические анализаторы, генераторы и оптимизаторы, экспертные системы, нейронные сети и т.п.
Такое приведение позволяет унифицировать эквивалентные логические высказывания, приводя их к функции одного вида, при этом сокращая число операций в этой функции.
Понятно, что в простых программах, зачастую не акцентируют внимание на подобных вещах, но когда блоки условий разрастаются в страницы однотипного кода, это просто обязано наводить на размышления о подобных преобразованиях.
Тут на помощь и приходят такие финты, как законы де Моргана, полиномы Жегалкина и другие, более сложные механизмы дискретной математики и булевой алгебры.
halyavin
20.01.2016 18:25+1А многомерное Фурье чем студентов не устраивает?
00010111
00010110 разбиваем на пары и добавляем левое число каждой пары к правому
00010111 разбиваем на пары двоек и добавляем левую двойку каждой пары к правой
00010110 разбиваем на пары четверок и добавляем левую четверку каждой пары к правой.
dcc0
23.01.2016 02:20Решил немного поиграть с задачей из статьи.
x1x2 or x2x3 or x1x3, наверное, можно так представить по закону де Моргана:
not( not x1x2 not x2x3 not x1x3 )
А это выражение в свою очередь в качестве (точно не уверен, верно ли)
(x1x2 xor 1)(x2x3 xor 1)(x1x3 xor 1)xor 1
Дальше раскрыть скобки (тут нужно вспомнить про идемпотентность, о которой говорил Кирсанов в лекции).
(x1x2x3 xor x1x2 xor x2x3 xor 1)(x1x3 xor 1) xor 1
x1x2x3 xor x1x2x3 xor x1x2x3 xor x1x2 xor x1x2x3 xor x2x3 xor x1x3
4 позиции сокращаются, остается
x1x2 xor x2x3 xor x1x3, что равно полиному в статье.
MichaelBorisov
Спасибо. Интересная тема, раньше о полиномах Жегалкина не читал.
Вопрос: есть ли примеры практической пользы от представления логических функций в таком виде? Думаю, что для задач вроде проектирования микросхем операция «исключающее ИЛИ» является невыгодной: на ее реализацию требуется больше логических элементов, чем для базиса вроде «И-НЕ», на котором тоже можно реализовать произвольную лог. функцию.
И еще. Если найти представление какой-нибудь логической функции в виде полинома Жегалкина — есть ли польза от рассмотрения этого полинома на поле действительных чисел? Имеет ли такой полином какое-нибудь отношение к рассматриваемой логической функции, дает ли он пользу для ее анализа?
Cobolorum
Самое главное в что существует только одна АНФ форма для записи функции, в отличии от других форм представлений. Т.е. если превести в данной форме функцию то две эквивалентные функции будут иметь однотипную запись.
Arturka
А еще главное, что для многих функций это единственное представление имеет сложность O(2^n), в отличии, например, от BDD. Собственно, алгоритм в статье для построения имеет такую же сложность, что ограничивает его применение контрольными для студентов.
vasiatka
Плиномы Жегалкина или АНФ — удобное представление булевых функций. Их использование можно увидеть во многих работах. С полиномами работать проще и удобнее, чем с ДНФ или КНФ.
Можно сказать, что это одно из базовых понятий в дискретной математике. Например, понятие линейных функций (см. замкнутые классы, теорема о полноте) вводится с их использованием.
Еще одной особенностью является отсутствие фиктивных переменных в представлнии функции через АНФ.
В вопросах схемотехники я, конечно, профан. Буду рад если меня поправят. Элементы типа и-не и или-не эффективно реализуются при помощи транзисторов. Более того, других вариантов нет, и ничего не остается, кроме как реализовать все остальные функции (или, и, не, xor) через и-не или или-не, чтобы использовать изученный математический аппарат.
Понятие «поля» предпологает наличие двух операций сложения и умножения над элементами. «xor» и «и» вводятся над множеством {0,1}, а не над действительными числами. Может быть я неверно понимаю ваш вопрос?
MichaelBorisov
В меру своей компетенции подтверждаю. При автоматизированном синтезе логических схем для реализации в микросхемах (это не относится к FPGA, т.к. там базовыми элементами являются не И-НЕ, а ПЗУ 5x1 или 6x1) заданная разработчиком логическая схема приводится к единому базису (И-НЕ, ИЛИ-НЕ), принятому в используемой архитектуре.
Как я понял, представление в виде полинома Жегалкина является единственным для любой логической функции, а потому в некотором роде оптимальным. Если бы на транзисторах можно было эффективно реализовать «исключающее ИЛИ» — то задача оптимального синтеза логики была бы этим решена. Наверное, при практическом синтезе схем можно пойти тем путем, чтобы получить сначала полином Жегалкина для требуемой функции, а потом преобразовать его к базису «И-НЕ». Вот если бы еще были гарантии оптимальности такого преобразования.
vasiatka
ну я это и говорил. Схемотехника позволяет реализовать только эти элементы. А методы дискретной математики, работают по большей части для ДНФ, КНФ и полиномов. Поэтому, чтобы построить некоторую управляющую функцию надо сначала представить ее в виде ДНФ, КНФ или полинома (используя различные методы синтеза схем), а потом заменить все элементы их представлениями через И-НЕ, ИЛИ-НЕ.
Кстати, подходы к синтезу есть разные. Схемы можно строить минимизируя сложность, или максимизируя надежность. Если говорить о надежности, то при использовании любого из указанных базисов лучший результат не получить (есть базисы которые дают более высокие оценки надежности). Если интересно, могу ссылку дать на автореферат или диссертацию.
Я правильно понимаю, FPGA — это ПЛИС по нашему?
MichaelBorisov
Ну, это был абстрактный вопрос, аналогично, например, тому, что для каждого линейного дифура существует характеристический полином. Изучая этот полином, можно получить важную информацию о дифуре и его решениях, хотя сам этот полином по своему графику совсем не напоминает решение искомого дифура. Вот я и подумал, может ли быть польза от анализа полинома Жегалкина, если его рассмотреть на поле действительных чисел?
vasiatka
Я таких аналогий не встречал.
Greyushko
Если мне не изменяет память, в 2014 году на ZeroNights ребята из ReCrypt рассказывали, что перевод последовательности инструкций в эту форму значительно упрощает процесс деобфускации.
MichaelBorisov
Спасибо. Действительно, это интересное применение. Получается, что, используя прочие представления логических функций (например, на базисе И-НЕ) нельзя гарантировать единственность?
vasiatka
Да.
Именно поэтому существуют различные методы минимизации булевых функций. Но Они по большей части для ДНФ и КНФ.
Пример.
Это одна и та же функция. В одном и том же базисе.