第四章 确定性推理方法精选PPT.ppt

《第四章 确定性推理方法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章 确定性推理方法精选PPT.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 确定性推理方法第1页，此课件共71页哦单调推理、非单调推理n按照推理过程中推出的结论是否越来越接近最终目标来划分，推理又分为单调推理和非单调推理。n单调推理是在推理过程中随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。n非单调推理是在推理过程中有新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的一步，然后重新开始。（知识不完全情况下发生。）X是鸟，会飞，X是企鹅，不会飞。第2页，此课件共71页哦命题逻辑n命题：能判断真假的陈述句为命题。n命题公式：单个常量或变量的命题称作合式公式。合式公式有限次组合所构成的字符串称为命题公式。n命题逻辑的基本联接词有

2、：，等价，当且仅当，双条件第3页，此课件共71页哦命题公式的解释：设A为一个命题公式，P1 P2 P3,Pn 是出现在A中的全部命题变量，给P1 P2 P3,Pn各指定一个真值（0或1），称为对A的一个赋值或解释。第4页，此课件共71页哦公式的分类n永真式：若A无成假赋值，则称A为重言式。或永真式。n永假式n可满足式：若A至少有一个成真赋值，则称A为可满足式。n非重言式的可满足式：若A至少有一个成真赋值，又至少有一个成假赋值，则称A为非重言式的可满足式。第5页，此课件共71页哦范式（公式的标准型式）n简单合取式：仅由有限个命题变量或其否定构成的合取式成为简单合取式。n简单析取式：仅由有限个命题

3、变量或其否定构成的析取式称为简单析取式。n合取范式：仅由有限个简单析取式构成的合取式称为合取范式。P(PQ)(P Q)n析取范式：仅由有限个简单合取式构成的析取式称为析取范式。P(PQ)(PQ)n析取范式是矛盾式，每个简单合取式都是矛盾式。n合取范式是重言式，每个简单析取式都是重言式。第6页，此课件共71页哦谓词逻辑n是一种形式语言，具有严密的理论体系n是一种常用的知识表示方法n例：nCity（北京）nCity（上海）nAge（张三，23）n(x)(y)(z)(F(x,y)F(y,z)GF(x,z)第7页，此课件共71页哦谓词逻辑n原子谓词公式：是一个不能再分解的命题。n原子谓词公式及其否定，

4、统称为文字。P与P为互补文字。n任何文字的析取称为子句。n由子句构成的集合成为子句集。n不包含任何文字的子句称为空子句，表示为NIL。n由于空子句不包含任何文字，不能被任何解释满足，所以，空子句是永假的，不可满足的。第8页，此课件共71页哦4.1 归结原理n归结原理是一种定理证明方法，1965年由Robinson提出，从理论上解决了定理证明问题。n子句集n无量词约束n元素只是文字的析取n否定符只作用于单个文字n元素间默认为和取n例：I(z)R(z),I(A),R(x)L(x),D(y)第9页，此课件共71页哦谓词公式化子句集的方法例：(z)(x)(y)(P(x)Q(x)R(y)U(z)1,消蕴

5、涵符理论根据：a b=a b p Q=(P Q)(P Q)(z)(x)(y)(P(x)Q(x)R(y)U(z)2,移动否定符（把否定符移动到紧靠谓词的位置上）理论根据：(a b)=a b (a b)=a b(x)P(x)=(x)P(x)(x)P(x)=(x)P(x)(z)(x)(y)(P(x)Q(x)R(y)U(z)第10页，此课件共71页哦化子句集的方法（续1）3,变量标准化即：对于不同的约束，对应于不同的变量(x)A(x)(x)B(x)=(x)A(x)(y)B(y)4,量词左移(x)A(x)(y)B(y)=(x)(y)A(x)B(y)5,消存在量词(skolem化）原则：对于一个受存在量词

6、约束的变量，如果他不受全程量词约束，则该变量用一个常量代替，如果他受全程量词约束，则该变量用一个函数代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x)R(f(x)U(a)第11页，此课件共71页哦化子句集的方法（续2）6,化为合取范式即(ab)(cd)(ef)的形式 (x)(P(x)Q(x)R(f(x)U(a)=(x)(P(x)Q(x)R(f(x)U(a)=(x)P(x)R(f(x)U(a)Q(x)R(f(x)U(a)7,隐去全程量词 P(x)R(f(x)U(a)Q(x)R(f(x)U(a)第12页，此课件共71页哦化子句集的方法（续3）8,表示为子句集 P(

7、x)R(f(x)U(a),Q(x)R(f(x)U(a)9,变量标准化（变量换名）P(x1)R(f(x1)U(a),Q(x2)R(f(x2)U(a)第13页，此课件共71页哦化下列公式成子句形式：（1）(x)P（x）P（x）（2）(x)P（x）(x)P（x）第14页，此课件共71页哦化下列逻辑表达式为合取范式 化下列逻辑表达式为合取范式:第15页，此课件共71页哦第16页，此课件共71页哦定理：若S是合式公式F的子句集，则F永假的充要条件是S不可满足。S不可满足：若nilS，则S不可满足。证明的思路：目标的否定连同已知条件一起，化为子句集，并给出一种变换的方法，使得S S1 S2.Sn，同时保证

8、当Sn不可满足时，有S不可满足。第17页，此课件共71页哦4.2 归结方法（命题逻辑）n设子句：C1=LC1C2=(L)C2则归结式C为：C=C1 C2n定理：子句集S=C1,C2,Cn与子句集S1=C,C1,C2,Cn的不可满足性是等价的。其中，C是C1和C2的归结式。第18页，此课件共71页哦证明归结式C是C1和C2的逻辑结论 即C1 C2 C(1)也就是要证明使C1和C2为真的解释I，也必然可以使C为真。C1=LC1 ，C2=(L)C2(2)设I是使C1和C2为真的任一解释，若I下的L为真，从而L为假。由C2为真的假设可以推出必有在I下的C2为真，故在I下，由于C=C1 C2，所以C也为

9、真。若在解释I下L为假，从而由于假设C1为真，必有C1为真，故在解释I下C=C1 C2也必为真。(3)归结式C是其亲本子句C1和C2的逻辑结论。第19页，此课件共71页哦推论：设C1和C2是子句集S上的子句，C是C1和C2的归结式。如果把C加入子句集S后得到新子句集S1，则S1和S在不可满足的意义下是等价的。S是不可满足的等价于S1是不可满足的第20页，此课件共71页哦归结推理过程：证明子句集S的不可满足性过程：（1）对子句集S中的各子句间使用归结推理规则。（2）将归结所得到的归结式放入子句集S中，得到新子句集S。（3）检查子句集S中是否有空子句(NIL)，若有，则停止推理，否则，转步骤（4）

10、（4）置S=S，转步骤（1）。第21页，此课件共71页哦归结的例子设公理集：P,(PQ)R,(ST)Q,T求证：R子句集：(1)P(2)PQR(3)SQ(4)TQ(5)T(6)R（目标求反）化子句集：(PQ)R=(PQ)R=PQR(ST)Q=(ST)Q=(ST)Q=(SQ)(TQ)=SQ,TQ第22页，此课件共71页哦子句集：(1)P(2)PQR(3)SQ(4)TQ(5)T(6)R（目标求反）归结：(7)PQ (2,6)(8)Q (1,7)(9)T (4,8)(10)nil (5,9)第23页，此课件共71页哦证明子句集S=PQ,Q,P不可满足第24页，此课件共71页哦4.3 谓词逻辑的归结原

11、理n问题：如何找归结对例：P(x)Q(y),P(f(y)R(y)P(A)Q(y),P(f(y)R(y)n基本概念n置换s=t1/v1,t2/v2,tn/vn(ti项，Vi是变量)对公式E实施置换s后得到的公式称为E的例，记作Es。例：s1=z/x,A/y,则：Px,f(y),Bs=Pz,f(A),B第25页，此课件共71页哦n合一如果存在一个S置换，使得Ei中 E1s=E2s=E3s=Ens，则称Ei是可合一的。S为Ei的合一者。例：P(x,f(y),B),P(z,f(B),B)置换s=A/x,B/y,A/z是一个合一者,因为：P(x,f(y),B)s=P(A,f(B),B)P(z,f(B),

12、B)s=P(A,f(B),B)置换s=z/x,B/y和置换s=x/z,B/y也都是合一者。结论：合一者不唯一。第26页，此课件共71页哦n最一般合一者（mgu）置换最少，限制最少，产生的例最具一般性。如前面的例子：P(x,f(y),B),P(z,f(B),B)对于置换A/x,B/y,A/z，产生的例是：P(A,f(B),B)对于置换=z/x,B/y，产生的例是：P(z,f(B),B)nmgu也不是唯一的。第27页，此课件共71页哦合一算法例：P(x,x,Z),P(f(y),f(B),y)前缀表示：(P x x z)(P(f y)(f B)y)置换：(f y)/x(P(f y)(f y)z)(P

13、(f y)(f B)y)置换：B/y,并使得(f B)/x(P(f B)(f B)z)(P(f B)(f B)B)置换：B/z得到置换：(f B)/x，B/y，B/z置换后的结果：(P(f B)(f B)B)第28页，此课件共71页哦谓词逻辑的归结方法对于子句C1L1和C2L2，如果L1与L2可合一，且s是其合一者，则(C1C2)s是其归结式。例：P(x)Q(y),P(f(z)R(z)=Q(y)R(z)第29页，此课件共71页哦归结举例设公理集：(x)(R(x)L(x)(x)(D(x)L(x)(x)(D(x)I(x)求证：(x)(I(x)R(x)化子句集：(x)(R(x)L(x)=(x)(R(

14、x)L(x)=R(x)L(x)(1)第30页，此课件共71页哦(x)(D(x)L(x)=(x)(D(x)L(x)=D(x)L(x)(2)(x)(D(x)I(x)=D(A)I(A)=D(A)(3)I(A)(4)第31页，此课件共71页哦n目标求反：(x)(I(x)R(x)=(x)(I(x)R(x)=(x)(I(x)R(x)=I(x)R(x)(5)换名后得字句集：R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5)第32页，此课件共71页哦例题得归结树R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5)I(A)I(x5)R(x5)R(A)A/x5R(

15、x1)L(x1)L(A)A/x1D(x2)L(x2)D(A)A/x2D(A)nil第33页，此课件共71页哦 归结方法的特点是简单，易于程序实现。其不足是效率低，不直观，人难于理解其证明过程。第34页，此课件共71页哦1、在命题逻辑下，可以归结的子句C1和C2，在某种模型下C1和C2为真。则其归结式C在该模型下（）A.必真 B.必假 C.真假不能断言 第35页，此课件共71页哦2、归结证明定理时，若当前归结式是（）,则可删除。A.永假式 B.重言式 C.空子句 D.可满足式第36页，此课件共71页哦3、什么是置换？g(y)/z,f(z)/y是一个置换么？置换是形如t1/x1,t1/x2,tn/

16、xn的一个有限集。其中，xi是变量，ti是不同于xi的项（常量、变量、函数），且xixj（ij），i,j=1,2,n。g(y)/z,f(z)/y不是一个置换，原因是它在x和y之间出现了循环置换现象。第37页，此课件共71页哦应用归结原理进行问题求解（1）把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S1。（2）把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词ANSWER构成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致。（3）把问题公式与谓词ANSWER构成的析取式化为子句集，并把该子句集与S1合并构成子句集S。

17、（4）对子句集S应用谓词归结原理进行归结，在归结的过程中，通过合一置换，改变ANSWER中的变元。（5）如果得到归结式ANSWER，问题的答案即在ANSWER中第38页，此课件共71页哦例题:某单位招聘工作人员，张三、李四、王五三人应试，经面试后单位有如下的想法：（1）如果录取张三而不录取李四，则一定录取王五。（2）如果录取李四，则一定录取王五。（3）三人中至少要录取一个人。求证：王五一定会被单位录取。（提示）定义谓词和常量：谓词Matr(x)表示x被录取。Z表示张三，L表示李四，W表示王五。第39页，此课件共71页哦第40页，此课件共71页哦例题:任何兄弟都有同一个父亲，John和Peter

18、是兄弟，且John的父亲是David，问Peter的父亲是谁？第一步：将已知条件用谓词表示出来，并化成字句集。那么，要先定义谓词。（1）定义谓词：设Father(x,y)表示x是y的父亲。设Brother(x,y)表示x和y是兄弟。第41页，此课件共71页哦（2）将已知事实用谓词公式表示出来：F1:任何兄弟都有同一个父亲。第42页，此课件共71页哦第43页，此课件共71页哦归结控制策略n盲目归结策略，产生了大量的无用的归结式。n研究以少量的归结尽快导出空子句。第44页，此课件共71页哦归结的一般策略S=C1,C2,C3,C4(1)C1开始，逐个和C2,C3,C4比较，看哪两个子句可以进行归结。

19、C2与C3,C4进行比较，C3与C4比较。得到一组归结式，称为第一级归结式。(2)再从C1开始，用S中的子句分别与第一级归结式中的子句逐个进行比较、归结，得到第二级归结式。(3)仍然从C1开始，用S中的子句及第一级归结式中的子句逐个地与第二级归结式中的子句逐个进行比较，得到第三级归结式。如此继续下去，知道出现了空子句或者不能再继续归结时为止。只要子句集是不可满足的，上述归结过程一定会归结出空子句而终止。第45页，此课件共71页哦S=P,R,PQ,Q RS:(1)P (2)R(3)PQ(4)Q R(5)Q (1)(3)归结(6)Q (2)(4)归结 第一级归结式(7)P R (3)(4)归结(8

20、)R (1)(7)归结(9)P (2)(7)归结 第二级归结式(10)P (3)(6)归结 (11)R (4)(5)归结(13)NIL (1)(9)归结 第三级归结式第46页，此课件共71页哦控制策略的分类n删除策略n限制策略第47页，此课件共71页哦删除策略n删除某些无用的子句来缩小归结的范围，从而提高归结效率。n包括：纯文字删除法、重言式删除法、包孕删除法。第48页，此课件共71页哦限制策略n主要是对参加归结的子句进行种种限制，尽可能地减小归结的盲目性。以使其尽快归结出空子句。n控制策略包括：线性归结策略、单文字归结策略、输入归结策略、支撑集策略等。第49页，此课件共71页哦删除策略之纯文

21、字删除法 如果某文字L在子句集中不存在可与之互补的文字 L，则称该文字为纯文字。纯文字不可能被消去，因而用包含它的子句进行归结时不可能得到空子句。这样的子句对归结是无意义的，所以可以把它所在的子句从子句集中删去。S=PQ R,Q R,Q,RP是纯文字，可将子句PQ R从R中删除。第50页，此课件共71页哦删除策略之重言式删除法n P(X)P(X),P(X)Q(X)P(X)都是重言式。重言式是真值为真的子句。不管P(X)为真还是为假，P(X)P(X)和 P(X)Q(X)P(X)结果都为真。n对于一个子句集来说，不管是增加或者删去一个真值为真的子句都不会影响它的不可满足性。第51页，此课件共71页

22、哦删除策略之包孕删除法如果子句C1和C2，如果存在一个代换S,使得C1s包含于C2中，则称C1包孕于C2。P(x)包孕于P(y)Q(z)s=y/xP(x)包孕于P(a)s=a/xP(x)包孕于P(a)Q(z)s=a/xP(x)Q(a)包孕于P(f(a)Q(a)R(y)s=f(a)/xP(x)Q(y)包孕于P(a)Q(u)R(w)s=a/x,u/y把子句集中包孕的子句删去后，不会影响子句集的不可满足性，因而可以从子句集中删去。第52页，此课件共71页哦支持集策略n支撑集：设有不可满足子句集S的子集T，如果S-T是可满足的，则称T是S的支撑集。n采用支撑集策略时，选取不同时属于S-T的子句对，在其

23、间进行归结。至少有一个子句来自于支撑集T或者由T导出的归结式。n参加归结的子句有一个是目标公式的否定所得到的子句或者他们的后裔。n思想：尽量避免在可满足的子句集中进行归结。第53页，此课件共71页哦S=P Q,P R,QR,R取T=R支撑集归结过程通常为：(1)P Q(2)P R(3)QR(4)R(5)P (2)(4)(6)Q (3)(4)(7)Q (1)(5)(8)P (1)(6)(9)R (3)(7)(10)Nil (4)(9)第54页，此课件共71页哦线性归结策略n线性归结策略首先从子句集中选取一个称作顶子句的C0开始进行归结。归结过程中所得到地归结式Ci立即同另一子句Bi进行归结，得归

24、结式Ci+1，而Bi属于S或者已经出现得归结式Cj(ji)。n简而言之，每次归结得到的新子句立即参加归结，而后再加入子句集等待再次参加归结。第55页，此课件共71页哦C0B0B1BnC1C2空较好的顶子句,就可以使归结顺利进行.第56页，此课件共71页哦输入归结策略n对参加归结的子句提出了如下限制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。n初始子句集就是由已知前提及结论的否定化来的子句。n可以避免归结出不必要的新子句加入归结而造成恶性循环，可以减少不必要地归结次数。n原始子句集中没有单元子句一定不能采用输入归结策略。第57页，此课件共71页哦(1)I(x)R(x)(2)I(a)

25、(3)R(y)L(y)(4)L(a)(5)R(a)(1)(2)(6)I(x)L(x)(1)(3)(7)R(a)(3)(4)(8)I(a)(1)(7)(9)L(a)(2)(6)(10)L(a)(3)(5)(11)I(a)(4)(6)(12)NIL (2)(8)第58页，此课件共71页哦I(x)R(x)I(a)R(y)L(y)L(a)R(a)I(x)L(x)R(a)I(a)L(a)L(a)I(a)NIL第59页，此课件共71页哦n输入归结策略可限制生成归结式的数量，具有简单、高效的优点。n例如：S=P(x)Q(x),P(y)Q(y),P(u)Q(u),P(t)Q(t)n它是不可满足的，用输入归结策

26、略却归结不出空子句。第60页，此课件共71页哦单文字子句策略n如果一个子句只包含一个文字，则称它为单文字子句。n单文字子句策略要求参加归结的两个子句中必须有一个单文字子句。第61页，此课件共71页哦S:(1)I(x)R(x)(2)I(a)(3)R(y)L(y)(4)L(a)S1:(5)R(a)(1)(2)(6)R(a)(3)(4)S2:(7)I(a)(1)(6)(8)L(a)(3)(5)S3:NIL (2)(7)第62页，此课件共71页哦祖先过滤策略该策略与线性输入策略比较相似，但放宽了限制。当两个子句C1和C2进行归结时，只要它们满足下述两个条件中的任意一个就可以进行归结：（1）C1与C2中

27、至少有一个是初始子句集中的子句。（2）如果两个子句都不是初始子句集中的子句，则一个应是另一个祖先（C2是由C1与别的子句归结后得到的归结式，C1是C2的祖先）第63页，此课件共71页哦归结演绎推理归结演绎推理比较简单又便于在计算机上实现。但是由于把逻辑公式化成子句集，带来如下问题：（1）不便于阅读与理解。(x)(Bird(x)Canfly(x)Bird(x)Canfly(x)第64页，此课件共71页哦（2）有可能丢失一些重要的控制信息(A B)C(A C)B(B C)A A(BC)B(AC)C(AB)具有不同的逻辑控制信息，却得到相同的子句。第65页，此课件共71页哦对子句集S=P(x)Q(x

28、),P(x)R(x),Q(x)R(x),R(x)使用单文字归结策略对其进行归结推理。第66页，此课件共71页哦解：单文字归结过程如下：(1)P(x)Q(x)(2)P(x)VR(x)(3)Q(x)VR(x)(4)R(x)(5)P(x)(4)与(2)归结(6)Q(x)(4)与(3)归结(7)Q(x)(5)与(1)归结(8)P(x)(6)与(1)归结(9)R(x)(7)与(3)归结(10)NIL(7)与(6)归结 第67页，此课件共71页哦对子句集S=I(x)R(x),I(a),R(y)L(y),L(a),用输入归结策略对其进行归结。第68页，此课件共71页哦解：归结过程如下，每次归结至少有一个子句

29、是初始集合S中的子句。S:(1)I(x)R(x)(2)I(a)(3)R(y)V L(y)(4)L(a)S1:(5)R(a)(1)与(2)归结=a/x (6)I(x)VL(x)(1)与(3)归结=x/y (7)R(a)(3)与(4)归结=a/yS2:(8)I(a)(1)与(7)归结=a/x (9)L(a)(2)与(6)归结=a/x (10)L(a)(3)与(5)归结=a/y (11)I(a)(4)与(6)归结=a/xS3:(12)NIL (2)与(8)归结 第69页，此课件共71页哦对子句集S=P(x)R(x),P(a),R(y)Q(y),Q(a),其中，假设 P(x)R(x)是目标公式否定得到的子句，请用支持集策略对其进行归结。第70页，此课件共71页哦解：用支持集策略进行归结的过程如下：S:(1)R(y)Q(y)(2)P(a)(3)Q(a)(4)P(x)R(x)(5)R(a)(2)与(4)归结=a/x (6)P(y)VQ(y)(1)与(4)归结=y/x (7)Q(a)(2)与(6)归结=a/y (8)Q(a)(1)与(5)归结=a/y (9)P(a)(2)与(6)归结=a/x (10)NIL (2)与(9)归结=a/x第71页，此课件共71页哦