| 二元可满足性问题有解的充要条件 |
| |
| 引用本文： | 吴向军,余丰人.二元可满足性问题有解的充要条件[J].软件学报,1996,7(1):51-58. |
| |
| 作者姓名： | 吴向军 余丰人 |
| |
| 作者单位： | 中山大学计算机系、电子系，广州,510275;中山大学计算机系、电子系，广州,510275 |
| |
| 摘 要： | 二元可满足性问题是一个多项式可解的问题．本文首先证明了该问题有解的充要条件，然后给出了判定该问题的一个新的多项式算法．如果判定某个表达式是可满足的话，那么求解算法不需要任何回溯就能准确地给出它的每个解．本文试图通过对二元可满足性的研究为研究其它问题提供一点启示．
|
| 关 键 词： | 二元组 解的相容性 布尔表达式的恒等变换 子句集 极大式 |
| 收稿时间： | 1994/5/27 0:00:00 |
| 修稿时间： | 1994/12/29 0:00:00 |
AN SUFFICIENT AND NECESSARY CONDITION FOR 2SAT PROBLEM |
| |
| Wu Xiangjun and Yu Fengren.AN SUFFICIENT AND NECESSARY CONDITION FOR 2SAT PROBLEM[J].Journal of Software,1996,7(1):51-58. |
| |
| Authors: | Wu Xiangjun and Yu Fengren |
| |
| Affiliation: | Department of Computer Science Department of Electrics Zhongshan University Guangzhou 510275 |
| |
| 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. |
| |
| Keywords: | Group of clauses with the same two variable compatible of two solutions identical transformation set of clauses minimax expression |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
