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