Есть ли алгоритм для уменьшения CNFS

Question

У меня есть логическая формула в конъюнктивной нормальной форме (CNF): $ (A \ vee b \ vee c) \ enge (a \ vee b \ vee \ neg c) \ enge (x \ vee y) $

Я знаю, что это может быть упрощено: $ (A \ vee b) \ enge (x \ vee y) $ .

a) Есть ли алгоритм для решения, если CNF уже находится в уменьшенной форме или нет?

b) Есть ли алгоритм, который может сделать это снижение эффективнее, чем сравнивать каждую пару пунктов, чтобы увидеть, можно ли уменьшить любую сопряжение?Я хочу автоматизировать это уменьшение для любого CNF и ищете любые алгоритмы, которые я могу одолжить / внедрить.

Answer 1

Минимизация CNF сложно;Смотрите https://cstheory.stackexchange.com/q/9839/5038 .Это, безусловно, NP-трудно, и есть смысл, в котором оно «даже сложнее».

Один из способов получить некоторую интуицию, почему трудно в том, что если CNF не удовлетворяется, то его уменьшенная форма - это «ложь», тогда как если она удовлетворялась, его уменьшенная форма - это что-то другое.Итак, если у вас был эффективный способ найти сниженную форму, которая сразу же даст вам способ сказать, является ли CNF удовлетворена - задача, которую мы знаем, это NP-Hard.

см. см. https://cstheory.stackexchange.com/q/9839/5038 и https://en.wikipedia.org/wiki/logic_optimization#Circuit_minimization_in_boolean_Algebra для некоторых точек в литературеалгоритмы для этой задачи.