On length of Boolean functions of a small number of variables in the class of pseudo-polynomials

Минимизация функций алгебры логики при различных их представлениях востребована при логическом проектировании цифровых устройств. Среди других представлений рассматриваются полиномиальные формы. Полиномиальной формой называется выражение, являющееся суммой по модулю два произведений сомножителей определенного вида. Можно выделить такие классы полиномиальных форм, как поляризованные полиномиальные, полиномиальные нормальные, псевдополиномиальные и др. В ряде работ разработаны алгоритмы минимизации и получены оценки длины функций в этих классах полиномиальных форм. При этом исследования ведутся в нескольких направлениях, в частности, получение оценок длины самых сложных функций $n$ переменных для произвольных $n$ и нахождение точной длины функций малого числа переменных.
Настоящая работа посвящена нахождению точной длины функций малого числа переменных. В ней рассматриваются псевдополиномиальные формы для функций алгебры логики. Под псевдополиномиальной формой (ПСПФ), или псевдополиномом, понимается выражение, являющееся суммой по модулю двух произведений линейных функций. Длиной ПСПФ называется число ее слагаемых; длиной функции алгебры логики в классе ПСПФ — наименьшая длина среди всех ПСПФ, представляющих эту функцию. В работе получена полная классификация по длине в классе ПСПФ функций, зависящих от четырех переменных. Для функций, зависящих от пяти переменных, найдена наибольшая и средняя длина в классе ПСПФ.