谈3SAT特殊的唯一解

姜咏江

在3-SAT求解中，很关键的是一个变量具有4个相同值的子句块，我们称之为4同值子句块。表1子句块的解只与变量x的值有关，与其余变量是无关的。只有当x=0时，这个子句块有解，其余情况都无解。

表1  变量4同值子句块

4同值子句块应该认为是唯一解还是多解？我认为叫变量唯一解比较合适，因为不取该值，子句块就无解，从而3SAT也无解。这种情况在逻辑电路设计时，起码可以节省元器件。

有7个子句的子句块有唯一解，其中必有4同值变量，因而有部分4同值子句块存在。求解时只要先设定4同值的变量，就立即得到了有唯一解的动态子句块，这样求唯一解十分迅速方便。

有5个或6个子句的子句块如果有4同值变量，那么先设定这个变量的值，即刻得到了多解的动态块。

用子句消去法在3SAT求解中，确定唯一解部分是首选。只要将唯一解部分全都解决了，那么剩下的多解部分就容易处理了。

2015-11-30