Классификация монотонных булевых функций при синтезе цифровых схем

Abstract

Классификация монотонных булевых функций (МБФ) по типам позволяет значительно сократить их перебор при синтезе цифровых схем. Связь типов и функциональных схем МБФ позволяет рассматривать только те типы, которые отвечают заданным свойствам схемы. Введены понятия максимального типа, ранга типа, веса типа, мощности типа, левой и правой границы типа. В работе исследованы МБФ с типами веса 1 и 2. Рассмотрены модельные функции типов и матрицы распределения максимальных типов. Выведена явная формула для перечисления МБФ с типом веса 1, которые имеют заданное число фиктивных переменных. Выведена рекуррентная формула для нахождения максимальных типов веса 2.