math - 在没有子句共享相同变量的一组 3-CNF 子句中，有多少个令人满意的赋值？

Question

也许有点超出本网站的范围，但我想这里有足够多的人会知道这一点，所以我试了一下。

假设我有一组 3-CNF 子句

 S = {Clause1, Clause2} = {<x1 or x2 or not x3>, <x4 or x5 or x6>}

每个变量范围超过{0,1}

S 有多少令人满意的作业？一般来说，对于 S 有多少令人满意的分配是 S 的大小是 k？

这是一个关于什么是 3-disjunctive 从句的令人满意的分配的问题，就像它是关于计数的问题一样。例如，当我只有 时，有 2 ³ = 8 个可能的分配：

(111),(011),(101),(110),(100),(010),(001),(000)

但其中哪一项是令人满意的任务？

Answer 1

对于不共享任何变量的子句，计数非常简单。

对于满足第一个子句的每组变量，您可以选择满足第二个子句的任何一组变量。因此，您只需要满足每个子句的分配的结果。