Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Шурыгин Д.М.
О длине системы функции сумматора и функции компаратора в классе псевдополиномиальных форм
Аннотация:
Задача реализации булевых функций в полиномиальных формах находит применения при синтезе логических схем, в дискретных моделях системной биологии. Одним из классов полиномиальных форм является класс псевдополиномиальных форм (ПСПФ) - выражений, являющихся суммой по модулю два конъюнкций полиномов Жегалкина линейных функций. Последние годы активно исследуются свойства реализации булевых функций в классе ПСПФ. Одной из сложностных характеристик реализации функций в классе ПСПФ является длина - минимальное количество слагаемых среди всех ПСПФ, реализующих функцию. В докладе будут представлены результаты об оценке длин системы функций сумматора и функции компаратора в классе ПСПФ.