Древесное представление бесповторных функций в расширенных элементарных базисах

Актуальность и цели. В области информационных технологий аппарат булевых функций играет значительную роль, в связи с чем становится актуальным исследование различных свойств булевых функций. Данная статья посвящена такому важному свойству, как возможность представления функции в заданном базисе формулой без повторения переменных (бесповторной формулой). Представленные таким образом функции можно рассматривать как класс функций, которые в данном базисе устроены достаточно просто. В работе исследуется вопрос представления бесповторных булевых функций помеченными деревьями. Целью данной работы является получение древесного представления для функций, бесповторных в базисах, состоящих из конъюнкции, дизъюнкции, отрицания и поляризуемых функций Стеценко, в котором деревья одинаковых функций изоморфны, а также множества эквивалентных преобразований для деревьев такого вида. Материалы и методы. Используется математический аппарат теории перестановок, свойства помеченных корневых деревьев и индивидуальные свойства поляризуемых функций Стеценко. Результаты и выводы. Получено древесное представление для бесповторных функций в базисах, состоящих из поляризуемых функций Стеценко и элементарного базиса, соответствующее их формулам с поднятым отрицанием, и выявлено множество эквивалентных преобразований для данного типа деревьев.