logic - 一个 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

两个值true和false有 2^5=32 可能分配给 5 个变量：

1:  00000
2:  00001
3:  00010
    ...
31: 11110
32: 11111

这些作业中有 16 个满足（我没有检查）给定的公式，因此是它的模型。