可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。

Sufficient and necessary conditions for SAT

Satisfiability problem abbreviated to SAT is a very important problem in computer science and artificial intelligence and is firstly proved to be a NPC problem.In this paper,the sets of clauses are researched,giving the definitions of flipping,simple sets of clauses and flipping isomorphism.Moreover,I prove that flipping doesn't affect the satisfiability of a set of clauses and three sufficient and necessary conditions are proved.In the end of this paper,it is simply discussed that these conditions can be utilized in complete algorithm and incomplete algorithm of SAT.