Порядок длины функций алгебры логики в классе псевдополиномиальных формстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
Аннотация:Псевдополиномиальная форма (ПСПФ) - это сумма по модулю два произведений аффинных (линейных) функций алгебры логики. Длиной ПСПФ называется число ее слагаемых; длиной функции алгебры логики в классе ПСПФ - наименьшая длина среди всех ПСПФ, представляющих эту функцию. В работе рассматривается функция Шеннона L^{\rm \mbox{ПСПФ}}(n) длины функций алгебры логики в классе ПСПФ как наибольшая длина в классе ПСПФ среди всех функций алгебры логики, зависящих от n переменных. Доказано, что L^{\rm \mbox{ПСПФ}}(n) = \Theta\left(2^n/n^2\right ).
Величина L^{\rm \mbox{ПСПФ}}(n) также равна такому наименьшему числу $l$, что каждую функцию алгебры логики, зависящую от n переменных, можно представить как сумму по модулю два не более l мультиаффинных функций.