О неприводимости булевых функций относительно коммутативной ассоциативной операциистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 20 января 2021 г.
Аннотация:В работе исследуется проблема представления булевых функций в виде f1*...*fm, где * - коммутативная ассоциативная операция и f1,...,fm - булевы функции меньшей арности. Для каждой коммутативной ассоциативной операции определены необходимые и достаточные условия отсутствия такого представления и найден соответствующий класс алгоритмической сложности.