人工智能第三章PPT讲稿.ppt

《人工智能第三章PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《人工智能第三章PPT讲稿.ppt（80页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、人工智能第三章第1页，共80页，编辑于2022年，星期四3.1.1命题l命题：命题：能判断真假（不是既真又假）的陈述句。简单陈述句描述事实、事物的状态、关系等性质。例如：11+1=2l2雪是黑色的。l3北京是中国的首都。l4到冥王星去渡假。命题通常用字母p,q,a,b表示；判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第4句的真值现在是假，随着人类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以上4个例子都是命题。而例如：1快点走吧！2到那去？3x+y10等等句子，都不是命题。第2页，共80页，编辑于2022年，星期四3.1.2命题逻

2、辑公式定义：原子命题：不能再分解的命题称为原子命题。合式公式：原子命题是合式公式，连接词联结的合式公式的组合也是合式公式（命题公式）。常用的联结词：合取式：p与q，记做p q析取式：p或q，记做p q蕴含式：如果p则q，记做p q等价式：p当且仅当q，记做p q否定：p、最优先，其次为、，再次为，第3页，共80页，编辑于2022年，星期四命题表示公式（1）将陈述句转化成命题公式。如：设“下雨”为p，“骑车上班”为q，1“只要不下雨，我骑自行车上班”。p是q的充分条件，因而，可得命题公式：pq2“只有不下雨，我才骑自行车上班”。p是q的必要条件，因而，可得命题公式：qp 第4页，共80页，编辑于

3、2022年，星期四命题表示公式（2）事件化为命题公式的步骤：（）分析简单命题，将其符号化；（）使用适当的联结词把简单命题连接起来。例如：l1“如果我进城我就去看你，除非我很累。”设：p，我进城，q，去看你，r，我很累。则有命题公式：r(pq)。l2“应届高中生，得过数学或物理竞赛的一等奖，保送上北京大学。”设：p，应届高中生，q，保送上北京大学上学，r，是得过数学一等奖。t，是得过物理一等奖。则有命题公式公式：p(r t)q。第5页，共80页，编辑于2022年，星期四命题公式的解释定义：设为一个命题公式，p1,p2,pn是出现在中的全部原子命题，给原子命题各指定一个真值（或者），称为对的一个赋

4、值或解释。若的值为真，则称为成真赋值。若的值为假，则称为成假赋值。第6页，共80页，编辑于2022年，星期四公式逻辑真值表第7页，共80页，编辑于2022年，星期四命题逻辑基础l基本等值式交换率：pq qp；p q q p 结合率：(pq)r p(q r);(p q)r p(q r)分配率：p(q r)(pq)(p r)；p(q r)(p q)(p r)双重否定率：p p 等幂率：p pp，p p p 等价等值式：p q(p q)(q p)等价否定式：p q p q第8页，共80页，编辑于2022年，星期四命题逻辑基础l摩根率:(pq)p q；(p q)p q 吸收率:p(pq)p；p(pq)

5、p同一律:p0 p；p1 p蕴含等值式:p q pq假言易位式:p q p q归谬式:(p q)(p q)p 排中律：pp；矛盾律：pp 零率：p；p 第9页，共80页，编辑于2022年，星期四范式：公式的标准型式。定义：设A为一个公式若A无成假赋值，则称A为重言式或永真式；若A无成真赋值，则称A为矛盾式或永假式；若A至少有一个成真赋值，则称A为可满足的；简单合取式：有限个原子命题或其否定构成合取式。简单析取式：有限个原子命题或其否定构成析取式。析取范式：仅由有限个简单合取式组成的析取式。合取范式：仅由有限个简单析取式组成的合取式。范式的性质：析取范式是矛盾式，当且仅当每个简单合取式是矛盾式。

6、合取范式是永真式，当且仅当每个简单析取式是永真式。第10页，共80页，编辑于2022年，星期四范式的转化存在定理：任何命题公式都存在着与之等值的析取范式和合取范式。求合取范式的步骤：（）消去多余的，以及联结词（）去掉否定符号（）利用分配率例：3.1,3.23.1.3命题逻辑的意义把自然语言转化为形式语言，以利于计算机能够处理。第11页，共80页，编辑于2022年，星期四例3.2：求的（）合取范式解：（）（）（）（）（）（）（）（）第12页，共80页，编辑于2022年，星期四3.1.4命题逻辑的推理规则（自然演绎推理）逻辑结论：对于，如果永真，则称是的逻辑结论，即推出的结论正确，为真则为真，记为

7、=。常用的推理定律（永真式）：，附加：=（）简化：（）=假言推理：（）=拒取式：（）=析取三段论：（）=假言三段论：（）（）=（）等价三段论：（）（）=（）构造性二难：（）（）（）=（）第13页，共80页，编辑于2022年，星期四常用的推理规则：（）前提引入规则（）结论引入规则（）置换规则：等价的可以置换例.4：证明：如果今天是下雨天，则要带伞或带雨衣。如果走路上班，则不带雨衣。今天下雨，走路上班，所以带雨伞。解：把题目用命题公式表示：今天下雨p，带伞q，带雨衣r，走路上班s前提：p（qr），sr，p，s要证的结论：q证明：p（qr）p前提引入（qr）假言推理ssr前提引入 r假言推理 q析取

8、三段论第14页，共80页，编辑于2022年，星期四3.1.5命题逻辑的归结法l归谬法：命题：A1、A2、A3 和 B求证：A1A2A3成立，则B成立，即：A1A2A3 B为永真 A1A2A3 B 等价于(A1A2A3)B 等价于(A1A2A3)B)等价于(A1A2A3)B)永真 即证明(A1A2A3)B)永假反证法：证明A1A2A3B 是矛盾式 （永假式）第15页，共80页，编辑于2022年，星期四例：前提：p（rs）q)，p，s要证的结论：q证明：p（rs）q)p前提引入（rs）q假言推理q引入否定结论（rs）拒取式 s前提引入 s简化 ss合取 永假矛盾。第16页，共80页，编辑于2022

9、年，星期四l归结原理由J.A.Robinson由1965年提出。与演绎法(deductiveinference)完全不同，新的逻辑演算(inductiveinference)算法。一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）第17页，共80页，编辑于2022年，星期四命题逻辑的归结法l子句集子句：子句是文字的集合，各个文字之间被析取分隔。文字：原子命题或否定被称为文

10、字。合取范式：命题、命题或的与，如：P（PQ）（PQ）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：P（PQ）（PQ）子句集 S：S=P,PQ,PQ 第18页，共80页，编辑于2022年，星期四l归结式设C1,C2是子句集中的两个子句，如果C1中的文字L1与C2中文字L2互补，则可以从C1和 C2中分别消去文字L1和文字L2，并将中余下的部分按析取关系构成一个新子句C12，这个过程就叫归结。如子句：C1=PQ,C2=PW，归结式：C12=WQ 性质：归结式 C12 是亲本子句C1和 C2逻辑结论。C1C2 C12，注意：反之不一定成立。第19页，共80页，编辑于2022年，星期四

11、命题逻辑的归结法l归结过程将命题写成合取范式求出子句集对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句，S是不可满足的（矛盾），原命题成立。（证明完毕）l谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。第20页，共80页，编辑于2022年，星期四命题逻辑归结例题（1）l例题，已知：(PQ)l求证：(QP)l证明：（1）根据归结原理，将待证明公式转化成待归结命题公式：(PQ)(QP)（2）分别将公式前项化为合取范式：PQPQ结论求后的后项化为合取范式：(QP)(QP)QP两项合并后化为合取范式：（PQ）QP（3）则子句集为：PQ，Q，P第21页，共80页，编辑于2022年

12、，星期四命题逻辑归结例题（2）子句集为：PQ，Q，P（4）对子句集中的子句进行归结可得：l1.PQl2.Ql3.Pl4.Q，（1，3归结）l5.，（2，4归结）由上可得原公式成立。第22页，共80页，编辑于2022年，星期四3.2谓词归结原理基础一阶逻辑l3.2.1基本概念个体词：表示主语的词(客体、具体事物或抽象的概念）谓词：刻画个体性质或个体之间关系的词量词：表示数量的词第23页，共80页，编辑于2022年，星期四谓词归结原理基础l小王是个工程师。l8是个自然数。l我去买花。l小丽和小华是朋友。其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师

13、”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。第24页，共80页，编辑于2022年，星期四谓词归结原理基础个体常量：a,b,c个体变量：x,y,z谓词符号：P,Q,R谓词：由谓词符号和个体（项）组成。例P(x,y)一阶谓词：谓词中不含有谓词。n元谓词：就是有n个项。量词符号：,第25页，共80页，编辑于2022年，星期四l例如：（1）所有的人都是要死的。l（2）有的人活到一百岁以上。在个体域D为人类集合时，可符号化为：（1）xP(x)，其中P(x

14、)表示x是要死的。（2）x Q(x),其中Q(x)表示x活到一百岁以上。在个体域D是全总个体域时，引入特殊谓词R(x)表示x是人，可符号化为：（1）x（R(x)P(x)）,其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)Q(x)），其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。第26页，共80页，编辑于2022年，星期四3.2.2一阶谓词逻辑1谓词公式原子公式：单个谓词就是原子公式。谓词公式：简单说就是由原子公式、连接词、否定符号以及量词构成的式子。指导变量：量词后面的变量称为指导变量。x、y辖域：就是量词管辖的区域。约束出现：在辖域内，受量词约束的变量是约束出现

15、。自由出现：在辖域内，不受量词约束的变量是约束出现。换名规则：将量词辖域中某个约束出现的个体变量改成在此辖域中未出现过的个体变量符号。xP(x,y)R(x,y)第27页，共80页，编辑于2022年，星期四替换规则：对某个自由变量用与原公式中所有个体变量符号不同的变量去替代，且处处替代。xP(x,y)R(x,y)替换xP(x,z)R(x,z)2.谓词公式的解释 对谓词公式的各变量常量去替代，就构成了一个谓词公式的解释。当存在解释能使谓词公式为真时，则称这个解释满足谓词公式。这个解释就是这个谓词公式的模型。两个谓词公式等价，当且仅当所有的解释下两个谓词公式的值是相同的。永真式 不可满足式 归结原理

16、就是对谓词公式的正确性证明转化为不可满足性证明。第28页，共80页，编辑于2022年，星期四3.2.3谓词演算与推理1.谓词演算公式量词否定等值式：(x）M（x）（y）M（y）(x）M（x）（y）M（y）量词分配等值式：(x）(P（x）Q（x）)(x）P（x）(x）Q（x）(x）(P（x）Q（x）)(x）P（x）(x）Q（x）消去量词等值式：设个体域为有穷集合（a1,a2,an）(x）P（x）P（a1）P（a2）P（an）(x）P（x）P（a1）P（a2）P（an）第29页，共80页，编辑于2022年，星期四约束变量换名规则：(Qx)P(x)(Qy)P(y)(Qx)P(x,z)(Qy)P(y,

17、z)量词辖域收缩与扩张等值式：(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(Q P（x）)Q (x）P（x）(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(Q P（x）)Q (x）P（x）第30页，共80页，编辑于2022年，星期四前束范式定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。第31页，共80页，编辑于2022年，星期四即：把所有的量词都提到前面去，然后消掉所有量词(Q1x1)

18、(Q2x2)(Qnxn)M(x1,x2,xn)例第32页，共80页，编辑于2022年，星期四谓词推理要运用与命题逻辑相同的推理规则和量词的消去和引入。任意量词可以消去，用变量或常量表示，存在量词可以用常量表示。对于任意量词，为自由变量，为不在中约束出现的个体变量时：（）=（）为常量（）=（）对于存在量词，（）=（）对于变量引入量词：（）=（）要求在（）中自由出现，且为真，不在（）中约束出现。（）=（）要求是特定常量，取代的不能在（）中出现。第33页，共80页，编辑于2022年，星期四例3.1020世纪年代的漫画都是日本漫画家创作的，这幅漫画是世纪年代的作品，因此这幅漫画是日本漫画家的作品。解：

19、设(x)：是20世纪年代的漫画Q():日本漫画家的作品a:一幅漫画前提x(x)Q(x),P(a)结论Q(a)证明 x(x)Q(x)P(a)(a)Q(a)Q(a)第34页，共80页，编辑于2022年，星期四3.2.4谓词知识表示知识：是人们在认识、改造世界中经验的总结或者实事的描述。使用逻辑法表示知识，将自然语言描述的知识，通过谓词、函数加以描述，获得逻辑谓词公式，进而利用计算机进行处理。例：校长与小李打网球。可以表示为：定义：Play(x,y,z)表示，和打这种球Play(zhang,li,tennis)清华是个大学定义：Univ(x)表示是大学Univ(qinghua)第35页，共80页，编

20、辑于2022年，星期四常用的可以用蕴含代表规则：人人都受法律管制：Human(x)Lawed(x)如果犯罪则被惩罚 Commit(x)Punished(x)（Human(x)Lawed(x)）（Commit(x)Punished(x)）应用谓词表示知识应用广泛：（）易于用数据库存贮知识（）谓词具有完备逻辑推理方法（）表达的知识具有科学严密性（）逻辑推理具有知识的一致性第36页，共80页，编辑于2022年，星期四.3谓词逻辑归结原理3.3.1归结原理命题：A1、A2、A3 和 B求证：A1A2A3成立，则B成立，反证法：证明A1A2A3B 是矛盾式 （永假式）3.3.2Skolem 标准形1.前

21、束范式2.Skolem 标准形 消去前束范式中的所有量词的公式第37页，共80页，编辑于2022年，星期四量词消去原则：消去存在量词“”，略去全程量词“”。注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。第38页，共80页，编辑于2022年，星期四谓词归结子句形(Skolem 标准形)Skolem定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。第39页，共80页，编辑于2022年，星期四谓词归结子句形(Skolem 标准形)例:将下

22、式化为Skolem标准形：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)解：第一步，消去号，得：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)第二步，深入到量词内部，得：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)第三步，变元易名，得(x)(y)P(a,x,y)(u)(v)(Q(v,b)R(u)第四步，存在量词左移，直至所有的量词移到前面，得：(x)(y)(u)(v)P(a,x,y)(Q(v,b)R(u)由此得到前述范式第40页，共80页，编辑于2022年，星期四谓词归结子句形(Skolem 标准形)第五步，消去“”（存在量词），略去“”全称量词消去

23、(y)，因为它左边只有(x)，所以使用x的函数f(x)代替之，这样得到：(x)(z)(P(a,x,f(x)Q(z,b)R(x)消去(z)，同理使用g(x)代替之，这样得到：(x)(P(a,x,f(x)Q(g(x),b)R(x)则，略去全称变量，原式的Skolem标准形为：P(a,x,f(x)Q(g(x),b)R(x)第41页，共80页，编辑于2022年，星期四3.3.3子句集l子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取：G SKOLEM标准形 消去存在变量 以“，”取代“”，并表示为集合形式。第42页，共80页，编辑于2022年，星期四谓词归结

24、子句形l G是不可满足的S是不可满足的G与S不等价，但在不可满足得意义下是一致的。定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的S是不可满足的。注意：G真不一定S真，而S真必有G真。即：S=G第43页，共80页，编辑于2022年，星期四谓词归结子句形lG=G1 G2 G3 Gn的子句形G的字句集可以分解成几个单独处理。有 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不可满足第44页，共80页，编辑于2022年，星期四求取子句集例(1)例：对所有的x

25、,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：lP(x,y)表示x是y的父亲lQ(x,y)表示x是y的祖父lANS(x)表示问题的解答第45页，共80页，编辑于2022年，星期四求取子句集例(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

26、(x,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，SB第46页，共80页，编辑于2022年，星期四归结原理l归结原理正确性的根本在于，找到矛盾可以肯定不真。l方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。第47页，共80页，编辑于2022年，星期四3.3.4置换与合一l置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。l定义：置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，x1,x2,xn是互不

27、相同的变量，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不是一个置换，第48页，共80页，编辑于2022年，星期四置换的合成l设t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,un/yn，是两个置换。则与的合成也是一个置换，记作。它是从集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn中删去以下两种元素：当ti=xi时，删去ti/xi(i=1,2,n);当yix1,x2,xn时，删去u

28、j/yj(j=1,2,m)最后剩下的元素所构成的集合。合成即是对ti先做置换然后再做置换，置换xi第49页，共80页，编辑于2022年，星期四置换的合成l例：设：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/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/z第50页，共80页，编辑于2022年，星期四合一l合

29、一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。l定义：设有公式集FF1，F2，Fn，若存在一个置换，可使F1F2=Fn，则称是F的一个合一。同时称F1，F2，.，Fn是可合一的。l例：设有公式集FP(x,y,f(y),P(a,g(x),z)，则a/x,g(a)/y,f(g(a)/z是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。第51页，共80页，编辑于2022年，星期四最一般合一：设是谓词公式集F，如果对F的任意一个合一都存在一个置换使得=，则称是一个最一般的合一mgu.最一般合一求取方法：逐一比较找出不一致，并做合一置换算法：对于F1和F2令W=F1,F2令k=

30、0，W0=W,0=如果Wk已合一，停止,k=mgu,，否则找不一致集Dk若Dk中存在元素vk和tk，其中vk不出现于tk中，转，否则不可合一令k+1=ktk/vk,Wk+1=Wktk/tk=Wk+1k=k+1转。可证明若F1和F2可合一，算法必停于第52页，共80页，编辑于2022年，星期四例3.16：W=P(a,x,f(g(y),P(z,f(a),f(u),F1=P(a,x,f(g(y),F2=P(z,f(a),f(u),求：F1和F2的最一般合一第53页，共80页，编辑于2022年，星期四3.3.5归结式要考虑变量的置换和合一归结式：对两个无公共变量的字句对于子句C1L1和C2L2，如果L

31、1与L2可合一，且s是其合一者，则(C1C2)s是其归结式。其中L1、L2是单文字。事实上L1、L2中有一个含有否定符，所以对另一个加上否定符后，才能判断它们是否可合一。例（1）P(x)Q(x,y)与P(a)R(b,z)（2）P(x,y)Q(x)R(x)与P(a,z)Q(b)第54页，共80页，编辑于2022年，星期四3.3.5归结式l归结的注意事项：1.谓词的一致性，P()与Q()，不可以2.常量的一致性，P(a,)与P(b,.)，不可以 变量，P(a,.)与P(x,)，可以3.变量与函数，P(a,x,.)与P(x,f(x),)，不可以；1.是不能同时消去两个互补对，PQ与PQ的空，不可以2

32、.先进行内部简化（置换、合并）第55页，共80页，编辑于2022年，星期四3.3.6归结的过程写出谓词关系公式 用反演法写出谓词表达式 SKOLEM标准形 子句集S 对S中可归结的子句做归结 归结式仍放入S中，反复归结过程 得到空子句 得证第56页，共80页，编辑于2022年，星期四子句集的化简子句集的化简l 在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。其化简步骤如下：规则化成相应的子句集。其化简步骤如下：l (1)消去连接词消去连接词“”和和“”l 反复使用如下等价公式：反复使用如下等价公式：l P

33、Q PQ l PQ (PQ)(PQ)l即可消去谓词公式中的连接词即可消去谓词公式中的连接词“”和和“”。l 例如公式例如公式l (x)(y)P(x,y)(y)(Q(x,y)R(x,y)l经等价变化后为经等价变化后为l (x)(y)P(x,y)(y)(Q(x,y)R(x,y)第57页，共80页，编辑于2022年，星期四2.子句集的化简子句集的化简l(2)减少否定符号的辖域减少否定符号的辖域l反复使用反复使用双重否定率双重否定率l (P)Pl摩根定律摩根定律l (PQ)PQl (PQ)PQl量词转换率量词转换率l (x)P(x)(x)P(x)l (x)P(x)(x)P(x)l将每个否定符号将每个否

34、定符号“”移到仅靠谓词的位置，使得每个否定符号最多移到仅靠谓词的位置，使得每个否定符号最多只作用于一个谓词上。只作用于一个谓词上。l 例如，例如，上式经等价变换后为上式经等价变换后为l (x)(y)P(x，y)(y)(Q(x，y)R(x，y)第58页，共80页，编辑于2022年，星期四子句集的化简子句集的化简l (3)对变元标准化对变元标准化l 在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。字。l

35、例如，上式经变换后为例如，上式经变换后为l (x)(y)P(x，y)(z)(Q(x，z)R(x，z)l (4)化为前束范式化为前束范式l 化为前束范式的方法化为前束范式的方法:把所有量词都移到公式的左边，并且在移动时把所有量词都移到公式的左边，并且在移动时不能改变其相对顺序不能改变其相对顺序。由于第。由于第(3)步已对变元进行了标准化，每个量步已对变元进行了标准化，每个量词都有自己的变元，这就消除了任何由变元引起冲突的可能，因词都有自己的变元，这就消除了任何由变元引起冲突的可能，因此这种移动是可行的。此这种移动是可行的。l 例如，上式化为前束范式后为例如，上式化为前束范式后为l (x)(y)(

36、z)(P(x，y)(Q(x，z)R(x，z)第59页，共80页，编辑于2022年，星期四2.子句集的化简子句集的化简l (5)消去存在量词消去存在量词l 消去存在量词时，需要区分以下两种情况：消去存在量词时，需要区分以下两种情况：l 若存在量词不出现在全称量词的辖域内若存在量词不出现在全称量词的辖域内（即它的左边没有全称量（即它的左边没有全称量词），只要用一个新的个体常量替换受该存在量词约束的变元，就可词），只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。消去该存在量词。l 若存在量词位于一个或多个全称量词的辖域内若存在量词位于一个或多个全称量词的辖域内，例如，例如l (

37、x1)(xn)(y)P(x1，x2,xn,y)l则需要用则需要用Skolem函数函数f(x1，x2,xn)替换受该存在量词约束的变元替换受该存在量词约束的变元y，然后再消去该存在量词。，然后再消去该存在量词。l 例如，上步所得公式中存在量词例如，上步所得公式中存在量词(y)和和(z)都位于都位于(x)的辖域内，的辖域内，因此都需要用因此都需要用Skolem函数来替换。设替换函数来替换。设替换y和和z的的Skolem函数分别函数分别是是f(x)和和g(x)，则替换后的式子为，则替换后的式子为l (x)(P(x,f(x)(Q(x,g(x)R(x,g(x)第60页，共80页，编辑于2022年，星期四

38、2.子句集的化简子句集的化简l (6)化为化为Skolem标准形标准形l Skolem标准形的一般形式为标准形的一般形式为l (x1)(xn)M(x1,x2,xn)l其中，其中，M(x1,x2,xn)是是Skolem标准形的母式，它由子句的合取所构标准形的母式，它由子句的合取所构成。成。l 把谓词公式化为把谓词公式化为Skolem标准形需要使用以下等价关系标准形需要使用以下等价关系l P(QR)(PQ)(PR)l例如，前面的公式化为例如，前面的公式化为Skolem标准形后为标准形后为l (x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)l (7)消去全称量词消去全称量词

39、l 由于母式中的全部变元均受全称量词的约束，并且全称量词的次由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。但剩下的母式，仍假设其序已无关紧要，因此可以省掉全称量词。但剩下的母式，仍假设其变元是被全称量词量化的。变元是被全称量词量化的。l 例如，上式消去全称量词后为例如，上式消去全称量词后为l (P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)第61页，共80页，编辑于2022年，星期四2.子句集的化简子句集的化简l (8)消去合取词消去合取词l 在母式中消去所有合取词，把母式用子句集的形式表示出来。其在母式中消去所有合取词，把母式

40、用子句集的形式表示出来。其中，子句集中的每一个元素都是一个子句。中，子句集中的每一个元素都是一个子句。l 例如，例如，上式的子句集中包含以下两个子句上式的子句集中包含以下两个子句l P(x,f(x)Q(x,g(x)l P(x,f(x)R(x,g(x)l (9)更换变量名称更换变量名称l 对子句集中的某些变量重新命名，使任意两个子句中不出现相对子句集中的某些变量重新命名，使任意两个子句中不出现相同的变量名。由于每一个子句都对应着母式中的一个合取元，并同的变量名。由于每一个子句都对应着母式中的一个合取元，并且所有变元都是由全称量词量化的，因此任意两个不同子句的变且所有变元都是由全称量词量化的，因此

41、任意两个不同子句的变量之间实际上不存在任何关系。这样，更换变量名是不会影响公量之间实际上不存在任何关系。这样，更换变量名是不会影响公式的真值的。式的真值的。l 例如，例如，对前面的公式，可把第二个子句集中的变元名对前面的公式，可把第二个子句集中的变元名x更换为更换为y，得，得到如下子句集到如下子句集l P(x,f(x)Q(x,g(x)l P(y,f(y)R(y,g(y)第62页，共80页，编辑于2022年，星期四对于证明问题设F为前提的公式集，Q为目标公式集，用归结反演证明的步骤：（1）否定Q，得到Q（2）把Q加入到公式集F，得到F，Q称为S（3）对S进行归结，归结到空子句为止。第63页，共8

42、0页，编辑于2022年，星期四例：求证例：求证:G是是F1和和F2的逻辑推论的逻辑推论 F1F1：F2:F2:G:证明：化为子句集P(a)(1)R(y)L(a,y)(2)P(x)Q(y)L(x,y)(3)R(b)(4)Q(b)(5)(2)(4)归结 L(a,b)(6)(1)(3)归结 Q(y)L(a,y)(7)(5)(7)L(a,b)(8)(6)(8)NIL 证毕。第64页，共80页，编辑于2022年，星期四例题“快乐学生”问题l假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。l解：先将问题用

43、谓词表示如下：lR1:“任何通过计算机考试并获奖的人都是快乐的”(x)(Pass(x,computer)Win(x,prize)Happy(x)lR2:“任何肯学习或幸运的人都可以通过所有考试”(x)(y)(Study(x)Lucky(x)Pass(x,y)lR3:“张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)lR4:“任何幸运的人都能获奖”(x)(Luck(x)Win(x,prize)l结论：“张是快乐的”的否定Happy(zhang)第65页，共80页，编辑于2022年，星期四例题“快乐学生”问题l由R1及逻辑转换公式:PWH=（PW）H，可得l(1)Pass(

44、x,computer)Win(x,prize)Happy(x)l由R2：(2)Study(y)Pass(y,z)l(3)Lucky(u)Pass(u,v)l由R3：(4)Study(zhang)l(5)Lucky(zhang)l由R4：(6)Lucky(w)Win(w，prize)l由结论：(7)Happy(zhang)（结论的否定）l(8)Pass(w,computer)Happy(w)Luck(w)(1)(6)，w/xl(9)Pass(zhang,computer)Lucky(zhang)(8)(7)，zhang/wl(10)Pass(zhang,computer)(9)(5)l(11)L

45、ucky(zhang)(10)(3)，zhang/u,computer/vl(12)(11)(5)第66页，共80页，编辑于2022年，星期四对于用归结原理求取问题答案步骤：（1）把已知化为谓词公式并转化成子句集S(2)把待求解的问题用谓词公式表示，并否定之，然后和谓词ANSWER(x)构成析取式，x代表问题的答案。（3）把第二步的析取式和S合并，构成S(4)对S进行归结（5）若归结出ANSWER(x)，并且在x已经被替代，被替代就是答案。第67页，共80页，编辑于2022年，星期四l已知：已知：F1:李李(li)先生是小赵先生是小赵(zhao)的老师；的老师；F2:小赵小赵(zhao)与小刘

46、与小刘(liu)是同班同学；是同班同学；F3:如果如果x与与y是同班同学，则是同班同学，则x的老师也是的老师也是y的老师。的老师。定义的谓词如下：定义的谓词如下：T(x，y)：表示：表示x是是y的老师；的老师；C(x，y)：表示：表示x与与y是同班同学；是同班同学；求：小刘的老师是谁？求：小刘的老师是谁？解：把已知前提及待求解的问题表示成谓词公式：第68页，共80页，编辑于2022年，星期四把上述公式化为子句集：（1）（2）（3）（4）应用归结原理进行归结：（5）（1）和（3）归结 （4）和（5）归结（2）和（6）归结得知小刘的老师是李老师。第69页，共80页，编辑于2022年，星期四第70页

47、，共80页，编辑于2022年，星期四归结原理l归结法的实质：归结法是仅有一条推理规则的推理方法。归结的过程是一个语义树倒塌的过程。l归结法的问题子句中有等号或不等号时，完备性不成立。Herbrand定理的不实用性引出了可实用的归结法。第71页，共80页，编辑于2022年，星期四3.3.7归结过程的控制策略l要解决的问题：归结方法的知识爆炸。l控制策略的目的归结点尽量少l控制策略的原则给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。第72页，共80页，编辑于2022年，星期四控制策略的方法(1)删除策略完备名词解释：归类：设有两

48、个子句C和D，若有置换使得C D成立，则称子句C把子句D归类。由于小的可以代表大的，所以小的吃掉大的了。若对S使用归结推理过程中，当归结式Cj是重言式（永真式）和Cj被S中子句和子句集的归结式Ci(ij)所归类时，便将Cj删除。这样的推理过程便称做使用了删除策略的归结过程。主要思想：归结过程在寻找可归结子句时，子句集中的子句越多，需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉，就会缩小搜索范围，减少比较次数，从而提高归结效率。删除策略对阻止不必要的归结式的产生来缩短归结过程是有效的。然而要在归结式Cj产生后方能判别它是否可被删除，这部分计算量是要花费的，只是节省了被删除的子句

49、又生成的归结式。尽管使用删除策略的归结，少做了归结但不影响产生空子句，就是说删除策略的归结推理是完备的。第73页，共80页，编辑于2022年，星期四控制策略的方法(2)采用支撑集完备 支撑集：设有不可满足子句集S的子集T，如果S-T是可满足的，则T是支持集。采用支撑集策略时，从开始到得到的整个归结过程中，只选取不同时属于S-T的子句，在其间进行归结。就是说，至少有一个子句来自于支撑集T或由T导出的归结式。例如：A1A2A3B中的B可以作为支撑集使用。要求每一次参加归结的亲本子句中，只要应该有一个是有目标公式的否定（B）所得到的子句或者它们的后裔。支撑集策略的归结是完备的，同样，所有可归结的谓词

50、公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非，即SB。第74页，共80页，编辑于2022年，星期四ST可满足支撑集示意图第75页，共80页，编辑于2022年，星期四控制策略的方法(3)语义归结 完备 语义归结策略是将子句S按照一定的语义分成两部分，约定每部分内的子句间不允许作归结。同时还引入了文字次序，约定归结时其中的一个子句的被归结文字只能是该子句中“最大”的文字。语义归结策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用语义归结策略达到加快归结速度的目的。问题是如何寻找合适的语义分类方法，并根据其含义将子句集两个