| 摘要: |
| 二元可满足性问题是一个多项式可解的问题．本文首先证明了该问题有解的充要条件，然后给出了判定该问题的一个新的多项式算法．如果判定某个表达式是可满足的话，那么求解算法不需要任何回溯就能准确地给出它的每个解．本文试图通过对二元可满足性的研究为研究其它问题提供一点启示． |
| 关键词: 二元组 解的相容性 布尔表达式的恒等变换 子句集 极大式 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| AN SUFFICIENT AND NECESSARY CONDITION FOR 2SAT PROBLEM |
|
Wu Xiangjun,Yu Fengren
|
| Abstract: |
| Satisfiability (2SAT) is a determinable problem in polynomial time. This paper proves a sufficient and necessary condition for 2SAT problem, and presents a new polynomial algorithm for 2SAT problem. In addition, if one 2 CNF expression is satisfiable, the algorithm for solution can give every solution without backtracking. This paper tries to give some idea for other problem through the study of 2SAT problem. |
| Key words: Group of clauses with the same two variable compatible of two solutions identical transformation set of clauses minimax expression. |
