100个逻辑变量能够写出多少个子句？

姜咏江

在研究3SAT问题中，会听到研究成千上万个子句求解问题，有人曾告诉我上百万子句竞赛求解。100个逻辑变量能够构成多少个3SAT子句？应该是C₂₀₀³=200×199×198/6=1313400个。如果真有这么多子句写在3SAT中，我会闭着眼睛说“没有满足解。”问题就这么简单。不包括正反变量都在一个子句中，100个逻辑变量能够形成8×C₁₀₀³=161700个子句。这么多子句存在与3SAT中自然也是无解。

子句分段消去法可以让你迅速地判断出3SAT一些简单的无解情况：

1.      相同变量的子句数为8个；

2.      任何一个局部的变量组成的子句关联段无解。

计算3SAT的满足解不能够用子句的多少去说明其解的多少，事实正好相反，3SAT的子句越多，反而满足解可能越少。当然这是不专业的说法，到底3SAT有多少解，我们可以用子句分段消去法去求出来。

2015-10-16