C'è un algoritmo per ridurre ulteriormente i CNF

Question

Ho una formula booleana nella forma normale congiuntiva (CNF): $ (A \ Vee B \ Vee c) \ Wedge (A \ Vee B \ Vee \ neg c) \ wedge (x \ vee y) $

So che questo può essere semplificato per: $ (A \ Vee B) \ Wedge (x \ Vee y) $ .

a) C'è un algoritmo per decidere se un CNF è già in forma ridotta o no?

b) Esiste un algoritmo che può fare questa riduzione in modo più efficiente rispetto a ciascuna coppia di clausole per vedere se qualsiasi accoppiamento può essere ridotto?Desidero automatizzare questa riduzione per qualsiasi CNF e sto cercando qualsiasi algoritmo che posso prendere in prestito / implementare.

Answer 1

Minimizzazione del CNF è difficile;Vedi https://cstheory.stackexchange.com/Q/9839/5038 .È certamente difficile NP, e c'è un senso in cui è "ancora più difficile".

Un modo per ottenere un'intuizione perché è difficile è che se il CNF non è soddisfacente, la sua forma ridotta è "falsa", mentre se è soddisfatta, la sua forma ridotta è qualcos'altro.Quindi, se avessi un modo efficiente per trovare una forma ridotta, ciò ti darà immediatamente un modo per dire se il CNF è soddisfavole - un compito che conosciamo è NP-Hard.

Vedi https://cstheory.stackexchange.com/Q/9839/5038 e https://en.wikipedia.org/wiki/logic_optimization#circuit_minimization_in_boolean_algebra per alcuni punti nella letteratura suAlgoritmi per questo compito.