CNF句子有多少个可能的作业？

Question

我很难理解以下内容：

当我们查看结合性正常形式的满意度问题时，一个不受约束的问题是一个相对较少的条款来限制变量。例如。这是一个随机生成的3-CNF句子，其中有五个符号和五个子句。 （每个子句都包含3个随机选择的不同符号，每个符号都以50％的概率否定。）

(¬D ∨ ¬B ∨ C) ∧ (B ∨ ¬A ∨ ¬C) ∧ (¬C ∨ ¬B ∨ E) ∧ (E ∨ ¬D ∨ B) ∧ (B ∨ E ∨ ¬C)

32个可能的作业中有16个是该句子的模型，因此，平均而言，只需2个随机猜测即可找到该模型。

我不明白最后一行 - 说有32个可能的作业。怎么样32？其中只有16个句子的模型？谢谢。

Answer 1

公式中有5个（布尔）变量。这些都可能是 真的 或者 错误的. 。这意味着有$ 2^5 = 32 $向这些变量分配值的方法。

在32种可能性中，只有16个使得公式为真 - 必须手动检查（或机器）。