k-CNF-SAT无解条件

姜咏江

K阶合取范式如何去判断有无解有实际意义。判断无解的方法简单，只要某子句的变量完全表示都存在，那么合取范式必定无解。什么叫子句的完全表示？

举例来说，k=3，那么子句的完全表示有2³=8个：x_i’+x_j’+x_m’，x_i’+x_j’+x_m，x_i’+x_j+x_m’，x_i’+x_j+x_m，x_i+x_j’+x_m’，x_i+x_j’+x_m，x_i+x_j+x_m’，x_i+x_j+x_m。

容易看出这就是3位二进制的8个数。

一般化，只要k个变量的各自正反表示子句都存在，则k-CNF-SAT必定无解。其原理来自子句子句消去记数法分组求解（见http://blog.sciencenet.cn/blog-340399-928224.html  ）

给子句完全表示下一个定义。

定义：k个逻辑变量表示子句对应的k位二进制数都存在，则称这些子句为子句完全表示。

由于子句完全表示的每个子句与k位二进制数一一对应，因而通过子句消去法总会有子句剩余下来，故这k个变量给定任何值都不会使合取范式有解。

为了能够快速判断k-CNF-SAT是否有解，在子句输入的过程中，要将能够构成子句完全表示的成员放到一起，如果有一组完全表示存在，则不必费力气求解了。

转：http://blog.sciencenet.cn/blog-340399-928224.html  

2015-7-30