AI-7(本)人工智能课件.ppt

《AI-7(本)人工智能课件.ppt》由会员分享，可在线阅读，更多相关《AI-7(本)人工智能课件.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能基础人工智能基础归结演绎方法归结演绎方法归结反演归结反演、规则演绎规则演绎n定理的自动证明定理的自动证明一般表示形式为：一般表示形式为：F1,F2,Fn|=WF1,F2,Fn|=WnF1,F2,FnF1,F2,Fn合适公式合适公式n公式间隐含合取关系，构成一个公式集公式间隐含合取关系，构成一个公式集(公理集、事实集公理集、事实集)nW W待证明的一个合适公式待证明的一个合适公式(定理、目标公式定理、目标公式)n证明的方法证明的方法分二类：分二类：n演绎法演绎法直接证明直接证明F1F2Fn F1F2Fn W W为永真；为永真；*从而，当公式集为真时，定理从而，当公式集为真时，定理W W成

2、立。成立。n反证法反证法间接证明间接证明(F1F2Fn(F1F2Fn W)W)为永假。为永假。即证明即证明 F1F2Fn F1F2Fn W W的永假性，的永假性，即即F1,F2,Fn F1,F2,Fn WW是一个矛盾集。是一个矛盾集。2.4 基于规则的演绎推理基于规则的演绎推理动机动机n基于归结的演绎推理基于归结的演绎推理n简单易行简单易行将问题求解的依据将问题求解的依据(事实或公式事实或公式)和目标以合适公式加以和目标以合适公式加以形式化描述，交由归结反演系统和问答系统执行。形式化描述，交由归结反演系统和问答系统执行。n丢失隐含于合适公式的启发式知识丢失隐含于合适公式的启发式知识n合适公式标

3、准化为高度统一的子句集合适公式标准化为高度统一的子句集:PQ R P QRn效率低下，难以适应于复杂的应用域效率低下，难以适应于复杂的应用域n归结演绎并非人类的自然思维方式归结演绎并非人类的自然思维方式难以建立高水平的问题求解系统难以建立高水平的问题求解系统n基于规则的演绎推理基于规则的演绎推理n保留蕴涵式，将其作为推理规则，用于直接推导目标公式保留蕴涵式，将其作为推理规则，用于直接推导目标公式n符合人的自然思维方式符合人的自然思维方式n通过规则通过规则(作为启发式知识作为启发式知识)更有效地引导演绎推理过程更有效地引导演绎推理过程n是比归结反演更为有效的推理技术，广泛地应用于许多问题求解任务

4、中是比归结反演更为有效的推理技术，广泛地应用于许多问题求解任务中2.4 基于规则的演绎推理基于规则的演绎推理总体描述总体描述n规则演绎将求解问题所需的知识分为二类：规则演绎将求解问题所需的知识分为二类：n规则规则表示为蕴涵式，作为启发式知识表示为蕴涵式，作为启发式知识(表示应用域中存在表示应用域中存在 的规律和法则的规律和法则)，引导演绎推理过程。，引导演绎推理过程。n事实事实表示为非蕴涵形式的合适公式，作为应用规则进行表示为非蕴涵形式的合适公式，作为应用规则进行 推理时参考的有关问题状态和环境的知识。推理时参考的有关问题状态和环境的知识。n规则演绎的任务规则演绎的任务从给定的事实从给定的事实

5、(问题的状态和环境知识问题的状态和环境知识)和规则，证明某个目标公式成立。和规则，证明某个目标公式成立。n分类分类：n正向演绎正向演绎从事实出发，应用规则不断推导出中间结果从事实出发，应用规则不断推导出中间结果 作为新的事实，直至推导出目标公式。作为新的事实，直至推导出目标公式。n逆向演绎逆向演绎从目标公式出发，逆向应用规则不断推导出子目标，从目标公式出发，逆向应用规则不断推导出子目标，直至所有子目标就是给定的事实为止。直至所有子目标就是给定的事实为止。(目标公式通过逆向推理目标公式通过逆向推理找到了支持其成立的所有依据找到了支持其成立的所有依据)2.4 基于规则的演绎推理基于规则的演绎推理总

6、体描述总体描述主要内容：主要内容：基于规则的正向演绎推理基于规则的正向演绎推理 基于规则的逆向演绎推理基于规则的逆向演绎推理 演绎推理的应用讨论演绎推理的应用讨论 逻辑语言逻辑语言Prolog(略略)2.4.1 基于规则的正向演绎推理基于规则的正向演绎推理1.问题求解的规范表示问题求解的规范表示事实、规则集和目标事实、规则集和目标n事实事实表示为不含蕴涵符号的文字与或形表示为不含蕴涵符号的文字与或形n相比子句集，文字与或形更接近原始表达式相比子句集，文字与或形更接近原始表达式例：有事实表达式：例：有事实表达式：(x)(y)(z)Q(x,y)(R(y)P(z)S(x,z)化简：化简：(x)(y)

7、(z)Q(x,y)(R(y)P(z)S(x,z)Q(A,y)(R(y)P(f(y)S(A,f(y)对顶层合取式的各项换名：对顶层合取式的各项换名：Q(A,w)(R(y)P(f(y)S(A,f(y)1.问题求解的规范表示问题求解的规范表示事实事实n事实表达式的文字与或形可用事实表达式的文字与或形可用与或图与或图表示：表示：n若母式为析取式：若母式为析取式：E1E2Ek 以一个以一个K-连接指向各析取项连接指向各析取项Ein若母式为合取式：若母式为合取式：E1E2 Ek 以以k个个1-连接指向各合取项连接指向各合取项Ei n与或图例：与或图例：n为使析取符号为使析取符号与与K-连接同向，连接同向，

8、根节点在图下方根节点在图下方n根节点根节点事实表达式事实表达式n叶节点叶节点文字与或形中的每一个文字文字与或形中的每一个文字 n借用与或图表示事实表达式，借用与或图表示事实表达式，但语义上与表示搜索过程的与但语义上与表示搜索过程的与 或图有本质的区别。或图有本质的区别。1.问题求解的规范表示问题求解的规范表示规则规则n正向演绎推理以正向方式使用规则正向演绎推理以正向方式使用规则(F规则规则),化简为化简为:L WnL为单文字为单文字便于通过便于通过L和与或图叶节点的匹配来激活规则和与或图叶节点的匹配来激活规则nW是文字与或形是文字与或形L1L2 W L1 W,L2 WL1L2 W L1 L2W

9、 或或 L2 L1W例：设表示规则的原始蕴涵式为：例：设表示规则的原始蕴涵式为：(x)(y)(z)P(x,y,z)=(u)Q(x,u)R(x,u)n暂时消去蕴涵符号，化简为文字与或形：暂时消去蕴涵符号，化简为文字与或形：P(x,y,f(x,y)Q(x,u)R(x,u)n恢复蕴涵式表示：恢复蕴涵式表示：P(x,y,f(x,y)=Q(x,u)R(x,u)1.问题求解的规范表示问题求解的规范表示目标目标n目标目标化简后限定表示为文字的析取式化简后限定表示为文字的析取式(子句子句)n量词消去方法取事实表达式的对偶形式量词消去方法取事实表达式的对偶形式：将全称量词的约将全称量词的约束变量以束变量以Skl

10、em函数或常量取代，子句隐含地受存在量词约束函数或常量取代，子句隐含地受存在量词约束.归结反演将目标公式取反，归结反演将目标公式取反，例：目标公式：例：目标公式：(x)(y)(z)P(x,y,z)Q(x,y)n以以Sklem 常量常量A、Sklem 函数函数g(y)分别取代约束变量分别取代约束变量x、z，再消去全称量词再消去全称量词:(y)P(A,y,g(y)Q(A,y)n消去存在量词，变量换名：消去存在量词，变量换名：P(A,y,g(y)Q(A,w)2.正向演绎推理的实现正向演绎推理的实现n借借助助与与或或图图表表示示方方式式，从从事事实实表表达达式式出出发发，不不断断用用激激活活(左左部部

11、单单文文字字和和与与或或图图叶叶节节点点匹匹配配)的的F规规则则对对与与或或图图进进行行变变换换(扩扩展展与与或或图图)，直直至至得得到到一一个个将将目目标标表表达达式式(子子句句)包包含含的的文文字字作作为为叶节点的一致解图。叶节点的一致解图。n命题逻辑命题逻辑n谓词逻辑谓词逻辑2.正向演绎推理的实现正向演绎推理的实现命题逻辑命题逻辑n方法方法建立相应于事实表达式的初始与或图建立相应于事实表达式的初始与或图(树树)，选用激活的规则对，选用激活的规则对 与或图进行变换与或图进行变换(易寻找左部单文字和与或图中叶节点匹配的规则易寻找左部单文字和与或图中叶节点匹配的规则)n与或图的变换与或图的变换

12、将激活的规则加入与或图：将激活的规则加入与或图：n规则左部单文字作为节点插入与或图规则左部单文字作为节点插入与或图n通过匹配弧通过匹配弧=和与或图相应叶节点连接和与或图相应叶节点连接n规则右部以与或图子图的方式插入规则右部以与或图子图的方式插入n目标文字加入与或图：目标文字加入与或图：目标公式中的某个文字和与或图叶节点匹配目标公式中的某个文字和与或图叶节点匹配 时，目标文字作为目标节点时，目标文字作为目标节点(方框指示方框指示)插入与插入与 或图或图,并通过匹配弧和与或图相应叶节点连接。并通过匹配弧和与或图相应叶节点连接。n演绎推理的成功结束条件演绎推理的成功结束条件 获得终止于目标节点的一个

13、解图获得终止于目标节点的一个解图 不要求解图的所有叶节点都是目标节点不要求解图的所有叶节点都是目标节点例：设事实表达式为：例：设事实表达式为：(PQ)(RS)T给定规则集：给定规则集：P C1C2,S C3C4,T C5目标公式为：目标公式为：C1C3C52.正向演绎推理的实现正向演绎推理的实现n借借助助与与或或图图表表示示方方式式，从从事事实实表表达达式式出出发发，不不断断用用激激活活(左左部部单单文文字字和和与与或或图图叶叶节节点点匹匹配配)的的F规规则则对对与与或或图图进进行行变变换换(扩扩展展与与或或图图)，直直至至得得到到一一个个将将目目标标表表达达式式(子子句句)包包含含的的文文字

14、字作作为为叶节点的一致解图。叶节点的一致解图。n命题逻辑命题逻辑n谓词逻辑谓词逻辑n规则或目标文字的激活判断规则或目标文字的激活判断须对单文字和与或图中的相应叶节须对单文字和与或图中的相应叶节点作点作合一处理合一处理n演绎推理过程可能会对同一演绎推理过程可能会对同一变量变量进行进行不一致的置换不一致的置换，导致不一致，导致不一致解图的生成解图的生成2.正向演绎推理的实现正向演绎推理的实现谓词逻辑谓词逻辑n猎狗问题例：猎狗问题例：事实：事实：Fido 会吠叫会吠叫(Barks)和咬人和咬人(Bites),否则否则Fido 就不是狗就不是狗(Dog).规则：所有梗规则：所有梗(Terrier,一种

15、小猎狗一种小猎狗)都是狗。都是狗。所有会吠叫的东西都是吵人的所有会吠叫的东西都是吵人的(Noisy)。目标：存在某个东西目标：存在某个东西,除非它不是梗除非它不是梗,否则是吵人的。否则是吵人的。n形式化表示：形式化表示：事实表达式：事实表达式：Barks(Fido)Bites(Fido)Dog(Fido)规则规则:R1:(x)Terrier(x)=Dog(x)R2:(y)Barks(y)=Noisy(y)目标公式：目标公式：(z)Terrier(z)Noisy(z)2.正向演绎推理的实现正向演绎推理的实现谓词逻辑谓词逻辑猎狗问题例：猎狗问题例：n形式化表示：形式化表示：事实表达式：事实表达式：

16、Barks(Fido)Bites(Fido)Dog(Fido)规则规则:R1:(x)Terrier(x)=Dog(x)R2:(y)Barks(y)=Noisy(y)目标公式：目标公式：(z)Terrier(z)Noisy(z)n 标准化：标准化：规则：规则：R1:Dog(x)=Terrier(x)R2:Barks(y)=Noisy(y)目标公式目标公式:Terrier(z)Noisy(z1)事实不含蕴涵符号的文字与或形事实不含蕴涵符号的文字与或形规则规则F规则：规则：L W(单文字、文字与或形单文字、文字与或形)目标文字的析取式，量词用目标文字的析取式，量词用对偶形式消去对偶形式消去2.正向演

17、绎推理的实现正向演绎推理的实现猎狗问题例猎狗问题例n 解图置换：解图置换：S=Fido/z1,Fido/y,Fido/z,Fido/x 其合一复合就是其自身，得到一致解图其合一复合就是其自身，得到一致解图n 解答：解答：Terrier(Fido)Noisy(Fido)与或图与或图n事实表达式：事实表达式：Barks(Fido)Bites(Fido)Dog(Fido)n 标准化：标准化：规则：规则：R1:Dog(x)=Terrier(x)R2:Barks(y)=Noisy(y)目标公式目标公式:Terrier(z)Noisy(z1)2.正向演绎推理的实现正向演绎推理的实现谓词逻辑谓词逻辑n解图置

18、换解图置换收集解图中所有变量的置换收集解图中所有变量的置换(为置换元素为置换元素)于一于一个置换中个置换中n解图置换的合一复合处理：解图置换的合一复合处理：(1)设解图置换中元素形如设解图置换中元素形如 ti/vi(i=1,2,n)，ti指示置换项，指示置换项，vi指示变量。指示变量。(2)建立两个分别由建立两个分别由ti和和 vi构成的表达式构成的表达式(i=1,2,n)：U1=(v1,v2,vn)U2=(t1,t2,tn)(3)检查检查U1和和U2能否合一能否合一,若不能合一若不能合一,则该置换是不一致的，进而则该置换是不一致的，进而解图是不一致的；若能合一解图是不一致的；若能合一,则建立

19、起使则建立起使U1和和U2合一的置换合一的置换,称为称为解图置换解图置换S的合一复合的合一复合,进而解图是一致的。进而解图是一致的。解图置换解图置换:S=Fido/z1,Fido/y,Fido/z,Fido/x U1=(z1,y,z,x)U2=(Fido,Fido,Fido,Fido)2.正向演绎推理的实现正向演绎推理的实现猎狗问题例猎狗问题例事实：事实：Fido 会吠叫会吠叫(Barks)和咬人和咬人(Bites)，否则，否则Fido 就不是狗就不是狗(Dog)。规则：所有梗规则：所有梗(Terrier,一种小猎狗一种小猎狗)都是狗。都是狗。所有会吠叫的东西都是吵人的所有会吠叫的东西都是吵人

20、的(Noisy)。目标：存在某个东西目标：存在某个东西,除非它不是梗除非它不是梗,否则是吵人的。否则是吵人的。n形式化表示：形式化表示：事实表达式：事实表达式：Barks(Fido)Bites(Fido)Dog(Fido)规则规则:R1:(x)Terrier(x)=Dog(x)R2:(y)Barks(y)=Noisy(y)目标公式：目标公式：(z)Terrier(z)Noisy(z)n 标准化：标准化：规则：规则：R1:Dog(x)=Terrier(x)R2:Barks(y)=Noisy(y)目标公式目标公式:Terrier(z)Noisy(z1)n 解图置换：解图置换：S=Fido/z1,F

21、ido/y,Fido/z,Fido/xn 解答：解答：Terrier(Fido)Noisy(Fido)事实不含蕴涵符号的文字与或形事实不含蕴涵符号的文字与或形规则规则F规则：规则：L W(单文字、文字与或形单文字、文字与或形)目标文字的析取式，量词用目标文字的析取式，量词用对偶形式消去对偶形式消去与或图与或图2.正向演绎推理的实现正向演绎推理的实现谓词逻辑谓词逻辑n注意：注意：n规则的使用相互独立，每条规则取不同变量名。规则的使用相互独立，每条规则取不同变量名。n演绎过程中同一规则或同一文字的多次使用，必须换名。演绎过程中同一规则或同一文字的多次使用，必须换名。n在解图不一致的情况下，并不意味

22、着演绎推理失败，因为在解图不一致的情况下，并不意味着演绎推理失败，因为可能存在另一解图并且其是一致的。只有在找不到一致解可能存在另一解图并且其是一致的。只有在找不到一致解图的情况下，演绎推理失败。图的情况下，演绎推理失败。2.4.2 基于规则的逆向演绎推理基于规则的逆向演绎推理n正向演绎推理正向演绎推理建立相应于建立相应于事实表达式事实表达式的初始与或图的初始与或图(树树)，选用激活的选用激活的F规则对与或图变换规则对与或图变换(左部单文字和与或图叶节点匹配左部单文字和与或图叶节点匹配),将将目标表达式目标表达式(子句子句)包含的文字作为叶节点的一致解图。包含的文字作为叶节点的一致解图。n逆向

23、演绎推理逆向演绎推理与正向演绎推理形成与正向演绎推理形成对偶关系对偶关系,其其从从目目标标公公式式出出发发,逆逆向向应应用用规规则则对对相相应应于于目目标标公公式式的的原原始始与与或或图图进进行行变变换换，直直至至得得到到一一个个所所有有叶叶节节点点都都是是事事实实节节点点(以以事事实实表表达达式式中中的文字作为节点内容的节点的文字作为节点内容的节点)的一致解图为止。的一致解图为止。1.问题求解的规范表示问题求解的规范表示事实、规则集、目标事实、规则集、目标其标准化表示形式与正向演绎呈现对偶关系其标准化表示形式与正向演绎呈现对偶关系2.4.2 基于规则的逆向演绎推理基于规则的逆向演绎推理1.问

24、题求解的规范表示目标公式问题求解的规范表示目标公式n目标公式的表示不受限制，化简为不含蕴涵符号的文字与或形目标公式的表示不受限制，化简为不含蕴涵符号的文字与或形例例:目标公式目标公式：(x)(y)P(x)=Q(x,y)(R(x)=S(x,y)化简：化简：(x)(y)P(x)Q(x,y)(R(x)S(x,y)n全称量词的约束变量以全称量词的约束变量以Sklem函数或常量取代函数或常量取代,对偶对偶方式方式消去消去量词量词,隐含着变量受存在量词的约束隐含着变量受存在量词的约束 P(x)Q(x,f(x)(R(x)S(x,f(x)n通过通过换名换名，使顶层析取式的各析取项不含同名变量，使顶层析取式的各

25、析取项不含同名变量 P(z)(Q(x,f(x)(R(x)S(x,f(x)n目标公式的文字与或形可用目标公式的文字与或形可用与或图与或图表示表示1.问题求解的规范表示问题求解的规范表示逆向演绎推理下的目标公式逆向演绎推理下的目标公式目标公式的与或图表示目标公式的与或图表示目标公式的文字与或形可用与或图表示：目标公式的文字与或形可用与或图表示：n若母式为合取式：若母式为合取式：E1E2 Ek 以一个以一个k-连接指向各合取项连接指向各合取项Ein若母式为析取式：若母式为析取式：E1E2 Ek 以以k个个1-连接指向各析取项连接指向各析取项Ei与或图例与或图例n为使合取为使合取(连词连词)符号与符号

26、与K-连接连接 同向，根节点在图上方同向，根节点在图上方n根节点根节点目标公式目标公式n叶节点叶节点目标公式中的每一个文字目标公式中的每一个文字1.问题求解的规范表示问题求解的规范表示规则规则n逆向演绎推理以逆向方式使用规则逆向演绎推理以逆向方式使用规则(B规则规则),化简为化简为:W LnL单文字单文字,便于通过便于通过L和与或图叶节点的匹配来激活规则和与或图叶节点的匹配来激活规则 W L1L2 W L1,W L2nW与或形与或形 例例:设表示规则的原始蕴涵式为：设表示规则的原始蕴涵式为：(x)(y)(z)P(x,y,z)Q(y,z)(u)R(x,u)化简：化简：(x)(y)(z)P(x,y

27、,z)Q(y,z)(u)R(x,u)P(x,y,f(x,y)Q(y,f(x,y)R(x,u)恢复蕴涵式表示：恢复蕴涵式表示：P(x,y,f(x,y)Q(y,f(x,y)R(x,u)1.问题求解的规范表示问题求解的规范表示事实事实n事实表达式事实表达式表示为文字的合取式表示为文字的合取式n消去量词时将消去量词时将存在量词存在量词的约束变量以的约束变量以Sklem函数或常量取函数或常量取代，合取式隐含地受全称量词约束。代，合取式隐含地受全称量词约束。n逆向演绎推理不断用激活逆向演绎推理不断用激活(右部单文字和与或图叶节点匹配右部单文字和与或图叶节点匹配)的的B规规则则对相应于对相应于目标公式的与或

28、图目标公式的与或图进行变换，直到获得一个叶节点全是进行变换，直到获得一个叶节点全是事实节点事实节点()的一致解图。的一致解图。n与或图的变换与或图的变换将激活的规则加入与或图：将激活的规则加入与或图：n规则右部单文字作为节点插入与或图规则右部单文字作为节点插入与或图n通过匹配弧通过匹配弧=和与或图相应叶节点连接和与或图相应叶节点连接n规则左部以与或图子图的方式插入规则左部以与或图子图的方式插入n事实文字加入与或图：事实文字加入与或图：和与或图叶节点匹配，其作为事实节点和与或图叶节点匹配，其作为事实节点()插入插入与或图，通过匹配弧和与或图相应叶节点连接。与或图，通过匹配弧和与或图相应叶节点连接

29、。n不要求所有事实文字都进入解图不要求所有事实文字都进入解图n是给目标公式寻找原始证据是给目标公式寻找原始证据(事实文字事实文字)的过程，当推理的各个分支的过程，当推理的各个分支(解图解图中的分支中的分支)都到达事实节点时，目标公式有了支持它成立的足够证据。都到达事实节点时，目标公式有了支持它成立的足够证据。2.逆向演绎推理的实现逆向演绎推理的实现2.逆向演绎推理的实现逆向演绎推理的实现不等式问题例：不等式问题例：令谓词令谓词G表示大于表示大于()关系，关系，plus,times和和divides分别表示算术操作分别表示算术操作+、*、/，例如：，例如：G(x,y):xy;plus(A,B,C

30、):A+B+C;times(A,B,C):A*B*C;divides(A,B):A/B已知有事实：已知有事实：(E0)(B0)(A0)(C0)(CE)B规则：规则：(x0)(yz)(x+y)z (x0)(yz)(xyxz)(xwy)(y0)(x/yw)求证：求证：B(A+C)/EB形式化表示：形式化表示：事实表达式：事实表达式：G(E,0)G(B,0)G(A,0)G(C,0)G(C,E)规则：规则：R1:G(x3,0)G(y3,z3)G(plus(x3,y3),z3)R2:G(x2,0)G(y2,z2)G(tims(x2,y2),times(x2,z2)R3:G(x1,times(w1,y1)

31、G(y1,0)G(divides(x1,y1),w1)目标公式：目标公式：G(divides(times(B,plus(A,C),E),B)标准化：标准化：与或图与或图:2.逆向演绎推理的实现逆向演绎推理的实现不等式问题例：不等式问题例：令谓词令谓词G表示大于表示大于()关系，关系，plus,times和和divides分别表示算术操作分别表示算术操作+、*、/，例如：，例如：G(x,y):xy;plus(A,B,C):A+B+C;times(A,B,C):A*B*C;divides(A,B):A/B已知有事实已知有事实:(E0)(B0)(A0)(C0)(CE)B规则：规则：(x0)(yz)(

32、x+y)z (x0)(yz)(xyxz)(xwy)(y0)(x/yw)求证：求证：B(A+C)/EB形式化表示：形式化表示：事实表达式：事实表达式：G(E,0)G(B,0)G(A,0)G(C,0)G(C,E)规则：规则：R1:G(x3,0)G(y3,z3)G(plus(x3,y3),z3)R2:G(x2,0)G(y2,z2)G(tims(x2,y2),times(x2,z2)R3:G(x1,times(w1,y1)G(y1,0)G(divides(x1,y1),w1)目标公式：目标公式：G(divides(times(B,plus(A,C),E),B)不等式问题的与或图不等式问题的与或图2.逆

33、向演绎推理的实现逆向演绎推理的实现n不等式问题例：不等式问题例：n解图置换解图置换 S=times(B,plus(A,C)/x1,E1/y1,B/w1,B/x2,plus(A,C)/y2,E/z2,A/x3,C/y3,E/z3)置换的合一复合置换的合一复合S就是其自身，故解图一致就是其自身，故解图一致n每次使用规则时都对变量作换名处理每次使用规则时都对变量作换名处理n事实表达式中的文字事实表达式中的文字G(C,0)未出现在解图中未出现在解图中,但不影响推理成功结束但不影响推理成功结束n事实可以原子谓词公式的集合形式给出事实可以原子谓词公式的集合形式给出,原子事实间隐含合取关系原子事实间隐含合取

34、关系2.4.3 演绎推理的应用讨论演绎推理的应用讨论1.正、逆向演绎推理的特点比较正、逆向演绎推理的特点比较n问题求解的描述问题求解的描述 事实、规则、目标事实、规则、目标n采用同样方式标准化这采用同样方式标准化这3个部分个部分的表示的表示n事实和规则的标准化过程事实和规则的标准化过程 对量词及其约束变元的处理遵对量词及其约束变元的处理遵从合取范式的化简要求。从合取范式的化简要求。n目标的标准化过程采用对偶目标的标准化过程采用对偶原则作处理原则作处理,即将全称量词的约即将全称量词的约束变量以束变量以Sk lem函数或常量取函数或常量取代，并在量词消去后隐含着所代，并在量词消去后隐含着所有变量均

35、受存在量词的约束。有变量均受存在量词的约束。正向演绎推理正向演绎推理逆向演绎推理逆向演绎推理问题求解问题求解的描述的描述事实事实文字与或形文字与或形事实事实文字合取式文字合取式规则规则L L W W单文字单文字 与或形与或形规则规则W W L L目标目标文字析取形文字析取形目标目标文字与或形文字与或形初始初始与或图与或图相应于事实表达式相应于事实表达式K-K-连接连接相应于目标公式相应于目标公式K-K-连接连接演绎推理演绎推理F F规则规则事实事实目标目标B B规则规则目标目标事实事实结束条件结束条件终止于目标节点终止于目标节点的一致解图的一致解图终止于事实节点终止于事实节点的一致解图的一致解

36、图共同特点共同特点:n以与或形和相应的与或图来表示和支持推理过程以与或形和相应的与或图来表示和支持推理过程n推理控制的基本策略推理控制的基本策略通过不断激活规则去变换与或图，直至搜索到某个通过不断激活规则去变换与或图，直至搜索到某个一致解图为止。一致解图为止。2.4.3 演绎推理的应用讨论演绎推理的应用讨论2.双向演绎推理双向演绎推理n优势互补优势互补n处理结束条件的复杂性以及需分别支持正、逆向推理，增加了处理结束条件的复杂性以及需分别支持正、逆向推理，增加了系统设计和知识获取的困难系统设计和知识获取的困难n更实用化的方式更实用化的方式分解复杂的问题求解任务，根据子任务的分解复杂的问题求解任务

37、，根据子任务的特点选用特点选用2.4.3 演绎推理的应用讨论演绎推理的应用讨论 3.解图搜索修剪策略解图搜索修剪策略n动机：动机：n与或图中的与或图中的“或或”关系导致多关系导致多个解图存在的可能个解图存在的可能 n基本的解图搜索策略基本的解图搜索策略先生先生成一个任意解图，再检索其一成一个任意解图，再检索其一致性；若否，则继续致性；若否，则继续若解图生成后才检查其一致性，太迟若解图生成后才检查其一致性，太迟n解图的不一致性往往在早期就解图的不一致性往往在早期就可发现，及时修剪有重要意义可发现，及时修剪有重要意义图图2.34 修剪不一致局部解图修剪不一致局部解图n修剪策略修剪策略每当以规则扩展

38、局部解图时，就及时检查解图每当以规则扩展局部解图时，就及时检查解图 置换的一致性，并随即修剪掉不一致的局部解图，以免置换的一致性，并随即修剪掉不一致的局部解图，以免 除对这种局部解图的进一步徒劳搜索。除对这种局部解图的进一步徒劳搜索。例：例：2.4 逻辑编程语言逻辑编程语言Prolog 一种面向演绎推理的逻辑型程序设计语言一种面向演绎推理的逻辑型程序设计语言Prolog程序实例程序实例(Turbo Prolog 2.0环境环境)谁是谁是john的朋友？的朋友？小结 问题求解的基本方法：搜索、推理一般图搜索、基于问题归约的与或图搜索一般图搜索、基于问题归约的与或图搜索n相同相同应用状态空间概念，

39、强调设计高效的算法应用状态空间概念，强调设计高效的算法n设计高效算法的关键设计高效算法的关键引入应用领域相关的启发式知识引入应用领域相关的启发式知识n启发式函数设计可采纳性启发式函数设计可采纳性n好的启发式函数不仅能快速搜索到解答，且能确保搜索算法可采纳性好的启发式函数不仅能快速搜索到解答，且能确保搜索算法可采纳性n考虑设计代价，放弃可采纳性，只求搜索到代价较小解答路径考虑设计代价，放弃可采纳性，只求搜索到代价较小解答路径/解图解图n本质区别本质区别关注的问题求解策略关注的问题求解策略n前者应用操作算子逐步缩小问题状态和目标状态的差别前者应用操作算子逐步缩小问题状态和目标状态的差别。与或图特例

40、与或图特例,解路径解路径n关注于把复杂的问题逐步关注于把复杂的问题逐步/逐层分解为子问题逐层分解为子问题。搜索的结果是解图搜索的结果是解图 小结问题求解的基本方法：搜索、推理n一阶谓词演算一阶谓词演算人工智能研究和应用的重要基础人工智能研究和应用的重要基础 提供合适公式提供合适公式实现实现演绎推理的形式化表示演绎推理的形式化表示建立建立基于归结基于归结/规则的演绎推理方法规则的演绎推理方法n归结演绎推理的理论基础归结演绎推理的理论基础海伯伦理论、鲁滨逊归结原理海伯伦理论、鲁滨逊归结原理n归结演绎推理的基本方法归结演绎推理的基本方法 寻找具有互补文字的子句对寻找具有互补文字的子句对产生产生归结式

41、归结式归结归结空子句空子句证明证明子句集不可满足子句集不可满足n归结反演归结反演自动定理证明自动定理证明 待证明的目标公式取反待证明的目标公式取反加入加入表示事实的公式集表示事实的公式集标准化标准化子句集子句集归结归结空子句空子句证明证明目标公式成立目标公式成立n缺点缺点：不符合人的思维方式，规范化子句集时丢失了表示为蕴涵式的启发式知识。：不符合人的思维方式，规范化子句集时丢失了表示为蕴涵式的启发式知识。n基于规则的演绎推理基于规则的演绎推理直接证明，正、逆向两类直接证明，正、逆向两类n演绎推理方式符合人的思维习惯，自然、直观、易于理解和接受；演绎推理方式符合人的思维习惯，自然、直观、易于理解

42、和接受；n保留了蕴涵式保留了蕴涵式(推理规则推理规则)表示的启发式知识，有利于提高问题求解效率。表示的启发式知识，有利于提高问题求解效率。n归结演绎推理、规则演绎推理效率仍较低归结演绎推理、规则演绎推理效率仍较低n知识表示的高度统一性知识表示的高度统一性(子句集、与或形子句集、与或形)不利于有效地表示关于复杂世界的知不利于有效地表示关于复杂世界的知识和控制推理过程。识和控制推理过程。n实用的智能问题求解系统已很少设计为纯粹的归结演绎和规则演绎推理系统。实用的智能问题求解系统已很少设计为纯粹的归结演绎和规则演绎推理系统。在合适的情况下，把它们作为复杂系统的子系统。在合适的情况下，把它们作为复杂系统的子系统。