3.2 推理的逻辑基础

在前面讨论了知识表示的逻辑基础，已经具备了谓词逻辑的一些简单概念。本节主要讨论推理所需要的一些逻辑基础。

3.2.1 谓词公式的解释

在命题逻辑中，命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。有了命题公式的解释，就可以根据这个解释求出该命题公式的真值。但谓词逻辑则不同，由于谓词公式中可能包含有个体常量、个体变元或函数，因此不能像命题公式那样直接通过真值指派给出解释，必须先考虑个体常量和函数在个体域上的取值，然后才能根据常量与函数的具体取值为谓词分别指派真值。下面给出谓词公式的解释的定义。

定义3.1 设D是谓词公式P的非空个体域，若对P中的个体常量、函数和谓词按如下规定赋值：

（1）为每个个体常量指派D中的一个元素；

（2）为每个n元函数指派一个从Dn到D的映射，其中，

Dn={（x1，x2，…，xn）|x1，x2，…，xn∈D}

（3）为每个n元谓词指派一个从Dn到{F，T}的映射。则称这些指派为P在D上的一个解释。

例3.1 设个体域D={1，2}，求公式A=（∀x）（∃y）P（x，y）在D上的解释，并指出在每一种解释下公式A的真值。

解：由于公式A中没有包含个体常量和函数，因此可以直接为谓词指派真值，设有

这就是公式A在D上的一个解释。从这个解释可以看出：

当x=1，y=1时，有P（x，y）的真值为T；

当x=2，y=1时，有P（x，y）的真值为T。

即对x在D上的任意取值，都存在y=1使P（x，y）的真值为T。因此，在此解释下公式A的真值为T。

需要注意，一个谓词公式在其个体域上的解释不是唯一的。例如，对公式A，若给出另一组真值指派。

这也是公式A在D上的一个解释。从这个解释可以看出：

当x=1，y=1时，有P（x，y）的真值为T；

当x=2，y=1时，有P（x，y）的真值为F。

同样

当x=1，y=2时，有P（x，y）的真值为T；

当x=2，y=2时，有P（x，y）的真值为F。

即对x在D上的任意取值，不存在一个y使得P（x，y）的真值为T。因此，在此解释下公式A的真值为F。

实际上，A在D上共有16种解释，这里就不再一一列举。

由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可能在某一个解释下真值为T，而在另一个解释下为F。

3.2.2 谓词公式的永真性与可满足性

为了以后推理的需要，下面先定义谓词公式的永真性、永假性、可满足性与不可满足性。

定义3.2 如果谓词公式P对非空个体域D上的任一解释都取得真值T，则称P在D上是永真的；如果P在任何非空个体域上均是永真的，则称P永真。

由此定义可以看出，要判定一个谓词公式为永真，必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数有限时，尽管工作量大，公式的永真性毕竟还可以判定，但当解释个数无限时，其永真性就很难判定了。

定义3.3 对于谓词公式P，如果至少存在D上的一个解释，使公式P在此解释下的真值为T，则称公式P在D上是可满足的。

谓词公式的可满足性也称为相容性。

定义3.4 如果谓词公式P对非空个体域D上的任一解释都取真值F，则称P在D上是永假的，如果P在任何非空个体域上均是永假的，则称P永假。

谓词公式的永假性又称为不可满足性或不相容性。

3.2.3 谓词公式的等价性与永真蕴涵性

谓词公式的等价性和永真蕴涵性可分别用相应的等价式和永真蕴涵式来表示，这些等价式和永真蕴涵式都是演绎推理的主要依据，因此也称它们为推理规则。

1.等价式

谓词公式的等价式可定义如下：

定义3.5 设P与Q是D上的两个谓词公式，若对D上的任意解释，P与Q都有相同的真值，则称P与Q在D上是等价的。如果D是任意非空个体域，则称P与Q是等价的，记做P⇔Q。

常用的等价式如下：

（1）双重否定率

￢￢P⇔P

（2）交换率

P∨Q⇔Q∨P，P∧Q⇔Q∧P

（3）结合率

（P∨Q）∨R⇔P∨（Q∨R）

（P∧Q）∧R⇔P∧（Q∧R）

（4）分配率

P∨（Q∧R）⇔（P∨Q）∧（P∨R）

P∧（Q∨R）⇔（P∧Q）∨（P∧R）

（5）摩根定律

￢（P∨Q）⇔￢P∧￢Q

￢（P∧Q）⇔￢P∨￢Q

（6）吸收率

P∨（P∧Q）⇔P，P∧（P∨Q）⇔P

（7）补余率

P∨￢P⇔T，P∧￢P⇔F

（8）连词化归率

P→Q⇔￢P∨Q

P↔Q⇔（P→Q）∧（Q→P）

P↔Q⇔（P∧Q）∨（￢Q∧￢P）

（9）量词转换率

￢（∃x）P（x）⇔（∀x）（￢P（x））

￢（∀x）P（x）⇔（∃x）（￢P（x））

（10）量词分配率

（∀x）（P（x）∧Q（x））⇔（∀x）P（x）∧（∀x）Q（x）

（∃x）（P（x）∨Q（x））⇔（∃x）P（x）∨（∃x）Q（x）

2.永真蕴涵式

谓词公式的永真蕴涵式可定义如下：

定义3.6 对谓词公式P和Q，如果P→Q永真，则称P永真蕴涵Q，且称Q为P的逻辑结论，P为Q的前提，记做P⇒Q。

常用的永真蕴涵式如下：

（1）化简式

P∧Q⇒P，P∧Q⇒Q

（2）附加式

P⇒P∨Q，Q⇒P∨Q

（3）析取三段论

￢P，P∨Q⇒Q

（4）假言推理

P，P→Q⇒Q

（5）拒取式

￢Q，P→Q⇒￢P

（6）假言三段论

P→Q，Q→R⇒P→R

（7）二难推理

P∨Q，P→R，Q→R⇒R

（8）全称固化

（∀x）P（x）⇒P（y）

式中，y是个体域中的任一个体，利用此永真蕴涵式可消去谓词公式中的全称量词。

（9）存在固化

（∃x）P（x）⇒P（y）

式中，y是个体域中某一个可以使P（y）为真的个体，利用此永真蕴涵式可消去谓词公式中的存在量词。

上面给出的等价式和永真蕴涵式是进行演绎推理的重要依据，因此这些公式也被称为推理规则。除了这些公式以外，在3.4节的归结演绎推理中，还需要将反证法推广到谓词公式集，即G为F的逻辑结论，当且仅当F∧￢G是不可满足的。

3.2.4 谓词公式的范式

范式是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们进行一般性的处理。在谓词逻辑中，根据量词在公式中出现的情况，可将谓词公式的范式分为两种。

1.前束范式

定义3.7 设F为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，而它们的辖域为整个公式，则称F为前束范式。一般地，前束范式可写成：

（Q1x1）…（Qnxn）M（x1，x2，…，xn）

式中，Qi（i=1，2，…，n）为前缀，它是一个由全称量词或存在量词组成的量词串；M（x1，x2，…，xn）为母式，它是一个不含任何量词的谓词公式。

例如，（∀x）（∀y）（∃z）（P（x）∧Q（y，z）∨R（x，z））是前束范式。

任一含有量词的谓词公式均可化为与其对应的前束范式，其化简方法将在后面子句集部分讨论。

2.Skolem范式

定义3.8 如果前束范式中所有的存在量词都在全称量词之前，则称这种形式的谓词公式为Skolem范式。

例如，（∃x）（∃z）（∀y）（P（x）∨Q（y，z）∧R（x，z））是Skolem范式。

任一含有量词的谓词公式均可化为与其对应的Skolem范式，其化简方法也将在后面子句集的化简中讨论。

3.2.5 置换与合一

在不同谓词公式中，往往会出现谓词名相同但其个体不同的情况，此时推埋过程是不能直接进行匹配的，需要先进行置换。例如，可根据全称固化推理和假言推理由谓词公式：

W1（x）和（∀x）（W1（x）→W2（x））

推出W2（A）。对谓词W1（A）可看做是由全称固化推理（即（∀x）（W1（x）⇒W1（A）））推出的，其中A是任一个体常量。要使用假言推理，首先需要找到项A对变元x的置换，使W1（A）与W1（x）一致。这种寻找项对变元的置换，使谓词一致的过程叫做合一的过程。下面讨论置换与合一的有关概念与方法。

1.置换

置换（Substitution）可以简单地理解为是在一个谓词公式中用置换项去替换变元。其形式定义如下。

定义3.9 置换是形如

{t1/x1，t2/x2，…，tn/xn}

的有限集合。其中，t1，t2，…，tn是项；x1，x2，…，xn是互不相同的变元；ti/xi表示用ti替换xi，并要求ti与xi不能相同，xi不能循环地出现在另一个ti中。

例如，

{a/x，c/y，f（b）/z}

是一个置换。但是

{g（y）/x，f（x）/y}

不是一个置换，原因是它在x与y之间出现了循环置换现象。置换的目的本来是要将某些变元用另外的变元、常量或函数取代，使其不在公式中出现。但在{g（y）/x，f（x）/y}中，它用g（y）置换x，用f（g（y））置换y，既没有消去x，也没有消去y。若改为

{g（a）/x，f（x）/y}

就可以了。它将把公式中的x用g（a）来置换，y用f（g（a））来置换，从而消去了x和y。

通常，置换是用希腊字母θ，σ，α，λ等来表示的。

定义3.10 设θ={t1/x1，t2/x2，…，tn/xn}是一个置换，F是一个谓词公式，把公式F中出现的所有xi换成ti（i=1，2，…，n），得到一个新的公式G，称G为F在置换θ下的例示，记做G=Fθ。

一个谓词公式的任何例示都是该公式的逻辑结论。

定义3.11 设

θ={t1/x1，t2/x2，…，tn/xn}

λ={u1/y1，u2/y2，…，um/ym}

是两个置换。则θ与λ的合成也是一个置换，记做θ·λ。它是从集合

{t1λ/x1，t2λ/x2，…，tnλ/xn，u1/y1，u2/y2，…，um/ym

中删去以下两种元素：

①当tiλ=xi时，删去tiλ/xi，（i=1，2，…，n）；

②当yj∈{x1，x2，…，xn}时，删去uj/yj，（j=1，2，…，m）。最后剩下的元素所构成的集合。

例3.2 设θ={f（y）/x，z/y}，λ={a/x，b/y，y/z}，求θ与λ的合成。

解：先求出集合

{f（b/y）/x，（y/z）/y，a/x，b/y，y/z}={f（b）/x，y/y，a/x，b/y，y/z}

式中，f（b）/x中的f（b）是置换λ作用于f（y）的结果；y/y中的y是置换λ作用于z的结果。在该集合中，y/y满足定义中的条件①，需要删除；a/x和b/y满足定义中的条件②，也需要删除。最后得

θ·λ={f（b）/x，y/z}

2.合一

合一（Unifier）可以简单地理解为是寻找项对变量的置换，使两个谓词公式一致。其形式定义如下。

定义3.12 设有公式集F={F1，F2，…，Fn}，若存在一个置换θ，可使F1θ=F2θ=…=Fnθ，则称θ是F的一个合一，称F1，F2，…，Fn是可合一的。

例如，设有公式集F={P（x，y，f（y）），P（a，g（x），z）}，则

λ={a/x，g（a）/y，f（g（a））/z}

是它的一个合一。

一般来说，一个公式集的合一不是唯一的。

定义3.13 设σ是公式集F的一个合一，如果对F的任一个合一θ都存在一个置换λ，使得θ=σ·λ，则称σ是一个最一般合一（Most General Unifier，MGU）。

一个公式集的最一般合一是唯一的。若用最一般合一去置换那些可合一的谓词公式，可使它们变成完全一致的谓词公式。