Дискретные функции

О числе решений систем булевых уравнений, состоящих из дизъюнктов ранга $2$ и возникающих в методе следствий решения систем булевых уравнений

К. Д. Лушников


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

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

УДК: 519.716.5

DOI: 10.17223/2226308X/18/19