1、第3篇 知识与推理导语导语 1.知识知识及其表示及其表示 一些常用的知识表示形式：一阶谓词、产生式规则、框架、语义网络、类和对象、贝叶斯网络、脚本、过程、软集合等。2.机器机器推理推理 机器推理涉及的各种推理 演绎推理、归纳推理和类比推理；不确定性推理、不确切性推理；约束推理、定性推理、范例推理、非单调推理第5章 基于一阶谓词的机器推理 5.1 一阶谓词逻辑 5.2 归结演绎推理 5.3 应用归结原理求取问题答案 5.4 归结策略 5.5 归结反演程序举例 5.6 Horn子句逻辑与逻辑程序设计语言 延伸学习导引 5.1 一阶谓词逻辑 5.1.1 谓词，函数，量词 定义 5-1 表达式 P(t
2、1,t2,tn)称为一个n元谓词，或简称谓词。其中P是谓词名或谓词符号，也称谓词，表示对象的属性、状态、关系、联系或行为，t1,t2,tn称为谓词的项，一般代表个体对象。例如：prime(2)friend(张三,李四)就是两个谓词。其中prime(2)是个一元谓词，表示：2是个素数；friend(张三,李四)是个二元谓词，表示：张三和李四是朋友。形式 f(x1,x2,xn)表示个体x1,x2,xn所对应的个体y，并称之为（n元）个体函数，简称函数（或函词、函词命名式），其中f是函数符号。例如，可用doctor(father(Li)表示“小李的父亲是医生”，用equa(sq(x),y)表示“x的
3、平方等于y”。下面约定用大写英文字母作为谓词符号，用小写字母f,g,h等表示函数符号，用小写字母x,y,z等作为个体变元符号，用小写字母a,b,c等作为个体常元符号。v谓词逻辑中，符号、依次表示（命题）连接词“非”“并且”“或者”“如果则”“当且仅当”，称为否定词、合取词、析取词、蕴涵词、等价词。它们也就是5个逻辑运算符。v谓词逻辑中，将“所有”“一切”“任一”“全体”“凡是”等词统称为全称量词，记为；“存在”“一些”“有些”“至少有一个”等词统称为存在量词，记为。例如命题“凡是人都有名字”，就可以表示为 x(P(x)N(x)或 xN(x)命题“存在不是偶数的整数”表示为 x(I(x)E(x)
4、紧接于量词之后被量词作用（即说明或限定）的命题函数式称为该量词的辖域。例如：(1)x P(x)(2)x(H(x)G(x,y)(3)x A(x)B(x)其中：(1)中的P(x)为全称量词的辖域，(2)中的H(x)G(x,y)为全称量词的辖域，(3)中的A(x)为存在量词 的辖域，但B(x)并非 的辖域。约束变元的改名规则：(1)对需改名的变元，应同时更改该变元在量词及其辖域中的所有出现。(2)新变元符号必须是量词辖域内原先没有的，最好是公式中也未出现过的。例如公式xP(x)Q(x)可改为yP(y)Q(x)，二者的意义相同。vxA(x)为全称命题，xA(x)为特称命题。当个体域为有限集时，有下面的
5、等价式：x A(x)A(a1)A(a2)A(an)x A(x)A(a1)A(a2)A(an)这两个式子也可以推广到个体域为可数无限集。5.1.2 谓词公式 定义 5-2 (1)个体常元和个体变元都是项。(2)设f是n元函数符号，若t1,t2,tn是项，则f(t1,t2,tn)也是项。(3)只有有限次使用(1)，(2)得到的符号串才是项。定义 5-3 设P为n元谓词符号，t1,t2,tn是项，则P(t1,t2,tn)称为原子谓词公式，简称原子公式或者原子。定义 5-4 （谓词公式的生成规则）(1)原子公式是谓词公式。(2)若P,Q是谓词公式，则 P,PQ,PQ,PQ,PQ,xP,xP也是谓词公式
6、。(3)只有有限步应用(1)、(2)生成的公式才是谓词公式。定义 5-5 设G为如下形式的谓词公式：P1P2Pn 其中P i(i=1,2,n)形如L1L2Lm，Lj(j=1,2,m)为原子公式或其否定，则G称为合取范式。例如：(P(x)Q(y)(P(x)Q(y)R(x,y)(Q(y)R(x,y)就是一个合取范式。应用逻辑等价式，任一谓词公式都可以化为与之等价的合取范式，这个合取范式就称为原公式的合取范式。一个谓词公式的合取范式一般不唯一。定义 5-6 设G为如下形式的命题公式：P1P2Pn 其中Pi(i=1,2,n)形如L1L2Lm，Lj(j=1,2,m)为原子公式或其否定，则G称为析取范式。
7、例如：(P(x)Q(y)R(x,y)(P(x)Q(y)(P(x)R(x,y)就是一个析取范式。应用逻辑等价式，任一谓词公式都可以化为与之等价的析取范式，这个析取范式就称为原公式的析取范式。同样，一个谓词公式的析取范式一般也不唯一。定义 5-7 谓词公式G在个体域D中的一个解释I是指：(1)对G中每一个常元符号指定D中的一个元素；(2)对G中每一个n元函数符号指定一个函数，即Dn到D的一个映射；(3)对每个n元谓词符号指定一个谓词，即Dn到T,F的一个映射。例 5-1 设谓词公式G=x(P(f(x)Q(x,f(a)，给出如下的一 个解释I：由于x=1时，P(f(x)Q(x,f(a)=P(f(1)
8、Q(1,f(1)=P(2)Q(1,2)=TT =T 所以，谓词公式G在I下为真。定义 5-8 设G,H是两个谓词公式，D是它们的公共个体域，若对于D中的任一解释，G,H有相同的真值，则称公式G,H在个体域D上逻辑等价。若G,H在所有个体域上等价，则称G,H逻辑等价，记为G H。定义 5-9 设G,H是两个谓词公式，D是它们的公共个体域，若对于D中的任一解释，当G真时H也真，则称在个体域D上公式G逻辑蕴涵公式H。若在所有个体域上G都逻辑蕴涵H，则称G逻辑蕴涵H，或称H是G的逻辑结果，记为 G H。定理 5-1 设G,H是两个谓词公式，GH的充分必要条件是 G H 且 H G。5.1.3 永真式与
9、推理规则 定义 5-10 设P为谓词公式，D为其个体域，对于D中的任一解释I：(1)若P恒为真，则称P在D上永真（或有效）或是D上的永真式。(2)若P恒为假，则称P在D上永假（或不可满足）或是D上的永假式。(3)若至少有一个解释,可使P为真，则称P在D上可满足或是D上的可满足式。定义 5-11 设P为谓词公式，对于任何个体域：(1)若P都永真，则称P为永真式。(2)若P都永假，则称P为永假式。(3)若P都可满足，则称P为可满足式。定理 5-2 设G,H是两个谓词公式，则 GH永真的充分必要条件是G H GH永真的充分必要条件是G H 定理 5-3 一个推理形式正确，当切仅当其对应的蕴涵式永真。
10、5.1.4 自然语言命题的谓词形式表示一般方法：(1)简单命题可以直接用原子公式来表示；(2)复合命题则需要先找出支命题，并将其符号化为原子公式，然 后根据支命题之间的逻辑关系选用合适的连接词（,）和量词（,）将这些原子公式连接起来。例 5-2 用谓词公式表示命题：不存在最大的整数。解 用I(x)表示：x是整数，用D(x,y)表示：x大于y。则原命题就可形式化为 x(I(x)y(I(y)D(x,y)或 x(I(x)y(I(y)D(y,x)例5-3 设有命题：对于所有的自然数x,y，均有x+yx。用谓词公式表示之。解 用N(x)表示：x是整数，S(x,y)表示函数：s=x+y，D(x,y)表示：
11、x大于y，则原命题可形式化为谓词公式 xy(N(x)N(y)D(S(x,y),x)例5-4 将命题“某些人对某些食物过敏”用谓词公式表示。解 用P(x)表示：x是人，用F(x)表示：x是食物，用A(x,y)表示：x对y过敏。则原命题可用谓词公式表示为 xy(P(x)F(y)A(x,y)5.1.5 基于谓词公式的形式演绎推理例5-5 设有前提：(1)凡是大学生都学过计算机；(2)小王是大学生。试问：小王学过计算机吗？解 令S(x)表示：x是大学生；M(x)表示：x学过计算机；a表示：小王。则上面的两个命题可用谓词公式表示为 (1)x(S(x)M(x)(2)S(a)下面遵循有关推理规则进行符号变换
12、和推理：(1)x(S(x)M(x)前提 (2)S(a)M(a)(1),US (3)S(a)前提 (4)M(a)(2),(3),I3 得结果：M(a)，即“小王学过计算机”。例 5-6 证明：P(a,b)是 xy(P(x,y)W(x,y)和 W(a,b)的逻辑结果。证 (1)x y(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-7 证明：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
13、)(1),US (3)Q(y)P(y)(2),逆否变换 (4)x(R(x)Q(x)前提 (5)R(y)Q(y)(4),US (6)R(y)P(y)(3),(5),I6 (7)x(R(x)P(x)(6),UG5.2 归结演绎推理5.2.1 子句集 定义 5-12 原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句，由r个文字组成的子句叫r-文字子句，1-文字子句叫单元子句，不含任何文字的子句称为空子句，记为或NIL。例：PQR P(x,y)Q(x)定义 5-13 对一个谓词公式G，通过以下步骤所得的子句集合S，称为G的子句集。(1)消去蕴含词和等值词。(2)缩小否定词的作用范围，直
14、到其仅作用于原子公式。(3)适当改名，使量词间不含同名指导变元和约束变元。(4)消去存在量词。(5)消去所有全称量词。(6)化公式为合取范式。(7)适当改名，使子句间无同名变元。(8)消去合取词，以子句为元素组成集合S。例 5-8 求下面谓词公式的子句集 xyP(x,y)yQ(x,y)R(x,y)解 由步骤(1)得 xyP(x,y)yQ(x,y)R(x,y)由步骤(2)得 x y P(x,y)yQ(x,y)R(x,y)由步骤(3)得 xy P(x,y)zQ(x,z)R(x,z)由步骤(4)得 xP(x,f(x)Q(x,g(x)R(x,g(x)由步骤(5)得 P(x,f(x)Q(x,g(x)R(
15、x,g(x)由步骤(6)得 P(x,f(x)Q(x,g(x)P(x,f(x)R(x,g(x)由步骤(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)这就是原谓词公式的子句集。定理 5-4 谓词公式G不可满足当且仅当其子句集S不可满足。定义 5-14 子句集S是不可满足的，当且仅当其全部子句的合取式是不可满足的。5.2.2 命题逻辑中的归结原理 定义 5-15 设L为一个文字，则称L与 L为互补文字。定义 5-16 设C
16、1,C2是命题逻辑中的两个子句，C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1,C2中分别删除L1,L2，再将剩余部分析取起来，记构成的新子句为C12，则称C12为C1,C2的归结式(或消解式)，C1,C2称为其归结式的亲本子句，L1,L2称为消解基。例例 5-10 设C1=PQR,C2=QS,则C1,C2的归结式为 PRS 定理5-5 归结式是其亲本子句的逻辑结果。由定理5-5即得推理规则：C1C2 (C1 L1)(C2 L2)其中C1,C2是两个子句，L1,L2分别是C1,C2中的文字，且L1,L2互补。此规则就是命题逻辑中的归结原理。例 5-11 用归结原理验证假言推理和拒
17、取式 P(PQ)Q，(P Q)Q P 证 P(PQ)=P(PQ)Q (PQ)Q=(PQ)Q P 由归结原理，L L=；又，LL=F（假）。于是有 F这样，就可通过推导空子句来作间接证明一个命题公式的永真性。具体来讲，就是先求出要证的命题公式（谓词公式也一样）的否定式的子句集S，然后对子句集S（一次或多次）使用消解原理，若在某一步推出了空子句，即推出了矛盾，则说明子句集S是不可满足的，从而原否定式也是不可满足的，进而说明原公式是永真的。例 5-12 证明子句集PQ,P,Q是不可满足的。证 (1)PQ (2)P (3)Q (4)Q 由(1),(2)(5)由(3),(4)例 5-13 用归结原理证明
18、R是 P,(PQ)R,(SU)Q,U 的逻辑结果。证 由所给条件得到子句集 S=P,P QR,SQ,UQ,U,R 然后对该子句集施行归结，归结过程用下面的归结演绎树表示(见图5-1)。由于最后推出了空子句，所以子句集S不可满足，即命题公式 P(P QR)(SQ)(UQ)U R 不可满足，从而R是题设前提的逻辑结果。图5-1 例5-13的归结演绎树 5.2.3 替换与合一 定义 5-17 一个替换(Substitution)是形如 t1/x1,t2/x2,tn/xn 的有限集合，其中t1,t2,tn是项，称为替换的分子；x1,x2,xn是互不相同的个体变元，称为替换的分母；ti不同于xi，xi也
19、不循环地出现在tj(i,j=1,2,n)中；ti/xi表示用ti替换xi。若t1,t2,tn都是不含变元的项（称为基项）时，该替换称为基替换；没有元素的替换称为空替换，记作，它表示不作替换。例如，设 C1=P(x)Q(x)，C2=P(a)R(y)，用a替换C1中的x，则得 C1=P(a)Q(a)，C2=P(a)R(y)又如：a/x,g(y)/y,f(g(b)/z 就是一个替换，而 g(y)/x,f(x)/y 则不是一个替换,因为x与y出现了循环替换。定义 5-18 设=t1/x1,tn/xn是一个替换，E是一个表达式，把对E施行替换，即把E中出现的个体变元xj(1jn)都用tj替换，记为E，所
20、得的结果称为E在下的例(instance)。定义 5-19 设=t1/x1,tn/xn,=u1/y1,um/ym是两个替换，则将集合t1/x1,tn/xn,u1/y1,um/ym中凡符合下列条件的元素删除：(1)ti/xi 当ti=xi (2)ui/yi 当yix1,xn 如此得到的集合仍然是一个替换，该替换称为与的复合或乘积，记为 。例 5-14 设=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 从而 =f(b)/x,y/z 定义 5-20 设S=F1,F2,Fn是一个原子谓词公
21、式集，若存在一个替换，可使F1=F2=Fn，则称为S的一个合一(Unifier)，称S为可合一的。定义 5-21 设是原子公式集S的一个合一，如果对S的任何一个合一，都存在一个替换，使得 =则称为S的最一般合一(Most General Unifier)，简称MGU。例 5-15 设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 使得 =5.2.4 谓词逻辑中的归结原理 定义5-23 设C1,C2是两个无相同变元的子句，L1,L2分别
22、是C1,C2中的两个文字，如果L1和L2有最一般合一，则子句 (C1 L1)(C2 L2)称作C1和C2的二元归结式(二元消解式)，C1和C2称作归结式的亲本子句，L1和L2称作消解文字。例 5-17 设 C1=P(x)Q(x),C2=P(a)R(y)，求C1,C2的归结式。解 取L1=P(x),L2=P(a),则L1与L2的最一般合一 =a/x 于是,(C1L1)(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-18 设C1=P(x,y)Q(a),C2=Q(x)R(y),求C1
23、,C2的归结式。解 由于C1,C2中都含有变元x,y，所以需先对其中一个进行改名,方可归结（归结过程是显然的，故从略）。定义5-24 如果子句C中，两个或两个以上的文字有一个最一般合一，则C称为C的因子，如果C是单元子句，则C称为C的单因子。例 5-19 设C=P(x)P(f(y)Q(x),令=f(y)/x，于是 C=P(f(y)Q(f(y)是C的因子。定义5-25 子句C1,C2的消解式，是下列二元消解式之一：(1)C1和C2的二元消解式;(2)C1和C2的因子的二元消解式;(3)C1的因子和C2的二元消解式;(4)C1的因子和C2的因子的二元消解式。定理5-6 谓词逻辑中的消解式是它的亲本
24、子句的逻辑结果。由此定理即得谓词逻辑中的推理规则：C1C2(C1 L1)(C2 L2)其中C1,C2是两个无相同变元的子句，L1,L2分别是C1,C2中的文字，为L1与L2的最一般合一。此规则称为谓词逻辑中的消解原理（或归结原理）。例5-20 求证G是A1和A2的逻辑结果。A1:x(P(x)(Q(x)R(x)A2:x(P(x)S(x)G:x(S(x)R(x)证 用反证法，即证明A1 A2G不可满足。首先求得子句集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)(
25、4),(5),2=a/z (8)(6),(7)所以S是不可满足的，从而G是A1和A2的逻辑结果。(A1)(A2)S 例 5-21 设已知：(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)
26、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-21 的归结演绎树 定理 5-7（归结原理的完备性定理）如果子句集S是不可满足的，那么必存在一个由S推出空子句的消解序列。(该定理的证明要用到Herbrand定理，故从略。)5.3 应用归结原理求取问题答案 例 4-22 已知：(1)如果x和y是同班同学，则x的老师也是y的老师。(2)王先生是小李的老师。(3)小李和小张是同班同学。问：小张的老师是谁？解 设谓词T(x,y)表示x是y的
27、老师，C(x,y)表示x与y是同班同学，则已知可表示成如下的谓词公式：F1:xyz(C(x,y)T(z,x)T(z,y)F2:T(Wang,Li)F3:C(Li,Zhang)为了得到问题的答案，先证明小张的老师是存在的，即证明公式：G:xT(x,Zhang)于是，求F1F2F3G的子句集如下:(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,y)由(1),(2),Wang/z,Li/x (6)C(Li,Zhang)由(4),5),Wang/u,Zhang/y (7)由(3),
28、(6)这说明，小张的老师确实是存在的。那么，为了找到这位老师，给原来的求证谓词的子句再增加一个谓词ANS(u)。于是，得到 (4)T(u,Zhang)ANS(u)现在，用(4)代替(4)，重新进行归结，则得 (5)C(Li,y)T(Wang,y)由(1),(2)(6)C(Li,Zhang)ANS(Wang)由(4),(5)(7)ANS(Wang)由(3),(6)例 5-23 设有如下关系:(1)如果x是y的父亲，y又是z的父亲，则x是z的祖父。(2)老李是大李的父亲。(3)大李是小李的父亲。问：上述人员中谁和谁是祖孙关系？解 先把上述前提中的三个命题符号化为谓词公式：F1:xyz(F(x,y)
29、F(y,z)G(x,z)F2:F(Lao,Da)F3:F(Da,Xiao)并求其子句集如下:(1)F(x,y)F(y,z)G(x,z)(2)F(Lao,Da)(3)F(Da,Xiao)设求证的公式为 G:xyG(x,y)（即存在x和y，x是y的祖父）把其否定化为子句形式再析取一个辅助谓词GA(x,y)，得 (4)G(u,v)GA(u,v)对(1)(4)进行归结,得 (5)F(Da,z)G(Lao,z)由(1),(2),Lao/x,Da/y (6)G(Lao,Xiao)由(3),(5),Xiao/z (7)GA(Lao,Xiao)由(4),(6),Lao/u,Xiao/v所以，上述人员中，老李是
30、小李的祖父。5.4 归结策略 5.4.1 问题的提出 一个实现归结原理的一般性算法：(1)将子句集S入CLAUSES表；(2)若空子句NIL在CLAUSES中，则归结成功，结束。(3)若CLAUSES表中存在可归结的子句对，则归结之，并 将归结式并入CLAUSES表，转步(2)；(4)归结失败，退出。例5-24 设有如下的子句集S，用上述的穷举算法归结如下：S:(1)PQ (2)PQ (3)PQ (4)PQ S1:(5)Q (1),(2)(6)P (1),(3)(7)QQ (1),(4)(8)PP (1),(4)(9)QQ (2),(3)(10)PP (2),(3)(11)P (2),(4)(
31、12)Q (3),(4)S2:(13)PQ (1),(7)(14)PQ (1),(8)(15)PQ (1),(9)(16)PQ (1),(10)(17)Q (1),(11)(18)P (1),(12)(19)Q (2),(6)(20)PQ (2),(7)(21)PQ (2),(8)(22)PQ (2),(9)(23)PQ (2),(10)(24)P (2),(12)(25)P (3),(5)(26)PQ (3),(7)(27)PQ (3),(8)(28)PQ (3),(9)(29)PQ (3),(10)(30)Q (3),(11)(31)P (4),(5)(32)Q (4),(6)(33)PQ
32、 (4),(7)(34)PQ (4),(8)(35)PQ (4),(9)(36)PQ (4),(10)(37)Q (5),(7)(38)Q (5),(9)(39)(5),(12)这个例子说明，穷举式归结效率低下。因此，必须讲究归结策略。5.4.2 几种常用的归结策略 1.删除策略删除策略 定义 5-26 设C1,C2是两个子句，若存在替换，使得C1C2，则称子句C1类含C2。删除策略：在归结过程中可随时删除以下子句：(1)含有纯文字的子句；(2)含有永真式的子句；(3)被子句集中别的子句类含的子句。例 5-25 对例5-24中的子句集使用删除策略。这时原归结过程中产生的有些归结式是永真式（如(
33、7)、(8)、(9)、(10)），有些被前面已有的子句所类含（如(17)、(18)等，重复出现可认为是一种类含），因此，它们可被立即删除。于是，归结步骤可简化为 (1)PQ (2)PQ (3)PQ (4)PQ (5)Q (1),(2)(6)P (1),(3)(7)P (2),(4)(8)Q (3),(4)(9)(5),(8)例 5-26 对下面的子句集S，用宽度优先策略与删除策略相结合的方法进行消解。S:(1)P(x)Q(x)R(x)(2)Q(a)(3)R(a)Q(a)(4)P(y)(5)P(z)R(z)可以看出，(4)类含了(1)，所以先将(1)删除。于是，剩下的四个子句归结得 S1:(6)
34、R(a)(2),(3)(7)P(a)Q(a)(3),(5),a/z (8)R(z)(4),(5),z/y (6)出现后(3)可被删除，所以，第二轮归结在(2)、(4)、(5)、(6)、(7)、(8)间进行。其中(2)、(4)、(5)间的归结不必再重做，于是得 S2:(9)P(a)(2),(7)(10)Q(a)(4),(7),a/y (11)P(a)(5),(6),a/z (12)(6),(8),a/z删除策略有如下特点：删除策略的思想是及早删除无用子句，以避免无效归结，缩小搜索规模；并尽量使归结式朝“小”（即元数少）方向发展。从而尽快导出空子句。删除策略是完备的。即对于不可满足的子句集，使用删
35、除策略进行归结，最终必导出空子句。定义5-27 一个归结策略是完备的，如果对于不可满足的子句集，使用该策略进行归结，最终必导出空子句。2.支持集策略支持集策略 支持集策略：每次归结时，两个亲本子句中至少要有一个是目标公式否定的子句或其后裔。这里的目标公式否定的子句集即为支持集。例 5-27 设有子句集 S=I(x)R(x),I(a),R(y)L(y),L(a)其中子句I(x)R(x)是目标公式否定的子句。用支持集策略归结如下：S:(1)I(x)R(x)(2)I(a)(3)R(y)L(y)(4)L(a)S1:(5)R(a)由(1),(2),a/x (6)I(x)L(x)由(1),(3),x/y
36、S2:(7)L(a)由(5),(3),a/y (8)L(a)由(6),(2),a/x (9)I(a)由(6),(4),a/x (10)由(7),(4)支持集策略有如下特点：这种策略的思想是尽量避免在可满足的子句集中做归结，因为从中导不出空子句。而求证公式的前提通常是一致的，所以，支持集策略要求归结时从目标公式否定的子句出发进行归结。所以，支持集策略实际是一种目标制导的反向推理。支持集策略是完备的。3.线性归结策略线性归结策略 线性归结策略：在归结过程中，除第一次归结可都用给定的子句集S中的子句外，其后的各次归结则至少要有一个亲本子句是上次归结的结果。例 5-28 对例5-27中的子句集，我们用
37、线性归结策略归结。(1)I(x)R(x)(2)I(a)(3)R(y)L(y)(4)L(a)(5)R(a)由(1),(2),a/x (6)L(a)由(5),(3),a/y (7)由(6),(4)4.输入归结策略输入归结策略 输入归结策略：每次参加归结的两个亲本子句，必须至少有一个是初始子句集S中的子句。输入归结策略的特点是：输入归结策略实际是一种自底向上的推理，它有相当高的效率。输入归结是不完备的。例如子句集 S=PQ,PQ,PQ,PQ 是不可满足的，用输入归结都不能导出空子句，因为最后导出的子句必定都是单文字子句，它们不可能在S中。5.单元归结策略单元归结策略 单元归结策略：在归结过程中，每次
38、参加归结的两个亲本子句中必须至少有一个是单元子句。单元归结策略的特点：单元归结的思想是，用单元子句归结可使归结式含有较少的文字，因而有利于尽快逼近空子句。单元归结也是一种效率高但不完备的策略。6.祖先过滤形策略祖先过滤形策略祖先过滤形策略：参加归结的两个子句，要么至少有一个是初始子句集中的子句；要么一个是另一个的祖先（或者说一个是另一个的后裔）。5.4.3 归结策略的类型 (1)简化性策略 这种策略的思想是尽量简化子句和子句集，以减少和避免无效归结。如删除策略就是简化策略。然而，简化策略在使用时，也要付出一定的开销，如要不断地做包含检验或真值计算。这又是它的缺点。(2)限制性策略 前面所介绍的
39、策略多数都是限制性策略。如支持集策略、线性策略、输入策略、单元策略、祖先过虑策略、语义归结等。限制性策略的思想是尽量缩小搜索范围，以提高搜索效率。(3)有序性策略有序性策略的思想是给子句安排一定的顺序，以便能尽快地推出空子句。单元优先策略、加权策略以及锁归结等都是有序性归结策略。有了归结策略后，本节开始所给的归结反演一般算法可改为：(1)将子句集S置入CLAUSES表；(2)若空子句NIL在CLAUSES中，则归结成功，结束。(3)按某种策略在CLAUSES表中寻找可归结的子句对，若存在则归结之，并将归结式并入CLAUSES表，转步(2)；(4)归结失败，退出。5.5 归结反演程序举例v一个可
40、用于命题逻辑归结反演的PROLOG示例程序。vprove(F,S):-union(F,S,SY),proof(SY).vunion(,Y,Y).vunion(X|XR,Y,Z):-member(X,Y),!,union(XR,Y,Z).vunion(X|XR,Y,X|ZR):-union(XR,Y,ZR).vproof(SH|ST):-resolution(SH,ST,),!.vproof(SH|ST):-resolution(SH,ST,NF),proof(NF,SH|ST).vresolution(SH,STH|ST,NF):-resolve(SH,STH,NF1),NF1=SH,!,re
41、solution(SH,ST,NF).vresolution(SH,STH|ST,NF):-resolve(SH,STH,NF),print(SH,STH,NF).vresolve(,_,):-!.vresolve(F|FR,SF,FR):-not(F=no),invert(F,IF),IF=SF,!.vresolve(F|FR,SF,NF):-not(F=no),invert(F,IF),member(IF,SF),!,pack(F,FR,SF,NF).resolve(F|FR,SF,NF):-not(F=no),!,resolve(FR,SF,NF1),pack(,F,NF1,NF).re
42、solve(F,SF,):-invert(F,IF),IF=SF,!.resolve(F,SF,NF):-invert(F,IF),member(IF,SF),!,pack(F,SF,NF).resolve(F,_,F).invert(X,no,X):-atom(X).invert(no,X,X):-atom(X).member(X,X|_):-!.member(X,_|Y):-member(X,Y).pack(A,X,Y,Z):-combine(A,X,Y,Z|),!.pack(A,X,Y,Z):-combine(A,X,Y,Z).combine(A,X,Y,Z):-union(X,Y,Z1
43、),delete(A,Z1,Z2),invert(A,IA),delete(IA,Z2,Z).delete(_,).delete(E,E|ER,R):-!,delete(E,ER,R).delete(E,X|XR,X|R):-delete(E,XR,R).print(F,S,R):-write(F),write(,),write(S),write(),write(R),nl.5.6 Horn子句逻辑与逻辑程序设计语言 5.6.1 子句的蕴涵表示形式 任一个子句，总可以表示为如下形式：Q1QnP1Pm (5-1)其中Pi,Qj皆为文字。可以看出，(5-1)式进一步可变形为 Q1Q2QnP1P2P
44、m (5-2)(5-2)式为一个蕴涵式，如果约定蕴涵式前件的文字之间恒为合取关系，而蕴涵式后件的文字恒为析取关系，那么(5-2)式又可以改写为 Q1,Q2,QnP1,P2,Pm (5-3)由于技术上的原因，又将(5-3)式改写为 P1,P2,PmQ1,Q2,Qn (5-4)作为特殊情形，当m=0时(5-4)式变为 Q1,Q2,Qn (5-4)它相当于(Q1Q2Qn)；当n=0时，(5-4)式变为 P1,P2,Pm (5-4)它相当于P1P2Pm。这样，对于任一子句，总可以把它表示成(5-4)式的形式。子句的这种表示形式称为子句的蕴涵表示形式。例如，子句 P(x)Q(x,y)R(y)的蕴涵表示形
45、式为 Q(x,y)P(x),R(y)一般地，这种蕴涵型子句的归结过程可表示如下：设子句 C：P1,PmQ1,Qn 和 C：P1,PsQ1,Qt 中有Pi与Qj（或Qi与Pj）可合一，为它们的MGU，则C与C的归结式为 P1,Pi1,Pi+1,Pm,P1,Ps Q1,Qn,Q1,Qj1,Qj+1,Qt或 P1,Pm,P1,Pj-1,Pj+1,Ps Q1,Qi1,Qi+1,Qn,Q1,Qt 5.6.2 Horn子句逻辑与计算机程序语言 定义5-26 至多含有一个正文字的子句称为Horn（有些文献中译为“霍恩”）子句。由定义，蕴涵型Horn子句有下列三种：(1)PQ1,Q2,Qm 称为条件子句,P称
46、为头部或结论；(2)P 称为无条件；;(3)Q1,Q2,Qm 称为目标子句,Qi称为子目标。例 5-31 证明P(a,c)是下面子句集(1),(2),(3),(4)的逻辑结论。证 (1)P(x,z)P1(x,y),P2(y,z)(2)P1(u,v)P11(u,v)(前提)(3)P11(a,b)(4)P2(b,c)(5)P(a,c)(目标子句)从目标子句出发，采用线性归结：(6)P1(a,y),P2(y,c)(5),(1),a/x,c/z (7)P11(a,y),P2(y,c)(6),(2),a/u,y/v (8)P2(b,c)(7),(3),b/y (9)(8),(4)延伸学习导引本章的内容也属于自动推理的范畴，在本章的基础上可参阅自动推理方面的著作继续学习。具体来讲，延伸学习的内容包括各种非经典(或非标准)逻辑及其推理。如：模态逻辑、时态逻辑、动态逻辑、真度逻辑、软语言真值逻辑、多值逻辑、多类逻辑和非单调逻辑等等。除了基于各种逻辑的推理外，还有约束推理、定性推理、范例推理、并行推理、缺省推理等等。
