An artificial neural network satisfiability tester

✍ Scribed by Tatiana Tambouratzis

• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 191 KB
• Volume: 16
• Category: Article
• ISSN: 0884-8173
• DOI: 10.1002/int.1064

✦ Synopsis

An artificial neural network tester for the satisfiability problem of propositional calculus is presented. Satisfiability is treated as a constraint satisfaction optimization problem and, contrary to most of the existing satisfiability testers, the expressions are converted into disjunctive normal form before testing. The artificial neural network is based on the principles of harmony theory. Its basic characteristics are the simulated annealing procedure and the harmony function; the latter constitutes a measure of the satisfiability of the expression under the current truth assignment to its variables. The tester is such Ž . Ž . that: a the satisfiability of any expression is determined; b a truth assignment to the variables of the expression is output which renders true the greatest possible number of Ž . clauses; c all the truth assignments which render true the maximum number of clauses can be produced.