3-人工智能经典逻辑推理剖析优秀PPT.ppt
《3-人工智能经典逻辑推理剖析优秀PPT.ppt》由会员分享,可在线阅读,更多相关《3-人工智能经典逻辑推理剖析优秀PPT.ppt(104页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、人工智能Artificial Intelligence主讲:杨利英主讲:杨利英西安电子科技高校西安电子科技高校E_mail:yangliying1208163 第三章第三章 经典逻辑推理经典逻辑推理3.1 基本概念基本概念3.2 自然演绎推理自然演绎推理3.3 归结演绎推理归结演绎推理3.4 与或形演绎推理与或形演绎推理3.1 基本概念3.1.1 什么是推理什么是推理所谓推理就是按某种策略由已知推断所谓推理就是按某种策略由已知推断推出另一个推断的思维过程。推出另一个推断的思维过程。在人工智能中,推理是由程序实现的,称在人工智能中,推理是由程序实现的,称为推理机。为推理机。3.1.2 推理方式及
2、其分类1.演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理演绎推理:从一般到特殊。例如三段论。演绎推理:从一般到特殊。例如三段论。归纳推理:从个体到一般。归纳推理:从个体到一般。默认推理:缺省推理,在学问不完全状况下默认推理:缺省推理,在学问不完全状况下假设某些条件已经具备所进行的推理。假设某些条件已经具备所进行的推理。2.确定性、不确定性推理确定性、不确定性推理3.1.2 推理方式及其分类3.单调推理、非单调推理单调推理、非单调推理推出的结论是否单调增加推出的结论是否单调增加 5.基于学问的推理(专家系统)基于学问的推理(专家系统)、统计、统计推理、直觉推理(常识性推理)推理、直觉推
3、理(常识性推理)4.启发式、非启发式推理启发式、非启发式推理 所谓启发性学问是指与问题有关且能加所谓启发性学问是指与问题有关且能加快推理进程、求得问题最优解的学问。快推理进程、求得问题最优解的学问。3.1.3 推理的限制策略推理的限制策略主要包括:推理方向、推理的限制策略主要包括:推理方向、搜寻策略、冲突消解策略、求解策略及搜寻策略、冲突消解策略、求解策略及限制策略。限制策略。1.正向推理正向推理(数据驱动推理)基本思想:从用户供应的初始已知事实动身,在学问库基本思想:从用户供应的初始已知事实动身,在学问库KB中找出当前可适用的学问,构成可适用的学问集中找出当前可适用的学问,构成可适用的学问集
4、KS,然,然后按某种冲突消解策略从后按某种冲突消解策略从KS中选出一条学问进行推理,中选出一条学问进行推理,并将推出的新事实加入到数据库并将推出的新事实加入到数据库DB中,作为下一步推理中,作为下一步推理的已知事实。在此之后,再在学问库中选取可适用的学问的已知事实。在此之后,再在学问库中选取可适用的学问进行推理。如此重复进行这一过程,直到求得所要求的解。进行推理。如此重复进行这一过程,直到求得所要求的解。正正向向推推理理示示意意图图2 逆向推理基本思想基本思想 首先选定一个假设目标,然后找寻支持该假设首先选定一个假设目标,然后找寻支持该假设的证据,若所需的证据都能找到,则说明原假的证据,若所需
5、的证据都能找到,则说明原假设是成立的;若找不到所须要的证据,则说明设是成立的;若找不到所须要的证据,则说明原假设不成立,此时须要另作新的假设。原假设不成立,此时须要另作新的假设。逆向推理示意图逆向推理示意图 动物识别的例子动物识别的例子(正向推理正向推理)已知事实:一动物已知事实:一动物有毛,吃草,黑条纹有毛,吃草,黑条纹nR1:动物有毛动物有毛 哺乳类哺乳类 nR2:动物产奶动物产奶 哺乳类哺乳类 nR3:哺乳类哺乳类 吃肉吃肉 食肉类食肉类 nR4:哺乳类哺乳类 吃草吃草 有蹄类有蹄类 nR5:食肉类食肉类 黄褐色黄褐色 有斑点有斑点 猎狗猎狗 nR6:食肉类食肉类 黄褐色黄褐色 黑条纹黑
6、条纹 虎虎 nR7:有蹄类有蹄类 长脖长脖 长颈鹿长颈鹿 nR8:有蹄类有蹄类 黑条纹黑条纹 斑马斑马3.1.3 推理的限制策略3.混合推理混合推理先正向推理后逆向推理先正向推理后逆向推理先逆向推理后正向推理先逆向推理后正向推理4.双向推理双向推理正向推理与逆向推理同时进行,且在推理过程中正向推理与逆向推理同时进行,且在推理过程中的某一步上的某一步上“碰头碰头”。5.求解策略求解策略只求一个解,还是求全部解以及最优解。只求一个解,还是求全部解以及最优解。6.限制策略限制策略限制搜寻的深度、宽度、时间、空间等等。限制搜寻的深度、宽度、时间、空间等等。模式匹配是指对两个学问模式模式匹配是指对两个学
7、问模式(例如两例如两个谓词公式、框架片断、语义网络片断个谓词公式、框架片断、语义网络片断)进行比较,检查这两个学问模式是否进行比较,检查这两个学问模式是否完全一样或者近似一样。完全一样或者近似一样。3.1.4 模式匹配模式匹配可分为模式匹配可分为确定性匹配确定性匹配与与不确定性匹配不确定性匹配。3.1.4 模式匹配确定性匹配是指两个学问模式完全一样,或者确定性匹配是指两个学问模式完全一样,或者经过变量代换后变得完全一样。经过变量代换后变得完全一样。学问:学问:IF father(x,y)and man(y)THEN son(y,x)事实:事实:father(李四,李小四李四,李小四)and m
8、an(李小四李小四)不确定性匹配是指两个学问模式不完全一样,不确定性匹配是指两个学问模式不完全一样,但是它们的相像程度又在规定的限度内。但是它们的相像程度又在规定的限度内。变量代换(置换)定义定义 代换是一个形如代换是一个形如t1/x1,t2/x2,tn/xn的有限集合。的有限集合。其中其中t1,t2,tn是项(常量、变量、函数);是项(常量、变量、函数);x1,x2,xn是(某一公式中)互不相同的变元;是(某一公式中)互不相同的变元;ti/xi表示用表示用ti代换代换xi 不允许不允许ti与与xi相同,也不允许变元相同,也不允许变元xi循环地出现在循环地出现在另一个另一个tj中。中。例如:例
9、如:a/x,f(b)/y,w/z是一个代换是一个代换g(y)/x,f(x)/y不是代换不是代换g(a)/x,f(x)/y是代换是代换令令=t1/x1,t2/x2,tn/xn为一个代换,为一个代换,F为表达为表达式,则式,则F表示对表示对F用用ti代换代换xi后得到的表达式。后得到的表达式。F称为称为F的特例。的特例。规则规则:IF father(x,y)and man(y)THEN son(y,x)事实事实:father(李四,李小四李四,李小四)and man(李小四李小四)F=father(x,y)man(y)=李四李四/X,李小四李小四/Y F=father(李四,李小四李四,李小四)m
10、an(李小四李小四)结论结论:son(李小四李小四,李四李四)代换的复合定义定义 设设=t1/x1,t2/x2,tn/xn=u1/y1,u2/y2,um/ym是两个代换,则这两个代换的复合也是一个代换,它是是两个代换,则这两个代换的复合也是一个代换,它是从从t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,um/ym中删去如下两种元素:中删去如下两种元素:ti/xi当当ti=xiui/yi当当yix1,x2,xn后剩下的元素所构成的集合,记为后剩下的元素所构成的集合,记为。注注(1)ti表示对表示对ti运用运用进行代换。进行代换。(2)就是对一个公式就是对一个公式F先运用先运用进行代
11、换,然后再运进行代换,然后再运用用进行代换:进行代换:F()=(F)代换复合的例子例如,设有代换例如,设有代换=f(y)/x,z/y=a/x,b/y,y/z则则=?=f(y)/x,z/y,a/x,b/y,y/z =f(b)/x,y/y,a/x,b/y,y/z =f(b)/x,y/z公式集的合一定义定义 设有公式集设有公式集F=F1,F2,Fn,若存在一,若存在一个代换个代换使得使得F1=F2=Fn则称则称为公式集为公式集F的一个合一,且称的一个合一,且称F1,F2,Fn是可合一的。是可合一的。例如,设有公式集例如,设有公式集F=P(x,y,f(y),P(a,g(x),z)则下式是它的一个合一:
12、则下式是它的一个合一:=a/x,g(a)/y,f(g(a)/z一个公式集的合一一般不唯一一个公式集的合一一般不唯一。最一般合一定义定义 设设是公式集是公式集F的一个合一,假如对任的一个合一,假如对任一个合一一个合一都存在一个代换都存在一个代换,使得,使得=则称则称是一个最一般的合一。是一个最一般的合一。最一般合一是唯一的最一般合一是唯一的。求取最一般合一差异集差异集:两个公式中相同位置处不同符号的集合。:两个公式中相同位置处不同符号的集合。例如:例如:F=F1:P(x,y,z),F2:P(x,f(a),h(b)则则D1=y,f(a),D2=z,h(b)求取最一般合一的算法:求取最一般合一的算法
13、:1.令令k=0,Fk=F,k=,是空代换。是空代换。2.若若Fk只含一个表达式,则算法停止,只含一个表达式,则算法停止,k就是最一般合一。就是最一般合一。3.找出找出Fk的差异集的差异集Dk。4.若若Dk中存在元素中存在元素xk和和tk,其中其中xk是变元,是变元,tk是项,且是项,且xk不在不在tk中出现,则置:中出现,则置:Fk+1=Fktk/xkK+1=ktk/xkk=k+1然后转然后转(2)。若不存在这样的。若不存在这样的xk和和tk则算法停止。则算法停止。5.算法终止,算法终止,F的最一般合一不存在。的最一般合一不存在。求取最一般合一的例子求公式集求公式集 F=P(a,x,f(g(
14、y),P(z,f(z),f(u)的最一般合一。的最一般合一。求取最一般合一的例子F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一的过程:求其最一般合一的过程:1.令令F0=F,0=。F0中有两个表达式,所以中有两个表达式,所以0不是最一般合一。不是最一般合一。2.差异集:差异集:D0=a,z。代换:代换:a/z3.F1=F0 a/z=P(a,x,f(g(y),P(a,f(a),f(u)。1=0a/z=a/zwD1=x,f(a)。代换:代换:f(a)/xwF2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u)。2=1f(a)/x=a/z,f(a)
15、/x D2=g(y),u。代换:代换:g(y)/uF3=F2g(y)/u=P(a,f(a),f(g(y),P(a,f(a),f(g(y)。3=2g(y)/u=a/z,f(a)/x,g(y)/u 至此,求得最一般合一至此,求得最一般合一 a/z,f(a)/x,g(y)/u 3.1.5 冲突消解策略冲突:多个学问都匹配成功。冲突:多个学问都匹配成功。正向推理:正向推理:多条产生式前件都与已知事实匹配成功多条产生式前件都与已知事实匹配成功逆向推理:逆向推理:多条规则后件都和同一个假设匹配成功多条规则后件都和同一个假设匹配成功冲突消解的基本思想都是对学问进行排序。冲突消解的基本思想都是对学问进行排序。
16、几种冲突消解策略1.按针对性排序按针对性排序2.优先选用针对性强的产生式规则。优先选用针对性强的产生式规则。3.按已知事实的簇新性排序按已知事实的簇新性排序4.优先选用与较多新事实匹配的规则。优先选用与较多新事实匹配的规则。5.按匹配度排序按匹配度排序6.在不确定性匹配中,计算两个学问模式的相像度在不确定性匹配中,计算两个学问模式的相像度(匹配度匹配度),并对其排序,相像度高的规则先推。,并对其排序,相像度高的规则先推。7.按领域问题特点排序按领域问题特点排序8.按上下文限制排序按上下文限制排序9.把规则依据下上文分组,并只能选取组中的规则。把规则依据下上文分组,并只能选取组中的规则。10.按
17、冗余限制排序按冗余限制排序11.冗余学问越少的规则先推。冗余学问越少的规则先推。12.按条件个数排序按条件个数排序13.条件少的规则先推。条件少的规则先推。3.2 自然演绎推理从从一一组组已已知知为为真真的的事事实实动动身身,干干脆脆运运用用经经典典逻逻辑辑的的推推理理规规则则推推出出结结论论的的过过程程,称称为为自自然然演演绎绎推推理理。其其中中,基基本本的的推推理理规规则则是是P规规则则、T规规则则、假假言言推推理理、拒拒取取式推理等。式推理等。假言推理的一般形式假言推理的一般形式拒取式推理的一般形式拒取式推理的一般形式P P规则:在推理的任何步骤都可以引入前提。规则:在推理的任何步骤都可
18、以引入前提。T T规则:推理时,假如前面步骤中有一个或者多规则:推理时,假如前面步骤中有一个或者多个公式永真蕴含公式个公式永真蕴含公式S S,则可把,则可把S S引入推理过程引入推理过程中。中。3.2 自然演绎推理3.3 归结演绎推理归结演绎推理定理证明:要证明定理证明:要证明PQ(PQ)的永真性。的永真性。依据反证法,只要证明其否定依据反证法,只要证明其否定(PQ)不不行满足性即可。行满足性即可。归结:归结:Resolution,也称为消解,消解原理,也称为消解,消解原理海伯伦海伯伦(Herbrand)定理为自动定理证明奠定理为自动定理证明奠定了理论基础;鲁滨逊定了理论基础;鲁滨逊(Robi
19、nson)提出的提出的归结原理使机器定理证明成为现实。归结原理使机器定理证明成为现实。3.3.1 子句子句在谓词逻辑中,把原子谓词公式及其否定在谓词逻辑中,把原子谓词公式及其否定统称为统称为文字文字。如:如:P(x),P(x,f(x),Q(x,g(x)定义:定义:不包含任何文字的子句称为不包含任何文字的子句称为空子句空子句。定义:定义:任何文字的析取式称为任何文字的析取式称为子句子句。例如:例如:P(x)Q(x),P(x,f(x)Q(x,g(x)子句集子句集(1)合取范式:合取范式:C1 C2 C3 Cn(2)子句集子句集:S=C1,C2,C3,Cn(3)任何谓词公式任何谓词公式F都可通过等价
20、关系及推都可通过等价关系及推理规则化为相应的子句集理规则化为相应的子句集S把谓词公式化成子句集的步骤(1)1.利用等价关系消去利用等价关系消去“”和和“”例如公式例如公式可等价变换成可等价变换成2.利用等价关系把利用等价关系把“”移到紧靠谓词的位置上移到紧靠谓词的位置上上式经等价变换后上式经等价变换后3.重新命名变元,使不同量词约束的变元有不同的名字重新命名变元,使不同量词约束的变元有不同的名字上式经变换后上式经变换后把谓词公式化成子句集的步骤(2)4.消去存在量词消去存在量词a.存在量词前面没有全称量词时,则只要用一个新的个体存在量词前面没有全称量词时,则只要用一个新的个体常量替换受该量词约
21、束的变元。常量替换受该量词约束的变元。b.存在量词前面有一个或者多个全称量词时,要用函数存在量词前面有一个或者多个全称量词时,要用函数f(x1,x2,xn)替换受该存在量词约束的变元。替换受该存在量词约束的变元。上式中存在量词上式中存在量词(y)及及(z)都位于都位于(x)的后面,所以须的后面,所以须要用函数替换,设替换要用函数替换,设替换y和和z的函数分别是的函数分别是f(x)和和g(x),则,则替换后得到替换后得到5.把全称量词全部移到公式的左边把全称量词全部移到公式的左边把谓词公式化成子句集的步骤把谓词公式化成子句集的步骤(3)6.利用等价关系把公式化为利用等价关系把公式化为Skolem
22、标准形标准形Skolem标准形的一般形式是标准形的一般形式是其中,其中,M是子句的合取式,称为是子句的合取式,称为Skolem标准形的母式。标准形的母式。上式化为上式化为Skolem标准形后得到标准形后得到7.消去全称量词消去全称量词8.对变元更名,使不同子句中的变元不同名对变元更名,使不同子句中的变元不同名上式化为上式化为9.消去合取词,就得到子句集消去合取词,就得到子句集 子句集的性质子句集的性质(1)子句集中子句之间是合取关系。)子句集中子句之间是合取关系。(2)子句集中的变元受全称量词的约束。)子句集中的变元受全称量词的约束。子句集的意义子句集子句集S的不行满足性:对于随意论域中的的不
23、行满足性:对于随意论域中的随意一个说明,随意一个说明,S中的子句不能同时取得中的子句不能同时取得真值真值T。定理定理 设有谓词公式设有谓词公式F,其子句集为,其子句集为S,则,则F不不行满足的充要条件是行满足的充要条件是S不行满足。不行满足。要证明要证明PQ永真,只需证明公式永真,只需证明公式F=(PQ)永假,即永假,即S P,Q不行满不行满足。足。3.3.2 海伯伦理论(Herbrand)为了推断子句集的不行满足性,须要对全部可能论域上的全为了推断子句集的不行满足性,须要对全部可能论域上的全部说明进行判定。只有当子句集对任何非空个体域上的任何部说明进行判定。只有当子句集对任何非空个体域上的任
24、何一个说明都是不行满足的时候,才可断定该子句集是不行满一个说明都是不行满足的时候,才可断定该子句集是不行满足的。足的。海伯伦构造了一个特殊的论域海伯伦构造了一个特殊的论域(海伯伦域海伯伦域),并证明只要对这个特殊域上的一切说明进行并证明只要对这个特殊域上的一切说明进行判定,就可知子句集是否不行满足。判定,就可知子句集是否不行满足。海伯伦域海伯伦域定义定义 设设S为子句集,则按下述方法构造的为子句集,则按下述方法构造的域域H称为海伯伦域,记为称为海伯伦域,记为H域:域:(1)令令H0是是S中全部个体常量的集合,若中全部个体常量的集合,若S中不包含个体常量,则令中不包含个体常量,则令H0a,其,其
25、中中a为随意指定的一个个体常量。为随意指定的一个个体常量。(2)令令Hi+1=HiS中全部中全部n元函数元函数f(x1,xn)|xj(j=1,n)是是Hi中的元中的元素素,其中,其中i=0,1,2,。海伯伦域的例子例例 求子句集求子句集S=P(x)Q(x),R(f(y)的的H域。域。解:此例中没有个体常量,随意指定一个常量解:此例中没有个体常量,随意指定一个常量a作为个体作为个体常量,得到常量,得到H0=aH1=a,f(a)H2=a,f(a),f(f(a)H3=a,f(a),f(f(a),f(f(f(a)H=a,f(a),f(f(a),f(f(f(a),子句集S在H域上的说明就是对S中出现的常
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 经典 逻辑推理 剖析 优秀 PPT
限制150内