1、AI人工智能综合讲义人工智能综合讲义reserved.状态空间法猴子和香蕉问题猴子和香蕉问题：在一个房间内有一只猴子、一个箱在一个房间内有一只猴子、一个箱 子和一束香蕉。香蕉挂在天花板下方，但猴子的高度子和一束香蕉。香蕉挂在天花板下方，但猴子的高度 不足以碰到它。那么这只猴子怎样才能摘到香蕉不足以碰到它。那么这只猴子怎样才能摘到香蕉呢呢?reserved.猴子和香蕉问题用一个四元表列用一个四元表列（W，x，Y，z）来表示来表示这这个问个问题题 状态状态 W：猴子的水平位置；：猴子的水平位置；x：当猴子在箱子顶上时当猴子在箱子顶上时取取1；否否则则取取0；Y：箱子的水平位置；箱子的水平位置；z：
2、当猴子摘到香蕉时当猴子摘到香蕉时取取1；否则否则取取0。初始状态初始状态为为(a,0,b,0)，目标状态为，目标状态为(c,1,c,1)这个问题的操作（算符）如这个问题的操作（算符）如下下：goto（U）表示猴子走到水平）表示猴子走到水平位置位置Upushbox（V）猴子猴子把把箱箱子子推到推到水水平位平位置置Vclimbbox猴子爬上箱顶猴子爬上箱顶grasp猴子摘到香蕉猴子摘到香蕉reserved.猴子和香蕉问题该初始状态变换为目标该初始状态变换为目标 状态的操作序列为：状态的操作序列为：Step1:goto(b)Step2:pushbox(c)Step3:climbboxStep4:gr
3、asp reserved.猴子和香蕉问题reserved.(b，1，b，0)（c，1，c，1）目标状态目标状态（a，0，b，0）goto（U）（U，0，b，0）U=b，climbbox（V，0，V，0）goto（U）U=bpushbox（V）goto（U）U=V（U，0，V，0）goto（U）V=c，climbbox（c，1，c，0）grasp汉诺塔问题本本原问原问题题本本原问原问题题 reserved.与与或或图图CBA谓词逻辑法合式公式（合式公式（WFF，Well-formed Formulas）：）：通常把通常把合合 式公式式公式叫叫做做谓词公式谓词公式，递归定义如下：，递归定义如下：(
4、1)原子谓词公式是合式公式原子谓词公式是合式公式(2)若若A为合式公式，为合式公式，则则 A也是一个合式公式也是一个合式公式(3)若若A,B是合式公式，则是合式公式，则AB，AB，AB，AB 也都是合式公式也都是合式公式(4)若若A是合式公式是合式公式，x为为A中中的的自自由由变元变元，则则 (x)A和和(x)A都是合式公式都是合式公式(5)只有按上述规只有按上述规则则(1)至至(4)求求得得的的那些那些公公式，式，才才是是合合式式 公式。公式。reserved.谓词逻辑法用谓词公式表示知识时，需要首用谓词公式表示知识时，需要首先先定义谓定义谓词词，然后再，然后再 用用连接连接词把有关的谓词连
5、接起来，形成一个谓词公式词把有关的谓词连接起来，形成一个谓词公式 表达一个完整的意义。表达一个完整的意义。例例1：设有下列知识设有下列知识刘欢比他父亲出名。刘欢比他父亲出名。高扬是计算机系的一名学高扬是计算机系的一名学生生，但，但他他不喜不喜欢欢编编程程 。任何整数或者为正或者为任何整数或者为正或者为负。负。为了用谓词公式表示上述知识，首为了用谓词公式表示上述知识，首先先需要需要定定义谓词：义谓词：FAMOUS(x,y):x比比y出名出名 COMPUTER(x):x 是计是计算机系的算机系的 LIKE(x,y):x 喜喜欢欢 y reserved.谓词逻辑法I(x)表示表示“x是是整数整数”P
6、(x)表示表示“x是正数是正数”N(x)表示表示“x是是负负数数”此时可用谓词公式把上述知识表示此时可用谓词公式把上述知识表示为为:刘欢比他父亲出刘欢比他父亲出名名:FAMOUS(liuhuan,father(liuhuan)高扬是计算机系的一名学高扬是计算机系的一名学生生，但，但他他不喜不喜欢欢编编程程 :COMPUTER(gaoyang)LIKE(gaoyang,programing)任何整数或者为正或者为任何整数或者为正或者为负负:(x)(I(x)(P(x)N(x)reserved.谓词逻辑法例例2：用谓词逻辑描述右图中的房子的概念用谓词逻辑描述右图中的房子的概念个个体体 ：A,B谓谓词
7、词 ：SUPPORT(x,y)：表表示示 x 被被 y支撑着支撑着WEDGE(x)：表表示示 x 是楔形块是楔形块BRICK(y)：表表示示 y 是长方块是长方块其其中中 x,y是个体变元是个体变元，它们它们的的个个体体域域A,B房子的概念可以表示成一组合房子的概念可以表示成一组合式式谓词谓词公公式式的的合取合取式式：SUPPORT(A,B)WEDGE(A)BRICK(B)reserved.谓词逻辑法若若P、Q是两个合式公式，则由这两个合式公式所组成是两个合式公式，则由这两个合式公式所组成 的复合表达式可由下列真值表给出。的复合表达式可由下列真值表给出。reserved.TTFTTTTTFFT
8、FFFFTTTFTFFFTFFTT语义网络法可用二元谓可用二元谓词词P(x,y)P(x,y)表表示的示的关关系。系。其其中，中，x,yx,y为实为实 体体，P P为实体之间的关为实体之间的关系系。单个二元关系可直接用一个单个二元关系可直接用一个基基本网本网元元来表示来表示对复杂关系，可通过一些相对复杂关系，可通过一些相对对独立独立的的二元二元或或一一元元关关 系的组合来实现。系的组合来实现。例如：用语义网络表示例如：用语义网络表示动物能运动、会吃。动物能运动、会吃。鸟是一种动物，鸟有翅膀、鸟是一种动物，鸟有翅膀、会会飞。飞。鱼是一种动物，鱼生活在水鱼是一种动物，鱼生活在水中中、会、会游游泳。泳
9、。reserved.语义网络法用语义网络用语义网络表示表示：1）动动物能物能运运动、动、会会吃吃；2）鸟是鸟是一一种动种动物物，鸟，鸟有有翅膀翅膀、会飞会飞；3）鱼鱼是一是一种种动物，动物，鱼生活在水鱼生活在水中、中、会会游泳。游泳。AKO：A kind ofreserved.动物动物吃吃运动运动翅膀翅膀水中水中鸟鸟鱼鱼飞飞游泳游泳CanCanAKOLiveHaveCanAKOCan语义网络法例如：用语义网络表示例如：用语义网络表示王强是理想公司的经理；王强是理想公司的经理；理想公司在中关村；理想公司在中关村；王强王强28岁。岁。reserved.中关村中关村理想公司理想公司王强王强经理经理2
10、8岁岁Located-at-Work-forHeadshipAge语义网络法例如：例如：我椅子的颜色是咖啡色的；我椅子的颜色是咖啡色的；椅子包套是皮革；椅子包套是皮革；椅子是一种家具；椅子是一种家具；座位是椅子的一部分；座位是椅子的一部分；椅子的所有者椅子的所有者是是XX是个人是个人reserved.语义网络法我椅子的颜色是咖啡色的；椅我椅子的颜色是咖啡色的；椅子子包套包套是是皮皮革革；椅；椅子子是一是一 种家具；座位是椅子的一部分种家具；座位是椅子的一部分；椅子椅子的的所所有有者者是是X；X是是 个人个人定义一个语义网络来表示椅子定义一个语义网络来表示椅子的的概念概念在椅子的基础上进一步具体
11、描在椅子的基础上进一步具体描述述：我：我的的椅椅子子reserved.FURNITURECHAIRPERSONSEATMY CHAIRBROWNXLEATHERISAOWNERCOLORISAISAISA PARTCOVERING椅子的概念椅子的概念语义网络法例如：用语义网络表示例如：用语义网络表示李新的汽车的款式是李新的汽车的款式是“捷达捷达”、银、银灰灰色。色。王红的汽车的款式是王红的汽车的款式是“凯越凯越”、红、红色。色。李新和王红的汽车均属于具李新和王红的汽车均属于具体体概概念念,可增可增加加“汽车汽车”这个抽象这个抽象概念。概念。reserved.捷达捷达李新李新汽车汽车1银灰色银灰
12、色人人汽车汽车交通工具交通工具王红王红汽车汽车2红色红色凯越凯越BrandOwnerColorISAISAAKOColorOwnerBrandISAISA语义网络法增增加加情情况况和和动动作作节点节点例如例如：用语义网络表用语义网络表示示 “小燕子从春天到秋天占有一小燕子从春天到秋天占有一个巢个巢”reserved.小燕子小燕子燕子燕子鸟鸟巢巢鸟窝鸟窝春天春天时间时间秋天秋天情况情况占有权占有权占有资格占有资格ISAAKOStartOwnAKOAKOEndAKOAKOOwnerAKO语义网络法增增加加情情况况和和动动作作节点节点例如例如：用语义网络表用语义网络表示示 “小王给小林一本书小王给小
13、林一本书”三元关系三元关系需要设立一个需要设立一个“给给”的动作节的动作节点点。动。动作作节节点点由一由一些些向外向外引出的弧来指出动作的主体与引出的弧来指出动作的主体与客客体。体。reserved.一本书一本书小王小王给给小林小林GiftReceiverGiver语义网络法否定的表示：否定的表示：一般语义关系的否定一般语义关系的否定：可通过引进可通过引进“非非”节节点点来表来表例如例如：用语义网络表用语义网络表示示 “小王没有给小林一本书小王没有给小林一本书”reserved.一本书一本书小王小王给给小林小林GiftReceiverGiver非非语义网络法增增加加事事件件节点节点例如例如：用
14、语义网络表用语义网络表示示 “北京大学和清华大学两校篮北京大学和清华大学两校篮 球队在北大进行一场比赛的比分球队在北大进行一场比赛的比分是是85：89”。三元关系三元关系需要设立一个需要设立一个“球赛球赛”的事件的事件节节点点引入事件节引入事件节点点G25来表示这场特点来表示这场特点的的球赛球赛 reserved.清华大学清华大学篮球比赛篮球比赛G2585:89北京大学北京大学VISITING TEAMHOME TEAMSCOREISA语义网络法 合取和析取合取和析取的的表表示示：可通过可通过 增加增加合取节合取节点点和和析取节点析取节点 来实现来实现例如：用语义网络表示：例如：用语义网络表示
15、：“参赛者有教师有学生，参赛者有教师有学生，参赛者的身高有高有低参赛者的身高有高有低”分析参赛者的不同情况，分析参赛者的不同情况，可得到以下四种情况：可得到以下四种情况：A.A.教师、高；教师、高；B.B.教师、低；教师、低；C.C.学生、高；学生、高；D.D.学生、低学生、低reserved.人人参赛者参赛者ABCD或或或或教师教师学生学生高高低低与与ISAPartPartPartPartStateStateStateState语义网络法 蕴含蕴含的表示：的表示：通过通过增增加蕴含加蕴含关关系节系节点点来实来实现现。在蕴。在蕴含含关系关系中中，有有 两条两条指向蕴含节点的指向蕴含节点的弧弧，
16、一，一条条代表代表前前提条件提条件(Antecedent)，标记，标记 为为ANTE；另一条代表结另一条代表结论论(Consequence)，标记，标记为为CONSE 例如：用例如：用语义网语义网络络表示表示：“如如果果学校学校组织大组织大学学生机生机器人竞器人竞赛赛活动活动，那么李强就参加比赛那么李强就参加比赛”reserved.CONSEANTE学校学校比赛比赛活动活动机器人机器人机器人竞赛机器人竞赛蕴含蕴含参加比赛参加比赛学生学生智能机器智能机器李强李强人人RacerAKOConstitutionManipulatorISAAKOAKOJoiner语义网络法存存在量词在量词的表的表示和示
17、和全全称量词称量词的的表表示示：例如例如：用语义网络表示：用语义网络表示：“每个学生都学习了一门程每个学生都学习了一门程序序设计设计语语言言”“每个学生都学习了所有的每个学生都学习了所有的程程序设序设计计课程课程”“每个学生都学习每个学生都学习了了C+语语言言”reserved.语义网络法“每个学生都学习了一门程序设计语言每个学生都学习了一门程序设计语言”GSgsrp学生学生学习学习程序语言程序语言ISAISAISAFSubjectObjectISA子空间子空间 GS：是一个是一个概念结概念结点点，它表示，它表示具有全称量化的一般事件具有全称量化的一般事件。g：是一个实例结点，代是一个实例结点
18、，代表表GS 中的一个具体例中的一个具体例子子，如上所提到的事实。，如上所提到的事实。s：是一个是一个全称变量全称变量，表示任意一个学生。，表示任意一个学生。r：是一个是一个存在变量存在变量，表示某一次学习。，表示某一次学习。p：是一个是一个存在变量存在变量，表示某一门程序设计语言。，表示某一门程序设计语言。F：弧弧“F”说明它所代表的子空间及其具体形式说明它所代表的子空间及其具体形式 ：弧弧“”说明它所代表的全称量词。说明它所代表的全称量词。reserved.语义网络法“每个学生都学习了所有的程序设计课程每个学生都学习了所有的程序设计课程”reserved.学生学生学习学习程序设计课程序设计
19、课gGSsrpISAISAISASubjectObjectISAF子空间子空间语义网络法“每个学生都学习每个学生都学习了了C+语言语言”GSgsr学生学生学习学习C+语言语言程序语言程序语言ISAISASubjectObjectFISAISA子空间子空间在这种表示方法中，要求子在这种表示方法中，要求子空空间中间中的的所有所有非非全称全称 变量节点都是全称变量的函数变量节点都是全称变量的函数C+C+是具体的程是具体的程序序设计语设计语言言，不，不是是全称全称变变量量s s的函的函数，应该放在子空间外面数，应该放在子空间外面reserved.代价树的广度优先搜索城市交通问题。设城市交通问题。设有有
20、5个城市，它们之间的交通线个城市，它们之间的交通线 路如下方左图所示，图中的数字表示两个城市之间的交通路如下方左图所示，图中的数字表示两个城市之间的交通 费用，即代价。用代价树的广度优先搜索，求费用，即代价。用代价树的广度优先搜索，求从从A市出发市出发 到到E市，费用最小的交通路市，费用最小的交通路线线。DEA 4B4C53 23城城市交通市交通图图代价树的广度优先搜索城城市交通市交通图图的代价的代价树树2AB1D15E12BC2E3E434C14D24233E25ABDE443C523首先将交通图转化为代价树。具体转化方法如首先将交通图转化为代价树。具体转化方法如下：下：从起始节点从起始节点
21、A开始，把与它直接相邻的节点作开始，把与它直接相邻的节点作 为它的子节点为它的子节点 对其他节点也做相同的处理对其他节点也做相同的处理 若一个节点已经为某节点的直系先辈节点时，若一个节点已经为某节点的直系先辈节点时，就不能作为这个节点的子节点。就不能作为这个节点的子节点。图中除了起始节点图中除了起始节点A之外，其它节点都可能要之外，其它节点都可能要 在代价树中出现多次，为了区分它们的多次出在代价树中出现多次，为了区分它们的多次出 现，分别用下现，分别用下标标1,2，标出标出代价树的广度优先搜索对此代价树进行广度优先搜索，可得对此代价树进行广度优先搜索，可得到到最优最优 解，如图红线部分为最优解
22、，解，如图红线部分为最优解，其其代价代价为为8CDE3A 4B45 2325AD1E1E434C133E2B1 4D242B2C2E3 5代价树的深度优先搜索(1)把初始节把初始节点点S放入放入OPEN表中，置表中，置S的代的代价价g(S)=0；(2)如果如果OPEN表为空，则问题无表为空，则问题无解解 ，失败退出；，失败退出；(3)把把OPEN表的第一个节点取出放表的第一个节点取出放入入CLOSED表，并表，并记该节点记该节点为为n；(4)考察节考察节点点n是否为目标节点。若是，则找到了问题是否为目标节点。若是，则找到了问题 的解，成功退出；的解，成功退出；(5)若节点若节点n不可扩展，则转
23、第不可扩展，则转第(2)步；步；(6)扩展节扩展节点点n，生成其子节点，生成其子节点，将这些子节点按边代价将这些子节点按边代价 由小到大放由小到大放入入Open表的首部表的首部，并为每一个子节点设置，并为每一个子节点设置 指向父节点的指针。然后转指向父节点的指针。然后转第第(2)步。步。启发性信息和估价函数用于评估节点重要用于评估节点重要性性的函的函数数称称为为估价估价 函数。估价函数的一般形式为：函数。估价函数的一般形式为：f(x)=g(x)+h(x)g(x)表示从初始节表示从初始节点点S0到节到节点点x的代价；的代价；h(x)是从节是从节点点x到目标节到目标节点点Sg的最优路的最优路径径的
24、的代代价价 的的估估计计，它体现了问题的启发，它体现了问题的启发性性信息。信息。h(x)称称为为启发函启发函数数。八数码难题八数码难题估价函数为：估价函数为：f(n)=d(n)+W(n)d(n)：表示节：表示节点点n在搜索树中的深在搜索树中的深 度度W(n)：表示节：表示节点点n中中“错放错放”的棋的棋 子个数子个数请计算初始状请计算初始状态态S0的估价函数值的估价函数值f(S0)12384765启发性信息和估价函数283设问题的初始状设问题的初始状态态S 和目标状态和目标状态S10g4如图所如图所示示765S0Sg启发性信息和估价函数计算初始状态计算初始状态S0的估价函数的估价函数值值f(S
25、0)取取g(n)=d(n)，h(n)=W(n)它说明是用它说明是用从从S0到到n的路径上的的路径上的单单位代位代价表价表 示实际代价示实际代价 用结点用结点n中中“错放错放”的棋子个的棋子个数数作为作为启启发信发信息。息。一般来说，某节点中的一般来说，某节点中的“错错放放”的的棋棋子个数子个数 越多，说明它离目标节点越越多，说明它离目标节点越远远（代（代价价的估的估 计）。计）。000 对初始节点对初始节点S，d(S)=0，W(S)=3。因因此此，f(S0)=0+3=31238476528314765S0SgA算法八数八数码码难难题题 设问题的初始状设问题的初始状态态S0和目标状态和目标状态S
26、g如如 图所示图所示 估价函数为：估价函数为：f(n)=d(n)+W(n)d(n)：表示节：表示节点点n在搜在搜索索树树中中的深的深度度 W(n)：表示节：表示节点点n中中“不不在在位位”的的数数码个数码个数 用全局择优搜索解决该问题用全局择优搜索解决该问题1238476528314765S0Sg启发性信息和估价函数该问题的全局择优搜该问题的全局择优搜 索树如右图所示索树如右图所示在该图中，每个节点在该图中，每个节点 旁边的数字是该节点旁边的数字是该节点 的估价函数值的估价函数值该问题的解为：该问题的解为：S0S1S2S3Sg与/或树的广度优先搜索设有下图所示的设有下图所示的与与/或树，节点按
27、标注顺序进行扩展，或树，节点按标注顺序进行扩展，其中标有其中标有t1、t2、t3的节点是终止节点的节点是终止节点，A、B、C为不为不 可解的端节点。可解的端节点。123A4t15t2Bt3C与/或树的广度优先搜索(1)先扩展先扩展1号节点，生成号节点，生成2 号节点和号节点和3号节点。号节点。(2)扩展扩展2号节点，生号节点，生成成A节节 点和点和4号节点。号节点。(3)扩扩展展3号节点，生成号节点，生成t1节点和节点和5号节点。号节点。由于由于t1为终止为终止 节点，则标记它为可解节节点，则标记它为可解节点点，并应用可解标记过程，不，并应用可解标记过程，不 能确定能确定3号节点是否可节。号节
28、点是否可节。(4)扩展节扩展节点点A，由于，由于A是端节点，因此不可扩展。调是端节点，因此不可扩展。调 用不可解标记过程。用不可解标记过程。与/或树的广度优先搜索(5)扩展扩展4号节点，生号节点，生成成t2节点和节点和B节点。节点。由由于于t2为终止节点为终止节点，标，标 记为可解节点，应记为可解节点，应用用可可解标记解标记 过程，过程，可标可标记记2号节点为可解，号节点为可解，但不能标但不能标记记1号号节点为可解。节点为可解。(6)扩展扩展5号节点，生号节点，生成成t3节点和节点和C节点节点。由于由于t3为终止节为终止节 点点，标记它为可解节点，应用可解标记过程，可标，标记它为可解节点，应用
29、可解标记过程，可标记记1 号节点为可解节点。号节点为可解节点。(7)搜索成功，得到搜索成功，得到由由1、2、3、4、5号节点号节点和和t1、t2、t3节点构成的解树。节点构成的解树。与/或树的深度优先搜索设有下图所示的设有下图所示的与与/或树，其中表有或树，其中表有t1、t2、t3的节点的节点 是是终止节点终止节点，A、B、C为不可解的端节点。若按有界为不可解的端节点。若按有界深度优先搜索，深度优先搜索，设设dm=4，则其，则其节节点扩展顺序为点扩展顺序为：1，3，5，2，4。123A4t15t2Bt3C与/或树的深度优先搜索(1)先扩展先扩展1号节点，生成号节点，生成2号号 节点和节点和3号
30、节点。号节点。(2)扩展扩展3号节点，生号节点，生成成t1节点节点 和和5号节点。由号节点。由于于t1为终止为终止节节 点，则标记它为可解节点，点，则标记它为可解节点，并应用可解标记过程，并应用可解标记过程，不能不能 确定确定3号节点是否可解。号节点是否可解。(3)扩展扩展5号节点，生号节点，生成成t3节点和节点和C节点。由节点。由于于t3为终止节为终止节 点，则标记它为可解节点，并应用可解标记过程，可标点，则标记它为可解节点，并应用可解标记过程，可标 记记3号节点为可解节点，但不能标号节点为可解节点，但不能标记记1号为可解。号为可解。与/或树的深度优先搜索(4)扩展扩展2号节点，生号节点，生
31、成成A节节 点和点和4号节点。号节点。(5)扩展扩展4号节点，生号节点，生成成t2节节 点和点和B节点。由节点。由于于t2为终止为终止节节 点，则标记它为可解节点，点，则标记它为可解节点，并应用可解标记过程，并应用可解标记过程，可标可标 记记2号节点为可解，再往上号节点为可解，再往上 又可标记又可标记1号节点为可号节点为可解。解。(6)搜索成功，得到搜索成功，得到由由1、3、5、2、4号节点号节点即即t1、t2、t3节点构成的解树。节点构成的解树。与/或树的启发式搜索1 i k(4)若若n是是端节点，但又不是终止节端节点，但又不是终止节点点，则则n不可扩展，不可扩展，其代价定义其代价定义为为h
32、(n)=。(5)根节点的代价即为解树的代价。根节点的代价即为解树的代价。h(n)maxc(n,ni )h(ni )k解树的代价可按如下规则计算解树的代价可按如下规则计算若用和代价法，则其计算公式为：若用和代价法，则其计算公式为：h(n)c(n,ni )h(ni )i1若用最大代价法，则其计算公式为：若用最大代价法，则其计算公式为：与/或树的启发式搜索设下图是一棵设下图是一棵与与/或树，它或树，它 包括两棵解树包括两棵解树左边的解树左边的解树由由S0、A、t1、C及及t3组成；组成；右边的解树右边的解树由由S0、B、t2、D及及t4组成。组成。在此与或树中，在此与或树中，t1、t2、t3、t4为
33、终止节点为终止节点；E、F是端是端 节点；边上的数字是该边节点；边上的数字是该边 的代价。的代价。请计算解树的代价。请计算解树的代价。3S022A4 Bt 516Ct2D21t3Et4F与/或树的启发式搜索解：先计算左边的解树解：先计算左边的解树按和代价：按和代价：h(S0)=2+4+6+2=14按最大代价：按最大代价：h(S0)=(2+6)+2=10再计算右边的解树再计算右边的解树按和代价：按和代价：h(S0)=1+5+3+2=11按最大代价：按最大代价：h(S0)=(1+5)+2=83S022A4 Bt 516Ct2D21t3Et4F与/或树的启发式搜索设初始节点设初始节点为为S0，要求搜
34、索要求搜索 过程每次扩展节点时都同时过程每次扩展节点时都同时 扩展两层，且按一层或节点、扩展两层，且按一层或节点、一层与节点的间隔方式进行一层与节点的间隔方式进行 扩展。扩展。S0经过扩展后得到的经过扩展后得到的与与/或树或树 如右图所示。其中，端节点如右图所示。其中，端节点B、C、E、F，下面的数字下面的数字是用启发函是用启发函数数估算估算出的出的h值；值；各个父节点到其子节点的代各个父节点到其子节点的代 价为价为1。S0ADBCEF3332h(B)=3，h(C)=3h(E)=3，h(F)=2按照和代价计算得到：按照和代价计算得到：h(A)=8，h(D)=7 h(S0)=8此时此时S0的右子
35、树是希望树的右子树是希望树与/或树的启发式搜索 依次对依次对当前希望树的端节当前希望树的端节点点进进到的与到的与/或树如右图所示。或树如右图所示。节点节点S0、A、D、E、G、H旁旁边边的的数数字是按字是按和代价和代价法法计算出来的节计算出来的节 点代价。点代价。此时，由此时，由右子右子树求出树求出的的h(S0)=12，由左子树由左子树求出求出的的h(S0)=9。显然显然，左子树的代价小。因此左子树的代价小。因此，当前当前的希望树应改为左子的希望树应改为左子树树。S09A8D11行扩展。对节行扩展。对节点点E扩展扩展两层后两层后得得BCEF337232226G7H与/或树的启发式搜索两层后得到
36、的两层后得到的与与/或树如下或树如下图所示。图所示。2S09对节对节点点B进行扩展，扩进行扩展，扩展展 A8D11BCEF33723226LNOPQ2M6G7H0022由于节点由于节点N和和O是可解节点是可解节点，故调故调用用可解可解标标记记过过程程，得节得节点点L、B也为可也为可解节解节点，但点，但不能不能标标记记S0为为可可解节点解节点，须继续扩展。须继续扩展。当前的希望树仍当前的希望树仍然然是左是左子树子树。与/或树的启发式搜索图所示。图所示。S09对节对节点点C进行扩展，扩展进行扩展，扩展 两层后得到的两层后得到的与与/或树如或树如下下A8D11BCEF3372322276LNOPQ0
37、0222M6RTS005229GH调用可解标记过程，可标调用可解标记过程，可标记记S0为可为可解解节点节点，这就这就得得 到了代价最小的解树。按和代到了代价最小的解树。按和代价价法法，该该最最优优解的解的代代 价为价为9。自然演绎推理自自然演绎然演绎推推理的例理的例子子设已知如下事实：设已知如下事实：(1)(1)只要是需要编程序的课，王程都喜欢。只要是需要编程序的课，王程都喜欢。(2)(2)所有的程序设计语言课都是需要编程序的课。所有的程序设计语言课都是需要编程序的课。(3)C是一门程序设计语言课。是一门程序设计语言课。求证：求证：王程喜王程喜欢欢C C这门课。这门课。证明证明：首先定义谓词首
38、先定义谓词Prog(x)：x是需要编程序的课。是需要编程序的课。Like(x,y):x喜欢喜欢y。Lang(x):x是一门程序设计语言课是一门程序设计语言课自然演绎推理自自然演绎然演绎推推理的例理的例子子把已知事实及待求解问题用谓词公式表示如下：把已知事实及待求解问题用谓词公式表示如下：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/yProg(C),Prog(x)Like(Wang,x)
39、Like(Wang,C)假假 言推言推理理 C/x因此，王程喜因此，王程喜欢欢C这门课。这门课。命题逻辑的消解例如例如：设设C1=PQR，C2=PS，求求C1和和C2的消的消 解式解式C12。解：解：这里这里L1=P，L2=P，通，通过过消解消解可可以得以得到到 C12=QRS例如例如：设设C1=Q，C2=Q，求求C1和和C2的消的消解解式式C12。解：解：这里这里L1=Q，L2=Q，通过通过消消解解可以可以得得到到 C12=NIL命题逻辑的消解例如例如：设设设设C1=P Q，C2=Q，C3=P，求求C1、C2、C3的消的消解解式式C123。解：若先对解：若先对C1、C2消解消解，可得可得到到
40、 C12=P 然后再对然后再对C12和和C3消消解解，得，得到到 C123=NIL 如果改变消解顺序，同样可如果改变消解顺序，同样可以以得到得到相相同的同的 结果，即其消解过程是不唯结果，即其消解过程是不唯一一的。的。其消解消解过程可用右图来其消解消解过程可用右图来表表示，示，该该树称树称为为消解树消解树。P QQPPNILP QPQQNIL命题逻辑的消解设已设已知知的公的公式式集集为为 P,(PQ)R,(ST)Q,T，求证结，求证结论论R。解：解：假设结假设结论论R为假为假,将将R加入公式加入公式 集，并化为子句集：集，并化为子句集：S=P,PQR,SQ,TQ,T,R 其消解过其消解过程如程
41、如右图的消右图的消解演解演绎树所示绎树所示。该树根为空子句。该树根为空子句。子句集子句集S不可满足，即假不可满足，即假设设R为为真是真是错误的，于错误的，于是是R为真。为真。P QR RP QPQT QTTNIL谓词逻辑的消解在谓词逻辑中，由于子句集在谓词逻辑中，由于子句集中中的谓的谓词词一般一般都都含含有有变变元元，因，因此此不能象不能象命命题逻辑那样直接消去互补文题逻辑那样直接消去互补文字字。对于谓词逻辑，需要先用一对于谓词逻辑，需要先用一个个最一最一般般合一合一对对变元进变元进行行置换置换，然后才然后才能能 进行消解。进行消解。谓词谓词逻辑的逻辑的消消解原解原理理 设设C1和和C2是两是
42、两个个没没有公有公共共变变元元的的子子句句，L1和和L2分分别别是是C1和和C2中的中的 文字。如文字。如果果 是是L1和和 L2存在存在最一般合一最一般合一，则称：，则称：C12=(C1-L1)(C2-L2)为为C1和和C2的的二元消解二元消解式式，L1和和L2为为消消解解式上式上的的文文字字。谓词逻辑的消解例：例：设设C1=P(a)R(x)，C2=P(y)Q(b)，求求 C12解解：取取L1=P(a),L2=P(y)，则则L1和和L2的最的最 一般合一一般合一是是=a/y。因此：。因此：C12=(C1-L1)(C2-L2)=(P(a),R(x)-P(a)(P(a),Q(b)-P(a)=(R
43、(x)(Q(b)=R(x),Q(b)=R(x)Q(b)谓词逻辑的消解例：例：设设C1=P(x)Q(a)，C2=P(b)R(x)，求求 C12解解：由于由于C1和和C2有相同的变有相同的变元元x，不符合，不符合定定义的义的要要 求。为了进行消解，需要修求。为了进行消解，需要修改改C2中变中变元元的名字的名字。令令C2=P(b)R(y)，此时此时L1=P(x),L2=P(b)，L1 和和L2的最一般合一的最一般合一是是=b/x。则。则有有:C12=(C1-L1)(C2-L2)=(P(b),Q(a)-P(b)(P(b),R(y)-P(b)=(Q(a)(R(y)=Q(a),R(y)=Q(a)R(y)谓
44、词逻辑的消解例：例：设设 C1=P(a)Q(x)R(x)C2=P(y)Q(b)求求C12对对C1和和C2通过最一通过最一般般合一（合一（=b/x,a/y）的作用，）的作用，可以得到可以得到两个互补两个互补对对。注意：求消解式不能同时消注意：求消解式不能同时消去去两个两个互互补补对对，这样这样的的 结果不是二元消解式。如结果不是二元消解式。如在在=b/x,a/y下，若同时下，若同时 消去两个互补对，所得消去两个互补对，所得的的R(b)不不是是C1和和C2的的二二元元消消 解式。解式。谓词逻辑的消解例：例：设设 C1=P(a)Q(x)R(x)C2=P(y)Q(b)求求C12解解1：取取L1=P(a
45、),L2=P(y)，则，则=a/y是是L1与与L2的最一般合一。此时：的最一般合一。此时：C12=Q(x)R(x)Q(b)解解2：取取L1=Q(x)，L2=Q(b)，则，则=b/x是是L1与与L2的最一般合一。此时：的最一般合一。此时：C12=P(a)R(b)P(y)谓词逻辑的消解例：例：设设 C1=P(x)P(f(a)Q(x)，C2=P(y)R(b)求求C12解：解：对参加消解的某个子句，对参加消解的某个子句，若若其内部有可合一的文其内部有可合一的文 字字，则在进行消解之前应先对这些文字进行合一。，则在进行消解之前应先对这些文字进行合一。本例的本例的C1中有可合一的文中有可合一的文字字P(x
46、)与与P(f(a)，若用它们的，若用它们的 最一般合最一般合一一=f(a)/x进行代换，可得进行代换，可得到到 ：C1=P(f(a)Q(f(a)此时对此时对C1与与C2进行消解。进行消解。选选L1=P(f(a),L2=P(y)，L1和和L2的最一般合一的最一般合一是是=f(a)/y，则可得，则可得到到C1和和C2的的 二元消解式为：二元消解式为：C12=R(b)Q(f(a)谓词逻辑的消解例：例：设设 C1=P(y)P(f(x)Q(g(x)C2=P(f(g(a)Q(b)求求C12 解：解：对对C1，取最一般合，取最一般合一一 =f(x)/y，得得C1的因子的因子 C1=P(f(x)Q(g(x)对
47、对C1的因子的因子和和C2消解消解（=g(a)/x），可得：），可得：C12=Q(g(g(a)Q(b)谓词逻辑的消解例：例：已知已知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化成化成子子句集句集，得得到到谓词逻辑的消解最后应用谓词逻辑的消解原最后应用谓词逻辑的消解原理理对上对上述述
48、子句子句集集进进行行消消 解，其过程为：解，其过程为：(6)A(x,y)B(y)(7)B(n)(8)NILF(1)A(x,y)B(y)C(f(x)(2)A(u,v)B(v)D(u,f(u)(3)(3)C(z)(4)A(m,n)(5)B(k)G(1)和和(3)消解，取消解，取=f(x)/z(4)和和(6)消解，消解，取取=m/x,n/y(5)和和(7)消解，取消解，取=n/k谓词逻辑的消解因此，因此，G是是F 的逻辑结论。的逻辑结论。上述消解过程可用如下消解上述消解过程可用如下消解树树来表示来表示A(x,y)B(y)C(f(x)C(z)A(x,y)B(y)A(m,n)B(n)B(k)NILf(x
49、)/zm/x,n/yn/k谓词逻辑的消解例例：“快乐学快乐学生生”问题问题假设：假设：任何通过计算机考试并获奖的人都是快乐的，任任何通过计算机考试并获奖的人都是快乐的，任 何肯学习或幸运的人都可以通过所有考试，张不肯学习何肯学习或幸运的人都可以通过所有考试，张不肯学习 但他是幸运的，任何幸运的人都能获奖。但他是幸运的，任何幸运的人都能获奖。求证：求证：张是快乐的。张是快乐的。解：解：先定义谓词：先定义谓词：Pass(x,y)：x可以通过可以通过y考试考试 Win(x,prize)：x能获得奖励能获得奖励 Study(x)：x肯学习肯学习 Happy(x)：x是快乐的是快乐的 Lucky(x)：
50、x是幸运的是幸运的谓词逻辑的消解再将问题用谓词表示如下：再将问题用谓词表示如下：“任何通过计算机考试并奖的人都是快乐的任何通过计算机考试并奖的人都是快乐的”(x)(Pass(x,computer)Win(x,prize)Happy(x)“任何肯学习或幸运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试”(x)(y)(Study(x)Lucky(x)Pass(x,y)“张不肯学习但他是幸运的张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)“任何幸运的人都能获奖任何幸运的人都能获奖”(x)(Lucky(x)Win(x,prize)结论结论“张是快乐的张是快乐的”
