¿Hay un algoritmo para reducir aún más los CNF?

Question

Tengo una fórmula booleana en forma de conjuntiva normal (CNF): $ (A \ Ve B \ Vee C) \ Wedge (A \ Vee B \ Vee \ NEG C) \ Wedge (X \ Vee y) $

Sé que esto se puede simplificar para: $ (A \ vee b) \ wedge (x \ vee y) $ .

a) ¿Hay un algoritmo para decidir si una CNF ya está en la forma reducida o no?

b) ¿Hay un algoritmo que pueda hacer esta reducción de una manera más eficiente que la comparación de cada par de cláusulas para ver si se puede reducir el emparejamiento?Deseo automatizar esta reducción de cualquier CNF y busco cualquier algoritmo que pueda pedir prestado / implementar.

Answer 1

La minimización CNF es difícil;Consulte https://cstheory.stackexchange.com/q/9839/5038 .Ciertamente es NP-HARD, y hay un sentido en el que es "aún más difícil".

Una forma de obtener algo de intuición por qué es difícil es que si el CNF no es satisfactorio, entonces su forma reducida es "Falso", mientras que si es satisfactorio, su forma reducida es otra cosa.Por lo tanto, si tuvo una forma eficiente de encontrar una forma reducida, eso le daría una manera inmediata a saber si el CNF es satisfactorio, una tarea que conocemos es NP-HARD.

ver https://cstheory.stackexchange.com/q/9839/5038 y https://en.wikipedia.org/wiki/logic_optimization#circuit_minimización_in_boolean_algebra para algunos puntos en la literatura enalgoritmos para esta tarea.