О методах оценивания веса булевых биюнктивных функций

Задача определения веса функции, представимой в виде 2-КНФ (т. е. биюнктивной функции), в общем случае входит в класс труднорешаемых задач перечисления. Однако существуют методы получения верхних и нижних оценок веса таких функций. В работе рассматриваются два метода получения таких оценок: метод включения-исключения и метод, использующий порядковую функцию графа 2-КНФ, представляющей биюнктивную функцию. На основе предложенных методов построен ряд полиномиально вычислимых оценок веса биюнктивных функций.