Y a-t-il un algorithme pour réduire davantage les CNF

Question

J'ai une formule booléenne sous forme normale conjonctive (CNF): $ (A \ vee b \ vee c) \ wedge (a \ vee b \ vee \ neg c) \ wedge (x \ vee y) $

Je sais que cela peut être simplifié pour: $ (a \ vee b) \ wedge (x \ vee y) $ .

a) existe-t-il un algorithme pour décider si un CNF est déjà sous la forme réduite ou non?

B) Existe-t-il un algorithme qui peut effectuer cette réduction de manière plus efficace que la comparaison de chaque paire de clauses pour voir si une appariement peut être réduite?Je souhaite automatiser cette réduction pour tout CNF et je cherche des algorithmes que je peux emprunter / mettre en œuvre.

Answer 1

La minimisation CNF est difficile;Voir https://cstheory.stackexchange.com/q/9839/5038 .C'est certainement NP-dur, et il y a un sens dans lequel il est "encore plus difficile".

Un moyen d'obtenir une certaine intuition pourquoi il est difficile, c'est que si le CNF n'est pas satisfait, sa forme réduite est "FALSE", alors que si elle est satisfaite, sa forme réduite est autre chose.Donc, si vous aviez un moyen efficace de trouver une forme réduite, cela vous donnerait immédiatement un moyen de dire si le CNF est satisfait - une tâche que nous savons est NP-dur.

voir https://cstheory.stackexchange.com/q/9839/5038 et https://fr.wikipedia.org/wiki/logic_optimization#Circuit_algebra Pour certains points dans la littérature sur la littératurealgorithmes pour cette tâche.