




已阅读5页,还剩38页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
计算引论,第四章推理与计算,4推理与计算,预备知识Horn逻辑程序命题Horn逻辑中的自动推理谓词Horn逻辑中的自动推理,4.1预备知识,考虑到读者已学习数理逻辑,基本熟悉相关概念和知识,下面我们简单给出有关逻辑推理的基本概念。因为篇幅所限,为理解更加形象,概念定义形式未必采用数理逻辑中严格定义形式,准确概念请参见离散数学数理逻辑部分。,命题,在一阶逻辑中,命题陈述某个对象的性质,或是某些对象的关系。陈述的形式是作为n元函数的“谓词”与它的变量“项”。例如命题“鸟会飞”表示为canfly(bird),其中“canfly”是谓词,“bird”是项。,项,项是指某个命题的“对象”或是“客体”。如下递归定义“项”i单个的常量和变量都是项。ii如果f是函数符,t1,tn是项,那么f(t1,tn)也是项。例如,gcd是表示最大公约数的函数符,a+b,cd-2是两个项,则gcd(a+b,cd-2)也是项。,原子,若P是一个n元谓词符号,t1,tn是项,那么P(t1,tn)是原子例如,father是表示父子关系的二元谓词,则father(John,Peter)是原子,表示John是Peter的父亲。这里father(John,Peter)做为基本二元关系。,公式,如下递归定义“公式”i原子是公式ii若P,Q是公式,则PQ,PQ,PQ,P是公式iii若P是公式,x是P中的变量,则(x)P,(x)P是公式。,文字和子句,若P是原子,则P,P称为文字。P称为正文字,P称为负文字。公式P称为子句,若P等值于L1Ln,其中L1,Ln是文字。没有变量符号出现的项、原子、子句,分别称为基项、基原子、基子句。,文字和子句(续),例如,gcd(45,b)是基项father(John,Peter)是基原子father(John,Peter)uncle(John,Peter)是基子句,Skolem标准型,上面定义的公式,形式是很多样的。这就会给机器的形式化处理带来很大的麻烦。为了便于机器处理,需要把公式化成统一的标准形式,即SKOLEM标准型,进而建立子句集。,Skolem标准型(续),设P是公式,P等价于x1xnG(x1.xn),并且GG1Gm,其中G1,Gm都是子句,则称G的子句集S=G1,Gm为公式P的Skolem标准型。,Skolem标准型(续),对公式P的SKOLEM化的步骤如下:(1)将P化为前束范式(Q1x1)(Qnxn)H(x1.xn)其中Q1Qn是存在量词或者全称量词,并将H化为合取范式的形式;,Skolem标准型(续),(2)用如下方法消去存在量词:i)若Qi是一个存在量词,并且它的左边没有全称量词,则用一个H中没有的常量符号代替H中所有的xi,之后消去(Qixi),Skolem标准型(续),ii)若Qi是一个存在量词,并且Qj1,Qjk是Qi左边的全称量词,则取一个H中没有的函数k元符号f,用f(xj1,xjk)代替xi,之后消去(Qixi)。,Skolem标准型(续),公式P经过如上处理,可以化为x1xn(G1Gm)的形式,其中G1,Gm都是子句。省略全称量词,再用“,”取代合取符号,便得到公式P的Skolem标准型G1,Gm。,Skolem标准型(续),由以上可知,任意公式都有与之相对的子句集。子句集的形式是相对简单的。需要注意的是,一个公式与它的Skolem标准型未必等值,但在不可满足的意义上是一致的。,Horn子句与Horn逻辑程序,如果在一个子句中最多含有一个正文字,那么该子句称为Horn子句。若一个子句集内的子句个数有限且都是Horn子句,那么该子句集称为一个Horn逻辑程序。,替换,一个替换是形如t1/x1,tn/xn的一个有限集合。其中xi(i=1,n)是两两不同的变量符号,ti是不同于xi的项。替换可以如下作用于一个表达式:给定替换=t1/x1,tn/xn和表达式E,E表示将E中出现的每一个xi(i=1,n)都替换成ti得到的新表达式。,替换(续),给定两个替换=t1/x1,tn/xn=u1/y1,um/ym将集合t1/x1,tn/xn,u1/y1,um/ym删去以下元素:ui/yi,当yix1,xnti/xi,当ti=xi得到的新替换表示为,称为和的复合。,合一替换,给定表达式E1,Ek,若存在替换,使得E1=Ek,则称是E1,Ek的一个合一替换。,合一替换(续),例1,设E1=g(x,y),E2=g(a,f(z)。令=a/x,f(h(u)/y,h(u)/z,则E1=g(a,f(h(u),E2=g(a,f(h(u)因为E1=E2,所以是E1与E2的合一替换。,合一替换(续),例2,设E1与E2同上,=a/x,f(z)/y,则E1=g(a,f(z)=E2,所以也是E1与E2的合一替换。显然比简单,易证=,其中=h(u)/z,4.2Horn逻辑程序,在知识工程中,知识要作为数据按一定格式存放在数据库中。已知的知识表示方法有产生式表示法语义网络表示法逻辑表示法产生式表示法是一类很重要的方法,知识表示成IFTHEN的形式。采用产生式方法,可以将规则与事实以统一的格式表示,即Horn子句。,4.2Horn逻辑程序,Horn子句可以表示成如下形式:规则体规则头其中规则体一般是n个原子的合取,n=0,1,。规则头可以是单个原子,也可以是空。,4.2Horn逻辑程序,在Horn逻辑程序自动推理时用到如下概念:规则:规则体非空且规则头非空的子句。例如,father(z,y),father(y,x)grandfather(z,x)事实:规则体空且规则头非空的子句。例如,father(John,Peter)。目标:无规则头的子句,例如,grandfather(Smith,Peter),即要查询Smith是否是Peter的祖父?,4.2Horn逻辑程序,一个Horn逻辑程序是Horn子句的集合,也就是规则和事实的集合。因此,一个Horn逻辑程序相当于一个知识库。知识库应当具有自动推理的能力。所谓推理,实际上是通过对一组子句按照一定的方式进行消解最终得到新的公式。,4.2Horn逻辑程序,自动推理的过程即给定目标子句,机器按照一定的顺序对逻辑程序中的子句进行消解,最后得到目标子句,或者得出目标不可满足的结论。,4.2Horn逻辑程序,因为Horn子句结构特殊,Horn逻辑程序上的消解过程简单。下面分别在命题Horn逻辑和谓词Horn逻辑情形下给出消解过程。,4.3命题Horn逻辑中的自动推理,在命题Horn逻辑中,子句之间可以按照如下的方式消解。若有子句S1:A1,AnS2:B1,BmAi则归结后的子句为S3:A1,Ai-1,B1,Bm,Ai+1,An即利用规则S2将原目标S1转化为新目标S3.,4.3命题Horn逻辑中的自动推理,基于上述消解方式,求证一个目标S:A1,An需要逐一以S的体中的每一个原子Ai作为新的目标进行求证。A1,An也称为S的子目标。在以一个原子Ai为目标进行求证时,考察子句集内所有头部是Ai的子句,以此子句的体作为新的目标。,4.3命题Horn逻辑中的自动推理,当某个关于A的子句体部的所有原子得到满足时,直接返回A是正确的,而不用再接着考察头是A的其他子句。假如对于某个原子A,逻辑程序中所有头部是A的子句都无法满足,则得出A无法满足的结论。,原子A的推理算法TorF(A)如下:TorF(A)i=0;while(in)/n是此Horn逻辑程序内子句的个数if(第i条规则的头部=A)/用第i条规则考察Aif(第i条规则的体是空的)thenreturn1;/A是事实elseif(TorF(A1)=TorF(Am)=1)/A1Am是第i条规则体内的所有原子thenreturn1;/由i规则推出原子A的正确i=i+1;/第i条规则体内并非所有原子正确,从而需要考察别的规则return0;/考察了所有的规则,都不能推出A,4.4谓词Horn逻辑中的自动推理,因为涉及到量词,谓词Horn逻辑的消解要复杂一些。消解方式如下。若有子句S1:A1,AnS2:B1,BmB,并且Ai,B具有合一替换,则归结后的子句为S3:(A1,Ai-1,B1,Bm,Ai+1,An)与命题Horn逻辑相比,需要考虑项的匹配,即合一问题。,4.4谓词Horn逻辑中的自动推理,基于以上消解方式,求证一个目标S1:A1,An时,要求得出的结果应该是一个替换的集合。集合内的每一个元素i应该使A1i,Ani成立。,4.4谓词Horn逻辑中的自动推理,在以一个原子Ai为目标进行考察时,考察每一个头部是Ai的子句,以此子句的体作为新的目标。返回的不是0(假)或者1(真),而应是一个替换的集合。为此先要给出替换算法Substitution以及求表达式合一算法Unify。,4.4谓词Horn逻辑中的自动推理,将替换作用于表达式e的算法如下Substitution(e,)if(e是常量符号)thenreturne;if(e是变量符号x)thenif(t/x)thenreturntelsereturne;if(e=f(t1,tn)thent1=Substitution(t1,);tn=Substitution(tn,)returnf(t1,tn),4.4谓词Horn逻辑中的自动推理,对两个表达式e1,e2作合一的算法如下/算法返回一个合一替换或“无法合一”的信息Unify(e1,e2)=空集;ife1是变量符号xthen=e2/x;elseife2是变量符号xthen=e1/x;elseif(e1是常量而e2不是,或e2是常量而e1不是,或e1,e2是两个不同的常量)thenreturn“无法合一”else/此时e1,e2形如f(t1,tn)和g(s1,sm);f,g为函数符号。,4.4谓词Horn逻辑中的自动推理,if(fg)thenreturn“无法合一”;else1=Unify(t1,s1);=1;2=Unify(Substitution(t2,),Substitution(s2,);=2;n=Unify(Substitution(tn,),Substitution(sn,);=n;return;,4.4谓词Horn逻辑中的自动推理,例:Horn逻辑程序(知识库)如下,father(z,y),father(y,x)grandfather(z,x),father(John,Peter),father(Smith,John)。目标为grandfather(Smith,Peter),即查询Smith是否是Peter的祖父?,4.4谓词Horn逻辑中的自动推理,推理过程如下;1.首先通过合一替换=Peter/x,Smith/z,将目标与知识库中第一条规则的规则头匹配,得到新目标father(Smith,y),father(y,Peter)2.考察知识库中第二条和第三条规则,通过合一替换=John/y与知识库中的事实匹配father(Smith,John),father(John,Peter)因此查询目标成立,并且返回替换=Peter/x,John/y,Smith/z,4.4谓词Horn逻辑中的自动推理,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025新能源行业品牌建设与市场推广策略研究报告:深度分析
- 四年级数学(简便运算)计算题专项练习与答案
- 自考专业(法律)模拟试题及参考答案详解1套
- 重难点自考专业(学前教育)【新题速递】附答案
- 2025年工业互联网平台光通信技术升级与光纤通信网络智能运维研究报告
- 重难点解析鲁教版(五四制)8年级数学下册试题【考试直接用】附答案详解
- 重难点解析四川遂宁市第二中学7年级下册数学期末考试专项攻克试卷(解析版)
- 自考专业(公共关系)常考点试卷及答案详解【历年真题】
- 自考专业(计算机网络)高分题库附参考答案详解【黄金题型】
- 化妆品行业-产品成分分析与配方优化
- 乡镇卫生院服务能力调查表
- 景区旅游安全风险评估报告
- 2024-2025学年人教版(2024)七年级英语上册 教学计划
- 顺丰快递员工入职合同范本
- DL-T 1476-2023 电力安全工器具预防性试验规程
- 常用急救药品课件
- 幼儿园食品安全培训内容资料
- 人教部编版语文八年级上册第一单元分层作业设计12
- 美发服务礼仪培训课件
- 人教版小学一至六年级英语单词汇总表
- 《生理性止血》课件
评论
0/150
提交评论