欢迎来到工友文库! | 帮助中心 工友共享,造福你我!
工友文库
全部分类
  • 行业文库 >
    行业文库
    行业标准 农林牧渔 能源矿业 电力热力 水利环境 材料技术 地理测绘 建筑工程 机械工程 制造加工 交通物流 网络计算 电气机电 信息通讯 汽车行业 航空航天 船舶工程 光电工程 住宿餐饮 财会金融 房地产业 城建规划 装饰装修 家电维修 电商行业 租赁商务 批发零售 居民服务 教育服务 医药卫生 体育行业 公共管理 图书管理 外语翻译 休闲旅游 文艺传媒 其他行业
  • 商业文档 >
    商业文档
    企业计划 工程管理 广告经营 财务报表 物业管理 质控管理 企业文化 绩效管理 商务礼仪 创业孵化 市场营销 经营企划 销售管理 营销创新 资本运营 招商加盟 合同协议 信息管理 励志材料 人事档案 员工关系 薪酬管理 招聘面试 其它文档
  • 办公文书 >
    办公文书
    统计图表 总结报告 演讲致辞 心得体会 述职报告 工作计划 解决方案 调研报告 事务文书 经验事迹 往来文书 规章制度 申请范文 求职简历 活动策划 会议纪要 党建材料 软件教程 其他文书
  • PPT模板库 >
    PPT模板库
    扁平风格 创意新颖 动画效果 动态模板 简约风格 静态模板 环保绿色 卡通风格 立体风格 欧洲风格 手绘风格 创意黑板 相册风格 星空风格 炫酷科技 中国风格 医疗风格 高端商务 工作常用 总结报告 毕业答辩 节日庆典 公益风格 化妆美容 婚礼策划 餐饮美食 培训课件 融资路演 商业策划 英文模板 党政机关 述职竞聘
  • 小学初中 >
    小学初中
    幼儿教育 小学语文 小学数学 小学英语 初中语文 初中数学 初中英语 初中物理 初中化学 初中地理 初中生物 初中政治 初中历史 思想品德 小学竞赛 初中竞赛 其他学科
  • 高中教育 >
    高中教育
    高中语文 高中数学 高中英语 高中物理 高中化学 高中生物 高中地理 高中政治 高中历史 高考资料 高中竞赛 其他学科
  • 高等教育 >
    高等教育
    基础课 艺术类 哲学类 体育类 水利类 测绘类 法学类 历史学 社会学 心理学 教育学 政治学 统计学 房地产 语言文化 生物科学 医药卫生 天文气象 地理科学 环境科学 系统科学 材料科学 机械仪表 图书档案 土建工程 海洋工程 轻工纺织 工程力学 能源动力 光电工程 电力技术 市政工程 财会金融 工商管理 语言文学 广播影视 公安司法 汽车汽修 交通运输 水产加工 植物生产 森林资源 动物科学 食品加工 餐饮旅游 公共事业 新闻传播学 农林业工程 城镇规划管理 水文与水资源 地矿及资源勘查 航空航天与武器 管理科学与工程 农林业经济管理 机电设备及自动化 计算机与信息科学 大学生竞赛资料
  • 执业资格考试 >
    执业资格考试
    财会类考试 建筑类考试 外贸类考试 外语类考试 医药类考试 管理类考试 公务员类考试 司法法律考试 教师资格考试 计算机类考试 公共服务类考试 其他资格证考试
  • 一线采风 >
    一线采风
    一线新闻 事迹宣传 工友作品
  • 教育视频 >
    教育视频
    幼儿教育视频 小学教育视频 初中教育视频 高中教育视频 大学教育视频 C#自学视频教程 软件视频教程 英语视频教学 其他教学视频
  • 换一换
    首页 工友文库 > 资源分类 > PPTX文档下载
     

    人工智能第六章教学课件.pptx

    • 资源ID:20111       资源大小:459.55KB        全文页数:127页
    • 资源格式: PPTX        下载权限:注册会员/VIP会员    下载费用:0金币 【人民币0元】
    下载资源需要0金币 【人民币0元】
    已注册用户请登录:
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,既可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

    人工智能第六章教学课件.pptx

    8/17/2019,1,第六章 归结原理,6.1 子句集的Herbrand域 一、 Herbrand域与 Herbrand解释 定义(Herbrand域)设S为子句集,令H0是出现于子句集S的常量符号集。如果S中无常量符号出现,则H0由一个常量符号a组成。 对于i=1,2,,令 Hi Hi-1{所有形如ft1,,tn的项} 其中ft1,,tn是出现在S中的所有n元函数符号, tj Hi-1,j=1,,n. 称Hi为S的i级常量集,H 称为S的Herbrand域, 简称S的H域。,8/17/2019,2,,例 S={Pfx,a,gy,b} H0 {a, b} H1 {a, b, fa, fb, ga, gb} H2={a, b, fa, fb, ga, gb, ffa, ffb, fga, fgb, gfa, gfb, gga, ggb} ,8/17/2019,3,练习 求S的Herbrand域,S={Px  Qy,Rz } S={Qa ~Pfx, ~Qb  Pgx,y },8/17/2019,4,原子集 基例,基把对象中的变量用常量代替后得到的无变量符号出现的对象。 基项、基项集、基原子、基原子集合、基文字、基子句、基子句集 定义 原子集、Herbrand底 设S是子句集,形如Pt1,,tn的基原子集合,称为S的Herbrand底或S的原子集. 其中Px1,,xn是出现于S的所有n元谓词符号,t1,,tn是S的H域中的元素. 定义(基例) 设S是子句集,C是S中的一个子句.用S的H域中元素代替C中所有变量所得到的基子句称为子句C的基例。,8/17/2019,5,练习,已知S={Pfx,a,gy,b},求S的原子集, 给出Pfx,a,gy,b的一个基例。 已知S={Px  Qy,Rz },求S的原子集, 分别给出Px  Qy, Rz的所有基例。 已知S= {Qa~Pfx,~Qb Pgx,y}, 求S的原子集, 分别给出Qa~Pfx , ~Qb Pgx,y的一个基例。 设S={Px, Qfy  Ry },求S的H域, S的原子集, Px的基例, Qfy  Ry 的基例。,8/17/2019,6,H解释,定义(子句集的H解释) 设S是子句集,H是S的H域,I*是S在H上的一个解释.称I*为S的一个H解释,如果I*满足如下条件 1) I*映射S中的所有常量符号到自身。 2)若f是S中n元函数符号,h1,,hn是H中元素,则I*指定映射 h1,,hn f h1,,hn 设A{A1,A2,,An, } 是S的原子集。于是S的一个H解释I可方便地表示为如下一个集合 I* ={m1,m2,,mn,} 其中, mi ,,,8/17/2019,7,H解释的例子,例 S{PxQx, Rfy } S的H域{a, fa, ffa, } S的原子集 A{Pa, Qa, Ra, Pfa, Qfa, Rfa, } S的H解释 I1* { Pa, Qa, Ra, Pfa, Qfa, Rfa, } I2* { ~Pa, ~Qa, Ra, Pfa, ~Qfa, ~Rfa, },8/17/2019,8,练习,S{PxQx, ~Pa, ~Qb }, 求S的所有H解释。,8/17/2019,9,二、Herbrand解释与普通解释的关系,子句集S的H解释是S的普通解释。 S的普通解释不一定是S的H解释普通解释不是必须定义在H域上,即使定义在H域上,也不一定是一个H解释。 任取普通解释I,依照I,可以按如下方法构造S的一个H解释I*,使得若 S在 I下为真则 S在I*下也为真。,8/17/2019,10,例.,S={Px, Qy,fy,a} 令S的一个解释I如下 D={1,2} a f1, 1 f1, 2 f2, 1 f2, 2 2 1 2 2 1 P1 P2 Q1, 1 Q1, 2 Q2, 1 Q2, 2 T F F T F T 对应于I的H解释I* I*={~Pa, Qa, a, Pfa, a, ~Qa, fa, a, Qfa, a, a, ~Qfa, a, fa, a, },8/17/2019,11,例,S{Px, Qy, fy, z} 令S的一个解释I如下 D{1, 2} f1, 1 f1, 2 f2, 1 f2, 2 1 2 2 1 P1 P2 Q1, 1 Q1, 2 Q2, 1 Q2, 2 T F F T F T 指定 a对应1得H解释 I1*={Pa, ~Qa, a, Pfa, a, ~Qa, fa, a, ~Qfa, a, a, ~Qfa, a, fa, a, } 指定 a对应2得H解释 I2*={~Pa, Qa, a, Pfa, a, ~Qa, fa, a, Qfa, a, a, ~Qfa, a, fa, a, },8/17/2019,12,对应于I的H解释I*,定义(对应于I的H解释I*) 设I是子句集S在区域D上的解释。H是S的H域。  是如下递归定义的H到D的映射 1) ①若S中有常量符号,H0是出现在S中所有常量符号的集合。 对任意aH0,规定 aIa. ②若S中无常量符号,H0{a}。 规定 ad,d∈D。 2)对任意h1,,hnHin,及S中任意n元函数符号fx1,,xn , 规定fh1,,hn Ifh1,,hn 。,8/17/2019,13,对应于I的H解释I*,对应于I的H解释I*是如下的一个H解释 任取S中n元谓词符号Px1,,xn, 任取h1,,hnHn,规定 TI*Ph1,,hnTIPh1,,hn,8/17/2019,14,引理 如果某区域D上的解释I满足子句集S, 则对应于I的任意一个H解释I*也满足S。 证明令S x1 xn C1 Cm,其中Ci为子句(i1, ,m)。由已知TIST,即对任意(x1,,xn)Dn,都有TICi(x1,,xn)T, i1, ,m,,8/17/2019,15,,因为对S中任意r元谓词符号P(x1,,xr)和任意(h1,,hr)Hr,都有 TI* P(h1,,hr)TIP(h1,,hr) 其中(h1,,hr)Dr。 所以,对任意(h1,,hn)Hn,都有 TI* Ci(h1,,hn)TICi(h1,,hn) 其中(h1,,hn)Dn。 i1, ,m。 故对任意(h1,,hn)Hn ,都有 TI*Ci(h1,,hn)T, 故TI*ST,即I*满足S。,8/17/2019,16,,只考虑子句集的H解释是否够用 定理 子句集S恒假当且仅当S被其所有H解释弄假。 证明 必要性显然。 充分性。假设S被其所有H解释弄假,而S又是可满足的。 设解释I满足S,于是由引理知,对应于I的H解释I*也满足 S,矛盾.故S是不可满足的. 从现在起,如不特别指出,提到的解释都是指H解释.,8/17/2019,17,结论,l)子句 C的基例 C’被解释 I满足,当且仅当 C’中的一个基文字L’出现在 I中. C Px  ~Qfy,a  Rz C’ Pa  ~Qfa,a  Rfa,8/17/2019,18,,2)子句C被解释I满足,当且仅当 C的每一个基例都被I满足. 3)子句 C被解释 I弄假,当且仅当 至少有一个C的基例C’被I弄假。,8/17/2019,19,例.,C~PxQfx I1{~Pa,~Qa,~Pfa,~Qfa,~Pffa,~Qffa,} I2{Pa,Qa,Pfa,Qfa,Pffa,Qffa,} I3{Pa,~Qa,Pfa,~Qfa,Pffa,~Qffa,} 显然,I1,I2满足C,I3弄假C。,8/17/2019,20,,4)子句集S不可满足,当且仅当 对每个解释I,至少有一个S中某个子句C的基例C’被I弄假。,8/17/2019,21,6.2 Herbrand定理,Herbrand定理是符号逻辑中一个很重要的定理.Herbrand定理就是使用语义树的方法,把需要考虑无穷个H解释的问题,变成只考虑有限个解释的问题.,8/17/2019,22,一、语义树,定义互补对 设 A是原子,两个文字A和~A都是另一个的补,集合{A,~A}称为一个互补对. 定义Tautology,重言式 含有互补对的子句.,8/17/2019,23,定义 (语义树) 设S是子句集,A是S的原子集.关于S的语义树是一棵向下生长的树T.在树的每一节上都以如下方式附着A中有限个原子或原子的否定 1)对于树中每一个节点N,只能向下引出有限的直接的节 L1,,Ln. 设Qi是附着在Li上所有文字的合取,i1, ,n, 则Q1Qn是一个恒真的命题公式. 2)对树中每一个节点 N,设 I(N)是树T由根向下到节点 N 的所有节上附着文字的并集, 则I(N)不含任何互补对.,语义树,8/17/2019,24,完全语义树,定义(完全语义树) 设A{A1,,An,}是子句集S的原子集. S的一个语义树是完全的,当且仅当 对于语义树中每一个尖端节点N(即从N不再 生出节的那种节点),都有 Ai或~Ai有且仅有一个属于IN,i1,,k,,8/17/2019,25,,例. 设A{P,Q,R}是子句集S的原子集, 完全语义树正规完全语义树 ,8/17/2019,26,,,8/17/2019,27,例. 设 S{Px, Qfx} S的原子集为A{Pa, Qa, Pfa, Qfa, Pffa, Qffa, },,8/17/2019,28,语义树与解释,S的完全语义树的每一个分枝都对应着S的一个解释; 定义(部分解释)对于子句集S的语义树中的每一个节点N,IN是S的某个解释的子集,称IN为S的部分解释。 S的任意解释都对应着S的完全语义树中的一条分枝 综合 子句集S的一棵完全语义树对应着S的所有解释。,8/17/2019,29,证明 若不然,设T中节点N向下生出的n个节L1,,Ln的每个节Li上,都至少有一个文字Ai不在I中. 由语义树的定义知Q1Qn是恒真公式,其中Qi表示Li 上所有文字的合取,i1, , n。将Q1Qn化为合取范式 Q1Qn=(A1A2An)  因为每一个析取式中都必须有一个互补对。不妨设 A1=~A2,于是A2,~A2都不在I中,这与I是一个解释矛盾。 结论对S的任意解释I,都可以从S的完全语义树的根点出发,向下找出一条分枝,使该分枝对应着解释I。,引理 设T是子句集S的完全语义树,I是S的一个解释。于是T中任意节点向下生出的直接节中,必有一节,其上所有文字都在I中。,8/17/2019,30,子句集的封闭语义树,定义(失效点) 称语义树T中的节点N为失效点,如果 1IN弄假S中某个子句的某个基例; 2IN’不弄假S中任意子句的任意基例,其中N’是 N的任意祖先节点。 定义(封闭语义树) 语义树T是封闭的,当且仅当T的每个分枝的终点都是失效点。 定义(推理点)称封闭语义树的节点 N为推理点,如果N的所有直接下降节点都是失效点.,8/17/2019,31,例. 设S{P, ~PR, ~P~Q, ~P~R}。,S的原子集 A{P, Q, R},,,,,,,,,,,,,,,,P,P,Q,Q,Q,Q,R,R,R,R,R,R,R,R,8/17/2019,32,练习,设子句集 S{~Px∨Qx,Pfx, ~Qfx} 分别画出S的完全语义树与 封闭语义树。,8/17/2019,33,二、Herbrand定理,Herbrand定理I.子句集S是不可满足的,当且仅当对应于S的每一个完全语义树都存在一个有限的封闭语义树. 证明 必要性 若S是不可满足的,设T是S的完全语义树. 对T的每一个分枝B,令IB是附着在B上所有文字的集合, 则IB是S的一个解释,故IB弄假S中某子句C的某个基例C’. 由于C’是有限的,所以B上存在一个节点NB使得部分解 释I(NB)弄假C’,于是分枝B上存在失效点. 因此,对T中每一分枝都存在一个失效点,于是从T得到 S的一个封闭语义树T’。,8/17/2019,34,Herbrand定理I.子句集S是不可满足的,当且仅当对应于S的每一个完全语义树都存在一个有限的封闭语义树.,有限性 因为封闭语义树T’中每一个节点只能向下生长有限个节,故T’必有有限个节点.否则,由Konig无限性引理,T’中必有一条无穷的分枝,此无穷分枝上当然没有失效点,矛盾。 (Konig无限性引理在一个其点之次数有限的无限有向树中,必有一源于根的无限路。 ) 充分性 若S的每一个完全语义树T都对应着一个有限封闭语义树 T’,则T的每条分枝上都有一个失效点。因为S的任一解 释都对应T的某一条分枝,所以每一个解释都弄假S, 故S是不可满足的。,8/17/2019,35,Herbrand定理II 子句集S是不可满足的,当且仅当存在S的一个有限不可满足的S的基例集S’。,证明 必要性 若S恒假,设T是S的完全语义树,由 Herbrand定理I知,有一个有限封闭 语义树 T’对应着T。 令S’是被 T’中所有失效点弄假的所有 基例(S中某些子句的基例)的集合。 因为T’中失效点的个数有限,所以S’ 是有限集合。 任取S’的一解释I’,则I’是S的某个解 释I的子集,而解释I是T中一个分 枝,所以,I弄假S’中子句C’,故 I弄假S’。因为I’I,且I’是S’的解释,故 I’弄假S’.由I’的任意性知S’不可满足。,S{Px, ~Pa∨~Pb, Qfx} H{a,b,fa,fb,ffa,ffb,} A{Pa,Pb,Qa,Qb,} S’{Pa, Pb, ~Pa∨~Pb},8/17/2019,36,Herbrand定理II 子句集S是不可满足的,当且仅当存在S的一个有限不可满足的S的基例集S’。,充分性假设S有一个有限的不可满足的基例集S’。 任取S的解释I, 因为S的每一个解释I都包含着S’的一个解释I’,而S’是不可满足的,所以S的任一解释I都弄假S’,故I弄假S’中至少一个子句,即I弄假S中至少一个子句的基例,亦即I弄假S。 由I的任意性,知S是不可满足的。,8/17/2019,37,,Herbrand定理II提出了一种证明子句集S的不可满足性的方法如果存在这样一个机械程序,它可以逐次生成S中子句的基例集 S0’,,Sn’,并逐次地检查S0’,,Sn’,的不可满足性,那么根据 Herbrand定理,如果 S是不可满足的,则这个程序一定可以找到一个有限数N,使SN’是不可满足的。,8/17/2019,38,使用Herbrand定理的机器证明过程,Gilmore过程 D-P过程,8/17/2019,39,Gilmore过程(1960年),逐次地生成S0’, S1’,Sn’,,其中Si’是用S的i级常量集合Hi中的常量,代替S中子句的变量,而得到的S的所有基例之集合。 对于每一个Si’,可以使用命题逻辑中的任意的方法去检查Si’的不可满足性。 Gilmore使用了所谓乘法方法即将Si’化为析取范式。如果其中任意一个合取项包含一个互补对,则可以删除这个合取项,最后,如果某个Si’是空的,则Si’是不可满足的。 当S不可满足时,该算法一定结束半可判定。,8/17/2019,40,,例. S{Pa, ~Px Qfx, ~Qfa } H0{a} S0Pa ~Pa Qfa ~Qfa Pa~Pa~QfaPa Qfa~Qfa   所以,S是不可满足的。 该算法具有指数复杂性,为此提出了改进规则,称为Davis-Putnam预处理----检验基子句集不可满足性。,8/17/2019,41,D-P过程,设S是基子句集 Tautology删除规则 设S’为删去S中所有的Tautology所剩子句集, 则 S恒假 iff S’恒假。,8/17/2019,42,,单文字规则 若S中有一个单元基子句L, 令S’为删除S中包含L的所有基子句所剩子句集, 则 1 若S’为空集,则S可满足。 2 否则, 令S’’为删除S’中所有文字~L所得子句集 (若S’ 中有单元基子句~L,则删文字~L 得空子句), 于是, S恒假 iff S’’恒假。 SL∧L∨C1’ ∧ ∧L∨Ci’ ∧ ~L∨Ci1’ ∧ ∧ ~L∨Cj’ ∧ Cj1 ∧ ∧ Cn,8/17/2019,43,,定义(纯文字)称S的基子句中文字L是纯的,如果~L不出现在S中。 纯文字规则 设L是S中纯文字,且S’为删除S中所有包含L的基子句所 剩子句集,则 1若S’为空集,则S可满足。 2 否则,S恒假 iff S’恒假。 SL∨C1’ ∧ ∧L∨Ci’ ∧ Ci1 ∧ ∧ Cn,8/17/2019,44,,分裂规则 若SA1 L   Am L  B1  ~L   Bn  ~L R 其中A i , Bi ,R都不含L或~L,令 S1 A1   Am R S2 B1   Bn R 则S恒假 iff S1 , S2同时恒假。,8/17/2019,45,Davis-Putnam方法练习,S PQ~R P~Q ~P R U S P~Q ~PQ  Q~R  ~Q~R S PQ P~Q  RQ  R~Q,8/17/2019,46,Herbrand定理的主要障碍,要求生成关于子句集S的基例集 S1’, S2’, 。在多数情况下,这些集合的元数是以指数方式增加的 例.S{Px,gx,y,hx,y,z,kx,y,z,~Pu,v,ev,w,fv,w,x} H0{a} H1{a, ga, ha, a, ka, a, a, ea, fa, a} S0’{Pa,ga,a,ha,a,a,ka,a,a,~Pa,a,ea,a,fa,a,a} S1’{666666621612961512个元素} S5’是不可满足的,但是H5’是1065数量级个元素,而S5’有10260数量级的元素。想将S5’存储起来都是不可能的,更不要说是检查它的不可满足性了。,8/17/2019,47,为了避免像Herbrand定理所要求的那样去生成子句的基例集,J.A.Robinson于1965年提出了归结原理,归结原理可以直接应用到任意子句集S上(不一定是基子句集),去检查S的不可满足性。 归结原理的本质思想是去检查子句集S是否包含一个空子句 如果S包含,则S是不可满足的。 如果S不包含,则去检查是否可由S推导出来。 当然这个推理规则必须保证推出的子句是原亲本子句的逻辑结果。归结原理就是具有这种性质的一种推理规则。,归结原理思想,8/17/2019,48,命题逻辑中的归结原理,,8/17/2019,49,归结式,定义(归结式) 对任意两个基子句C1和C2。如果C1中存在文字L1,C2中存在文字L2,且L1=~L2, 则从C1和C2中分别删除L1和L2,将C1和C2的剩余部分析取起来构成的子句,称为C1和C2的归结式,记为RC1, C2。 C1和C2称为亲本子句。,8/17/2019,50,练习求下述各子句对的归结式,C1 ~PQR, C2~QS C1 PQ~R, C2~P RQ,8/17/2019,51,定理 设C1和C2是两个基子句, RC1, C2 是C1,C2的归结式,则RC1, C2是C1和C2的逻辑结果。 证明 设 C1L C1’, C2~LC2’。于是 RC1, C2 =C1’ C2’ 设I是C1和C2的一个解释,且满足C1也满足C2。因为L和~L中有一个在I下为假,不妨设为L。于是C1’非空,且在I下为真。故RC1, C2在I下为真。,命题逻辑归结方法的可靠性,8/17/2019,52,归结演绎,定义(归结演绎) 设S是子句集。从S推出子句C的一个归结演绎是如下一个有限子句序列 C1,C2,,Ck 其中Ci或者是S中子句,或者是Cj和Cr的归结式 ji, r i; 并且Ck=C。 称从子句集S演绎出子句C,是指存在一个从S推出C的演绎。 定理 若从子句集S可以演绎出子句C,则C是S的逻辑结果。 推论 若子句集S是可满足的, 则S推出的任意子句也是可满足的。,8/17/2019,53,,定义 从S推出空子句的演绎称为一个反驳(反证) ,或称为S的一个证明。 结论若从基子句集S可演绎出空子句,则S是不可满足的。 演绎树从子句集S出发,通过归结原理可得到一个向下的演绎树,其每个初始节点上附着一个S中子句,每个非初始节点上附着一个其前任节点上子句的归结式。,8/17/2019,54,例. S{PQ, ~PQ, P~Q, ~P~Q },归结演绎 1 PQ 2 ~PQ 3 P~Q 4 ~P~Q 5 Q 由1、2 6 ~Q 由3、4 7  由5、6,8/17/2019,55,归结原理一般过程,1建立子句集S。 2如果S含空子句,则结束。 3从子句集S出发,仅对S的子句间使用归结推理规则。 4如果得出空子句,则结束。 5将所得归结式仍放入S中。 6对新的子句集使用归结推理规则。转4。,8/17/2019,56,例.证明P Q Q  p,首先建立子句集 S{PQ, Q , P} 归结演绎 1 P Q 2 Q 3 P 4 P 12归结 5  34归结,8/17/2019,57,命题逻辑归结原理的完备性,定理 如果基子句集S是不可满足的, 则存在从S推出空子句的归结演绎。 证明 设M是S的原子集,对M的元素数|M|用归纳法。 当|M|1时,设原子为P。 若∈S ,得证。 否则,因为S是不可满足的,于是,S中必包含单元子 句P和~P,而P和~P的归结式是,所以存在从S推出的 归结演绎。 假设|M|n n≥2 时,定理成立。往证 |M|=n时定理成立。,8/17/2019,58,,取M中任意一原子P,做如下两个子句集 S’将S中所有含P的子句删除,然后在剩下的子 句中删除文字~P; S”将S中所有含~P的子句删除,然后在剩下的 子句中删除文字P。 显然,S’和S”都不可满足,且它们的原子集的元 素数都小于n。根据归纳假设,存在从S’推出  的 归结演绎D1,从S”推出的归结演绎D2。,8/17/2019,59,,S{P∨C1’, ,P∨Ci’ , ~P∨Ci1’, ,~P∨Cj’, Cj1 , , Cn} S’{Ci1’, ,Cj’,Cj1 , , Cn} S’’{C1’, ,Ci’ , Cj1 , , Cn} 例 S{PQ, P~Q, ~PR, ~ R} M{P,Q,R},8/17/2019,60,,在D1中,将S’中所有不是S中的子句,通过 添加文字~P而恢复成S中子句,于是,得到从S 推出  或者~P的归结演绎D1’。 用同样方法从D2可得一个从S推出  或者P的 归结演绎D2’。 显然,从D1’和D2’就不难得到一个从S推出  的 归结演绎D。 归纳法完成。,8/17/2019,61,,Resolution Principle 两种译法 归结原理从内部看 刘叙华,一种新的语义归结原理,吉林大学学报,1978。 消解原理从外部看 马希文,机器证明及其应用,计算机应用, 1978。,8/17/2019,62,6.3 合一算法,,8/17/2019,63,,例1 C1Px  Qy C2Pa  Rz 例2 C1Px  Qx C2Pfx  Rx 替换和合一是为了处理谓词逻辑中子句之间的模式匹配而引进.,8/17/2019,64,一、替换与最一般合一替换,定义替换一个替换是形如{t1/v1, , tn/vn }的一个有限集合,其中vi是变量符号,ti是不同于vi的项。并且在此集合中没有在斜线符号后面有相同变量符号的两个元素,称ti为替换的分子,vi为替换的分母。 例. {a/x, gy/y, fgb/z}是替换; {x/x}, {y/fx}, {a/x, gy/y, fgb/y}不是替换; 基替换当t1,,tn是基项时,称此替换为基替换。 空替换没有元素的替换称为空替换,记为。,8/17/2019,65,替换,定义(改名) 设替换  { t1/x1, , tn/xn } 如果t1, , tn是不同的变量符号,则称为一个改 名替换,简称改名。 替换作用对象表达式(项、项集、原子、原子集、 文字、子句、子句集) 基表达式没有变量符号的表达式。 子表达式出现在表达式E中的表达式称为E的子 表达式。,8/17/2019,66,E的例,定义(E的例) 设  { t1/v1, , tn/vn }是一个替换,E是一个表达式。将E中出现的每一个变量符号,vi 1 i n ,都用项ti替换,这样得到的表达式记为E。称E 为E的例。 若E 不含变量,则E 为E的基例。 例. 令  {a/x, fb/y, c/z},EPx, y, z 于是E的例(也是E的基例)为 E Pa, fb, c,,8/17/2019,67,,练习 EPx, gy, hx,z, {a/x, fb/y, gw/z} EPa, gfb, ha,gw EPx, y, z, {y/x, z/y} EPy, z, z. EPz, z, z.,8/17/2019,68,替换的乘积,定义(替换的乘积)设 { t1/x1, , tn/xn }, { u1/y1, , um/ym} 是两个替换。将下面集合 { t1/x1, , tn/xn , u1/y1, , um/ym } 中任意符合下面条件的元素删除 1)ui/yi,当yi{x1, , xn }时; 2)ti/xi,当ti xi 时。 如此得到一个替换,称为与的乘积,记为 。 例. 令  {fy/x, z/y}  {a/x, b/y, y/z} 于是得集合 { t1/x1, t2/x2 , u1/y1, u2/y2 , u3/y3 } {fb/x, y/y, a/x, b/y, y/z }  与的乘积为   {fb/x, y/z },8/17/2019,69,,{a/x}, {b/x} {a/x} {b/x} 可见  ,8/17/2019,70,,例子 EPx, y, z {a/x, fz/y, w/z} EPa, fz, w {t/z, gb/w} EPa, ft, gb {a/x, ft/y, gb/z,gb/w} EPa, ft, gb,8/17/2019,71,引理 若E是表达式,,是两个替换, 则E   E,证明 设vi是E中任意一个变量符号,而  { t1/x1, , tn/xn },  { u1/y1, , um/ym } 若vi既不在{ x1, , xn }中,也不在{ y1, , ym }中,则vi在E  中和在E中都不变。 若vixj 1jn,则E中的vi,在E中先变成tj,然后再变成tj;E中的vi在E中立即就变成了tj。故E中vi在E中和在E中有相同变化。 若viyj 1jm,且yj{ x1,,xn },则E中vi在E中变为uj;E中vi在E中也变为uj注意yj{x1,, xn},所以uj/yj),故E中vi在E中和在E 中有相同变化。 由于vi的任意性,故引理得证。,8/17/2019,72,引理 设,, 是三个替换, 于是=,证明 设E是任一表达式,由上面引理知 E E E E E  E 所以 E E 由于E的任意性,故 =,8/17/2019,73,,定义合一称替换是表达式集合{E1,,Ek}的 合一,当且仅当E1=E2Ek。 表达式集合{E1, , Ek}称为可合一的,如果存在关于此集合的一个合一。 定义最一般合一 表达式集合{E1, , Ek}的合一 称为是最一般合一most general unifier, 简写为mgu,当且仅当对此集合的每一个合一,都存在替换,使得 =,8/17/2019,74,,例. 表达式集合{Pa, y, Px, fb}是可合一的,其最一般合一={a/x, fb/y}。显然,这也是此集合的mgu。 表达式集合{Pa, b, Px, fb}是否可合一 例. 表达式集合{Px, Pfy}是可合一的,其最一般合一={fy/x} ={fa/x, a/y}也是合一,有替换 {a/y},使 ={fy/x}{a/y},8/17/2019,75,,例 S{Px  Qx,Py, Qb} {Px,Py}可合一,={a/x, a/y}是合一, 其mgu ={x/y},有替换 {a/x},使 = {x/y} {a/x},8/17/2019,76,二、合一算法,定义(差异集合) 设W是非空表达式集合,W的差异集合是如下一个集合首先找出W的所有表达式中不是都相同的第一个符号,然后从W的每一个表达式中抽出占有这个符号位置的子表达式。所有这些子表达式组成的集合称为这步找到的W的差异集合D。,8/17/2019,77,W不可合一的三种情况,(1)若D中无变量符号为元素,则W是不可合一的。 例. W{Pfx, Pgx} D{fx, gx} (2)若D中有奇异元素和非奇异元素,则W是不可合一的。 例. W{Px, Px, y} D{⊙, y} (3)若D中元素有变量符号x和项t,且x出现在t中,则W是不可合一的。 例. W{Px, Pfx} D{x, fx},8/17/2019,78,,换名 {Pfx, x, Px, a}; 如果不换名D{fx, x}. 换名 {Pfy, y, Px, a}; mgu {fa/x, a/y},8/17/2019,79,步骤1置 k0, WkW, k 步骤2若Wk只有一个元素,则停止,k是W的最一般合一; 否则,找出Wk的差异集合Dk。 步骤3若Dk非奇异,Dk中存在元素vk和tk,其中vk是变量符号,并且 不出现在tk中,则转步骤4; 否则,算法停止,W是不可合一的。 步骤4令 k1k{tk/vk},Wk1Wk (注Wk1W ) 步骤5置 kk1,转步骤2。,合一算法(Unification algorithm),,,8/17/2019,80,例. 令 W{Qfa, gx, Qy, y}, 求W的mgu。,步骤1 k0, W0W, 0。 步骤2 D0 {fa, y}。 步骤3有v0 y D0,v0不出现在t0=fa中。 步骤4令 10{t0/v0}{fa/y}, W1{Qfa, gx, Qfa, fa} 步骤5kk11 步骤2 D1 {gx, fa }。 步骤3D1中无变量符号,算法停止,W不可合一。 若令W{Qfa, gx, Qy, z}, W是否可合一,8/17/2019,81,例 令 W {Pa, x, fgy, Pz, fz, fu}, 求出W的mgu。,,步骤1k0,W0W, 0 。 步骤2 D0 {a, z}。 步骤3有v0 z D0,v0不出现在t0=a中。 步骤4令 10{t0/v0}{a/z}{a/z}, W1W0{t0/v0}{Pa,x,fgy,Pz,fz,fu}{a/z}{Pa,x,fgy,Pa,fa,fu} 步骤5kk11 步骤2 D1 {x, fa }。 步骤3有v1 x D1,且v1不出现在t1=fa中。 步骤4令 21{t1/v1}{a/z} { fa/x }{a/z, fa/x }, W2W1{t1/v1}{Pa,x,fgy,Pa,fa,fu}{fa/x} {Pa,fa,fgy,Pa,fa,fu},8/17/2019,82,例.,步骤5

    注意事项

    本文(人工智能第六章教学课件.pptx)为本站会员(小旋风)主动上传,工友文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知工友文库(发送邮件至gydoc@qq.com或直接QQ联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    copyright@ 2019-2022 工友文库网站版权所有
    经营许可证编号:鲁ICP备19032292号-1


    1
    收起
    展开