《谓词逻辑与归结原理2.ppt》由会员分享，可在线阅读，更多相关《谓词逻辑与归结原理2.ppt（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、大工软院06级选修课人工智能（byWeifengSun,）人工智能基础谓词逻辑与谓词逻辑的归结原理1归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理2谓词逻辑谓词逻辑 苏格拉底苏格拉底三段论三段论:“所有的人都是要死的所有的人都是要死的,苏格拉底苏格拉底是人是人,所以苏格拉底是要死的所以苏格拉底是要死的”。论证应该是成立的。论证应该是成立的,但但是不能用命题逻辑来论证。是不能用命题逻辑来论证。若若设设P:P:所有的人都是要死的所有的人都是要死的,Q:苏格拉底是人苏格拉底是人,R:苏格拉底是要死的。但是苏格拉底
2、是要死的。但是(P Q)R不是永真式。不是永真式。P:张三是大学生张三是大学生,Q:李四是大学生李四是大学生都是原子命题都是原子命题,只能用不同的符号来表示只能用不同的符号来表示,这样就不能揭示出这两个命这样就不能揭示出这两个命题的共同特性。题的共同特性。3谓词的概念和表示谓词的概念和表示 命题是一个陈述句，它一般可分成命题是一个陈述句，它一般可分成主语主语和和谓语谓语两两部分。有时还需要用到部分。有时还需要用到量词量词。主语一般是可以独立存在的物体主语一般是可以独立存在的物体,称为称为个体个体(客体客体),用来刻划个体的性质或关系的词称为用来刻划个体的性质或关系的词称为谓语谓语(谓词谓词)。
3、通常用大写字母表示谓词，而用小写字母表示客体。通常用大写字母表示谓词，而用小写字母表示客体。4例例.设有下列命题设有下列命题:(1)张三是大学生张三是大学生;李四是大学生李四是大学生;(2)地球绕着太阳转地球绕着太阳转;(3)上海在北京与广州之间。上海在北京与广州之间。用谓词表示之。用谓词表示之。(1)设设P:张三是大学生张三是大学生,Q:李四是大学生。李四是大学生。这是两个不同的命题这是两个不同的命题,但有相同的谓语但有相同的谓语_是大学生是大学生。若设若设A:是大学生是大学生，a:张三张三,b:李四李四,则则A(a)(或或A(张三张三):张三是大学生张三是大学生,A(b)(或或A(李四李四
4、):李四是大学生。李四是大学生。5(2)地球地球绕着绕着太阳太阳转转;若设若设B:绕着绕着转转,x:地球地球,y:太阳太阳,则则B(x,y):地球绕着太阳转地球绕着太阳转#注意注意:B(y,x):太阳绕着地球转。太阳绕着地球转。B(y,x)与与B(x,y)是是不同的命题。不同的命题。(3)上海上海在在北京北京与与广州广州之间之间。若设若设Z:在在与与之间之间,s:上海上海,b:北京北京,g:广州广州,则则Z(s,b,g):上海上海在在北京北京与与广州广州之间之间。6 刻划一个个体的性质的谓词刻划一个个体的性质的谓词A(c)称为称为一元谓词一元谓词，刻，刻划二个个体间关系的谓词划二个个体间关系的
5、谓词A(a,b)称为称为二元谓词二元谓词,刻划刻划n n个个体间关系的谓词个个体间关系的谓词A(a1,a2,an,)称为称为n元元谓词。通常，一元谓词表示客体的性质，而多元谓词表谓词。通常，一元谓词表示客体的性质，而多元谓词表示客体之间的关系。示客体之间的关系。n元谓词中个体出现的次序一经约定，就是完全确元谓词中个体出现的次序一经约定，就是完全确定的定的,不可以随意改变。谓词也分不可以随意改变。谓词也分谓词常量谓词常量和和谓词变谓词变元元,这里仅讨论谓词常量。这里仅讨论谓词常量。当谓词当谓词A(a1,a2,an,)中的个体名称用具体的中的个体名称用具体的n个个个体替代得到的式子称为个体替代得到
6、的式子称为谓词填式谓词填式。7 引入符号引入符号“”称为称为全称量词全称量词,“”称为称为存在量存在量词词,统称为统称为量词量词(Quantifier),全称量词表示全称量词表示“凡是凡是”,“一切一切”,“所有所有”,“任一个任一个”等意义等意义;存在量词表存在量词表示示“至少有一个至少有一个”等意义等意义;现在用量词来表达上面几个现在用量词来表达上面几个命题。命题。(a)若设若设M(x):x是人是人,H(x):x要呼吸要呼吸,则原命题可写成则原命题可写成:(x)(M(x)H(x)(b)若设若设P(x):x是是学生学生,Q(x):x要参加考试要参加考试,则原命题可写成则原命题可写成:(x)(
7、P(x)Q(x)(c)若设若设Z(x):x是整数是整数,R(x):x是正数是正数,N(x):x是负是负 数数,则则原命题可写成原命题可写成:(x)(Z(x)(R(x)N(x)#8例例.不管黑猫白猫不管黑猫白猫,抓住老鼠就是好猫。抓住老鼠就是好猫。解解:设设C(x):x是猫是猫,B(x):x黑的黑的,W(x):x是白的是白的,G(x):x是是好的好的,M(x):x是是老鼠老鼠,K(x,y):x抓住抓住y,则则原命题可表示为原命题可表示为:(x)(y)(C(x)M(y)(B(x)W(x)K(x,y)G(x).9谓词归结原理基础一阶逻辑n基本概念q个体词：表示主语的词q谓词：刻画个体性质或个体之间关
8、系的词q量词：表示数量的词10谓词归结原理基础一阶逻辑n公式及其解释q个体常量：a,b,cq个体变量：x,y,zq谓词符号：P,Q,Rq量词符号：,11谓词归结原理基础量词否定等值式：q(x）M（x）（y）M（y）q(x）M（x）（y）M（y）量词分配等值式：q(x）(P（x）Q（x）)(x）P（x）(x）Q（x）q(x）(P（x）Q（x）)(x）P（x）(x）Q（x）消去量词等值式：设个体域为有穷集合（a1,a2,an）q(x）P（x）P（a1）P（a2）P（an）q(x）P（x）P（a1）P（a2）P（an）12谓词归结原理基础量词辖域收缩与扩张等值式：q(x）(P（x）Q)(x）P（x）
9、Qq(x）(P（x）Q)(x）P（x）Q q(x）(P（x）Q)(x）P（x）Q q(x）(Q P（x）)Q (x）P（x）q(x）(P（x）Q)(x）P（x）Qq(x）(P（x）Q)(x）P（x）Q q(x）(P（x）Q)(x）P（x）Q q(x）(Q P（x）)Q (x）P（x）13谓词归结子句形(Skolem 标准形)SKOLEM标准形()q前束范式定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。14谓词归结子句形(Skolem 标准形)即：把所有的量词都提到前面去，然后消掉所有量词(Q1x1)(Q2x2)(Qnxn
10、)M(x1,x2,xn)约束变项换名规则：q(Qx）M（x）（Qy）M（y）q(Qx）M（x,z）（Qy）M（y,z）15v字句集的求解：共9步将下列谓词演算公式化为一个子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)开始：(1)消去蕴涵符号 只应用和符号，以AB替换AB。(1)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)16(2)减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3)对变量标准化对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。(2)(x)P(x)(y)P(y)P(f(x,y)(y)
11、Q(x,y)P(y)(3)(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)17(4)消去存在量词 以Skolem函数代替存在量词内的约束变量，然后消去存在量词(5)化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=前缀 母式 全称量词串 无量词公式(4)(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，w=g(x)为一Skolem函数。(5)(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)18(6)把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定
12、的析取的有限集组成的合取。(7)消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。(6)(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(7)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)19(8)消去连词符号 用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。(8)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(9)P(x1)P(y)Pf(x1,y)P
13、(x2)Qx2,g(x2)P(x3)Pg(x3)20谓词归结子句形(Skolem 标准形)q量词消去原则：消去存在量词“”，略去全程量词“”。注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。21谓词归结子句形(Skolem 标准形)qSkolem定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。qSKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。22谓词归结子句形n子句与子句集q文字：不含任何连接词的谓词公式。q子句：一些文字的析取（谓词的和）。q子句集S的求取：G SKOLEM标准
14、形 消去存在变量 以“，”取代“”，并表示为集合形式。23谓词归结子句形n G是不可满足的S是不可满足的qG与与S不等价，但在不可满足的意义下是一致的。不等价，但在不可满足的意义下是一致的。q定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的S是不可满足的。注意：G真不一定S真，而S真必有G真。即：S=G24谓词归结子句形nG=G1 G2 G3 Gn的子句形qG的字句集可以分解成几个单独处理。q有 SG=S1 U S2 U S3 U U Sn则SG 与 S1 U S2 U S3 U U Sn在不可满足得意义上是一致的。即SG 不可满足 S1 U S2 U S3 U U Sn不可满足2
15、5求取子句集例(1)例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：nP(x,y)表示x是y的父亲nQ(x,y)表示x是y的祖父nANS(x)表示问题的解答26求取子句集例(2)对于第一个条件，“如果x是y的父亲，y又是z的父亲，则x是z的祖父”，一阶逻辑表达式如下：A1：(x)(y)(z)(P(x,y)P(y,z)Q(x,z)SA1：P(x,y)P(y,z)Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：A2：(y)(x)P(x,
16、y)SA2：P(f(y),y)对于结论：某个人是它的祖父B：(x)(y)Q(x,y)否定后得到子句：（(x)(y)Q(x,y)）ANS(x)SB：Q(x,y)ANS(x)则得到的相应的子句集为：SA1，SA2，SB27归结原理n也叫消解原理q消解反演（过程）nResolutionprinciplen化为与、或、非来表示28谓词逻辑的归结原理 n在谓词逻辑中，要考虑变量的约束问题，在应用归结法时，要对公式作变量置换和合一等处理，才能得到互补的基本式，以使进行归结。n归结过程：若S中两子句间有相同互补文字的谓词，但它们的项不同，则必须找出对应的不一致项；进行变量置换，使它们的对应项一致;求归结式看
17、能否导出空子句。29归结原理n归结原理正确性的根本在于，找到矛盾可以肯定不真。n方法：q和命题逻辑一样。q但由于有函数和量词，所以要考虑置换和合一。30置换n置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。n定义：置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，x1,x2,xn是互不相同的变量，t1,t2,tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如a/x，c/y，f(b)/z是一个置换。g(y)/x，f(x)/y不是一个置换，31n例如表达式Px,f(y)，B，对应于不
18、同的变换si，可得到不同的例:n 置换置换 置换的例置换的例slsl=z/x,w/y=z/x,w/y，Px,f(y)Px,f(y)，Bs1=Pz,f(w),BBs1=Pz,f(w),Bs2=A/ys2=A/y，Px,f(y)Px,f(y)，Bs2=Px,f(A),BBs2=Px,f(A),Bs3=g(z)/x,A/ys3=g(z)/x,A/y，Px,f(y)Px,f(y)，Bs3=Pg(z),f(A),BBs3=Pg(z),f(A),Bs4=C/x,A/ys4=C/x,A/y，Px,f(y)Px,f(y)，Bs4=PC,f(A),BBs4=PC,f(A),B32n置换 置换的例slsl=z/x
19、,w/y=z/x,w/y，Px,f(y)Px,f(y)，Bs1=Pz,f(w),BBs1=Pz,f(w),Bs2=A/ys2=A/y，Px,f(y)Px,f(y)，Bs2=Px,f(A),BBs2=Px,f(A),Bs3=g(z)/x,A/ys3=g(z)/x,A/y，Px,f(y)Px,f(y)，Bs3=Pg(z),f(A),BBs3=Pg(z),f(A),Bs4=C/x,A/ys4=C/x,A/y，Px,f(y)Px,f(y)，Bs4=PC,f(A),BBs4=PC,f(A),Bn第一个例叫做原始文字的初等变式，实际上置换后只是对变量作了换名。n第四个例称作基例，即置换后项中不再含有变量。
20、n用s=t1/v1,t2/v2,.,tn/vn来表示任一置换，n用s对表达式E作置换后的例简记为Es。33n置换集的元素ti/vi的含义是表达式中的变量vi处以项ti来替换，但不允许vi用与vi有关的项ti(vi)作置换。n对表达式多次置换，如用s1，s2依次进行置换(即(Es1)s2)，可以将这两个置换合成为一个置换(记为 s1 s2)。34n合成置换s1s2是由两部分的置换对组成:n一部分仍是s1的置换对，只是s1的项被s2作了置换;另一部分是s2中与s1变量不同的那些变量对。n如 s1=g(x,y)/z，s2=A/x,B/y,C/w,D/z s1s2=g(A,B)/z,A/x,B/y,C
21、/w 35置换的合成n设t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,un/yn，是两个置换。与的合成也是一个置换，记作。从集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn中删去以下两种元素：q当ti=xi时，删去ti/xi(i=1,2,n);q当yix1,x2,xn时，删去uj/yj(j=1,2,m)最后剩下的元素所构成的集合合成即是对ti先做置换然后再做置换，置换xi36置换的合成n例：设：f(y)/x,z/y，a/x,b/y,y/z，求与的合成。解：先求出集合f(b/y)/x,(y/z)/y,a/x,b/y,y/zf(b)/x,y/y,a/x,b/
22、y,y/z其中，f(b)/x中的f(b)是置换作用于f(y)的结果；y/y中的y是置换作用于z的结果。在该集合中，y/y满足定义中的条件i，需要删除；a/x，b/y满足定义中的条件ii，也需要删除。最后得f(b)/x，y/z37n这样的合成法可使这样的合成法可使(Es1)s2=E(s1s2)(Es1)s2=E(s1s2)，(可结合可结合)n但置换是不可交换的但置换是不可交换的n 即s1s2s2s1 n若存在一个置换若存在一个置换s s使得表达式集使得表达式集 EiEi 中每个中每个元素经置换后的例有元素经置换后的例有:E:E1 1s=Es=E2 2s=Es=E3 3s=s=，则称表达式集则称表
23、达式集 E Ei i 是是可合一可合一的，这个置换的，这个置换s s称作称作 E Ei i 的的合一者合一者。ni2时很简单38合一n合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。n定义：设有公式集FF1，F2，Fn，若存在一个置换，可使F1F2=Fn，则称是F的一个合一。同时称F1，F2，.，Fn是可合一的。n例：设有公式集FP(x,y,f(y),P(a,g(x),z)，则a/x,g(a)/y,f(g(a)/z是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。39n如有子句集P(x，f(y)，B)，P(x，f(B)，B),作置换s=A/x，B/y，得P(A,f(B
24、),B)，该子句集是可合一的。ns并不是最简单的合一者，因为s1=B/y，使子句集合一为Px，f(B)，B。n要求找的是最一般或最普通的合一者(most general unifier)g，记为mgu g。40n任一合一者s与g之间的关系是:存在一个置换s，使得Eis=Eigs。再比较上例的两个合一者，有A/x,B/y=B/yA/x，因此mgu g=B/y。nmgu g的置换限制最少，所产生的例更一般化，有利于归结过程的灵活使用。41n例例:ClCl=P(x,f(A)P(x,f(y)Q(y)=P(x,f(A)P(x,f(y)Q(y)C2=C2=P(z,f(A)P(z,f(A)Q(zQ(z)(1
25、)(1)取取 L L1111=P(x,f(A)=P(x,f(A)，L L2121=P(z=P(z，f(A)f(A)则则s=z/xs=z/x使使L L1111和和L L2121合一，归结式为合一，归结式为 P(zP(z，f(y)Q(y)Q(zf(y)Q(y)Q(z)(2)(2)取取L L1111=P(x,f(y)=P(x,f(y)，L L2121=P(z=P(z，f(A)f(A)则则s=z/xs=z/x，A/yA/y，归结式为归结式为 Q(A)Q(z)Q(A)Q(z)(3)(3)取取L L1111=Q(y)=Q(y)，L L2121=Q(z),=Q(z),则则s=y/zs=y/z，归结式为归结式
26、为 P(xP(x，f(A)P(xf(A)P(x，f(y)P(y,f(Af(y)P(y,f(A)42归结原理n归结的注意事项：1.谓词的一致性，P()与Q()，不可以2.常量的一致性，P(a,)与P(b,.)，不可以 变量，P(a,.)与P(x,)，可以3.变量与函数，P(a,x,.)与P(x,f(x),)，不可以；1.是不能同时消去两个互补对，PQ与PQ的空，不可以2.先进行内部简化（置换、合并）43归结原理n归结的过程写出谓词关系公式 用反演法写出谓词表达式 SKOLEM标准形 子句集S 对S中可归结的子句做归结 归结式仍放入S中，反复归结过程 得到空子句 得证44n例例：已知：（1）会朗读
27、的人是识字的，（2）海豚都不识字，（3）有些海豚是很机灵的。证明：有些很机灵的东西不会朗读有些很机灵的东西不会朗读。n解：把问题用谓词逻辑描述如下，已知：（1）(x)(R(x)L(x)(2)(x)(D(x)L(x)(3)(x)(D(x)I(x)求证:(x(I(x)R(x)45n前前提提化化简简，待待证证结结论论取取反反并并化化成成子子句句形形，求求得得子子句集句集:(1)(1)R(x)L(x)R(x)L(x)(2)(2)D(y)D(y)L(y)L(y)(3a)D(A)(3a)D(A)(3b)I(A)(3b)I(A)(4)(4)I(z)R(z)I(z)R(z)n一个可行的证明过程:(5)R(A)
28、(3b)和(4)的归结式 (6)L(A)(5)和(1)的归结式 (7)D(A)(6)和(2)的归结式 (8)NIL (7)和(3a)的归结式46例题“快乐学生”问题n假假设设任任何何通通过过计计算算机机考考试试并并获获奖奖的的人人都都是是快快乐乐的的，任任何何肯肯学学习习或或幸幸运运的的人人都都可可以以通通过过所所有有的的考考试试，张张不不肯肯学学习习但但他他是是幸幸运运的的，任任何幸运的人都能获奖。求证：张是快乐的。何幸运的人都能获奖。求证：张是快乐的。n解：先将问题用谓词表示如下：解：先将问题用谓词表示如下：nR1:“任何通过计算机考试并获奖的人都是快乐的任何通过计算机考试并获奖的人都是快
29、乐的”(x)(Pass(x,computer)Win(x,prize)Happy(x)nR2:“任何肯学习或幸运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试”(x)(y)(Study(x)Lucky(x)Pass(x,y)nR3:“张不肯学习但他是幸运的张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)nR4:“任何幸运的人都能获奖任何幸运的人都能获奖”(x)(Luck(x)Win(x,prize)n结论：结论：“张是快乐的张是快乐的”的否定的否定Happy(zhang)47例题“快乐学生”问题n由R1及逻辑转换公式:PWH=（PW）H，可得n(1)Pas
30、s(x,computer)Win(x,prize)Happy(x)n由R2：(2)Study(y)Pass(y,z)n(3)Lucky(u)Pass(u,v)n由R3：(4)Study(zhang)n(5)Lucky(zhang)n由R4：(6)Lucky(w)Win(w，prize)n由结论：(7)Happy(zhang)（结论的否定）n(8)Pass(w,computer)Happy(w)Luck(w)(1)(6)，w/xn(9)Pass(zhang,computer)Lucky(zhang)(8)(7)，zhang/wn(10)Pass(zhang,computer)(9)(5)n(11
31、)Lucky(zhang)(10)(3)，zhang/u,computer/vn(12)(11)(5)48归结原理n归结法的实质：q归结法是仅有一条推理规则的推理方法。q归结的过程是一个语义树倒塌的过程。n归结法的问题q子句中有等号或不等号时，完备性不成立。Herbrand定理的不实用性引出了可实用的归结法。49归结反演(Refutation)n归结反演系统是用反演(反驳)或矛盾的证明法，使用归结推理规则建立的定理证明系统。n这种证明系统是基于归结的反证法，故称归结反演系统。n可用在信息检索、常识性推理和自动程序设计等。50l归结反演的基本算法 n综合数据库:子句集n规则集合:IF IF cx
32、(Sicx(Si)和和cy(Sicy(Si)有有归归结结式式r rxyxy THEN S THEN S i+1i+1=SirSirxyxy 目标条件:SnSn中出现空子句中出现空子句51n归结过程用归结反演树表示比较简单。n搜索策略的目标就是要找到一棵归结反演树。n一个反演系统当存在一个矛盾时，如果使用的一种策略，最终都将找到一棵反演树，则这种策略是完备的。归结反演树归结反演树nS=S=I(z)R(zI(z)R(z)，I(A)I(A)，R(x)L(xR(x)L(x)，n D(y)D(y)L(yL(y)，D(A)D(A)52n提高策略效率只归结含有互补对的文字；及时删去出现的重言式和被其他子句所
33、包含的子句;每次归结都取与目标公式否定式有关的子句作为母子句之一进行归结等等。(1)宽度优先策略宽度优先策略（完备，效率低）宽度优先策略首先归结出基本集S中可能生成的所有归结式，称第一级归结式，然后生成第二级归结式等等，直到出现空子句。53(2)支持集策略（完备）n归结时，其母子句中至少有一个是与目标公式否定式有关的子句。54(3)单元子句优先策略n每次归结时优先选取单文字的子句(称单元子句)为母子句进行归结，n显然归结式的文字数会比其他情况归结的结果要少，这有利于向空子句的方向搜索，实际上会提高效率。55(4)线性输入形策略n每每次次归归结结时时，至至少少有有一一个个母母子子句句是是从从基基本本集集中中挑挑选。选。n该该策策略略可可限限制制生生成成归归结结式式的的数数目目，具具有有简简单单和和效效率高的优点。率高的优点。56n它不是一个完备的策略，它不是一个完备的策略，n反例：反例：nS=S=Q(u)P(AQ(u)P(A)，Q(w)P(wQ(w)P(w)，Q(x)P(xQ(x)P(x)，Q(y)P(yQ(y)P(y)，n从从S S出发很容易找到一棵反演树，但不出发很容易找到一棵反演树，但不存在一个线性输入形策略的反演树。存在一个线性输入形策略的反演树。57n（5）祖先过滤策略 n（完备）祖先过滤策略的搜索过程 58