О длине булевых функций в классе полиномиальных форм с аффинными множителями в слагаемыхстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
Аннотация:В работе изучается представление булевых функций полиномиальными формами (по модулю два) с аффинными множителями в слагаемых. Полиномиальная форма с аффинными множителями в слагаемых (п.ф.а.м.) - это сумма по модулю два произведений аффинных (линейных) булевых функций. В англоязычной литературе такие полиномиальные формы называются EXOR Sums of Pseudoproducts (ESPPs). Вводится понятие длины п.ф.а.м. как числа ее слагаемых и длины булевой функции в классе п.ф.а.м. как минимальной длины среди всех п.ф.а.м., представляющих эту функцию. Рассматривается функция Шеннона L{p.f.a.}(n) длины булевых функций в классе п.ф.а.м, равная максимальной длине в классе п.ф.а.м. среди всех булевых функций, зависящих от n переменных. Найдены нижняя и верхняя оценки функции Шеннона L{p.f.a.}(n). При доказательстве верхней оценки функции Шеннона предложен алгоритм, который может применяться при построении полиномиальных форм с аффинными множителями в слагаемых для конкретных булевых функций.