资源描述
,1/4/2020,#,AI,人工智能综合讲义,reserved.,AI人工智能综合讲义,1,状,态空,间,法,猴子和香蕉问题,：,在一个房间内有一只猴子、一个箱 子和一束香蕉。香蕉挂在天花板下方，但猴子的高度,不足以碰到它。那么这只猴子怎样才能摘到香蕉,呢,?,reserved.,状态空间法猴子和香蕉问题：在一个房间内有一只猴子、一个箱 子,2,猴,子和,香,蕉问题,用一个四元表列,（,W,，,x,，,Y,，,z,）,来表示,这,个问,题,状态,W,：猴子的水平位置；,x,：,当猴子在箱子顶上时,取,1,；,否,则,取,0,；,Y,：,箱子的水平位置；,z,：,当猴子摘到香蕉时,取,1,；,否则,取,0,。,初始状态,为,(a,0,b,0),，目标状态为,(c,1,c,1),这个问题的操作（算符）如,下,：,goto,（,U,）表示猴子走到水平,位置,U,pushbox,（,V,）,猴子,把,箱,子,推到,水,平位,置,V,climbbox,猴子爬上箱顶,grasp,猴子摘到香蕉,reserved.,猴子和香蕉问题用一个四元表列（W，x，Y，z）来表示这个问题,3,猴,子和,香,蕉问题,该初始状态变换为目标,状态的操作序列为：,Step1:,goto(b),Step2:,pushbox(c),Step3:,climbbox,Step4:,grasp,reserved.,猴子和香蕉问题该初始状态变换为目标 状态的操作序列为： re,4,猴,子和,香,蕉问题,reserved.,(b,，,1,，,b,，,0),（,c,，,1,，,c,，,1,）,目标状态,（,a,，,0,，,b,，,0,）,goto,（,U,）,（,U,，,0,，,b,，,0,）,U=,b,，,cl,i,mb,b,ox,（,V,，,0,，,V,，,0,）,goto,（,U,）,U=b,pushbox,（,V,）,got,o,（,U,）,U=V,（,U,，,0,，,V,，,0,）,goto,（,U,）,V=,c,，,climb,b,ox,（,c,，,1,，,c,，,0,）,grasp,猴子和香蕉问题(b，1，b，0)（c，1，c，1）（a，0，,5,汉,诺塔,问,题,本,原问,题,本,原问,题,reserved.,与,或,图,CBA,汉诺塔问题本原问题本原问题与或图CBA,6,谓,词逻,辑,法,合式公式（,WFF,，,Well-formed,Formulas,）：,通常把,合,式公式,叫,做,谓词公式,，递归定义如下：,(1),原子谓词公式是合式公式,(2),若,A,为合式公式，,则,A,也是一个合式公式,(3),若,A,B,是合式公式，则,A,B,，,A,B,，,AB,，,AB,也都是合式公式,(4),若,A,是合式公式,，,x,为,A,中,的,自,由,变元,，,则,(,x)A,和,(,x)A,都是合式公式,(5),只有按上述规,则,(1),至,(4),求,得,的,那些,公,式，,才,是,合,式,公式。,reserved.,谓词逻辑法合式公式（WFF，Well-formed Form,7,谓,词逻,辑,法,用谓词公式表示知识时，需要首,先,定义谓,词,，然后再 用,连接,词把有关的谓词连接起来，形成一个谓词公式 表达一个完整的意义。,例,1,：,设有下列知识,刘欢比他父亲出名。,高扬是计算机系的一名学,生,，但,他,不喜,欢,编,程,。,任何整数或者为正或者为,负。,为了用谓词公式表示上述知识，首,先,需要,定,义谓词：,FAMOUS (x,y),:,x,比,y,出名,COMPUTER,(,x,),:,x,是计算机系的,LIKE,(x,y,),:,x,喜,欢,y,reserved.,谓词逻辑法用谓词公式表示知识时，需要首先定义谓词，然后再 用,8,谓,词逻,辑,法,I(x),表示“,x,是,整数,”,P,(x,),表示,“,x,是正数”,N,(,x,),表示,“,x,是,负,数,”,此时可用谓词公式把上述知识表示,为,:,刘欢比他父亲出,名,:,FAMOUS ( liuhuan, father ( liuhuan,),高扬是计算机系的一名学,生,，但,他,不喜,欢,编,程,:,COMPUTER(gaoyang),LIKE(gaoyang,programing),任何整数或者为正或者为,负,:,(,x)(I(x),(P(x),N(x),reserved.,谓词逻辑法I(x)表示“x是整数”,9,谓,词逻,辑,法,例,2,：,用谓词逻辑描述右图中的房子的概念,个,体,：,A ,B,谓,词,：,SUPPORT(,x,y,),：,表,示,x,被,y,支撑着,WEDGE,( x,),：,表,示,x,是楔形块,BRICK(,y,),：,表,示,y,是长方块,其,中,x ,y,是个体变元,，,它们,的,个,体,域,A,B,房子的概念可以表示成一组合,式,谓词,公,式,的,合取,式,：,SUPPORT(A,B),WEDGE(,A,),BRICK( B,),reserved.,谓词逻辑法例2：用谓词逻辑描述右图中的房子的概念,10,谓,词逻,辑,法,若,P,、,Q,是两个合式公式，则由这两个合式公式所组成 的复合表达式可由下列真值表给出。,reserved.,T,T,F,T,T,T,T,T,F,F,T,F,F,F,F,T,T,T,F,T,F,F,F,T,F,F,T,T,谓词逻辑法若P、Q是两个合式公式，则由这两个合式公式所组成,11,语,义网,络,法,可用二元谓,词P(x,y),表,示的,关,系。,其,中，x,y为实 体,，P,为实体之间的关,系,。,单个二元关系可直接用一个,基,本网,元,来表示,对复杂关系，可通过一些相,对,独立,的,二元,或,一,元,关,系的组合来实现。,例如：用语义网络表示,动物能运动、会吃。,鸟是一种动物，鸟有翅膀、,会,飞。,鱼是一种动物，鱼生活在水,中,、会,游,泳。,reserved.,语义网络法可用二元谓词P(x,y)表示的关系。其中，x,y为,12,语,义网,络,法,用语义网络,表示,：,1,）,动,物能,运,动、,会,吃,；,2,）,鸟是,一,种动,物,，鸟,有,翅膀,、,会飞,；,3,）,鱼,是一,种,动物，,鱼生活在水,中、,会,游泳。,AKO,：,A kind,of,reserved.,动物,吃,运动,翅膀,水中,鸟,鱼,飞,游泳,C,a,n,C,a,n,A,KO,L,i,v,e,H,a,v,e,Can,A,KO,Can,语义网络法用语义网络表示：1）动物能运动、会吃；2）鸟是一种,13,语,义网,络,法,例如：用语义网络表示,王强是理想公司的经理； 理想公司在中关村；,王强,28,岁。,reserved.,中关村,理想公司,王强,经理,28,岁,L,o,c,a,ted,-at-,W,o,r,k,-f,o,r,H,e,ad,s,h,i,p,A,ge,语义网络法例如：用语义网络表示中关村理想公司王强经理28岁L,14,语,义网,络,法,例如：,我椅子的颜色是咖啡色的；,椅子包套是皮革；,椅子是一种家具；,座位是椅子的一部分；,椅子的所有者,是,X,X,是个人,reserved.,语义网络法例如：,15,语,义网,络,法,我椅子的颜色是咖啡色的；椅,子,包套,是,皮,革,；椅,子,是一 种家具；座位是椅子的一部分,；,椅子,的,所,有,者,是,X,；,X,是,个人,定义一个语义网络来表示椅子,的,概念,在椅子的基础上进一步具体描,述,：我,的,椅,子,reserved.,FURNITURE,CHAIR,PERSON,SEAT,MY,CHAIR,BROWN,X,LEATHER,ISA,O,W,NER,COL,O,R,IS,A,ISA,ISA,PART,COVERING,椅子的概念,语义网络法我椅子的颜色是咖啡色的；椅子包套是皮革；椅子是一,16,语,义网,络,法,例如：用语义网络表示,李新的汽车的款式是“捷达,”,、银,灰,色。,王红的汽车的款式是“凯越,”,、红,色。,李新和王红的汽车均属于具,体,概,念,可增,加,“汽车,”,这个抽象,概念。,reserved.,捷达,李新,汽车,1,银灰色,人,汽车,交通工具,王红,汽车,2,红色,凯越,B,r,and,O,w,ner,Col,o,r,ISA,ISA,A,KO,Col,o,r,O,w,ner,B,r,and,ISA,ISA,语义网络法例如：用语义网络表示概念。 reserved.捷达,17,语,义网,络,法,增,加,情,况,和,动,作,节点,例如,：,用语义网络表,示,“小燕子从春天到秋天占有一,个巢”,reserved.,小燕子,燕子,鸟,巢,鸟窝,春天,时间,秋天,情况,占有权,占有资格,ISA,A,KO,Sta,r,t,O,w,n,A,KO,A,KO,End,A,KO,A,KO,O,w,ner,A,KO,语义网络法增加情况和动作节点个巢”小燕子燕子鸟巢鸟窝春天时间,18,语,义网,络,法,增,加,情,况,和,动,作,节点,例如,：,用语义网络表,示,“小王给小林一本书”,三元关系,需要设立一个“给”的动作节,点,。动,作,节,点,由一,些,向外,引出的弧来指出动作的主体与,客,体。,reserved.,一本书,小王,给,小林,G,i,ft,R,e,c,e,i,v,er,G,i,v,er,语义网络法增加情况和动作节点一本书小王给小林GiftRece,19,语,义网,络,法,否定的表示：,一般语义关系的否定,：,可通过引进,“非”节,点,来表,例如,：,用语义网络表,示,“小王没有给小林一本书”,reserved.,一本书,小王,给,小林,G,i,ft,R,e,c,e,i,v,er,G,i,v,er,非,语义网络法否定的表示：一本书小王给小林GiftReceive,20,语,义网,络,法,增,加,事,件,节点,例如,：,用语义网络表,示,“,北京大学和清华大学两校篮 球队在北大进行一场比赛的比分,是,85,：,89”,。,三元关系,需要设立一个“球赛”的事件,节,点,引入事件节,点,G25,来表示这场特点,的,球赛,reserved.,清华大学,篮球比赛,G25,85:89,北京大学,VI,S,ITING,TEAM,HOME,TEAM,SCORE,ISA,语义网络法增加事件节点 reserved.清华大学篮球比赛G,21,语,义网,络,法,合取和析取,的,表,示,：,可通过 增加,合取节,点,和,析取节点,来实现,例如：用语义网络表示： “参赛者有教师有学生， 参赛者的身高有高有低”,分析参赛者的不同情况， 可得到以下四种情况：,教师、高；,教师、低；,学生、高；,学生、低,reserved.,人,参赛者,A,B,C,D,或,或,教师,学生,高,低,与,ISA,Pa,r,t,Pa,r,t,Pa,r,t,Pa,r,t,State,State,State,Sta,t,e,语义网络法合取和析取的表示：可通过 增加合取节点和析取节点,22,语,义网,络,法,蕴含,的表示：,通过,增,加蕴含,关,系节,点,来实,现,。在蕴,含,关系,中,，,有,两条,指向蕴含节点的,弧,，一,条,代表,前,提条件,(Antecedent),，标记 为,ANTE,；,另一条代表结,论,(Consequence),，标记,为,CONSE,例如：用,语义网,络,表示,：“如,果,学校,组织大,学,生机,器人竞,赛,活动,，,那么李强就参加比赛”,reserved.,C,O,NSE,A,N,T,E,学校,比赛,活动,机器人,机器人竞赛,蕴含,参加比赛,学生,智能机器,李强,人,Racer,A,KO,Co,n,sti,t,u,t,ion,Manip,u,lat,o,r,ISA,A,KO,A,KO,Joi,n,er,语义网络法蕴含的表示：通过增加蕴含关系节点来实现。在蕴含关系,23,语,义网,络,法,存,在量词,的表,示和,全,称量词,的,表,示,：,例如,：,用语义网络表示：,“每个学生都学习了一门程,序,设计,语,言”,“每个学生都学习了所有的,程,序设,计,课程”,“每个学生都学习,了,C+,语,言”,reserved.,语义网络法存在量词的表示和全称量词的表示：,24,语,义网,络,法,“每个学生都学习了一门程序设计语言”,GS,g,s,r,p,学生,学习,程序语言,ISA,ISA,ISA,F,Subject,O,b,je,c,t,ISA,子空间,GS,：,是一个,概念结,点,，它表示,具有全称量化的一般事件,。,g,：,是一个实例结点，代,表,GS,中的一个具体例,子,，如上所提到的事实。,s,：,是一个,全称变量,，表示任意一个学生。,r,：,是一个,存在变量,，表示某一次学习。,p,：,是一个,存在变量,，表示某一门程序设计语言。,F,：,弧“,F”,说明它所代表的子空间及其具体形式,：,弧,“,”,说明它所代表的全称量词。,reserved.,语义网络法“每个学生都学习了一门程序设计语言”GSgsrp学,25,语,义网,络,法,“每个学生都学习了所有的程序设计课程”,reserved.,学生,学习,程序设计课,g,GS,s,r,p,ISA,ISA,ISA,Subject,O,b,je,c,t,ISA,F,子空间,语义网络法“每个学生都学习了所有的程序设计课程”学生学习程序,26,语,义网,络,法,“每个学生都学习,了,C+,语言”,GS,g,sr,学生,学习,C+,语言,程序语言,ISA,ISA,Subject,O,b,je,c,t,F,ISA,IS,A,子空间,在这种表示方法中，要求子,空,间中,的,所有,非,全称 变量节点都是全称变量的函数,C+是具体的程,序,设计语,言,，不,是,全称,变,量,s,的函,数，应该放在子空间外面,reser,v,ed.,语义网络法“每个学生都学习了C+语言”GSgsr学生学习,27,代,价树,的,广度,优,先搜索,城市交通问题。设,有,5,个城市，它们之间的交通线 路如下方左图所示，图中的数字表示两个城市之间的交通 费用，即代价。用代价树的广度优先搜索，求,从,A,市出发 到,E,市，费用最小的交通路,线,。,D,E,A,4,B,4,C,5,3,2,3,城,市交通,图,代价树的广度优先搜索城市交通问题。设有5个城市，它们之间的交,28,代,价树,的,广度,优,先搜索,城,市交通,图,的代价,树,2,A,B,1,D,1,5,E,1,2,B,C,2,E,3,E,4,3,4,C,1,4,D,2,42,3,3,E,2,5,AB,D,E,4,4,3,C,5,2,3,首先将交通图转化为代价树。具体转化方法如,下：,从起始节点,A,开始，把与它直接相邻的节点作 为它的子节点,对其他节点也做相同的处理,若一个节点已经为某节点的直系先辈节点时，,就不能作为这个节点的子节点。,图中除了起始节点,A,之外，其它节点都可能要 在代价树中出现多次，为了区分它们的多次出 现，分别用下,标,1,2,，,标出,代价树的广度优先搜索城市交通图的代价树2AB1D152BC,29,代,价树,的,广度,优,先搜索,对此代价树进行广度优先搜索，可得,到,最优 解，如图红线部分为最优解，,其,代价,为,8,C,D,E,3,A,4,B,4,5,2,3,2,5,A,D,1,E,1,E,4,3,4,C,1,3,3,E,2,B,1,4,D,2,42,B,2,C,2,E,3,5,代价树的广度优先搜索对此代价树进行广度优先搜索，可得到最优,30,代,价树,的,深度,优,先搜索,(1),把初始节,点,S,放入,OPEN,表中，置,S,的代,价,g(S)=0,；,(2),如果,OPEN,表为空，则问题无,解,，失败退出；,(3),把,OPEN,表的第一个节点取出放,入,CLOSED,表，并,记该节点,为,n,；,(4),考察节,点,n,是否为目标节点。若是，则找到了问题 的解，成功退出；,(5),若节点,n,不可扩展，则转第,(2),步；,(6),扩展节,点,n,，,生成其子节点，,将这些子节点按边代价 由小到大放,入,Open,表的首部,，并为每一个子节点设置,指向父节点的指针。然后转,第,(2),步。,代价树的深度优先搜索(1) 把初始节点S放入OPEN表中，置,31,启,发性,信,息和,估,价函数,用于评估节点重要,性,的函,数,称,为,估价 函数。估价函数的一般形式为：,f(x) =,g(x)+h(x),g(x),表示从初始节,点,S,0,到节,点,x,的代价；,h(x),是从节,点,x,到目标节,点,S,g,的最优路,径,的,代,价,的,估,计,，它体现了问题的启发,性,信息。,h(x),称,为,启发函,数,。,启发性信息和估价函数用于评估节点重要性的函数称为估价 函数。,32,八数码难题,估价函数为：,f(n)=d(n)+W(n),d(n,),：表示节,点,n,在搜索树中的深,度,W,(,n,),：表示节,点,n,中“错放”的棋 子个数,请计算初始状,态,S,0,的估价函数值,f(S,0,),1,2,3,8,4,7,6,5,启,发性,信,息和,估,价函数,2,8,3,设问题的初始状,态,S,和目标状态,S,1,0g,4,如图所,示,7,6,5,S,0,S,g,八数码难题估价函数为：f(n)=d(n)+W(n)12384,33,启,发性,信,息和,估,价函数,计算初始状态,S,0,的估价函数,值,f(,S,0,),取,g(n)=d(n),，,h(n)=W(n),它说明是用,从,S,0,到,n,的路径上的,单,位代,价表,示实际代价,用结点,n,中“错放”的棋子个,数,作为,启,发信,息。,一般来说，某节点中的“错,放,”的,棋,子个数 越多，说明它离目标节点越,远,（代,价,的估,计）。,000,对初始节点,S,，,d(S,)=0,，,W(S,)=3,。,因,此,，,f(S,0,)=0+3=3,1,2,3,8,4,7,6,5,2,8,3,1,4,7,6,5,S,0,S,g,启发性信息和估价函数计算初始状态S0的估价函数值f(S0),34,A,算法,八数,码,难,题,设问题的初始状,态,S,0,和目标状态,S,g,如,图所示,估价函数为：,f(n)=d(n)+W(n),d(n,),：表示节,点,n,在搜,索,树,中,的深,度,W(n,),：表示节,点,n,中“不,在,位”,的,数,码个数,用全局择优搜索解决该问题,1,2,3,8,4,7,6,5,2,8,3,1,4,7,6,5,S,0,S,g,A算法八数码难题1238476528314765S0Sg,35,启,发性,信,息和,估,价函数,该问题的全局择优搜 索树如右图所示,在该图中，每个节点 旁边的数字是该节点 的估价函数值,该问题的解为：,S,0,S,1,S,2,S,3,S,g,启发性信息和估价函数该问题的全局择优搜 索树如右图所示,36,与,/,或树的,广,度,优先,搜,索,设有下图所示的,与,/,或树，节点按标注顺序进行扩展， 其中标有,t1,、,t,2,、,t,3,的节点是终止节点,，,A,、,B,、,C,为不 可解的端节点。,1,23,A,4,t,1,5,t,2,Bt,3,C,与/或树的广度优先搜索设有下图所示的与/或树，节点按标注顺序,37,与,/,或树的,广,度,优先,搜,索,(1),先扩展,1,号节点，生成,2,号节点和,3,号节点。,(2),扩展,2,号节点，生,成,A,节,点和,4,号节点。,(3),扩,展,3,号节点，生成,t,1,节点和,5,号节点。,由于,t,1,为终止 节点，则标记它为可解节,点,，并应用可解标记过程，不 能确定,3,号节点是否可节。,(4),扩展节,点,A,，由于,A,是端节点，因此不可扩展。调 用不可解标记过程。,与/或树的广度优先搜索(1) 先扩展1号节点，生成2 号节,38,与,/,或树的,广,度,优先,搜,索,(5),扩展,4,号节点，生,成,t,2,节点和,B,节点。,由,于,t,2,为终止节点,，标 记为可解节点，应,用,可解标记,过程，,可标,记,2,号节点为可解，,但不能标,记,1,号节点为可解。,(6),扩展,5,号节点，生,成,t,3,节点和,C,节点,。,由于,t,3,为终止节,点,，标记它为可解节点，应用可解标记过程，可标,记,1,号节点为可解节点。,(7),搜索成功，得到,由,1,、,2,、,3,、,4,、,5,号节点,和,t,1,、,t,2,、,t,3,节点构成的解树。,与/或树的广度优先搜索(5) 扩展4号节点，生成t2节点和,39,与,/,或树的,深,度,优先,搜,索,设有下图所示的,与,/,或树，其中表有,t1,、,t2,、,t3,的节点 是终止节点,，,A,、,B,、,C,为不可解的端节点。若按有界,深度优先搜索，,设,d,m,=4,，则其,节,点扩展顺序为,：,1,，,3,，,5,，,2,，,4,。,1,2,3,A,4,t,1,5,t,2,B,t,3,C,与/或树的深度优先搜索设有下图所示的与/或树，其中表有t1、,40,与,/,或树的,深,度,优先,搜,索,(1),先扩展,1,号节点，生成,2,号,节点和,3,号节点。,(2,),扩展,3,号节点，生,成,t,1,节点 和,5,号节点。由,于,t,1,为终止节 点，则标记它为可解节点， 并应用可解标记过程，不能,确定,3,号节点是否可解。,(3),扩展,5,号节点，生,成,t,3,节点和,C,节点。由,于,t,3,为终止节 点，则标记它为可解节点，并应用可解标记过程，可标 记,3,号节点为可解节点，但不能标,记,1,号为可解。,与/或树的深度优先搜索(1) 先扩展1号节点，生成2号 节点,41,与,/,或树的,深,度,优先,搜,索,(4),扩展,2,号节点，生,成,A,节,点和,4,号节点。,(5),扩展,4,号节点，生,成,t,2,节,点和,B,节点。由,于,t,2,为终止节 点，则标记它为可解节点， 并应用可解标记过程，可标,记,2,号节点为可解，再往上,又可标记,1,号节点为可解。,(6),搜索成功，得到,由,1,、,3,、,5,、,2,、,4,号节点,即,t1,、,t2,、,t3,节点构成的解树。,与/或树的深度优先搜索(4) 扩展2号节点，生成A节 点和4,42,与,/,或树的,启,发,式搜索,1,i,k,(4),若,n,是,端节点，但又不是终止节,点,，,则,n,不可扩展，,其代价定义,为,h(n)=,。,(5),根节点的代价即为解树的代价。,h,(,n,),max,c,(,n,n,i,),h,(,n,i,),k,解树的代价可按如下规则计算,若用和代价法，则其计算公式为：,h,(,n,),c,(,n,n,i,),h,(,n,i,),i,1,若用最大代价法，则其计算公式为：,与/或树的启发式搜索1ikh(n) maxc(n,43,与,/,或树的,启,发,式搜索,设下图是一棵,与,/,或树，它 包括两棵解树,左边的解树,由,S,0,、,A,、,t,1,、,C,及,t,3,组成；,右边的解树,由,S,0,、,B,、,t,2,、,D,及,t,4,组成。,在此与或树中，,t,1,、,t,2,、,t,3,、,t,4,为终止节点,；,E,、,F,是端 节点；边上的数字是该边 的代价。,请计算解树的代价。,3,S,0,2,2,A,4,B,t,5,1,6,C,t,2,D,2,1,t,3,E,t,4,F,与/或树的启发式搜索设下图是一棵与/或树，它 包括两棵解树左,44,与,/,或树的,启,发,式搜索,解：先计算左边的解树,按和代价：,h(S,0,)=2+4+6+2=14,按最大代价：,h(S,0,)=(2+6)+2=10,再计算右边的解树,按和代价：,h(S,0,)=1+5+3+2=11,按最大代价：,h(S,0,)=(1+5)+2=8,3,S,0,2,2,A,4,B,t,5,1,6,C,t,2,D,2,1,t,3,E,t,4,F,与/或树的启发式搜索解：先计算左边的解树3S02A4 Bt,45,与,/,或树的,启,发,式搜索,设初始节点,为,S,0,，,要求搜索 过程每次扩展节点时都同时 扩展两层，且按一层或节点、 一层与节点的间隔方式进行 扩展。,S,0,经过扩展后得到的,与,/,或树,如右图所示。其中，端节点,B,、,C,、,E,、,F,，,下面的数字,是用启发函,数,估算,出的,h,值；,各个父节点到其子节点的代 价为,1,。,S,0,A,D,B,C,E,F,3,33,2,h,(B)=3,，,h,(C)=3,h,(E)=3,，,h,(F)=2,按照和代价计算得到：,h,(A)=8,，,h,(D)=7,h,(S,0,)=8,此时,S,0,的右子树是希望树,与/或树的启发式搜索设初始节点为S0，要求搜索 过程每次扩展,46,与,/,或树的,启,发,式搜索,依次对,当前希望树的端节,点,进,到的与,/,或树如右图所示。,节点,S,0,、,A,、,D,、,E,、,G,、,H,旁,边,的,数,字是按,和代价,法,计算出来的节 点代价。,此时，由,右子,树求出,的,h(,S,0,),=,1,2,，,由左子树,求出,的,h(S,0,)=9,。,显然,，,左子树的代价小。因此,，,当前,的希望树应改为左子,树,。,S,0,9,A,8,D,11,行扩展。对节,点,E,扩展,两层后,得,B,C,E,F,3,3,7,2,3,2,2,2,6,G,7,H,与/或树的启发式搜索依次对当前希望树的端节点进到的与/或树如,47,与,/,或树的,启,发,式搜索,两层后得到的,与,/,或树如下,图所示。,2,S,0,9,对节,点,B,进行扩展，扩,展,A,8,D,11,B,C,E,F,3,3,7,2,3,2,2,6,L,N,O,PQ,2,M,6,G7,H,00,22,由于节点,N,和,O,是可解节点,，,故调,用,可解,标,记,过,程,，,得节,点,L,、,B,也为可,解节,点，但,不能,标,记,S,0,为,可,解节点,，,须继续扩展。,当前的希望树仍,然,是左,子树,。,与/或树的启发式搜索两层后得到的与/或树如下图所示。2S0,48,与,/,或树的,启,发,式搜索,图所示。,S,0,9,对节,点,C,进行扩展，扩展 两层后得到的,与,/,或树如,下,A,8,D,11,B,C,E,F,3,3,7,2,3,2,2,2,7,6,L,N,O,PQ,00,22,2,M,6,R,T,S,00,52,2,9,G,H,调用可解标记过程，可标,记,S,0,为可,解,节点,，,这就,得,到了代价最小的解树。按和代,价,法,，,该,最,优,解的,代,价为,9,。,与/或树的启发式搜索图所示。S09对节点C进行扩展，扩展 两,49,自,然演,绎,推理,自,然演绎,推,理的例,子,设已知如下事实：,只要是需要编程序的课，王程都喜欢。,所有的程序设计语言课都是需要编程序的课。,C,是一门程序设计语言课。,求证：,王程喜,欢,C这门课。,证明,：,首先定义谓词,Pro,g,(x),：,x,是需要编程序的课。,Like(x,y):,x,喜欢,y,。,Lang(x):,x,是一门程序设计语言课,自然演绎推理自然演绎推理的例子,50,自,然演,绎,推理,自,然演绎,推,理的例,子,把已知事实及待求解问题用谓词公式表示如下：,Prog(x)Like(Wang ,x),(,x)(,Lang(x)Prog(x) Lang(C),应用推理规则进行推理：,Lang(y)Prog(y),全称固化,Lang(C),，,Lang(y)Prog(y),Prog(C),假言推,理,C/y,Pro,g,(C),Pro,g,(x)Like(W,a,n,g,x,),Like(Wang,C),假,言推,理,C/x,因此，王程喜,欢,C,这门课。,自然演绎推理自然演绎推理的例子,51,命,题逻,辑,的消解,例如,：,设,C,1,=,P,Q,R,，,C,2,=,P,S,，,求,C,1,和,C,2,的消 解式,C,12,。,解：,这里,L,1,=P,，,L,2,=,P,，通,过,消解,可,以得,到,C,12,=,Q,R,S,例如,：,设,C,1,=,Q,，,C,2,=,Q,，,求,C1,和,C2,的消,解,式,C,12,。,解：,这里,L,1,=,Q,，,L,2,=Q,，,通过,消,解,可以,得,到,C,12,=,NIL,命题逻辑的消解例如：设C1=PQR，C2=PS，求C,52,命,题逻,辑,的消解,例如,：,设设,C,1,=,P,Q,，,C,2,=,Q,，,C,3,=,P,，,求,C,1,、,C,2,、,C,3,的消,解,式,C,123,。,解：若先对,C,1,、,C,2,消解,，,可得,到,C,12,=,P,然后再对,C,12,和,C,3,消,解,，得,到,C,123,=NIL,如果改变消解顺序，同样可,以,得到,相,同的 结果，即其消解过程是不唯,一,的。,其消解消解过程可用右图来,表,示，,该,树称,为,消解树,。,P,Q,Q,P,P,NIL,P,Q,P,Q,Q,NIL,命题逻辑的消解例如：设设C1 =P Q ，C2=Q，,53,命,题逻,辑,的消解,设已,知,的公,式,集,为,P,(P,Q)R, (S,T)Q,T,，求证结,论,R,。,解：,假设结,论,R,为假,将,R,加入公式 集，并化为子句集：,S=P,P,Q,R,S,Q,T,Q,T,R,其消解过,程如,右图的消,解演,绎树所示,。,该树根为空子句。,子句集,S,不可满足，即假,设,R,为,真是,错误的，于,是,R,为真。,P,Q,R,R,P,Q,P,Q,T,Q,T,T,NIL,命题逻辑的消解设已知的公式集为 P, (PQ)R,54,谓,词逻,辑,的消解,在谓词逻辑中，由于子句集,中,的谓,词,一般,都,含,有,变,元,，因,此,不能象,命,题逻辑那样直接消去互补文,字,。,对于谓词逻辑，需要先用一,个,最一,般,合一,对,变元进,行,置换,，,然后才,能,进行消解。,谓词,逻辑的,消,解原,理,设,C,1,和,C,2,是两,个,没,有公,共,变,元,的,子,句,，,L,1,和,L,2,分,别,是,C,1,和,C,2,中的,文字。如,果,是,L,1,和,L,2,存在,最一般合一,，则称：,C,12,=(C,1,-,L,1,),(,C,2,-,L,2,),为,C,1,和,C,2,的,二元消解,式,，,L,1,和,L,2,为,消,解,式上,的,文,字,。,谓词逻辑的消解在谓词逻辑中，由于子句集中的谓词一般都含有变元,55,谓,词逻,辑,的消解,例：,设,C,1,=,P(a),R(x),，,C,2,=,P(y),Q(b),，,求,C,12,解,：,取,L,1,=,P(a,),L,2,=,P(y,),，,则,L,1,和,L,2,的最 一般合一,是,=a/y,。因此：,C,12,=,( C,1,-L,1,),(C,2,-L,2,),= (,P(a),R(x)-,P(a),),(,P(a),Q(b)-,P(a),),=,(R(x),(Q(b),= R(x), Q(b),=,R(x),Q(b),谓词逻辑的消解例：设C1=P(a)R(x)，C2=P(y,56,谓,词逻,辑,的消解,例：,设,C,1,=P(,x,),Q(a),，,C,2,=,P(b),R(,x,),，,求,C,12,解,：,由于,C,1,和,C,2,有相同的变,元,x,，不符合,定,义的,要,求。为了进行消解，需要修,改,C,2,中变,元,的名字,。,令,C,2,=,P(b),R(,y,),，,此时,L,1,=,P(x),L,2,=,P(b),，,L,1,和,L,2,的最一般合一,是,=b/x,。则,有,:,C,12,= (,C,1,-L,1,),(C,2,-L,2,),= (,P(b),Q(a)-,P(b),),(,P(b),R(,y,)-,P(b),),= (Q(a),(R(,y,),= Q(a),R(,y,),=,Q(a),R(,y,),谓词逻辑的消解例：设C1=P(x)Q(a)，C2=P(b,57,谓,词逻,辑,的消解,例：,设,C,1,=P(a),Q(x),R(x),C,2,=,P(y),Q(b),求,C,12,对,C,1,和,C,2,通过最一,般,合一（,=b/x,a/y,）的作用， 可以得到,两个互补,对,。,注意：求消解式不能同时消,去,两个,互,补,对,，,这样,的,结果不是二元消解式。如,在,=b/x,a/y,下，若同时 消去两个互补对，所得,的,R(b),不,是,C,1,和,C,2,的,二,元,消,解式。,谓词逻辑的消解例：设C1=P(a)Q(x) R(x),58,谓,词逻,辑,的消解,例：,设,C,1,=P(a),Q(x),R(x),C,2,=,P(y),Q(b),求,C,12,解,1,：,取,L,1,=,P(a),L,2,=,P(y),，则,=a/y,是,L,1,与,L,2,的最一般合一。此时：,C,12,=,Q(x),R(x),Q(b),解,2,：,取,L,1,=,Q(x),，,L,2,=Q(b),，则,=b/x,是,L,1,与,L,2,的最一般合一。此时：,C,12,=,P(a),R(b),P(y),谓词逻辑的消解例：设C1=P(a)Q(x) R(x),59,谓,词逻,辑,的消解,例：,设,C,1,=,P(x),P(f(a),Q(x),，,C,2,=,P(y),R(b),求,C,12,解：,对参加消解的某个子句，,若,其内部有可合一的文 字,，则在进行消解之前应先对这些文字进行合一。,本例的,C,1,中有可合一的文,字,P(x,),与,P(,f,(a,),),，若用它们的 最一般合,一,=f(a)/x,进行代换，可得,到,：,C,1,=P(f(a),Q(f(a),此时对,C,1,与,C,2,进行消解。,选,L,1,=,P(f(a),L,2,=,P(y),，,L,1,和,L,2,的最一般合一,是,=,f,(a,),/y,，则可得,到,C,1,和,C,2,的,二元消解式为：,C,12,=R(b),Q(f(a),谓词逻辑的消解例：设C1=P(x)P(f(a)Q(x),60,谓,词逻,辑,的消解,例：,设,C,1,=P(y),P(f(x),Q(g(x),C,2,=,P(f(g(a),Q(b),求,C,12,解：,对,C,1,，取最一般合,一,=f(x)/y,，,得,C,1,的因子,C,1,=P(f(x),Q(g(x),对,C,1,的因子,和,C,2,消解,（,=g(a)/x,），可得：,C,12,=Q(g(g(a),Q(b),谓词逻辑的消解例：设C1=P(y)P(f(x)Q(g(,61,谓,词逻,辑,的消解,例：,已知,F:(,x)(,y)(A(x,y),B(y)(,y)(C(y),D(x,y),G:,(,x)C(x)(,x)(,y)(A(x,y),B(y),求,证,G,是,F,的逻辑结论。,证明：,先,把,G,否,定,，并放,入,F,中，得,到,的,F,G,：,(,x)(,y)(A(x,y),B(y)(,y)(C(y),D(x,y),(,(,x)C(x)(,x)(,y)(A(x,y),B(y),再把,F,G,化成,子,句集,，,得,到,谓词逻辑的消解例：已知,62,谓,词逻,辑,的消解,最后应用谓词逻辑的消解原,理,对上,述,子句,集,进,行,消,解，其过程为：,(6),A(x,y),B(y),(7),B(n),(8),NIL,F,(1),A(x,y),B(y),C(f(x),(2),A(u,v),B(v),D(u,f(u),C(z),A(m,n),B(k),G,(1),和,(3),消解，取,=f(x)/z,(4),和,(6),消解，,取,=m/x,n/y,(5),和,(7),消解，取,=n/k,谓词逻辑的消解最后应用谓词逻辑的消解原理对上述子句集进行消,63,谓,词逻,辑,的消解,因此，,G,是,F,的逻辑结论。,上述消解过程可用如下消解,树,来表示,A(x,y),B(y),C(f(x),C(z),A(x,y),B(y),A(m,n),B(n),B(k),NIL,f,(,x)/,z,m,/,x,n,/,y,n/k,谓词逻辑的消解因此，G是F 的逻辑结论。A(x,y),64,谓,词逻,辑,的消解,例,：,“,快乐学,生”,问题,假设：,任何通过计算机考试并获奖的人都是快乐的，任 何肯学习或幸运的人都可以通过所有考试，张不肯学习 但他是幸运的，任何幸运的人都能获奖。,求证：,张是快乐的。,解：,先定义谓词：,Pass(x,y),：,x,可以通过,y,考试,Win(x,prize),：,x,能获得奖励,Study(x),：,x,肯学习,Happy(x,),：,x,是快乐的,Lucky(x),：,x,是幸运的,谓词逻辑的消解例：“快乐学生”问题,65,谓,词逻,辑,的消解,再将问题用谓词表示如下：,“任何通过计算机考试并奖的人都是快乐的”,(,x)(Pass(x, computer),Win(x,prize)Happy(x),“,任何肯学习或幸运的人都可以通过所有考试”,(,x),(,y) (Study(x),Lucky(x)Pass(x,y),“,张不肯学习但他是幸运的”,Study(,z,hang),L,u,c,ky(,z,h,a,ng),“,任何幸运的人都能获奖”,(,x) (Lucky(x)Win(x,prize),结论“张是快乐的”,的,否定,Happy(zhang),谓词逻辑的消解再将问题用谓词表示如下：,66,谓,词逻,辑,的消解,将上述谓词公式转化为子句集如下：,(1),Pass(x,computer),Win(x,prize),Happy(x),(2),Study(y),Pass(y,z),(3),Lucky(u),Pass(u, v),(4),Study(zhang),(5),Lucky(zhang),(6),Lucky(w),Win(w,prize),(7),Happy(zhang),(,结论的否定,),按消解原理进行消解，消解树如下：,谓词逻辑的消解将上述谓词公式转化为子句集如下：,67,谓,词逻,辑,的消解,Pass(x,computer),Win(x, prize),Happy(x),Luck,y,(,w,),W,in,(,w, prize),Pass(w,Computer),Happy(w),Lucky(w),Happy(zhang),Pass(zhang,Computer),Lucky(u),Pass(u,v),Lucky(zhang),Lucky(zhang),NIL,w,/,x,zhang/w,Lucky(zhang),Pass(zhang,Computer),Lucky(zhang),zhang/u,computer/v,谓词逻辑的消解Pass(x, computer)Win,68,用消解反演求取问题的答案,例,1：,已知：,“张和李是同班同学,，,如,果,x,和,y,是,同,班同学,，,则,x,的教,室也,是,y,的教室，现在张,在,302,教,室上课,。”,问：,“现在李在哪个教室上,课,？”,解：,首先定义谓词,C(x,y),：,x,和,y,是同班同学,At(x,u),：,x,在,u,教室上课。,把已知前提用谓词公式表示如下：,C(zhang,li),(,x),(,y) (,u),(C(x, y),At(x,u)At(y,u) At(zhang,302),用消解反演求取问题的答案例1：,69,用消解反演求取问题的答案,把目标的,否,定,用谓词,公,式表,示,如,下,：,(,v)At(li,v),把上述公式化为子句集：,C(zhang,li),C(x,y),At(x,u),At(y,u) At(zhang,302),把目标的否定化成子句式，并,用,下面,的,重,言,式代,替,：,At(li,v),At(li,v),把此重言式加入前提子句,集,中，,得,到一,个,新,的,子句,集,，,对这个新的子句集，应用,消,解原,理,求出,其,证,明,树。,用消解反演求取问题的答案把目标的否定用谓词公式表示如下：,70,用消解反演求取问题的答案,求解过程如下图所示。该证明,树,的根,子,句,就,是,所求的答案，即“李明,在,302,教室”。,At(li,v),At(li,v),C(x,y),At(x,u),At(y,u),At(li,v),C(x,li),At(x,v),C(zhang,li),At(zhang,v),At(li,v),At(zhang,302),At(li,302),li/y,v/u,Zhang/x,302/,v,用消解反演求取问题的答案求解过程如下图所示。该证明树的根子句,71,用消解反演求取问题的答案,例,2：,已知,：,A,B,C,三人中有人从不说真话，也有人从不说假 话。某人向这三人分别提出同一个问题：谁是说谎者？,A,答：“,B,和,C,都是说谎者”,；,B,答：“,A,和,C,都是说谎者”,；,C,答,：“,A,和,B,中至少有一个是说谎者,”,。,问：,求谁是老实人，谁是说谎者？,解：,首先定义谓词,T(x),：,表示,x,说真话,用消解反演求取问题的答案例2：,72,用消解反演求取问题的答案,把已知前提用谓词公式表示如,下,：,有人从不说真话,：,T(C),T(A),T(B),有人从不说假话,：,T(C,),T(A,),T(B),根据“,A,答,：,B,和,C,都,是说,谎,者,”,，,则,若,A,说真话,：,T(A)T(B,),T(,C,),若,A,说假话,：,T(A)T(B),T(C),同理：,根据“,B,答,：,A,和,C,都,是说,谎,者,”，,则,T(B)T(A),T(C),T(B)T(A),T(C),根据,“,C,答,：,A,和,B,中,至少,有,一个,是,说,谎,者,”，,则,T(C)T(A),T(B,),T(C)T(A),T(B),用消解反演求取问题的答案把已知前提用谓词公式表示如下：,73,用消解反演求取问题的答案,把上述公式化成子句集，得到前提子句,集,S,：,T(A),T(B),T(A),T(C),T(,C,),T(,A,),T(,B,),T(B),T(C),T(C),T(A),T(B),T(A),T(C),T(B),T(C),先求谁是老实人，结论的否定为,：,(,x)T(x),用消解反演求取问题的答案把上述公式化成子句集，得到前提子句集,74,用消解反演求取问题的答案,把目标的否定化成子句式，并用下面的重言式代替：,T(x),T(x),把此重言式加入前提子句,集,S,，,得到一个新子句集，,对这个新的子句集，应用消解原理求出其证明树。,T(A),T(B),T(B),T(C),T(A),T(C),T(A),T(C),T(C),T(x),T(x),T(C),C,/x,C,是老实人,用消解反演求取问题的答案把目标的否定化成子句式，并用下面的重,75,用消解反演求取问题的答案,下面证明,A,不是老实人，结论的否定为,：,T(A),将结论的否,定,(T(A),加入并入前提子句,集,S,中， 应用消解原理对新的子句集进行消解：,T(A),T(B),T(B),T(C),T(A),T(C),T(A),T(C),T(A),T(A),NIL,得证。,A,不是 是老实人,同理可证,B,不,是老实人,用消解反演求取问题的答案下面证明A不是老实人，结论的否定为：,76,消,解演,绎,推理,消解演绎推,理,的,优点,：,简单，便于在计算机上实现
展开阅读全文