Математика
0,0
рейтинг
19 января в 20:02

Разработка → Что нам стоит полином Жегалкина построить… tutorial

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

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

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

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

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

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

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


Требуется построить полином Жегалкина для функции f. Для примера, в качестве функции f возьмем функцию голосования f(x_1, x_2, x_3)=x_1x_2\vee x_2x_3\vee x_1x_3 = (00010111).

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

Таблица значений функции

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

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

Выписываем вектор значений функции

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

Строим треугольник

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

Завершили построение треугольника

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

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

Левая сторона треугольника

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

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

Формирование мономов

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

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

Выбор конъюнкций для полинома

Это и есть конъюнкции, входящие в состав полинома Жегалкина. Осталось лишь выписать сам полином:
f({{x}_{1}},{{x}_{2}},{{x}_{3}})={{x}_{1}}{{x}_{2}}\oplus {{x}_{2}}{{x}_{3}}\oplus {{x}_{1}}{{x}_{3}}.

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

Литература


К сожалению, мне не удалось найти и посмотреть источник, указанный в Википедии:
В.П. Супрун Табличный метод полиномиального разложения булевых функций // Кибернетика. — 1987. — № 1. — С. 116-117.
Алексей @vasiatka
карма
31,0
рейтинг 0,0
Математика
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (19)

  • 0
    Спасибо. Интересная тема, раньше о полиномах Жегалкина не читал.

    Вопрос: есть ли примеры практической пользы от представления логических функций в таком виде? Думаю, что для задач вроде проектирования микросхем операция «исключающее ИЛИ» является невыгодной: на ее реализацию требуется больше логических элементов, чем для базиса вроде «И-НЕ», на котором тоже можно реализовать произвольную лог. функцию.

    И еще. Если найти представление какой-нибудь логической функции в виде полинома Жегалкина — есть ли польза от рассмотрения этого полинома на поле действительных чисел? Имеет ли такой полином какое-нибудь отношение к рассматриваемой логической функции, дает ли он пользу для ее анализа?
    • +2
      Самое главное в что существует только одна АНФ форма для записи функции, в отличии от других форм представлений. Т.е. если превести в данной форме функцию то две эквивалентные функции будут иметь однотипную запись.
      • +2
        А еще главное, что для многих функций это единственное представление имеет сложность O(2^n), в отличии, например, от BDD. Собственно, алгоритм в статье для построения имеет такую же сложность, что ограничивает его применение контрольными для студентов.
    • +2
      есть ли примеры практической пользы от представления логических

      Плиномы Жегалкина или АНФ — удобное представление булевых функций. Их использование можно увидеть во многих работах. С полиномами работать проще и удобнее, чем с ДНФ или КНФ.
      Можно сказать, что это одно из базовых понятий в дискретной математике. Например, понятие линейных функций (см. замкнутые классы, теорема о полноте) вводится с их использованием.
      Еще одной особенностью является отсутствие фиктивных переменных в представлнии функции через АНФ.
      для задач вроде проектирования микросхем операция «исключающее ИЛИ» является невыгодной: на ее реализацию требуется больше логических элементов, чем для базиса вроде «И-НЕ»

      В вопросах схемотехники я, конечно, профан. Буду рад если меня поправят. Элементы типа и-не и или-не эффективно реализуются при помощи транзисторов. Более того, других вариантов нет, и ничего не остается, кроме как реализовать все остальные функции (или, и, не, xor) через и-не или или-не, чтобы использовать изученный математический аппарат.
      Если найти представление какой-нибудь логической функции в виде полинома Жегалкина — есть ли польза от рассмотрения этого полинома на поле действительных чисел? Имеет ли такой полином какое-нибудь отношение к рассматриваемой логической функции, дает ли он пользу для ее анализа?

      Понятие «поля» предпологает наличие двух операций сложения и умножения над элементами. «xor» и «и» вводятся над множеством {0,1}, а не над действительными числами. Может быть я неверно понимаю ваш вопрос?
      • 0
        ничего не остается, кроме как реализовать все остальные функции (или, и, не, xor) через и-не или или-не

        В меру своей компетенции подтверждаю. При автоматизированном синтезе логических схем для реализации в микросхемах (это не относится к FPGA, т.к. там базовыми элементами являются не И-НЕ, а ПЗУ 5x1 или 6x1) заданная разработчиком логическая схема приводится к единому базису (И-НЕ, ИЛИ-НЕ), принятому в используемой архитектуре.

        Как я понял, представление в виде полинома Жегалкина является единственным для любой логической функции, а потому в некотором роде оптимальным. Если бы на транзисторах можно было эффективно реализовать «исключающее ИЛИ» — то задача оптимального синтеза логики была бы этим решена. Наверное, при практическом синтезе схем можно пойти тем путем, чтобы получить сначала полином Жегалкина для требуемой функции, а потом преобразовать его к базису «И-НЕ». Вот если бы еще были гарантии оптимальности такого преобразования.
        • 0
          заданная разработчиком логическая схема приводится к единому базису (И-НЕ, ИЛИ-НЕ)

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

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

          Я правильно понимаю, FPGA — это ПЛИС по нашему?
      • 0
        Понятие «поля» предпологает наличие двух операций сложения и умножения над элементами. «xor» и «и» вводятся над множеством {0,1}, а не над действительными числами. Может быть я неверно понимаю ваш вопрос?

        Ну, это был абстрактный вопрос, аналогично, например, тому, что для каждого линейного дифура существует характеристический полином. Изучая этот полином, можно получить важную информацию о дифуре и его решениях, хотя сам этот полином по своему графику совсем не напоминает решение искомого дифура. Вот я и подумал, может ли быть польза от анализа полинома Жегалкина, если его рассмотреть на поле действительных чисел?
        • 0
          Я таких аналогий не встречал.
    • 0
      Если мне не изменяет память, в 2014 году на ZeroNights ребята из ReCrypt рассказывали, что перевод последовательности инструкций в эту форму значительно упрощает процесс деобфускации.
      • 0
        Спасибо. Действительно, это интересное применение. Получается, что, используя прочие представления логических функций (например, на базисе И-НЕ) нельзя гарантировать единственность?
        • 0
          Да.
          Именно поэтому существуют различные методы минимизации булевых функций. Но Они по большей части для ДНФ и КНФ.
          Пример.
          image
          image
          Это одна и та же функция. В одном и том же базисе.
  • +4
    Читал про полином Жегалкина, не знал про метод Треугольника Паскаля.

    Вот это видео еще в своем время пролило лучик света в мою гуманитарную голову:
    https://www.youtube.com/watch?v=UWy4--GyO4c

    Спасибо. Перечитаю еще потом.
  • +1
    Еще в детстве читал про полином Жегалкина, но до сих пор не знаю: есть ли у него какое-либо практическое применение? Зачем представлять булеву функцию в этой форме?
    • +1
      Сказанное мной ниже в качестве предположения.
      Классическая математика оперирует объектами или реально существующими, или абстрактными, т.е. занимается именно исчислением объектов, и тут на помощь приходит программирование, — операндов.
      Не знаю правильно ли будет сказано — булева алгебра — скажу луше — абстрактная — смещает акцент от исчисления оперндов к исчислению операторов.
      Далее, снова в качестве предположения, полином Жегалкина может сократить проведение теста над длинным формальным высказыванием на предмет его истинности. Делаю это утверждению из того, чтоб было сказано про единственность таблицы истинности для одной функции. А из этого делаю вывод, что можно использовать полином для составления «тестов истинности» логики программ.
    • 0
      Просто исходя из логических сображений — мы получаем полином над кольцом Z2, что позволяет нам строить, к примеру, матрицы этой функции (по аналогии с матрицами квадратичной формы; не знаю, как их назвать в случае булевой алгебры :) ) Возможно, это, как и в случае «обыкновенных» многочленов может дать что-то интересное.
      • 0
        Добавляя себя, возможно, это (представление в виде матриц) позволит намного легче исследовать именно нелинейные системы, состоящие из булевых многочленов, опять же, исходя из аналогии с «обыкновенными» многочленами. Опять же, это лишь мои домыслы и я, честн говоря, не уверен в их правдивости.
    • +2
      Как было сказано выше, это азы дискретной математики.
      Как следствие, практическое применение очень объемно в программировании: компиляторы, логические анализаторы, генераторы и оптимизаторы, экспертные системы, нейронные сети и т.п.
      Такое приведение позволяет унифицировать эквивалентные логические высказывания, приводя их к функции одного вида, при этом сокращая число операций в этой функции.

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

    00010111
    00010110 разбиваем на пары и добавляем левое число каждой пары к правому
    00010111 разбиваем на пары двоек и добавляем левую двойку каждой пары к правой
    00010110 разбиваем на пары четверок и добавляем левую четверку каждой пары к правой.
  • 0
    Решил немного поиграть с задачей из статьи.
    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, что равно полиному в статье.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.