Реализация булевых функций с ограниченным числом нулей в классе дизъюнктивных нормальных форм

Рассматривается задача построения простых дизъюнктивных нормальных форм (ДНФ) булевых функций с малым числом нулей. Указанная задача интересна как в контексте исследования сложности булевых функций, так и с точки зрения ее приложений в задачах анализа данных. Метод, используемый в работе, является развитием редукционного подхода к построению ДНФ булевых функций. Ключевой идеей редукционного метода является представление булевой функции в виде дизъюнкции булевых функций с меньшим числом нулей. В ряде практически важных случаев предлагаемая техника позволяет значительно снизить сложность ДНФ реализации булевых функций. Библ. 41.