optimizationsatisfiabilitycnf

CNF simplification


Given a set of clauses, I want to first check whether they are satisfiable. If they are, I want to simplify them and create a CNF, eg., (a OR b) ^ (NOT b) should simplify to: a ^ (NOT b). I'm only working with propositional formulas. I've tried to use Java SAT4j library for doing this. It can show me whether the set of clauses are satisfiable, but doesn't seem to have any method for returning me a simplified CNF. What can I do for simplifying CNF efficiently? Are there any Java or Python implementations for this?


Solution

  • You could use the Riss3g Coprocessor of Norbert Manthey to simplify your CNF.

    The SAT solver minisat 2 allows to store the preprocessed CNF in a file.

    Lingeling, a SAT solver from Austria has an option "-s" to simplify CNF clauses.

    To convert a Boolean expression into a simplified CNF, you could use bc2cnf.