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

Abstract

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