Pull to refresh

Comments 20

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отвечаю на свой же вопрос. Системы image и image — моноиды, а image — уже абелева группа. Комбинация image и image по image дают поле image. Полином Жегалкина предоставляет удобные механизмы абелевых групп для анализа логических функций, что не имеет места для ДНФ/КНФ.
Sign up to leave a comment.

Articles