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

1、1李伟生李伟生信科大厦信科大厦19楼楼Tel：2内容提要内容提要: : 2.1 .1 命题逻辑命题逻辑 2.2 2.2 一阶谓词逻辑一阶谓词逻辑 2.3 2.3 归结演绎推理归结演绎推理 2.4 2.4 应用归结原理求取问题答案应用归结原理求取问题答案3 逻辑学是研究人如何正确地思维以达到认识客观真理的科学，它包括形式逻辑和辨证逻辑两部分。形式逻辑又名静态逻辑或初等逻辑，它着重研究思维形式的结构及其规律。辩证逻辑又名动态逻辑或高等逻辑，它是全面研究思维的形式和内容，研究思维的辨证发展规律的科学。形式逻辑反映的是认识过程处在量变阶段的规律，它完成的是已知规律的逻辑推理。辩证逻辑反映的是认识过程处

2、在质变阶段的规律，它研究的是人的认识的发生、发展和完善的全过程。4 数理逻辑是用数学方法研究逻辑学的科学，目前仅局限在形式逻辑范围内。数理逻辑以命题演算和一阶谓词演算为基础。在数理逻辑中，仅关心推理在形式上的有效性，而不涉及推理的内容本身。命题逻辑与谓词逻辑是最先应用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的自动证明发挥了重要作用，在人工智能的发展史中占有重要地位。本节主要介绍命题逻辑，在下一节介绍谓词逻辑。52.1.1 命题2.1.2 命题定律2.1.3 范式2.1.4 命题逻辑的局限性6定义定义2.1 命题（命题（Proposition）：命题是具有真假意义的语句。命题代表人

3、们进行思维时的一种判断，或者是肯定，或者是否定，只有这两种情况。如果命题的意义为真，称它的真值为真，记作T；如果命题的意义为假，称它的真值为假，记作F。一个命题不能同时既为真又为假，但可以在一定条件下为真，在另一种条件下为假。没有真假意义的语句(如感叹句、疑问句等)不是命题。例如，“北京是中华人民共和国的首都”、“33”这个不等式可用谓词表示为Greater（5，3），这里Greater刻画了5与3之间的“大于”关系。 36看几个命题：1. 3是质数2. 王二生于武汉市3. 7=23 x是质数x生于武汉市x=y zF(x)G(x,y)H(x,y,z)称“3”、“王二”、“武汉市”、“7”、“2

4、”、“3”为个体;代表个体的变元称为个体变元；刻画个体性质或个体之间关系的词叫谓词。“是质数”、“生于”、“=. .”都是谓词。37谓词的一般形式是： P (x1, x2, ., xn)其中，P是谓词名，x1, x2, ., xn是个体。谓词名通常用大写的英文字母表示，个体通常用小写的英文字母表示,个体可以是常量，也可以是变元，还可以是一个函数。 例如，对于“x5，可表示为Less (x , 5 )，其中x是变元。又如，对于“小王的父亲是教师”，可表示为Teacher (father(Wang)，其中father (Wang)是一个函数。 在用谓词表示客观事物时，谓词的语义是由使用者根据需要人

5、为地定义的。例如对于谓词S(x)，既可以定义它表示“x是一个学生”，也可以定义它表示“x是一只船”或者别的什么。 当谓词中的变元都用特定的个体取代时，谓词就具有一个确定的真值：T或F。38 谓词中包含的个体数目称为谓词的元数。例如P (x)是一元谓词，P (x, y)是二元谓词，P (x1, x2, ., xn)是n元谓词。 在谓词P (x1, x2, ., xn)中，若xi (i = 1, ., n)都是个体常量、变元或函数，称它为一阶谓词。如果某个xi本身又是一个一阶谓词，则称它为二阶谓词。余者类推。 个体变元的取值范围称为个体域。个体域可以是有限的，也可以是无限的。例，若用I (x)表示

6、“x是整数”，则个体域是所有整数，是无限的。 谓词与函数表面上很相似，容易混淆，其实这是两个完全不同的概念。谓词的真值是“真”或“假”，而函数的值是个体域中的某个个体，函数无真值可言，它只是在个体域中从一个个体到另一个个体的映射。 个体常量、个体变元、函数统称为“项”。 39 怎样来刻画谓词与个体之间的这两种不同的关系呢？为此我们引入了一个新的概念量词。量词有两种：全称量词和存在量词。 全称量词( x) ，读作“对于所有的x”，它表示“对个体域中的所有(或任一个)个体x；另一个是存在量词( x) ，读作“存在x”，它表示“在个体域中存在个体x”。 符号“( x)P(x)”表示命题：“对于个体域

7、中所有的个体x，谓词P(x)均为T”。谓词P(x)称为的辖域或作用范围。 符号“( x)Q(x)”表示命题：“对于个体域中存在某些个体使谓词Q(x)为T”。谓词Q(x)称为的辖域或存在范围。再看前面的三段论法：P:“所有的人都会犯错误”Q:“张三是人”R:“张三会犯错误”x(M(x) R(x)M(“张三”)R(“张三”)40 将谓词转化成命题的方法有二： 将谓词中的个体变元全部换成确定的个体； 使谓词量化。注意： 量词本身并不是一个独立的逻辑概念，可以用，联结词代替。设某个体域是有限集合S： S=a1, a2, ., an,对任意谓词A(x)有 由量词所确定的命题的真值与个体域有关。)()()

8、()()(21naAaAaAxAx)()()()()(21naAaAaAxAx41可按下述规则得到谓词逻辑的合式公式：(1) 单个谓词是合式公式，称为原子谓词公式；(2) 若A是合式公式，则A也是合式公式；(3) 若A、B都是合式公式，则AB，AB，AB，AB也都是合式公式；(4) 若A是合式公式，x是任一个体变元，则( x)A和( x)A也都是合式公式。 在合式公式中，连接词的优先级别是, , , , 42 位于量词后面的单个谓词或者用括弧括起来的合式公式称为量词的辖域，那么，辖域内与量词中同名的变元称为约束变元，不受约束的变元称为自由变元。 例如: 其中，（P(x,y) Q(x,y)）是(

9、 x)的辖域，辖域内的变元x是受( x)约束的变元，而R(x,y)中的x是自由变元，公式中的所有y都是自由变元。 在谓词公式中，变元的名字是无关紧要的，可以把一个名字换成另一个名字。但必须注意，当对量词辖域内的约束变元更名时，必须把同名的约束变元都统一改成相同的名字，且不能与辖域内的自由变元同名；当对辖域内的自由变元改名时，不能改成与约束变元相同的名字。 ），（），（），（yxRyxQyxPx )(43 在命题逻辑中，对命题公式中各个命题变元的一次真值指派称为命题公式的一个解释。一旦解释确定后，根据各连接词的定义就可求出命题公式的真值(T或F)。在谓词逻辑中，由于公式中可能有个体常量、个体变元

10、以及函数，因此不能像命题公式那样直接通过真值指派给出解释，必须首先考虑个体常量和函数在个体域中的取值，然后才能针对常量与函数的具体取值为谓词分别指派真值。由于存在多种组合情况，所以一个谓词公式的解释可能有很多个。对于每一个解释，谓词公式都可求出一个真值(T或F)。 下面首先给出解释的定义，然后用例子说明如何构造一个解释以及如何根据解释求出谓词公式的真值。 44定义2.7：设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按如下规定赋值：(1) 为每个个体常量指派D中的一个元素；(2) 为每个n元函数指派一个从Dn到D的映射，其中 Dn=(x1, x2,., xn) | x1, x2,.,

11、 xnD (3) 为每个n元谓词指派一个从Dn到F，T的映射。则称这些指派为公式P在D上的一个解释。 45例1：设个体域D=1,2，求公式 在D上的解释，并指出在每一种解释下公式A的真值。解：在公式A中没有包括个体常量和函数，所以可直接为谓词指派真值，设为 P(1,1)=T, P(1,2)=F , P(2,1)=T , P(2,2)=F 这就是公式A在D上的一个解释。在此解释下，因为x1时有y1使P(x,y)的真值为T；x=2时也有y1使F(x,y)的真值为T，即对于D中的所有x都有y1使P(x,y)的真值为T，所以在此解释下公式A的真值为T。还可以对公式A中的谓词指派另外一组真值，设为 P(

12、1,1)=F, P(1,2)=F , P(2,1)=F , P(2,2)=F 这是对公式A的另一个解释。在此解释下，对D中的所有x (x1与x2)不存在一个y，使得公式A的真值为T，所以在此解释下公式A的真值为F。公式A在D上共有16种解释，这里不再一一列出，可自行列出其中的几个，并求出公式A的真值。 ),()(yxPyxA46例2：设个体域D=1,2，求公式 在D上的某一个解释，并指出公式B在此解释下的真值。解：设对个体常量b，函数f (x)指派的值分别为： b=1，f (1)=2，f (2)=1 对谓词指派的真值为： P(1)=F，P(2)=T ，Q(1,1)=T，Q(2,1)=F 这里，

13、由于已指派b=1，所以Q(1,2)与Q(2,2)不可能出现，故没有给它们指派真值。上述指派就是对公式B的一个解释。在此解释下，由于当x1时，有 P(1)=F ，Q(f (1),1)= Q(2,1)=F 所以P(1) Q(f (1),1)的真值为T。2时 P(2)=T，Q(f (2),1)= Q(1,1)=T 所以P(2) Q(f (2),1)的真值也为T。即对个体域D中的所有x均有 (P(x) Q(f (x),b) 的真值为T。所以公式B在此解释下的真值为T。 ),()()(bxfQxPx47 仅个体变元被量化的谓词称为一阶谓词一阶谓词，如果不仅个体变元被量化，而且函数符号和谓词符号也被量化，

14、这样的谓词称为二阶谓词二阶谓词。 我们只讨论一阶谓词。 用谓词公式表示知识的步骤： 可以用合取符号和析取符号联结形成的谓词公式表示事实性知识，也可以用蕴含符号联结形成的谓词公式表示规则性知识。(1)定义谓词及个体，确定每个谓词及个体的确切含义；(2)根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值；(3)根据所要表达的知识的语义，用适当的联结符号将各个谓词联结起来，形成谓词公式。48例3：设有下列事实性知识： 张辉是一名计算机系的学生，但他不喜欢编程序。 李晓比他姐姐长得高。用谓词公式表示这些知识。解：首先定义谓词如下： Compuer(x): x是计算机系的学生。 Like(x, y

15、): x喜欢y。 Higher(x, y): x比y长得高。 将个体带入谓词中，得到 Computer(zhang), Like(zhang, programming), Higher(li, sister(li) 根据语义，用逻辑联结词进行联结，就得到了谓词公式： Computer(zhang) Like(zhang, programming) Higher(li, sister(li)49练习1：用谓词公式表示下列规则性知识： 人人爱劳动。 所有整数要么是偶数要么是奇数。 自然数都是大于零的整数。 偶数除以2是整数。(提示：用函数S(x)表示x除以2) 解：首先定义谓词如下： Man(x)

16、: x是人。 Love(x, y): x爱y。 N(x): x是自然数。 I(x): x是整数。 E(x): x是偶数。 O(x): x是奇数。 GZ(x): x大于零。可以得到谓词公式表示： (x) (Man(x) Love(x, labour) (x) (I(x) E(x)O(x) (x) (N(x) GZ(x)I(x) (x) (E(x) I(S(x) 50 2.3.1 子句集2.3.2 命题逻辑中的归结原理 2.3.3 替换与合一2.3.4 谓词逻辑中的归结原理511.前束范式2.Skolem范式3.子句和子句集52一个谓词公式，如果量词非否定地放在全式的开头，而量词的辖域都延伸到整个

17、谓词公式，则称这样的公式为前束范式。一般地，谓词逻辑中的公式G如果有如下形状：Q1x1,Qn xn M(x1,xn)则称G为前束范式。其中Qi是xi或xi, i =1,n，M(x1,xn)是不含量词的公式。 Q1x1,Qn xn称为首标，M称为母式。如：xyz(P(x,y ) Q(x,z)xyzP(x,y,z)都是前束范式。53 利用改名规则、量词否定公式和量词辖域扩张公式等，可把任一谓词公式化成前束范式。例如：x(P(x) xQ(x)=x(P(x) xQ(x)=x(P(x) xQ(x)= x(P(x) xQ(x)= x(P(x) yQ(y) xy(P(x) Q(y)例2.2将公式xy(z (

18、P(x,z) P(y,z) uQ(x,y,u)化为前束范式：解： xy(z (P(x,z) P(y,z) uQ(x,y,u)= xy(z (P(x,z) P(y,z) uQ(x,y,u)= xy(z (P(x,z) P(y,z) uQ(x,y,u)=xyzu (P(x,z) P(y,z) Q(x,y,u)54步骤1：使用以下基本等价公式，将G中的和删去：F H=(F H) (H F)F H=F H步骤2：使用(F)=F，摩根定律及以下等价公式，将谓词公式中的所有 否定号放在原子之前：xG(x)=xG(x)xG(x)=xG(x)步骤3：如果需要，则将约束变量改名。步骤4：利用等价公式将所有量词提

19、到公式的最前面。将任意谓词公式化为前束范式的四个步骤：55Skolem范式是谓词逻辑中公式的又一种标准形式。设公式G的形式如下：Q1x1,Qn xn M(x1,xn)其中Qi是xi或xi, i =1,n，M(x1,xn)是不含量词的公式。将上式中的M(x1,xn)化为等值的合取范式，然后将所有的存在量词消去，便可得到公式G的Skolem范式。消去G中的存在量词的方法如下：设Qrxr (1 r n )是第一个出现在Q1x1, Qrxr ,Qn xn M(x1,xn)中的存在量词，即Q1x1, Qr-1xr-1 均为全称量词。若r=1，即Qrxr 左边没有全称量词，则取异于M(x1,xn)中所有常

20、量符号的常量符号C,并用C代表M(x1,xn)中的xr，然后在首标中删除Qrxr。若1r n，即Qrxr左边有全称量词Qs1 xs1 ,Qsm xsm而m1，1 s1s2.s mr，则取异于出现在M中的所有函数符号的m元函数符号f(xs1,xsm)，用f(xs1,xsm)代表出现在M中的所有xr,然后在首标中删除存在量词Qrxr。56例将公式G=xyz(P(x,y)Q(x,z) R(x,y,z)化成Skolem范式。解：先将M(x,y,z)化成合取范式：M(x,y,z)= (P(x,y) Q(x,z) R(x,y,z)= (P(x,y) R(x,y,z) (Q(x,z) R(x,y,z) G=

21、 xyz(P(x,y) R(x,y,z) (Q(x,z) R(x,y,z) 消去y得到：xz(P(x,f(x) R(x,f(x),z) (Q(x,z) R(x,f(x),z) 消去z得到：x (P(x,f(x) R(x,f(x),g(x) (Q(x,g(x) R(x,f(x),g(x)此式就是公式G的Skolem范式。 57例将公式G=xyzuvwP(x,y,z,u,v,w)化成Skolem标准型。解：消去x,因为其左边没有全称量词，于是引入常量a代替P(x,y,z,u,v,w) 中的所有x,得： yzuvwP(a,y,z,u,v,w)消去u，因为其左边有全称量词yz，于是引入一个二元函数f(

22、y,z)代替P(a,y,z,u,v,w)中的所有u，得： yzvwP(a,y,z,f(y,z),v,w)消去w ，因为其左边有全称量词 yzv，于是引入一个三元函数g(y,z,v)，代替P(a,y,z,f(y,z),v,w)中的所有w。最后得到的Skolem 标准型为：yzvP(a,y,z,f(y,z),v,g(y,z,v)注意：1.公式的Skolem 标准型与原公式并不等值；2.公式的Skolem 标准型与原公式在不可满足的意义上相等。58总结：得到谓词公式Skolem标准型的步骤1)消去蕴含词和等值词。2)缩小否定词的范围，直到其只作用于原子公式。3)利用等价公式将所有量词提到公式的最前面

23、，并适当改名，使量词间不含同名指导变元和约束变元。(得到前束范式)4)消去存在量词 4.1 若存在量词在某些全称量词辖域内，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元(Skloem函数)。 4.2若存在量词不在任何全称量词辖域内，则用一个常量符号代替该存在量词辖域中的相应约束变元(Skolem常量)。5)消去所有全称量词。6)化公式为合取范式。7)适当改名，使子句间无同名变元。不含第5)步得到的结果即为Skolem范式，由Skolem范式得到子句集：8)消去合取词，以子句为元素组成一个集合S。59练习3：求下列谓词公式的前束范式、Skolem标准型及子句集xyP(x,

24、y)yQ(x,y) R(x,y)60若干文字的一个析取式成为子句。如：P(x,y) Q(x,y,z) R(u)没有文字的子句成为空子句。只有一个文字的子句成为单元子句。 原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句。由r个文字组成的子句叫r-文字子句，1-文字子句叫单元子句，不含任何文字的子句称为空子句，计为或NIL。61将公式G化为Skolem 标准型，其母式M已为合取范式，M中的每一个合取项都是一个子句，M中这些子句的集合用S表示，称为公式G的子句集。从公式G得到子句集S的方法是：先从公式G得到Skolem 标准型，然后去掉全称量词，最后用符号“，”代替符号“”。外层括

25、号用。如公式：G=xyz(P(x,y) R(x,y,z) (Q(x,z) R(x,y,z)G的Skolem标准型为：x (P(x,f(x) R(x,f(x),g(x) (Q(x,g(x) R(x,f(x),g(x)G的子句集S为： (P(x,f(x) R(x,f(x),g(x)，(Q(x,g(x) R(x,f(x),g(x)子句集中S中的每一个子句中的变量都是由全称量词约束着。62 对任一公式G都可以建立其对应的S子句集。这样对公式的讨论就可以用对集合的讨论来代替。引进子句集S的目的就是要简化对A1 A2 A3B的证明，而证明A1 A2 A3B只需证明G= A1 A2 A3 B的子句集不可满足

26、即可。定理设S是公式G的子句集。于是，G是不可满足的，当且仅当S是不可满足的。子句集概念的推广：设G= G1 . Gn ，Si是Gi化为Skolem范式后其公式给出的子句集，i=1,2,n。令S=S1. S n。于是G是不可满足的，当且仅当S是不可满足的。也称S是G的子句集。63子句集的海伯伦域定义：H0是出现于子句集S的常量符号集合。如果S中无常量符号出现，则H0由一个常量符号a组成。对于 i =1,2,n 令Hi=Hi-1 所有型如fn(t1,t2,tn)的项的集合 其中fn(t1,t2,tn)是出现在S中的n元函数符号，tj Hi-1 j=1,2,n。于是称Hi为S的i级常量集，H 称为

27、S的海伯伦（Herbrand）域,简称S的H域。例子句集S为：S=P(f(x),a,g(y),b)求子句集S的H域。解：根据定义H0=a,bH1=H0 f(a), f(b), g(a), g(b)=a,b, f(a), f(b), g(a),g(b)H2=H1 f(a), f(b), g(a),g(b),f(f(a), f(f(b), g(f(a),g(f(b), f(g(a), f(g(b), g(g(a),g(g(b)= a,b, f(a), f(b), g(a),g(b),f(f(a), f(f(b), g(f(a),g(f(b), f(g(a), f(g(b), g(g(a),g(g(

28、b).64见2.3.465练习2已知：张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员A说“赵与钱中至少有一个作案”；侦察员B说“钱与孙中至少有一人作案”；侦察员C说“孙与李中至少有一人作案”；侦察员D说“赵与孙中至少有一人与此案无关”；侦察员E说“钱与李中至少有一人与此案无关”。如果这五个侦察员的话都可信，请求出谁是盗窃犯。661.替换与最一般合一替换一个替换是型如t1/v1 ,t n/vn 的一个有限集其中vi是变量，而ti是不同于vi 的项（常量、变量、函数），且vi vj (i j ) ，i,j=1,2,n。称ti为替换分子， vi为替换分母。当t1,tn是基项（不含变元的项）

29、时，称此替换为基替换。不含任何元素的替换为空替换，以表示。例如a/x,b/y,f(x)/z就是一个替换。替换可作用与某个谓词公式上，也可作用于某个项上。令替换= t1/v1 ,t n/vn ，作用于E，而E是一谓词公式。就是将E中出现的vi均以ti代入(i=1,2,n), 作用的结果用E表示，并称E为E的一个例。若t是项， 作用于项t也是将t中出现的vi均以ti代入，作用的结果用t表示。67例令= a/x,f(b)/y,c/z E=P(x,y,z)t=g(x,y)于是E的例为 E =P(a,f(b),c) 而 t=g(a,f(b)当E是子句集S的一个子句，用作用于E，当中的v1,vn含有E的所

30、有变量， t1,tn又是H的元素时， E 便是S的子句E的基例。例子句集S=P(x,y),Q(x,a) R(y,b)此子句集的H域：H=a,bP(x,y)是S的一个子句，以= a/x,b/y作用于P(x,y)，得到P(a,b)。P(a,b)就是S子句P(x,y)的基例。68定义：设= t1/x1 ,t n/xn， =u1/y1 ,u m/ym是两个替换。将下面集合t1 /x1 ,t n /xn，u1/y1 ,u m/ym中符合下面条件的元素删除1. ui/yi ，当 yi x1,x n时；2. ti /xi ，当ti =xi 时。如此得到一个替换，称为与的乘积，记作例令=f(y)/x,z/y

31、=a/x,b/y,y/z解：先作替换f(y) /x,z/y,a/x,b/y,y/z = f(b)/x,y/y,a/x,b/y,y/z其中a/x,b/y符合条件1，应删除。y/y符合条件2，也应删除，所以得： = f(b)/x,y/z当子句 E=P(x,y,z)时E() =P(f(b),y,y)如果先用作用于E,则E=P(f(y),z,z)再用作用于E得(E) = P(f(b),y,y)与用= f(b)/x,y/z直接作用于E的结果一样。即：E() = (E) 求： 69引理设，是三个替换，于是： ()= ()设E是任一表达式E() ) =(E() ) =( (E) E( ) =(E)()=(

32、(E) 所以 E() ) = E( ) 由于E的任意性，故 ()= () 注意，在，中，交换律是不成立的。70 为了在两个文字中找出互补文字，常常需要去统一两个或多个表达式。即需要找一个替换，使得在此替换下，一些本来不同的表达式会一致起来。定义 替换称为表达式集合E1,E k的合一，当且仅当E1 = E2 =.= Ek 。表达式集合E1,E k称为可合一的，如果存在关于此集合的一个合一。定义 表达式集合E1,E k的合一称为是最一般合一（most general unifier）记作mgu，当且仅当对此集合的每一个合一，都存在替换，使得= 。例 表达式集合P(a,y),P(x,f(b)是可合一

33、的，其合一为：=a/x,f(b)/y例 表达式集合P(x),P(f(y)是可合一的,其最一般合一为：=f(y)/x因为对此表达式集合的任一合一=f(a)/x, a/y 都有替换=a/y，使= =f(a)/x, a/y71定义 设W是非空表达式集合，W的差异集合是如下一个集合：首先找出W的所有表达式中不相同的第一个符号，然后从W的每个表达式中抽出占有这个位置的子表达式。所有这些子表达式的集合就是W 的差异集合。 例求表达式集合W=P(x,f(x,z),z),P(x,a),P(x,g(h(k(x),z)的差异集合解： 从P(x,f(x,z),z)中抽出f(x,z) 从P(x,a)中抽出a 从P(x

34、,g(h(k(x),z)中抽出g(h(k(x)得到W的差异集合=f(x,z),a,g(h(k(x)。2.合一算法72若W是非空表达式集合，D是W的差异集合，则有下面的结论：1.若D中无变量符号，则W是不可合一的，例如W=P(f(x),P(g(x)D=f(x),g(x)只有函数符号2.若D中只有一个元素，则W是不可合一的，例如W=P(x),P(x,y) D=y3.若D中有变量符号x和项t，且x出现在t中，则W是不可合一的，例如W=P(x),P(f(x) D=x,f(x)x出现在项f(x)中73求公式E1，E2的最一般合一算法（mgu算法）：步骤1：令W=E1,E2步骤2：令k=0, Wk=W,

35、k=步骤3：如果Wk只有一个元素，则停止， k是W的最一般合一；否则，找出Wk的差异集合Dk。步骤4：若D k中存在元素vk、t k，其中vk是变量符号，并且不出现在t k中，则转到步骤5；否则，W是不可合一的，算法停止。步骤5：令k+1= k t k /vk， Wk+1=Wk+1 步骤6：K+1K,转到步骤3。若E1,E2可合一，算法必停于步骤3。74例有公式E1=P(a,x,f(g(y) , E2=P(z,f(a),f(u) 求E1,E2的最一般合一mgu。解：根据算法1.W=E1 , E2=P(a,x,f(g(y) , P(z,f(a),f(u) 2.W0=W, 0= 3. W0未合一，

36、找出W0的差异集合D0=a,z4.取v0=z，t0=a5.令1= 0t0 /v0=a/zW1= W0 1 =P(a,x,f(g(y) , P(a,f(a),f(u) 3. W1未合一，找出W1的差异集合D1=x,f(a)4.取v1=x，t1=f(a)5.令2= 1t1 /v1=a/z,f(a)/xW2= W12 =P(a,f(a),f(g(y) , P(a,f(a),f(u) 3. W2未合一，找出W1的差异集合D2=g(y),u4.取v2=u，t2=g(y)5.令3= 2t2 /v2=a/z,f(a)/x,g(y)/u W3= W23=P(a,f(a),f(g(y) , P(a,f(a),f

37、(g(y) 3. W3已合一，此时3= a/z,f(a)/x,g(y)/u 是E1,E2的最一般合一mgu。75例有公式E1=Q(f(a),g(x) , E2=Q(y,y) 求E1,E2的最一般合一mgu。解：根据算法1.令W=E1 , E2=Q(f(a),g(x) , Q(y,y)2.W0=W, 0= 3. W0未合一，找出W0的差异集合D0=f(a),y4.取v0=y，t0=f(a)5.令1= 0t0 /v0=f(a)/yW1= W0 1 =Q(f(a),g(x) , Q(f(a),f(a)3. W1未合一，找出W1的差异集合D1=g(x),f(a)4. D1中无变量符号，算法停止，W不可

38、合一。76 归结原理也称消解原理，它可直接应用到任意子句集S上，去检验S的不可满足性。 归结原理的本质思想是去检查子句集S是否包含一个空子句，如果S包含，则S是不可满足的。如果S不包含 ，则去检查是否可由S推导出来。当然这个推理规则必须保证推出的子句是原亲本子句的逻辑结果。归结原理就是这样一种推理规则。771. 命题逻辑中的归结原理 定义：设C1与C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么从C1和C2中分别消去L1和L2,并将两个子句中的余下部分析取，构成一个新的子句C12，则称这一过程为归结。称C12是C1和C2的归结式。称C1和C2是C12的亲本子句。例

39、设C1=PQRC2=Q S可见C1中的文字L1=Q与C2中的文字L2=Q互补。因此可通过归结得：C12=PR S例设 C1=P， C2=P文字P与文字P互补，通过归结可得：C12= 例设C1=PQ C2=Q R C3=P首先对C1，C2进行归结，得到 C12=PR 再对C12，C3进行归结，得 C123=R 78定理：归结式C12是其亲本子句C1和C2的逻辑结论。证明 设C1=LC1， C2=LC2，通过归结可得到C12=C1C2C1和C2是C12的亲本子句。 C1L= C1LL C2 =LC2 C1C2 = ( C1L) (LC2 )由假言三段论得到：( C1L) (LC2 ) ( C1C2

40、 ) C1C2= C1C2 = C12 C1C2 C1279由以上定理可得到如下两个推论： 1.设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性。即：S1不可满足S不可满足 2.设C1与C2是子句集S中的两个子句，C12是它们的归结式，若把C12加入到S中，得到新子句集S2，则S与S2在不可满足的意义上是等价的。即： S2不可满足=S不可满足 为了证明子句集S的不可满足，只要对S中可进行归结的子句进行归结，并把归结式加入子句集S，或用归结式代替它的亲本子句，然后证明新子句集不可满足就可以了。如

41、果经过归结能得到空子句，根据空子句的不可满足性，立即得到原子句集不可满足的结论。 在命题逻辑中，对不可满足的子句集S，归结原理是完备的。这就是说：若子句集S不可满足，则必然存在一个从S到空子句的归结演绎；若存在一个从S到空子句的归结演绎，则S一定是不可满足的。 对于可满足的子句集S，用归结原理得不到任何结论。802. 谓词逻辑中的归结原理 在谓词逻辑中，由于子句中含有变元，所以不能直接消去互补文字，需要用最一般合一对变元进行代换，然后才能进行归结。例如：有子句 C1=P(x)Q(x) C2=P(a)R(y)C1的P(x)与C2的P(a)不同，所以不能直接将C1与C2进行归结。可先用最一般合一=

42、a/x分别对C1，C2进行代换：C1 =P(a)Q(a) C2 =P(a)R(y)再对C1 ，C2 进行归结，消去P(a) 、P(a)得到C1与C2的归结式 Q(a) R(y)。 定义 如果子句C中，两个或两个以上的文字有一个最一般合一，则C称为C的因子；如果C是单元子句，则称C是C的单因子。如：C=P(x) P(f(y) Q(x)令=f(y)/x，则 C = P(f(y) Q(x) C是C的因子。81 定义 设C1，C2是两个无公共变量的子句，L1，L2分别是C1，C2中的两个文字。如果L1和 L2有最一般合一，则称子句：C12=(C1 L1) (C2 L2)为C1和C2的归结式，L1，L2

43、称为归结文字。例设C1=P(a)Q(x)R(x)C2=P(y)Q(b)若取L1=P(a),L2=P(y), =a/y 有L1=P(a) L2=P(a)由定义可得：C12=(C1 L1) (C2 L2)=(P(a),Q(x),R(x)P(a) (P(a),Q(b)P(a)有时将子句写成文字的集合，要理解文字之间是合取关系=Q(x),R(x), Q(b)=Q(x) R(x) Q(b)82例 设C1=P(x) Q(x)C2=P(a) R(x)在子句C1C2中有相同的变元x，与定义的要求不符。为进行归结，先将C2中的x改名为y，令C2=P(a) R(y)并取L1=P(x),L2=P(a), =a/x,

44、则C12=(C1 L1) (C2 L2)=(P(a) , Q(a) P(a) (P(a) ,R(y) P(a)=Q(a),R(y)= Q(a) R(y)例设C1=P(x) P(f(y) R(g(y) C2=P(f(g(a) Q(b)1=f(y)/x,则C1的因子C11 = P(f(y) R(g(y)。于是C11和C2的归结式，也是C1和C2的归结式： R(g(g(a) Q(b)83 对于谓词逻辑，归结式是它的亲本子句的逻辑结论。用归结式取代它在子句集S中的亲本子句所得的新子句集仍然保持着原子句集S的不可满足性。 对于一阶谓词逻辑，从不可满足的意义上说，归结原理也是完备的，即：若子句集是不可满足

45、的，则必然存在一个从该子句集到空子句的归结演绎；若存在一个从子句集到空子句的演绎，则子句集是不可满足的。84 从子句集出发，通过归结原理可得到一个向下的演绎树，其每个初始结点代表着S的一个子句，每一个非初始结点代表着一个其前任结点上的子句归结式。例S=P Q,P Q,P Q,P Q归结演绎过程用演绎树表示如下：12345672 PQ1 PQ3 PQ4 PQ5 Q 由1 , 2归结6 Q 由3 , 4归结7 由5 , 6归结初始节点：非初始节点：123485 归结原理显然是一个很好的推理规则，但我们一般不使用它直接从前提推导结论，而是通过推导空子句来作间接证明。具体地将，就是先求出要证的命题公式

46、（或谓词公式）的否定式的子句集S，然后对子句集S（一次或多次）使用消解原理，若在某一步推出了空子句，即说明子句集S是不可满足的，从而原否定式也是不满足的，进而说明原公式是永真的。 即，对于那些由前提推结论的问题，并不需要先求出其整个谓词公式，然后再求其否定式，而只需把求证结论的否定式加入前提公式即可。例 用归结原理证明R是P，(P Q)R，(S U) Q，U的逻辑结果。证 先把诸前提条件化为子句形式，再把结论的否定也化为子句，然后对该子句集实施归结。86例 求证明G是A1和A2的逻辑结果。A1: x(P(x) (Q(x) R(x)A2: x(P(x) S(x)G: x(S(x) R(x)证 用

47、反证法。例 设已知：(1)能阅读者是识字的； (2)海豚不识字； (3)有些海豚是很聪明的。 求证：有些聪明者并不能阅读。证 首先定义谓词：R(x):x能阅读；L(x):x能识字；I(x):x是聪明的；D(x):x是海豚。然后将上述各语句翻译为谓词公式 87例 已知：。(1)如果x和y是同班同学，则x的老师也是y的老师。(2)王先生是小李的老师(3)小李和小张是同班同学。问？小张的老师是谁？解解 设谓词T(x,y)表示x是y的老师，C(x,y)表示x和y是同班同学，则已知可表示为下面的谓词公式： 为了得到问题的答案，先证明小张的老师是存在的。88已知一串香蕉挂在天花板上，猴子直接去拿是够不到的

48、，但猴子可以走动且可以搬着梯子走动，也可以爬上梯子来达到吃香蕉的目的。对这个问题的描述，不可忽视动作的先后次序，需体现出时间概念。常用的方法是引入状态S来区分动作的先后，以不同的状态表现不同的时间，而状态间的转换由一些算子(函数)来实现。89l首先引入谓词 P(x,y,z,s)表示猴子位于x处，香蕉位于y 处，梯子位于z处，相应的状态为s。或说猴子在x 处，香蕉在y 处，梯子在z处，而状态又为s时，谓词P(x,y,z,s)方为真。R(s)表示s状态下猴子吃到香蕉。ANS(s)表示形式谓词 ，只是为求得回答的动作序列而虚设的。 90l其次引入状态转移函数。Walk (y,z,s)表示原状态s下，

49、在walk作用下猴子从y走到z 处所建立的一个新状态。lCarry(y,z,s)表示原状态s 下，在Carry 作用下猴子搬着梯子从y走到z 处建立的一个新状态。lClimb(s) 表示原状态s下，在Climb作用下猴子爬上梯子所建立的一个新状态。l设初始状态为S0,猴子位于a,香蕉位于b ,梯子位于c。919293l（1）P(x,y,z,s) P(z,y,z,walk(x,z,s)（2）P(x,y,x,s) P(y,y,y,Carry(x,y,s)（3）P(b,b,b,s) R(Climb (s)（4）P(a,b,c,s)（5）R(s) ANS(s)（6）P(b,b,b,s) ANS(Cli

50、mb(s)(3)(5)归结（7）P(x,b,x,s) ANS(Climb(Carry(x,b,s) (2)(6)归结（8）P(x,b,z,s) ANS(Climb(Carry(z,b,walk(x,z,s) (1)(7)归结（9）ANS(Climb(Carry(c,b,walk(a,c,s) (4)(8)归结于是猴子吃香蕉的问题的答案是Climb (Carry(c,b,walk(a,c,s) 943.4 用归结原理证明定理的过程成为归结反演。归结反演的步骤：设已知前提的公式集F,目标公式为Q。1.否定Q，得到Q。2.把Q并入到公式集F中，得到F,Q。3.把公式集F,Q化为子句集S。4.应用归结

51、原理对子句集S中的子句进行归结，并把每次得到的归结式再并入S中，如此反复进行，若出现空子句则停止，此时就证明了定理。95例 已知某些病人喜欢所有的医生，没有一个病人喜欢任意一个骗子。证明：任意一个医生都不是骗子。证明：令：P(x):x是病人 D(x):x是医生Q(x):x是骗子L(x,y):x喜欢yA1:x(P(x)y(D(y)L(x,y)某些病人喜欢所有的医生A2:x(P(x)y(Q(y)L(x,y)没有一个病人喜欢任意一个骗子B: x(D(x) Q(x)任意一个医生都不是骗子为证明公式A1 A2 B是不可满足的，先求出A1 A2 B的子句集。A1 =x(P(x)y(D(y)L(x,y) =

52、x(P(x)y(D(y) L(x,y) =xy(P(x) (D(y) L(x,y) =y(P(a) (D(y) L(a,y)A2 =x(P(x)y(Q(y)L(x,y) =x(P(x)y(Q(y) L(x,y) =x(P(x) y(Q(y) L(x,y) =xy(P(x) Q(y) L(x,y)B= x(D(x) Q(x) = x (D(x) Q(x) = x (D(x) Q(x) = x (D(x) Q(x) = D(b) Q(b)得到公式A1 A2 B的子句集：S=P(a), D(y) L(a,y), P(x) Q(y) L(x,y), D(b) , Q(b)96对子句集 S=P(a),

53、D(y) L(a,y), P(x) Q(y) L(x,y), D(b) , Q(b)应用归结原理：1. P(a)2. D(y) L(a,y)3. P(x) Q(y) L(x,y) 4.D(b)5.Q(b)6.L(a,b) 由2,4归结7. Q(y) L(a,y) 由1,3归结8. L(a,b) 由5,7归结9. 由6,8归结对应的演绎树：D(y) L(x,y) D(b)P(a)P(x) Q(y) L(x,y)Q(b)L(a,b)Q(y) L(a,y)L(a,b)97例 若A1= x(A(x)B(x)C(x) A2=x(A(x)D(x) B= x(D(x)C(x)求证B是A1 A2的逻辑结论。证

54、明求证A1 A2 B，就是证明公式A1 A2 B是不可满足的。将A1 ， A2 ， B分别化成Skolem标准型，求子句集S。A1= x(A(x)B(x)C(x)= x(A(x) (B(x)C(x)= x(A(x) B(x)(A(x) C(x) )A2=x(A(x)D(x)Skolem范式：A(a) D(a)B= x(D(x)C(x)= x(D(x) C(x)公式A1 A2 B对应的子句集为：S=A(x) B(x), A(x) C(x) , A(a) ,D(a), D(x) C(x)98对S=A(x) B(x), A(x) C(x) , A(a) ,D(a), D(x) C(x)应用归结原理：1. A(x) B(x),2. A(x) C(x) 3. A(a) 4. D(a)5. D(x) C(x)7. C(a)由4、56.C(a)由2、38. 由6、7993.5 计算机在对子句集进行归结时，由于事先不知道哪两个子句可以进行归结，更不知道通过哪些子句的归结可以尽快得到空子句，因而必须对子句集中的所有子句逐对地进行比较，对任何一对可以归结的子句都进行归结。 这样不仅耗费时间，而且会导致大量不必要的无用的归结式产生。为提高归结效率，就需要给出归结控制策略，使归结过程中避免多余的不必要的归结式出