第5章基于谓词逻辑的机器推理

第3篇知识与推理概述第5章基于谓词逻辑的机器推理第6章基于产生式规则的机器推理

第7章几种结构化知识表示及其推理第8章不确定性知识的表示与推理概述知识及其表示

◆一些常用的知识表示形式：一阶谓词逻辑、产生式规则、框架、语义网络、类和对象、模糊集合、贝叶斯网络、脚本、过程等。机器推理

◆演绎推理、归纳推理和类比推理

◆不确定性推理和不确切性推理◆约束推理、定性推理、范例推理、非单调推理第5章基于谓词逻辑的机器推理主要内容1、一阶谓词逻辑2、归结演绎推理3、应用归结原理求取问题答案4、归结策略5、Horn子句归结与逻辑程序

基于谓词逻辑的机器推理也称自动推理。它是人工智能早期的主要研究内容之一。一阶谓词逻辑是一种表达力很强的形式语言，而且这种语言很适合当前的数字计算机。因而就成为知识表示的首选。基于这种语言，不仅可以实现类似于人推理的自然演绎法自动推理，而且也可实现不同于人的归结（或称消解）法自动推理。本节主要介绍基于谓词逻辑归结演绎推理。5.1一阶谓词逻辑5.1.1谓词、函数、量词

命题：凡可确定真假的陈述句称为命题。可以取值“真”（T）或“假”（F）在一定的条件下，只能取其中一个值例：（1）北京是中国的首都√（2）3+2>10×（3）禁止吸烟（祈使句）

A(a1,a2,…,an)在谓词逻辑中就表示一个原子命题。如：素数（2），表示命题“2是个素数”。命题的表达例：凡偶数都能被2整除，6是偶数。所以，6能被2整除将它们命题符号化：p：凡偶数都能被2整除

q：6是偶数

r：6能被2整除则推理的形式结构符号化为：(p

q)

r由于上式不是重言式（永真式），所以不能由它判断推理的正确性。为了克服命题逻辑的局限性，就应该将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是谓词逻辑。(1)８是自然数。(2)21世纪末，人类将住在月球。(3)x+y=y+x(4)只有x能被2整除，x才能被4整除。个体词x,y的取值范围：复数域a的取值范围：整数域表示具体或特定的客体的个体词称作个体常项；常用a,b,c,…表示。表示抽象或泛指的客体的个体词称作个体变项；常用x,y,z,…表示。个体变项的取值范围为个体域，个体域可以是有穷集合，也可以是无穷集合。全总个体域：由宇宙间一切事物组成的域为全总个体域。

谓词谓词：是用来刻画个体词的性质或个体词之间的关系的词（带参量的命题叫谓词）n元谓词，P（x1,x2,x3,…,xn）P是谓词符号，代表一个确定的特征（一个参量）或关系（多个参量）x1,x2,x3,…,xn

称为参量或项（个体常元或个体变元）论述域（个体域）：个体变元的取值范围例：北京是一个城市——CITY（北京）x是人——HUMAN（x）A是B的兄弟——兄弟（A，B）x大于y——G（x，y）不带个体变元的谓词公式叫命题，命题是谓词公式的特例一般的用F(a)表示个体常项a具有性质F（F是谓词常项或谓词变项），用F(x)表示个体变项x具有性质F。而用F(a,b)表示个体常项a,b具有关系F，用F(x,y)表示个体变项x,y具有关系F。函数为了表达个体之间的关系，我们引入通常数学中函数的概念和记法。例如我们用father(x)表示x的父亲，用sum(x,y)表示x和y之和，一般地，我们用如下形式：f(x1,x2,…,xn)表示个体变元x1，x2，…，xn所对应的个体y，并称之为n元个体函数，简称函数（或函词、函词命名式）。有了函数的概念和记法，谓词的表达能力就更强了。例如，Doctor(father(Li))表示“小李的父亲是医生）。我们约定：（1）用大写应为字母作为谓词符号；（2）用小写字母f，g，h等表示函数符号；（3）用小写字母x，y，z等作为个体变元符号；（4）用小写字母a，b，c等作为个体常元符号。逻辑连接词：研究单个谓词是不够的，还必须研究多个谓词之间的关系，这需要引入逻辑连接词¬：否定词¬A读为“非A”，当A为真时，¬A为假，当A为假时，¬A为真∧：合取词A∧B读为“A并且B”，当且仅当A和B都为真时，A∧B为真，否则A∧B为假∨：析取词A∨B读为“A或者B”，当且仅当A和B都为假时，A∨B为假，否则A∨B为真→：蕴涵词A→B读为“若A则B”，当且仅当A为真，且B为假时，A→B为假，否则A→B为真在A→B中，A称为前件，B称为后件：等值词AB读为“A等值于B”，当且仅当A和B同为真或同为假时，AB为真，否则AB为假量词有些陈述句包含表示数量的词，如“所有”、“任一”、“存在”、“至少有一个”等，为了表示这样的陈述句，需引入新的符号，称为量词。全称量词（x）表示“对于所有的x…”例：凡是人都有名字——（x）（M（x）→N（x））（x）A（x）A（a1）∧A（a2）∧…∧A（an），若论域为有限集合，且a1、a2、…、an是论域中的所有个体。存在量词（x）表示“对于某个x…”例：存在不是偶数的整数——（x）（G（x）∧¬E（x））（x）A（x）A（a1）∨A（a2）∨…∨A（an）不同的个体变元，可能有不同的个体域。为了方便和统一起见，我们用谓词表示命题时，一般总取全总个体域，然后再采取使用限定谓词的办法来指出每个个体变元的个体域。具体来讲，有下面两条：

（1）对全称量词，把限定谓词作为蕴含式之前件加入，即x（p（x）→…）。（2）对于存在量词，把限定谓词作为一个合取项加入，即x（p（x）∧…）。例：不存在最大的整数分析：命题中“不存在最大的”显然是对所有的整数而言，所以可理解为“对所有的x，如果x是整数，则一定还有比x大的整数”；再具体点，即“对所有的x如果x是整数，则一定存在y，y也是整数，并且y比x大”。则可以翻译成如下形式：﹁x（G（x）∧y（G（y）→D（x，y））或x（G（x）→y（G（y）∧D（y，x））例：对于所有的自然数，均有x+y>x

xy（N(x)∧N(y）→S(x，y，x））例：某些人对某些食物过敏xy（M（x）∧F（y）G（x，y）5.1.2谓词公式用谓词、量词及真值联结词可以表达相当复杂的命题。抽象的来看，我们把命题的这种符号表达式称为谓词公式。项：（定义1）（1）个体常元和个体变元都是项（2）f是n元函数，若t1,t2,…,tn

是项，则f(t1,t2,…,tn)是项，（3）只有有限次使用（1）、（2）得到的符号串才是项原子公式：（定义2）设P为n元谓词符号，t1,t2,…,tn是项，则P（t1,t2,…,tn）称为原子谓词公式，简称原子公式谓词公式：（定义3）（1）原子公式是谓词公式（2）若A、B是谓词公式，则A∧B、A∨B、¬A、A→B、AB、xA、xA也是谓词公式（3）只有有限次应用（1）、（2）生成的公式才是谓词公式谓词公式又称为谓词逻辑中的合式公式，记为Wff(well-formedformula)几个概念：辖域：紧接于量词之后被量词作用的（说明的）谓词公式称为该量词的辖域指导变元、约束变元和自由变元改名规则，保证一个变元或者是约束变元，或者是自由变元例：x（H（x）→G（x,y））∧xA（x）∧B（x）量词的辖域定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。例：XP(X)→Q(X)

X的辖域是P(X)X(P(X,Y)→Q(X，Y))P(Y,Z)

X的辖域是P(X，Y)→Q(X，Y)定义：量词后的变元如x，y中的x，y成为量词的指导变元（或作用变元）。在量词X，X辖域内变元X的一切出现叫约束出现，称这样的X为约束变元。

变元的非约束出现称为自由出现,称这样的变元为自由变元。例：指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域（1）X(P(X)R(X))→XP(X)Q(X)

解：表达式中的X(P(X)R(X))中X的辖域是P(X)R(X),其中的X是约束出现

Q(X)中的X是自由变元

例：指出下列谓词公式中的自由变元和约束变元。并指明量词的辖域(2)X(P(X，Y)→YR(X，Y))解：其中的P(X，Y)中的Y是自由变元，X是约束变元，R(X，Y)中的X，Y是约束变元。

注：在一个公式中，一个变元既可以约束出现，又可以自由出现。为避免混淆可用改名规则对变元改名。约束变元改名规则（1）对需改名的变元，应同时更改该变元在量词及其辖域中的所有出现。（2）新变元符号必须事量词辖域内原先没有的，最好是公式中也未出现过的。例如公式xP(x)Q(x)可改为yP(y)Q(x)，二者意义相同。量化在谓词前加上量词，称作谓词中相应的个体变元被量化，例如xA(x)中的x被量化。如果一个谓词中的所有个体变元都被量化，则这个谓词就变成了一个命题。这样，我们就有两种从谓词得到命题的方法：（1）给谓词中的个体变元代入个体常元。（2）把谓词中的个体变元全部量化。一阶谓词：仅个体变元被量化的谓词称为一阶谓词。二阶谓词：不仅个体变元被量化，而且函数符号和谓词符号也被量化，这样的谓词称为二阶谓词。

特别地，我们称xA(x)为全称命题，xA(x)为特称命题。当个体域为有限集时，如D={a1,a2,…,an}，对于任意的谓词A(x)，都有①

xA(x)A(a1)

A(a2)…

A(an)②xA(x)A(a1)

A(a2)…

A(an)这实际上是将谓词逻辑中命题公式转化为命题逻辑中的命题公式问题。合取范式：（定义4）A为合取范式，B1∧B2∧…∧Bn,其中Bi形如L1∨

L2∨…∨Lm,Lj为原子公式或其否定例：（P（x）∨Q（y））∧（¬P（x）∨Q（y）∨R（x，y））∧…任一谓词公式均可化为与之等价的合取范式，但一般不唯一析取范式：（定义5）A为析取范式，B1∨B2∨…∨Bn,其中Bi形如L1∧

L2∧…∧Lm,Lj为原子公式或其否定例：（P（x）∧Q（y））∨（¬P（x）∧Q（y）∧R（x，y））∨…任一谓词公式均可化为与之等价的析取范式，但一般不唯一定义6设P为谓词公式，D为其个体域，对于D中的任一解释I：（1）若P恒为真，则称P在D上永真（或有效）或是D上的永真式。（2）若P恒为假，则称P在D上永假（或不可满足）或是D上的永假式。（3）若至少有一个解释，可使P为真，则称P在D上可满足或是D上的可满足式。定义7设P为谓词公式，对于任何个体域：（1）若P都永真，则称P为永真式。（2）若P都永假，则称P为永假式。（3）若P都可满足，则称P为可满足式。5.1.3谓词逻辑中的形式演绎推理谓词公式之间的关系常用逻辑等价式表5.1注意与的区别，是等价符号，说明两个谓词公式之间的等价性，是逻辑连接词，是谓词公式的组成部分

常用逻辑蕴涵式表5.2注意与的区别，是推导符号，说明由左边的谓词公式可以推导出右边的谓词公式，是逻辑连接词，是谓词公式的组成部分

自然演绎推理：（1）将自然语言命题转化为谓词公式（2）利用上面的逻辑等价式和逻辑蕴涵式，可以进行推理，得出一些隐含在谓词公式中的结论利用一阶谓词逻辑的这种形式语言，就可以把关于自然语言的逻辑推理问题，转换为这种符号表达式的推演变换。例5.4设有前提：（1）凡是大学生都学过计算机；（2）小王是大学生。试问：小王学过计算机吗？

解：令S(x)：x是大学生；M(x)：x学过计算机；a：小王。则上面两个命题可用谓词公式表示为（1）x(S(X)→M(x))（2）S(a)问题：M(a)是否成立？形式推理如下：（1）x(S(X)→M(x))[前提]（2）S(a)→M(x)[(1)，US]（3）S(a)[前提]（4）M(a)[（2），（3），I3]例5.5证明﹁P(a，b)是xy（P(x，y)→W（x，y）和﹁W（a，b）的逻辑结果。

证：

（1）xy（P(x，y)→W（x，y）[前提]（2）y（P(a，y)→W（a，y）[(1),US]（3）（P(a，b)→W（a，b）[(2),US]（4）﹁W（a，b）[前提]（5）﹁P(a，b)[(3),(4),I4]例5.6证明x(P(x)→Q(x))∧x(R(x)→﹁Q(x))x(R(x)→﹁(P(x))。

证：

（1）x(P(x)→Q(x))[前提]（2）P(y)→Q(y)[(1),US]（3）﹁Q(y)→﹁P(y)[(2),E24]（4）x(R(x)→﹁Q(x))[前提]（5）R(y)→﹁Q(y)[(3),US]（6）R(y)→﹁P(y)[(3),(5),I6]（7）x(R(x)→﹁(P(x))上述推理过程完全是一个符号变换过程。类似于人们用自然语言推理的思维过程，因而成为自然演绎推理。这种推理实际上已几乎与谓词公式所表示的含义完全无关，而是一种形式推理。于是，可将这种推理方法引入机器推理。自然演绎推理实施困难，推理规则太多、应用规则需要很强的模式识别能力、中间结论呈指数增长引入新的推理技术——归结演绎推理技术归结——消解（Resolution），由Robinson于1965年提出，大大推动了自动定理证明的发展5.2归结演绎推理5.2.1子句集定义1原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句，由r个文字组成的子句叫r—文字子句，1—文字子句叫单元子句，不含任何文字的子句称为空子句，记为□或NIL。例：

P∨Q∨﹁R

P(x,y)∨﹁

Q(x)

定义2对一个谓词公式G，通过以下步骤所得的子句集合S，称为G的子句集。(1)消去蕴含词→和等值词←→。(2)缩小否定词﹁的作用范围，直到其仅作用于原子公式。(3)适当改名，使量词间不含同名指导变元和约束变元。(4)消去存在量词。(5)消去所有全称量词。(6)化公式为合取范式。(7)适当改名，使子句间无同名变元。(8)消去合取词∧，以子句为元素组成集合S。(1)消去蕴含词→和等值词←→使用逻辑等价式①A→B﹁A∨BE14②AB(﹁A∨B)∧(﹁B∨A)E15（2）缩小否定词﹁的作用范围，直到其仅作用于原子公式使用逻辑等价式：

①﹁(﹁A)AE1②﹁(A∧B)﹁A∨﹁BE12③﹁(A∨B)﹁A∧﹁BE13④﹁xp(x)x﹁P(X)E29⑤﹁xP(X)﹁xp(x)E30(4)消去存在量词消去存在量词时，同时还要进行变元替换。变元替换分两种情况：①若该存在量词在某些全称量词的辖域内，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元，这样的函数称为Skolem函数。②若该存在量词不在任何全称量词的辖域内，则用一个常量符号代替该存在量词辖域中的相应约束变元，这样的常量符号称为Skolem常量。(6)化公式为合取范式可使用逻辑等价式：①A∨(B∧C)(A∨B)∧(A∨C)②(A∧B)∨C(A∨C)∧(B∨C)例5.7求下面谓词公式的子句集

x{yP(x,y)﹁y[Q(x,y)R(x,y)]}解：由步(1)得x{﹁yP(x,y)∨﹁y[﹁Q(x,y)∨R(x,y)]}消去蕴含词由步(2)得x{y﹁P(x,y)∨y[Q(x,y)∧﹁R(x,y)]}缩小否定词﹁范围由步(3)得x{y﹁P(x,y)∨z[Q(x,z)∧﹁R(x,z)]}改名由步(4)得x{﹁P(x,f(x))∨[Q(x,g(x))∧﹁R(x,g(x))]}消存在量词，标准型由步(5)得﹁P(x,f(x))∨[Q(x,g(x))∧﹁R(x,g(x))]消全称量词，US由步(6)得[﹁P(x,f(x))∨Q(x,g(x))]∧[﹁P(x,f(x))∨﹁R(x,g(x))]E9由步(7)得[﹁P(x,f(x))∨Q(x,g(x))]∧[﹁P(y,f(y))∨﹁R(y,g(y))]改名由步(8)得{﹁P(x,f(x))∨Q(x,g(x)),﹁P(y,f(y))∨﹁R(y,g(y))}消去合取词或﹁P(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))Skolem标准型上述步骤步（4）所得式子就是Skolem标准型：把所有全称量词都依次移到整个式子的最左边（或者先把所有量词都依次移到整个最左边，再消去存在量词），再将右部的式子化为合取范式，这时所得的式子称为原公式的Skolem标准型。消去Skolem标准型左部的全称量词和合取词，即得公式的子句集。例5.8设G=xyzuvw(P(x,y,z)∧﹁Q(u,v,w)那么，用a替代x，用f(y,z)替代u，用g(y,z,v)代替w，则得G的Skolem标准型

yzv(P(a,y,z)∧﹁Q(f(y,z),v,g(y,z,v)那么可以得到G的子句集为{P(a,x,y),﹁Q(f(u,v),w,g(u,v,w)}由此例得出，一个公式的子句集也可以通过先求前束范式，再求Skolem标准型而得到。量词在最前面，后面不含量词的式子注意：引入Skolem函数，是由于存在量词在全称量词的辖域内，其约束变元的取值则完全依赖于全称量词的取值。Skolem函数反应了这种依赖关系。Skolem标准型与原公式一般并不等价，所以经过变换后的子句集S，与谓词公式G不等价。定理1谓词公式G不可满足当且仅当其子句集S不可满足。把证明G的不可满足转化为证明子句集S的不可满足。定义3子句集S是不可满足的，当且仅当其全部子句的合取式是不可满足的。5.2.2命题逻辑中的归结原理定义4

设L为一个文字，则称L与﹁L为互补文字。定义5设C1,C2是命题逻辑中的两个子句，C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1,C2中分别删除L1,L2，再将剩余部分析取起来，记构成的新子句为C12，则称C12为C1,C2的归结式(或消解式)，C1,C2称为其归结式的亲本子句，L1,L2称为消解基。例5.9设C1=﹁P∨Q∨R,C2=﹁Q∨S,则C1,C2的归结式为

﹁P∨R∨S定理2归结式是其亲本子句的逻辑结果。证明：设C1=L∨C1’,C2=﹁L∨C2’,C1’,C2’都是文字的析取式，则C1,C2的归结式为C1’∨C2’,因为C1=C1’∨L=﹁C1’LC2=﹁L∨C2’=LC2’所以C1∧C2=(﹁C1’L)∧(LC2’)﹁C1’C2’=C1’∨C2’I6假言三段论由定理2即得推理规则：

C1∧C2(C1-｛L1｝)∪(C2-｛L2｝)其中C1,C2是两个子句，L1,L2分别是C1,C2中的文字，且L1,L2互补。此规则就是命题逻辑中的归结原理。

例5.10用归结原理验证分离规则和拒取式

A∧(A→B)B(A→B)∧﹁B

﹁A

解

A∧(A→B)＝A∧(﹁A∨B)B(A→B)∧﹁B＝(﹁A∨B)∧(﹁B)

﹁A类似可以验证其他推理规则也都可以经消解原理推出。如果两个互否的单元子句进行归结，则归结式为空子句，即L∧﹁L=□并且

L∧﹁L=F所以，空子句恒为假，即□F有了空子句□，那么我们就可以用归结原理来推导空子句，反向证明。①求出要证的命题的否定式的子句集；②对子句集进行消解，寻找空子句，若存在，则子句集不可满足，从而原否定式不可满足，那么原公式是永真的。即，否定式子句集S假，则﹁S为真，要证命题为真。推论设C1,C2是子句集S的两个子句，C12是它们的归结式，则：（1）若用C12代替C1,C2，得到新子句集S1，则由S1的不可满足可推出原子句集S的不可满足。即S1不可满足S不可满足（2）若把C12加入到S中，得到新子句集S2，则S2与原S的不可满足等同。即S2不可满足S不可满足例5.11证明子句集{P∨﹁Q,﹁P,Q}是不可满足的。证(1)P∨﹁Q(2)﹁P(3)Q(4)﹁Q由(1),(2)(5)□由(3),(4)所以，子句集S不可满足。例5.12用归结原理证明R是P,(P∧Q)→R,(S∨U)→Q,U的逻辑结果。证由所给条件得到子句集S=｛P,﹁

P∨﹁

Q∨R,﹁

S∨Q,﹁

U∨Q,U,﹁

R｝然后对该子句集施行归结，归结过程用下面的归结演绎树表示（见图5―1）。由于最后推出了空子句，所以子句集S不可满足，即命题公式P∧(﹁

P∨﹁

Q∨R)∧(﹁

S∨Q)∧(﹁

U∨Q)∧U∧﹁

R不可满足，从而R是题设前提的逻辑结果。图5―1例5.12归结演绎树

5.2.3替换与合一一阶谓词逻辑中含有个体变元，因此应用消解原理不像命题逻辑中那样简单，寻找含互否文字的子句对的操作比较复杂。例：C1=P(x)∨Q(x)C2=﹁P(a)∨R(y)若用a替换C1中的x，则得到C1′=P(a)∨Q(a)C2′=﹁P(a)∨R(y)则消解式为

C3’=C1’∧C2’=Q(a)∨R(y)

结论：要在谓词逻辑中应用消解原理，则一般需要对个体变元作适当的替换。定义6

一个替换(Substitution)是形如｛t1/x1,t2/x2,…,tn/xn｝的有限集合，其中t1,t2,…,tn是项，称为替换的分子；x1,x2,…,xn是互不相同的个体变元，称为替换的分母；ti不同于xi，xi也不循环地出现在tj(i,j=1,2,…,n)中；ti/xi表示用ti替换xi。若t1,t2,…,tn都是不含变元的项（称为基项）时，该替换称为基替换；没有元素的替换称为空替换，记作ε，它表示不作替换。例如：

｛a/x,g(y)/y,f(g(b))/z｝就是一个替换，而

{g(y)/x,f(x)/y}则不是一个替换,因为x与y出现了循环替换。下面我们将项、原子公式、文字、子句等统称为表达式，没有变元的表达式称为基表达式，出现在表达式E中的表达式称为E的子表达式。定义7设θ=｛t1/x1,…,tn/xn｝是一个替换，E是一个表达式，把对E施行替换θ，即把E中出现的个体变元xj(1≤j≤n)都用tj替换，记为Eθ，所得的结果称为E在θ下的例(instance)。例如，若θ={a/x,f(b)/y,c/z},则Gθ=P(a,f(b),c)。定义8设θ=｛t1/x1,…,tn/xn｝，

λ={u1/y1,…，um/ym}是两个替换，则将集合

{t1λ/x1，…，tnλ/xn，u1/y1,…，um/ym}中凡符合下列条件的元素删除：（1）tiλ/xi当tiλ=xi

（2）ui/yi当yiϵ{x1，…，xi}这样得到的集合仍然是一个替换，该替换称为θ与λ的复合或乘积，记为θ·λ。例5.13设

θ={f(y)/x,z/y}

λ={a/x,b/y,y/z}于是，{t1λ/x1，t2λ/x2，u1/y1，u2/y2，u3/y3}={f(b)/x,y/y,a/x,b/y,y/z}可以证明，替换的乘积满足结合律，即(θ·λ)·u=θ·(λ·u)定义9设S=｛F1,F2,…,Fn｝是一个原子谓词公式集，若存在一个替换θ，可使F1θ=F2θ=…=Fnθ，则称θ为S的一个合一(Unifier)，称S为可合一的。定义10设σ是原子公式集S的一个合一，如果对S的任何一个合一θ，都存在一个替换λ，使得

θ=σ·λ则称σ为S的最一般合一(MostGeneralUnifier)，简称MGU。

例5.14设S=｛P(u,y,g(y)),P(x,f(u),z)｝，S有一个最一般合一σ=｛u/x,f(u)/y,g(f(u))/z｝对S的任一合一，例如：

θ=｛a/x,f(a)/y,g(f(a))/z,a/u｝存在一个替换λ=｛a/u｝使得

θ=σ·λ得出结论：如果能够找到一个公式集的合一，特别是最一般合一，则可使互否文字的形式结构完全一致起来，进而达到消解的目的。怎么求一个公式集的最一般合一？有一个算法可以求出，为了解该算法，先引入差异集。定义11设S是一个非空的具有相同谓名词的原子公式集，从S中各公式的左边第一项开始，同时向右比较，知道发现第一个不都相同的项为止，用这些项的差异部分组成一个集合，这个集合就是原公式集S的一个差异集。例5.15设S={P(x,y,z),P(x,f(a),h(b))},则不难看出，S有两个差异集D1={y,f(a)}D2={z,h(b)}合一算法步1置k=0，Sk=S，σk=ε。步2若Sk只含有一个谓词公式，则算法停止，σk就是要求的最一般合一。步3求Sk的差异集Dk。步4若Dk中存在元素xk和tk，其中xk是变元，tk是项且xk不在tk中出现，则置Sk+1=Sk{tk/xk,σk+1=σk·{tk/xk},k=k+1,然后转步2。步5算法停止，S的最一般合一不存在。例5.16求公式集S={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的最一般合一。解：k=0：S0=S,σ0=ε,S0不是单元集，求得D0={a，z}，其中z是变元，且不在a中出现，所以有

σ1=σ0·{a/z}=ε·{a/z}={a/z}S1=S0{a/z}={P(a,x,f(g(y))),P(a,h(a,u),f(u))}k=1:S1不是单元集,D1={x，h(a,u)},所以

σ2=σ1·{h(a,u)/x}={a/z}·{h(a,u)/x}={a/z,h(a,u)/x}S2=S1{h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}只含有一个谓词公式k=2:S2不是单元集,D2={g(y)，u}，所以

σ3=σ2·{g(y)/u}={{a/z,h(a,u)/x}·{g(y)/u}={a/z,h(a,g(y))/u}S3=S2{g(y)/u}={P(a,h(a,g(y)),f(g(y))),P(a,h(a,g(y)),f(g(y)))}={P(a,h(a,g(y)),f(g(y)))}k=3:S3是单元集，所以σ3就是S的最一般合一。例5.17判定S={P(x,x),P(y,f(y))是否可合一？解：k=0：S0=S,σ0=ε,S0不是单元集，求得D0={x,y}

σ1=σ0·{y/x}=ε·{y/x}={y/x}S1=S0{y/x}={P(y,y),P(y,f(y))k=1：S1不是单元集，求得D1={y,f(y)}，变元y在项f(y)中出现，所以算法停止，不存在最一般合一。两个都是变元，所以有两种替换方法，因此最一般合一可能不唯一。定理3（合一定理）如果S是一个非空有限可合一公式集，则合一算法总是在步2停止，且最后的σk即是S的最一般合一。5.2.4谓词逻辑中的归结原理定义12设C1,C2是两个无相同变元的子句，L1,L2分别是C1,C2中的两个文字，如果L1和L2有最一般合一σ，则子句(C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)称作C1和C2的二元归结式(二元消解式)，C1和C2称作归结式的亲本子句，L1和L2称作消解文字。例5.18设C1=P(x)∨Q(x),C2=﹁P(a)∨R(y)，求C1,C2的归结式。解取L1=P(x),L2=﹁P(a),则L1与﹁L2的最一般合一σ=｛a/x｝，于是,(C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)=(｛P(a),Q(a)｝-｛P(a)｝)∪(｛﹁P(a),R(y)｝-｛﹁P(a)｝)=｛Q(a),R(y)｝=Q(a)∨R(y)所以，Q(a)∨R(y)是C1和C2的二元归结式。

例5.19设C1=P(x,y)∨﹁Q(a),C2=Q(x)∨R(y),求C1,C2的归结式。

解由于C1,C2中都含有变元x,y，所以需先对其中一个进行改名,方可归结（归结过程是显然的，故从略）。

还需说明的是，如果在参加归结的子句内部含有可合一的文字，则在进行归结之前，也应对这些文字进行合一，从而使子句达到最简。例如，设有两个子句：C1=P(x)∨P(f(a))∨Q(x)C2=﹁P(y)∨R(b)定义13如果子句C中，两个或两个以上的文字有一个最一般合一σ，则Cσ称为C的因子，如果Cσ是单元子句，则Cσ称为C的单因子。例5.20设C=P(x)∨P(f(y))∨﹁Q(x),令σ=｛f(y)/x｝，于是Cσ=P(f(y))∨﹁Q(f(y))是C的因子。定义14子句C1,C2的消解式，是下列二元消解式之一：(1)C1和C2的二元消解式;(2)C1和C2的因子的二元消解式;(3)C1的因子和C2的二元消解式;(4)C1的因子和C2的因子的二元消解式。定理4谓词逻辑中的消解式是它的亲本子句的逻辑结果。由此定理我们即得谓词逻辑中的推理规则：

C1∧C2(C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)其中C1,C2是两个无相同变元的子句，L1,L2分别是C1,C2中的文字，σ为L1与L2的最一般合一。此规则称为谓词逻辑中的消解原理（或归结原理）。

例5.21求证G是A1和A2的逻辑结果。A1:x(P(x)→(Q(x)∧R(x)))A2:x(P(x)∧S(x))G:x(S(x)∧R(x))

证我们用反证法，即证明A1∧A2﹁G不可满足。首先求得子句集S：

(1)﹁P(x)∨Q(x)(2)﹁P(y)∨R(y)(3)P(a)(4)S(a)(5)﹁S(z)∨﹁R(z)(﹁G)然后应用消解原理，得(6)R(a)［(2),(3),σ1=｛a/y｝］(7)﹁R(a)［(4),(5),σ2=｛a/z｝］(8)□［(6),(7)］所以S是不可满足的，从而G是A1和A2的逻辑结果。(A1)(A2)S例5.22设已知：(1)能阅读者是识字的；(2)海豚不识字；(3)有些海豚是很聪明的。试证明：有些聪明者并不能阅读。证首先，定义如下谓词：R(x)：x能阅读。L(x)：x识字。I(x)：x是聪明的。D(x)：x是海豚。然后把上述各语句翻译为谓词公式：(1)x(R(x)→L(x))(2)x(D(x)→﹁L(x))已知条件(3)x(D(x)∧I(x))(4)x(I(x)∧﹁R(x))需证结论

求题设与结论否定的子句集，得(1)﹁R(x)∨L(x)(2)﹁D(y)∨﹁L(y)(3)D(a)(4)I(a)(5)﹁I(z)∨R(z)归结得(6)R(a)(5)，(4)，{a/z}(7)L(a)(6)，(1)，{a/x}(8)﹁D(a)(7),(2),{a/y}(9)□(8),(3)这个归结过程的演绎树如图5―2所示。

图5-2例5.22归结演绎树

定理5（归结原理的完备性定理）如果子句集S是不可满足的，那么必存在一个由S推出空子句□的消解序列。(该定理的证明要用到Herbrand定理，故从略。)5.3应用归结原理求取问题答案例5.23已知：（1）如果x和y是同班同学，则x的老师也是y的老师。（2）王先生是小李的老师。（3）小李和小张是同班同学。问：小张的老师是谁？解：定义谓词：T(x,y)：x是y的老师；C(x,y)：x，y是同班同学改写已知条件为谓词公式：F1：xyz(C(x,y)∧T(z,x)T(z,y)F2：T(Wang,Li)F2：C(Li,Zhang)为了得到问题的答案，我们先证明小张的老师是存在的，即证明公式：G：xT(x,Zhang)反证法：求F1∧

F2∧

F3∧﹁G的子句集：（1）﹁

C(x,y)∨﹁

T(z,x)∨

T(z,y)（2）T(Wang,Li)（3）C(Li,Zhang)（4）﹁T(u,Zhang)归结演绎，得（5）﹁

C(Li,y)∨T(Wang,Li)由(1),(2),{Wang/z,Li/x}（6）﹁

C(Li,Zhang)由(4),(5),{Wang/u,Zhang/y}（7）□由(3),(6)G为真，小张的老师存在，为了寻找该老师，给原来求证谓词的子句增加一个谓词ANS(u)。于是有：（4）’﹁T(u,Zhang)∨ANS(u)用（4）’替换（4），则可得到结果（7）’ANS(Wang)归结原理求取问题的方法:（1）寻找问题的合适求证目标谓词；（2）增配（析取形式）一个辅助谓词（辅助谓词中变元与目标谓词变元一致）；（3）归结，直至归结式刚好剩下辅助谓词，即得问题答案。5.4归结策略问题：前面用归结方法是人工的，这不是最终目的，人工智能要实现的是机器的推理，那么就需要自动推理。这样，怎样让机器去自动归结子句就成为一个需要考虑的重要方面。自动推理就是需要把算法用程序表示，让计算机运行。算法如下：步1将子句集S置入CLAUSES表。步2若空子句NIL在CLAUSES中，则归结成功，结束。步3若CLAUSES表中存在可归结的子句对，则将归结式并入CLAUSES表，转步2。步4归结失败，退出。该怎样选择参与消解的子句？穷举式归结方式

1、让所有子句两两进行归结，产生归结式集合S1，S1并入原CLAUSES中，记为S1’。

2、让新CLAUSES中子句，即集合S1’与S1中子句两两归结，产生归结式集合S2，S2并入S1’中，记为S2’。

3、以此类推，直至□。例5.25设有如下的子句集S，我们用上述的穷举算法归结如下：S：(1)P∨Q(2)﹁P∨Q(3)P∨﹁Q(4)﹁P∨﹁QS1：(5)Q[(1),(2)]

(6)P[(1),(3)](7)Q∨﹁Q[(1),(4)](8)P∨﹁P[(1),(4)]

(9)Q∨﹁Q[(2),(3)](10)P∨﹁P[(2),(3)]

(11)﹁P[(2),(4)](12)﹁Q[(3),(4)]S2：(13)P∨Q[(1),(7)](14)P∨Q[(1),(8)](15)P∨Q[(1),(9)](16)P∨Q[(1),(10)](17)Q[(1),(11)](18)P∨Q[(1),(10)](19)Q[(2),(6)]……(39)□归