О характеристическом свойстве одного класса нормализованных формул, реализующих линейные булевы функции

Аннотация

Посредством модификации предложенного С. В. Яблонским метода построения реализующей данную линейную булеву функцию экономной (гипотетически минимальной) нормализованной формулы ($\Pi$-схемы) построен целый класс подобных формул --  класс  так называемых оптимальных совершенных нормализованных формул. Предположительно он является  классом всех реализующих эту функцию минимальных нормализованных формул. С целью доказательства этой гипотезы рассматривается расширение указанного класса до класса также реализующих ту же функцию совершенных нормализованных формул. Установлено, что нормализованная формула тогда и только тогда является совершенной, когда она имеет совершенное представление на собственном прямоугольнике указанной функции.