人工智能:第3章.ppt
《人工智能:第3章.ppt》由会员分享,可在线阅读,更多相关《人工智能:第3章.ppt(92页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第三章第三章 归结推理方法归结推理方法概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法第三章第三章 归结推理方法归结推理方法概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法概述概述归结原理由J.A.Robinson由1965年提出。与演
2、绎法(deductiveinference)完全不同,新的逻辑演算(inductiveinference)算法。一阶逻辑中,至今为止的最有效的半可判定的算法。即,一阶逻辑中任意恒真公式,使用归结原理,总可以在有限步内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即,有了规则已知条件,顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。(“数学定理机器证明”)本课程只讨论一阶谓词逻辑描述下的归结推理方法,不涉及高阶谓词逻辑问题。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法第三章第三章 归结推理方法归结推理方法概述命题逻辑的归结法谓词归结子句形归结原理
3、归结过程的策略控制Herbrand定理人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法第三章第三章 归结推理方法归结推理方法概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题逻辑的归结法命题逻辑的归结法命题逻辑基础:定义:合取式:p与q,记做p q析取式:p或q,记做p q蕴含式:如果p则q,记做p q等价式:p当且仅当q,记做p q。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题逻辑基础命题逻辑基础定义:若A无成假赋值,则称A为重言式或永真式;若A无成真赋值,则称
4、A为矛盾式或永假式;若A至少有一个成真赋值,则称A为可满足的;析取范式:仅由有限个简单合取式组成的析取式。合取范式:仅由有限个简单析取式组成的合取式。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题逻辑基础命题逻辑基础基本等值式24个(1)交换率: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)人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题逻辑基础命题逻辑基础基本等值式(1)摩根率:(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人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题例命题例命题:命题:能判断真假(不是既真又假)的陈述句。简单陈述句描述事实、事物的状态、关系等性质。例如:11+1=22雪是黑色的。3北京是中国的首都。4到冥王星去渡假。判断一个句子是否是命题,有先要看它是否是陈述句,而后看它的真值是否唯一。以上的例子都是陈述句,第4句的真值现在是假,随着人类科学的发展,有可能变成真,但不管怎样,真值是唯一的。因此,以上4个例子都是命题。而例如:1快点走吧!2到那去?3x+y10等等句子,都不是命题。人工智能原理人工
6、智能原理第三章第三章 归结推理方法归结推理方法命题表示公式(命题表示公式(1)将陈述句转化成命题公式。如:设“下雨”为p,“骑车上班”为q,1“只要不下雨,我骑自行车上班”。p是q的充分条件,因而,可得命题公式:pq2“只有不下雨,我才骑自行车上班”。p是q的必要条件,因而,可得命题公式:qp 人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题表示公式(命题表示公式(2)例如:1“如果我进城我就去看你,除非我很累。”设:p,我进城,q,去看你,r,我很累。则有命题公式:r(pq)。2“应届高中生,得过数学或物理竞赛的一等奖,保送上北京大学。”设:p,应届高中生,q,保送上北京大
7、学上学,r,是得过数学一等奖。t,是得过物理一等奖。则有命题公式公式:p(r t)q。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题逻辑的归结命题逻辑的归结法法基本单元:简单命题(陈述句)例:命题:A1、A2、A3 和 B求证:A1A2A3成立,则B成立,即:A1A2A3 B反证法:证明A1A2A3B 是矛盾式 (永假式)人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题逻辑的归结命题逻辑的归结法法建立子句集合取范式:命题、命题和的与,如:P(PQ)(PQ)子句集S:合取范式形式下的子命题(元素)的集合例:命题公式:P(PQ)(PQ)子句集 S:S=P,PQ
8、,PQ 人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题逻辑的归结法命题逻辑的归结法归结式消除互补对,求新子句得到归结式。如子句:C1,C2,归结式:R(C1,C2)=C1C2注意:C1C2 R(C1,C2),反之不一定成立。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题逻辑的归结法命题逻辑的归结法归结过程将命题写成合取范式求出子句集对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句,S是不可满足的(矛盾),原命题成立。(证明完毕)谓词的归结:除了有量词和函数以外,其余和命题归结过程一样。人工智能原理人工智能原理第三章第三章 归结推理方法归结推
9、理方法命题逻辑归结例题(命题逻辑归结例题(1)例题,证明公式:(PQ)(QP)证明:(1)根据归结原理,将待证明公式转化成待归结命题公式:(PQ)(QP)(2)分别将公式前项化为合取范式:PQPQ结论求后的后项化为合取范式:(QP)(QP)QP两项合并后化为合取范式:(PQ)QP(3)则子句集为:PQ,Q,P人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法命题逻辑归结例题(命题逻辑归结例题(2)子句集为:PQ,Q,P(4)对子句集中的子句进行归结可得:1.PQ2.Q3.P4.Q,(1,3归结)5.,(2,4归结)由上可得原公式成立。人工智能原理人工智能原理第三章第三章 归结推理方
10、法归结推理方法第三章第三章 归结推理方法归结推理方法概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法第三章第三章 归结推理方法归结推理方法概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结原理基础谓词归结原理基础一阶逻辑基本概念个体词:表示主语的词谓词:刻画个体性质或个体之间关系的词量词:表示数量的词人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结原理基础谓词归结原理基础小王是个工
11、程师。8是个自然数。我去买花。小丽和小华是朋友。其中,“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词,而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质,第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系,最后一个谓词“是朋友”表示两个个体词之间的关系。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结原理基础谓词归结原理基础一阶逻辑公式及其解释个体常量:a,b,c个体变量:x,y,z谓词符号:P,Q,R量词符号:,人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结原理
12、基础谓词归结原理基础例如:(1)所有的人都是要死的。(2)有的人活到一百岁以上。在个体域D为人类集合时,可符号化为:(1)xP(x),其中P(x)表示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活到一百岁以上。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结原理基础谓词归结原理基础量词否定等值式:(x)M(x)(y)M(y)(x)M(
13、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)人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结原理基础谓词归结原理基础量词辖域收缩与扩张等值式:(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(
14、x)Q)(x)P(x)Q(x)(P(x)Q)(x)P(x)Q(x)(Q P(x))Q (x)P(x)人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结子句形谓词归结子句形(SkolemSkolem 标准形标准形)SKOLEM标准形前束范式定义:说公式A是一个前束范式,如果A中的一切量词都位于该公式的最左边(不含否定词),且这些量词的辖域都延伸到公式的末端。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结子句形谓词归结子句形(SkolemSkolem 标准形标准形)即:把所有的量词都提到前面去,然后消掉所有量词(Q1x1)(Q2x2)(Qnxn)M(x1
15、,x2,xn)约束变项换名规则:(Qx)M(x)(Qy)M(y)(Qx)M(x,z)(Qy)M(y,z)人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结子句形谓词归结子句形(SkolemSkolem 标准形标准形)量词消去原则:消去存在量词“”,略去全程量词“”。注意:左边有全程量词的存在量词,消去时该变量改写成为全程量词的函数;如没有,改写成为常量。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结子句形谓词归结子句形(SkolemSkolem 标准形标准形)Skolem定理:谓词逻辑的任意公式都可以化为与之等价的前束范式,但其前束范式不唯一。SKO
16、LEM标准形定义:消去量词后的谓词公式。注意:谓词公式G的SKOLEM标准形同G并不等值。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结子句形谓词归结子句形(SkolemSkolem 标准形标准形)例:将下式化为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)第四步,存在量词左移,直至所有
17、的量词移到前面,得:(x)(y)(u)(v)P(a,x,y)(Q(v,b)R(u)由此得到前述范式人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结子句形谓词归结子句形(SkolemSkolem 标准形标准形)第五步,消去“”(存在量词),略去“”全称量词消去(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)人
18、工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结子句形谓词归结子句形子句与子句集文字:不含任何连接词的谓词公式。子句:一些文字的析取(谓词的和)。子句集S的求取:G SKOLEM标准形 消去存在变量 以“,”取代“”,并表示为集合形式。人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法谓词归结子句形谓词归结子句形 G是不可满足的S是不可满足的G与S不等价,但在不可满足得意义下是一致的。定理:若G是给定的公式,而S是相应的子句集,则G是不可满足的S是不可满足的。注意:G真不一定S真,而S真必有G真。即:S=G人工智能原理人工智能原理第三章第三章 归结推理方法归结推
19、理方法谓词归结子句形谓词归结子句形G=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不可满足人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法求取子句集例求取子句集例(1)例:对所有的x,y,z来说,如果y是x的父亲,z又是y的父亲,则z是x的祖父。又知每个人都有父亲,试问对某个人来说谁是它的祖父?求:用一阶逻辑表示这个问题,并建立子句集。解:这里我们首先引入谓词:P(x,y)表示x是
20、y的父亲Q(x,y)表示x是y的祖父ANS(x)表示问题的解答人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法求取子句集例求取子句集例(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,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)则
21、得到的相应的子句集为:SA1,SA2,SB人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法第三章第三章 归结推理方法归结推理方法概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法第三章第三章 归结推理方法归结推理方法概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法归结原理归结原理归结原理正确性的根本在于,找到矛盾可以肯定不真。方法:和命题逻辑一样。但由于有函数,所以要考虑合一和置换。人工智能原理人
22、工智能原理第三章第三章 归结推理方法归结推理方法置换置换置换:可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义:置换是形如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不是一个置换,人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法置换的合成置换的合成设t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un
23、/yn,是两个置换。则与的合成也是一个置换,记作。它是从集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn中删去以下两种元素:当ti=xi时,删去ti/xi(i=1,2,n);当yix1,x2,xn时,删去uj/yj(j=1,2,m)最后剩下的元素所构成的集合。合成即是对ti先做置换然后再做置换,置换xi人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法置换的合成置换的合成例:设: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
24、(b)/x中的f(b)是置换作用于f(y)的结果;y/y中的y是置换作用于z的结果。在该集合中,y/y满足定义中的条件i,需要删除;a/x,b/y满足定义中的条件ii,也需要删除。最后得f(b)/x,y/z人工智能原理人工智能原理第三章第三章 归结推理方法归结推理方法合一合一合一可以简单地理解为“寻找相对变量的置换,使两个谓词公式一致”。定义:设有公式集FF1,F2,Fn,若存在一个置换,可使F1F2=Fn,则称是F的一个合一。同时称F1,F2,.,Fn是可合一的。例:设有公式集FP(x,y,f(y),P(a,g(x),z),则a/x,g(a)/y,f(g(a)/z是它的一个合一。注意:一般说
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能
限制150内