合法性和可满足性

7.4.5 等价、合法性和可满足性

在进入逻辑推理算法的细节之前，我们需要先给出一些与蕴涵相关的附加概念。跟蕴涵一样，这些概念对所有形式的逻辑都适用，但是他们最好在某个特定的逻辑下进行阐述，比如命题逻辑。

第一个概念是逻辑等价：两语句α 和β 是逻辑等价的，如果它们在同一模型集合中为真。写为α ⇔β。例如，我们很容易证明（用真值表），P∧Q和Q∧P是逻辑等价的；其它的等价关系如图7.11所示。它们在逻辑中扮演与普通数学中的算术恒等式几乎相同的角色。等价的一种替换定义如下所示：对于任意两个语句α 和β ，

α ≡ β 当且仅当 α|= β 且 β|= α

（回顾一下，|= 表示蕴涵。）

图7.11 标准的逻辑等价。符号α、β 和γ代表命题逻辑的任意语句

我们将需要的第二个概念是合法性。一个语句是合法的，如果在所有的模型中它都为真。例如，语句 P∨¬P 为合法的。合法语句也被称为重言式——它们必定为真，因此没有实质意义。因为语句True在所有的模型中为真，每个合法语句都逻辑等价于True。

合法语句有什么好处呢？从我们对蕴涵的定义，可以得到古希腊人早已了解的演绎定理：

对于任意语句α 和β，α|=β当且仅当语句(αβ)是合法的。

（习题7.4要求对此证明。）我们可以把图7.10的推理算法当作检验(KBα) 的合法性的过程。反过来，每个合法的蕴涵语句描述了一个合法的推理。

我们需要的最后一个概念是可满足性。一个句子是可满足的，如果它在某些模型中为真。例如，在先前给出的知识库中，(R1∧R2∧R3∧R4∧R5)是可满足的，因为存在 3 个使得它为真的模型，如图7.9所示。如果语句α 在模型m中为真，那么我们称m满足α ，或者称m是α 的一个模型。可以通过对可能的模型进行枚举直到发现某个满足该语句的模型来检验可满足性。命题逻辑语句的可满足性判定是第一个被证明为NP完全问题的问题。

计算机科学的很多问题实际上是可满足性问题。例如，第五章中的所有约束满足问题本质上是询问在某个赋值下约束是否为可满足的。通过适当变换，搜索问题也可以通过可满足性检验来求解。合法性和可满足性必然是相关联的：α 是合法的，当且仅当¬α 不可满足；逆否地看，α 是可满足的，当且仅当¬α 是不合法的。我们还可得到以下有用的结果：

α|= β当且仅当语句 (α∧¬β )是不可满足的。

通过验证(α∧¬β )的不可满足性，从α 证明β ，刚好符合归谬（字面意思为“归约到荒谬的结论”）的标准数学证明技术。它也被称为反证法或矛盾法证明。假定语句β 为假，并证明这将推导出和已知公理α 的一个矛盾。该矛盾正是说语句(α∧¬β )不可满足的含义。