《[PPT模板]人工智能_ch3.ppt》由会员分享,可在线阅读,更多相关《[PPT模板]人工智能_ch3.ppt(60页珍藏版)》请在三一文库上搜索。
1、人工智能与知识工程,教学计划,人工智能及其发展 知识表示 确定性推理 不确定推理 搜索策略 机器学习知识获取 专家系统,第三章 确定性推理,推理中的一般问题 自然演绎 归结演绎 与/或形演绎推理,1、推理中的一般问题,推理 推理是按照某种策略由已知判断推出另一判断(新判断)的思维过程。 用于实现推理的程序称为推理机 推理的分类 按推出新判断的方法分类 演绎推理 从全称判断推出特称判断或单称判断的推理过程/方法 三段论: 大前提已知的一般性知识 小前提关于具体情况或个别事实的判断 结论由大前提推出的适合于小前提的判断(结论) 例:,大前提:如果地球围绕太阳旋转,那么月球就是围绕地球旋转。 小前提
2、:今天地球是围绕太阳旋转的。 结论:今天月球就是围绕地球旋转。 特点:演绎推出的结论都包含在前提的一般性知识中。如果大前提正确,得到的结论肯定正确。 归纳推理 从众多的事例(事实)中归纳出一般性结论(知识)的推理过程。 穷举所有事例(事实)完全归纳推理 列举部分事例(事实)不完全归纳推理 例 特点: 完全归纳推理能保证结论正确,但很难做到。 不完全归纳推理不能保证结论正确,经常使用的形式。 注:归纳推理是人类思维活动中最基本、最常用的一种推理方式。如果经归纳得到的结论能从理论上证明其正确性,就能得到普遍实用的知识。,默认推理 在知识不完全的情况下假设(默认)某些条件已经具备所进行的推理 例 特
3、点: 当不存在与假设相矛盾的条件时,可以认为假设为真 当出现与假设相矛盾的条件时,应修正或撤消已获得的结论。 按所用知识的确定性分类 确定性推理 推理中所用的知识是精确的,获得的结论也是确定的 例 特点:基于经典逻辑的推理属于确定性推理本章的主要内容 不确定性推理 推理中所用的知识不都是精确的,获得的结论也不完全是确定的 例,特点:客观世界本身存在的不确定性显然比确定性更普遍,因此不确定推理的需求是普遍存在的,研究它的意义比研究确定性推理更大。下章的主要内容 按新旧判断的关系分类 单调推理 推理获得的新知识与已有的旧知识之间无矛盾,即不否定已有知识的正确性 例:从欧几里德公理出发,推出的几何学
4、的各种定理相互之间是无矛盾的 特点:随着推理的进行,能够获得越来越多的新知识,即获得的知识数量随推理的进程单调增加。 非单调推理 推理获得的新知识与已有的某些旧知识之间存在矛盾,即否定了已有知识的正确性 例: 特点:获得的知识数量不随推理的进程单调增加 按是否用启发性知识分类,启发式推理 在推理过程中使用启发性知识来改善推理的进程 例 特点:正确的启发性知识能使推理进程加快,错误的启发性知识使推理进程变慢 非启发式推理 在推理过程中仅使用已有的事实和知识进行推理 例 特点:推理过程不受环境(上下文)变化的影响 按推理所用的方法论分类 基于知识的推理 根据已有的事实和知识进行的推理 例 特点:逻
5、辑性强 统计推理 根据对某些事物的数据进行统计而获得新的知识或结论 例 特点:使用数学、统计学的方法与理论,直觉推理 根据常识进行的推理 例 特点:广泛存在,难于表示 按是否使用定量描述分类 定量推理 推理中直接或间接使用定量描述或定量分析方法 例 特点:定量分析 定性推理 推理中使用或部分使用定性知识,获得的结论是定性的或部分是定性的 例 特点:弥补了当前事实、知识和定性分析的不足 注: (1)确定性推理是研究推理的基础 (2)不确定性推理应用范围最广泛 (3)定性推理是推理研究的难点和目前的重点,推理中的策略控制策略 策略的概念 指导知识应用的方法和技术 分类:推理方向策略,搜索策略,冲突
6、消解策略,求解策略,限制策略 推理方向策略 概念 推理方向用于确定推理的驱动方式 环境要求:知识库,综合数据库,推理机 正向推理(数据驱动推理,前向链推理,模式制导推理,前件推理) 以事实为出发点,利用知识库中的知识进行推理。 算法:,逆向推理 以某个假设目标为出发点的推理。 算法:,混合推理 将正向推理与逆向推理结合起来进行的推理 先正向后逆向推理 根据正向推理的结果来帮助选择逆向推理的目标,以证实目标或提高目标的可信度 算法 先逆向后正向推理 先假设目标进行逆向推理,然后进行正向推理以获得更多的结论 算法,双向推理 将正向与逆向推理同时进行。推理结束的条件是:正向推理某个步骤的结论正好是逆
7、向推理的目标;或逆向推理某个步骤的目标正好是正向推理的结论。 算法: 正向推理与逆向推理的算法结合 示意:,搜索策略 用于确定推理的路线。CH5中讲。 冲突消解策略 稍后讲。 求解策略 用于确定求得的解满足什么样的要求。 要求: 可行解:求出一个满足条件的解即可。 局部最优解:它是可行解,并且在局部达到最优。 最优解:它是可行解,并且在所有可行解中最优。 策略的表示:一般为一组约束条件。 例: 对不确定推理,要求结论的可信度达到60%以上。 可行解:只要结论的可信度=60%即可 局部最优解:结论的可信度=60%,并且在不调整其它策略的前提下尽可能高 最优解:结论的可信度=60%,并且通过其它策
8、略的调整达到最高,限制策略 对求解或推理过程进行约束和限制 策略 限制时间:避免无穷推理 限制空间:避免综合数据库过大 策略的表示 约束条件 过程表示 例: 围棋程序,必须限制搜索的最大步数(限制时间、空间),模式匹配 问题: 如何确定哪些知识可以被使用 如何确定满足要求的结论 一般方法 定义匹配度量函数:d(x,y),当d(x,y)= 时,认为x,y匹配(成功) 例:相似度计算 确定性推理中的匹配 命题逻辑中的匹配 命题 p,q 匹配定义为: pq,即p,q互为逻辑结论。 例:命题逻辑中的等价公式 谓词的匹配 问题:谓词中含有变量,确定其匹配的关键是变量的处理。 定义1(代换)代换是形如 t
9、1/x1,t2/x2,tn/xn 的有限集合。其中:ti是项,xi是互不相同的变元。 ti/ xi表示用ti代,换xi ,不允许ti与xi相同,不允许xi循环地出现在另一个ti中。 例: a/x,f(b)/y,w/z 是代换 f(y)/x,f(x)/y 不是代换 g(a)/x,f(x)/y 是代换 定义2(复合代换)设代换 =ti/ xi i=1n =ui/ yi j=1m 则它们的复合也是代换,由从 t1 / x1, tn / xn,u1/ y1,.,um/ ym 中删除满足 ti/xi 当 ti=xi ui/ yi 当 yjx1,, xn 的元素后剩下的元素构成。 例:书p.120 定义3
10、(合一)公式集F=F1,,Fn,若存在代换使得 F1 = F2 = Fn 称是F的一个合一,称F1,,Fn是可合一的。,例:书p.121 定义4(最一般合一)设是公式集F的一个合一,如果对任一个合一都存在一个代换 ,使得 = 称是F的最一般合一。 最一般合一是唯一的 求最一般合一的算法 输入:含两个公式的公式集F 输出:最一般合一 (1) k=0,Fk =F,= ,k= ; 代换 (2) 若Fk只含一个公式,算法结束,输出 = k ; (3) 找出Fk的差异集Dk ; (4) 若Dk中存在元素xk,tk,其中xk是变元,tk是项,且xk不在tk中出现,则置 k+1 = k t k/x k F
11、k+1 =F kt k /x k k=k+1 然后转(2) ; (5) 算法终止,输出= 。,例:p.121 当公式集中含有两个以上的公式时,如何求它们的合一? 不确定性推理中的匹配 下章讲 冲突消解 基本问题 当用已知事实与知识库中的知识进行匹配时,可能出现三种情况: (1)没有知识可以匹配 (2)只有一条知识可以匹配 (3)有多条知识可以匹配 当出现第一种情况时,推理被中断。当出现第二种情况时,直接选择该条知识进行推理。当出现第三种情况时,称发生冲突。冲突消解策略即是在发生冲突时如何选择一条知识用于推理。,策略 按针对性排序 知识前件中条件的数目越多越先使用 按已知事实的新鲜性排序 越后放
12、入综合数据库的事实越先使用 按匹配度排序 匹配度越高越先使用 根据领域问题的特点排序 知识的专业性越强越先使用 按上下文限制排序 问题求解或推理中越先涉及的知识越先使用 按冗余限制排序 产生结论冗余度越小的知识越先使用 按条件个数排序 知识前件中条件数越少的越先使用 注:应用中这些策略不可能同时满足。一般满足其中的12种即可。,2、自然演绎推理,概念 从一组已知为真的事实出发,直接应用经典逻辑的推理规则推出结论的过程称为自然演绎推理。 推理规则 假言式规则 P,P Q Q 拒取式规则 P Q,Q P P规则 在推理的任何步骤都可引入前提 T规则 推理时,如果前面步骤中有一个或多个公式永真蕴含公
13、式S,则可把S引入推理过程中,CP规则 如果能从R和前提集合中推出S来,则可从前提集合中推出RS来 反证法 PQ,当且仅当PQF 例: 已知:A,B,A C,BC D,D Q 求证:Q 证明: A,A C C B,C B C B C,B C D D D,D Q Q Q为真,已知: 事实: P(a) S(a) 知识(规则):P(x) (Q(x) R(x) 求证:S(a) R(a) 证明: P(a) S(a) P(a), S(a) 对知识使用代换a/x后与P(a)匹配成功,得: Q(a) R(a) 又 Q(a) R(a) Q(a),R(a) S(a),R(a) S(a) R(a) S(a) R(a
14、) 为真,特点 优点: 表达证明过程自然,容易理解,推理规则丰富,推理过程灵活,便于使用启发式知识。 不足: 容易产生组合爆炸,对大的推理问题不利。,3、归结演绎推理,基本原理 若证明:P Q,只须证明:P Q不可满足 证明过程: 将P Q 转换成P Q的形式 将P Q转换成子句集S 归结S 若归结后的子句集中含有空子句, 即P Q不可满足,从而P Q得证 子句与子句集 定义: 原子谓词公式及其否定称文字 文字的析取式称子句 不含任何文字的公式称空子句,元素仅为子句的集合称子句集 结论 空子句是永假的 空子句是不可满足的 子句集 谓词公式P能够通过应用等价代换转换成等价的合取范式P 由P的所有
15、合取项构成的集合称为P的子句集 子句集算法 利用等价关系消去谓词公式中的蕴含和双条件 P Q P Q PQ (P Q)( P Q),利用等价关系将 移到紧靠谓词的位置 (P) P (P Q) P Q (P Q) P Q (x)P (x) P (x)P ( x) P 替换变元,使不同的量词约束的变元有不同的名字 消去存在量词 当存在量词不在全称量词的辖域内,用个体常量替换受该存在量词约束的变元,消去存在量词 当存在量词在全称量词的辖域内,用全称量词的函数替换受该存在量词约束的变元,消去存在量词 将所有的全称量词移到公式的前部 将公式转换成等价的合取范式 P (Q R) (P Q) ( P R)
16、消去全称量词 变元更名,使不同子句中的变元具有不同的名字 消去合取词,得到子句集,例:p.153,4.12(4) (x)(y)(z)(P(x,y) Q(x,y) R(x,z) (x)(y)(z)(P(x,y) Q(x,y) R(x,z) (x)(y)(z)(P(x,y) Q(x,y)R(x,z) (x)(y)(P(x,y) Q(x,y)R(x,f(x,y) 子句集 P(x,y)Q(x,y)R(x,f(x,y) 定理 设谓词公式F的子句集为S,F不可满足的充分必要条件是S不可满足的 海伯伦理论 思路 对子句集S的不可满足验证是无穷验证,它需要穷举S的所有解释 海伯伦给出了一个验证范围称为H域,并
17、指出S的不可满足验证只需要在H域上验证就可以了,H域 定义 设S为子句集,下述方法构造的H称为海伯伦域,记为H 令H0是S中所有个体常量的集合。若S中无个体常量,置H0 =a,a是任一个体常量。 Hi+1 = Hi S中所有f(x1, xn )| xj Hi H= H =lim Hi 例 设S=P(x) Q(x),R(f(y) H0=a H1= H0f(y)|y H0=a,f(a) H2= H1f(y)|y H1=a,f(a),f(f(a) H= H =a,f(a),f(f(a),f(f(f(a),,设S= P(x,y) Q(x,y)R(x,f(x,y) H0=a H1= H0f(x,y)|x
18、,yH0=a,f(a,a) H2= H1f(x,y)|x,yH1=a,f(a,a),f(a,f(a,a),f(f(a,a),a),f(f(a,a),f(a,a) 注:一般来说H域是无限的,特例是:当S中没有函数时,H仅含S中的个体常量,或仅含一个个体常量。 基子句与原子集 用H中的元素代换子句中的变元,所得的子句称基子句,其中的谓词称基原子。子句集中所有基原子构成的集合称原子集。 基子句的集合称为基子句集。 子句集S在H上的一个解释I满足下列条件 在解释I下,常量映射到自身 S中的任一个n元函数是Hn到H的映射 S中的任一个n元谓词是Hn到T,F的映射。谓词的真值可以指派为T,也可以指派为F,
19、结论:对给定域D上的任一个解释,总能在H中构造一个解释与它对应,如果D上的解释能满足S,则在H上相应的解释也能满足S 海伯伦定理 定理:子句集S不可满足的充分必要条件是S对H上的一切解释都为假 定理(海伯伦定理):子句集S不可满足的充分必要条件是存在一个有限的不可满足的基子句集S 问题: 海伯伦定理说明了S不可满足时一定存在一个有限的不可满足的基子句集S 该定理没有说明找出S的算法(存在性与构造性) 鲁宾逊给出了一个这样的算法,鲁宾逊归结 思路 检查S中是否有空子句。若有,则S不可满足 通过归结,一旦能推出S中有空子句,则S不可满足 命题逻辑中的归结 定义:设C1,C2是子句集中的任意两个子句
20、。如果C1的文字L1与C2的文字L2互补,那么从C1和C2中分别消去L1和L2,并将二个子句余下的部分析取形成新子句C12,这个过程称为归结,C12称为C1和C2的归结式,称C1和C2为C12的亲本子句。 例 设:C1=PQR,C2=QS 有 L1=Q,L=Q,则C12=PRS 定理:归结式是亲本子句的逻辑结论 证明:书p.131,结论 设在子句集S中用归结式代替亲本子句得到子句集S。如果S不可满足则S不可满足 设在子句集S中添加其子句的归结式得到子句集S”。则有:S”不可满足的充分必要条件是S不可满足 注:由上述结论,如果子句集S中有两个子句的归结式为空子句,那么S是不可满足的 例: 设 S
21、=P,R,P Q,Q R 归结: (1) P (2)R (3)P Q (4)Q R (5)Q (1)(3)归结 (6)R (4)(5)归结 (7)NIL (2)(6)归结 结论:S不可满足,归结过程的树形表示 子句 (1) P (2)R (3)P Q (4)Q R,谓词逻辑中的归结 定义:设C1与C2是两个没有相同变元的子句,L1和L2分别是C1和C2中的文字,若是L1和L2的最一般合一,称 C12=(C1-L1 )(C2 -L2 ) 为C1和C2的二元归结式,L1和L2称为归结式上的文字 例:设 C1=P(x)Q(a),C2=P(b)R(x) 由于C1和C2中有相同的变元,应先该变元的名字,
22、如C2修改为 C2=P(b)R(y) 取 L1=P(x),L2=P(b),则=b/x是L1和L2的最一般合一。 因此 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),定义:若子句C中有两个或两个以上的文字具有最一般合一,称C为子句C的因子,若C是单一文字,称C是C的单因子 定义:子句C1和C2的归结式是下列二元归结式之一: (1)C1与C2的二元归结式 (2)C1与C2的因子C22的二元归结式 (3)C1的因子C11与C2的二元归结式 (4)C1的因子C11与C2的因子C22的二元归结式 称
23、C1,C2是它们的归结式的亲本子句 定理:归结式是亲本子句的逻辑结论 结论 设在子句集S中用归结式代替亲本子句得到子句集S。如果S不可满足则S不可满足 设在子句集S中添加其子句的归结式得到子句集S”。则有:S”不可满足的充分必要条件是S不可满足,鲁宾逊归结原理即是:将子句集中子句的归结式添加到子句集中不该变子句集的不可满足性 结论:在一阶谓词逻辑范畴,鲁宾逊归结原理是完备的。即:子句集不可满足的充分必要条件是存在一个到含有空子句的子句集的鲁宾逊归结,归结反演方法 定理证明方法 若证明定理: P Q 证明方法: (1)求出公式 P的子句集S (2)求出公式Q的子句集S” (3)合并S与S”得公式
24、集S (4)对S进行归结 (5)若归结后的子句集含有空子句,原定理得证。 注:如果不能归结出含有空子句的子句集,并不能说明原定理不成立。 例1: 某公司招聘人员,A,B,C三人应聘,面试后公司决定: (1)至少录取一人 (2)如果录取A而不录取B,则一定录取C (3)如果录取B,则一定录取C 求证:一定录取C,证明:设P(x)表示录取x。那么公司的决定可表示为: P(A)P(B)P(C) (P(A) P(B) P(C) P(B) P(C) 需要求证的是:P(C) 由此需要证明: P(C) 按归结反演方法,分别求 与 P(C)的子句集如下: 由 得子句 (1)P(A)P(B)P(C) 由得 (P
25、(A) P(B) P(C) =(P(A) P(B) P(C) =(P(A) P(B) P(C) =P(A) P(B) P(C) 即子句 (2) P(A) P(B) P(C),由得 P(B) P(C) =P(B) P(C) 即子句 (3) P(B) P(C) 再由需证明的结论得子句 (4) P(C) 归结过程: (5) P(B) (3)(4)归结 (6) P(A) P(B) (2)(4)归结 (7) P(A) (5)(6)归结 (8) P(B) P(C) (1)(7)归结 (9) P(C) (5)(8)归结 (10)NIL (4)(9)归结 因此,由归结原理有 P(C) 又 , P(C) 故有:
26、P(C) 注:得到(9)时并不能结束证明。为什么?,例2: 已知 F1=(x)(P(x) (Q(x)R(x) F2=( x)(P(x)S(x) 求证:G=( x)(S(x)R(x)是F1和F2的逻辑结论 证明:按逻辑结论的定义即是证明:F1F2 G F1的子句: F1=(x)(P(x)(Q(x)R(x) =(x)(P(x)Q(x)(P(x)R(x) (1) P(x)Q(x) (2) P(x)R(x) F2的子句: (3) P(a) (4) S(a) 再由 G = ( x)(S(x)R(x) = ( x)(S(x)R(x) = ( x)(S(x)R(x) 得子句 (5)(S(x)R(x),归结过
27、程: (6) R(a) (2)作代换a/x后与(3)归结 (7) R(a) (5)作代换a/x后与(4)归结 (8) NIL (6)(7)归结 由归结反演方法,原命题得证,问题求解方法 步骤 (1)把问题的已知前提用谓词公式表示出来,并求出其子句集S (2)把待求的解用谓词公式表示出来,然后把它的否定与谓词ANSWER构成析取式,并求出其子句集S”。 (3)合并S与S”得子句集S (4)对S进行归结 (5)若能归结到ANSWER,则问题的答案就是ANSWER的变元的值 注:ANSWER是为求解问题特别设置的谓词,它的变元与待求解的谓词公式的变元相同。 例: (p.154,4.17)张某被盗,公
28、安局派5个侦察员去调查。研究案情时,侦察员A说“赵与钱中至少有一人作案”, B说“钱与孙中至少有一人作案”, C说“孙与李中至少有一人作案”, D说“赵与孙中至少有一人与本案无关”,E说“钱与李中至少有一人与本案无关”。如果这5位侦察员的话都是可信的,请问谁是盗窃犯?,解:设P(x)表示x是盗窃犯(作案),案情可描述为: (1) P(赵)P(钱) (2) P(钱)P(孙) (3) P(孙)P(李) (4) P(赵) P(孙) (5) P(钱) P(李) 问题可描述为:P(x) 按求解步骤,上述(1)(5)构成问题前提的子句集 问题的否定与ANSWER的析取构成的子句集为: (6) P(x)AN
29、SWER(x) 对(1)(6)进行归结的树形表示为:,归结策略 问题 归结中选择哪些子句进行归结可以获得结果 按照什么样的归结顺序可以较快的获得结果 策略 广度优先策略 每个子句都与当前子句集中的所有可归结的子句归结 删除策略 纯文字删除 如果某文字L在子句集中不存在可与其互补或合一的文字L,该文字称为纯文字 对纯文字不可能进行归结,它的删除不影响子句集的不可满足性 重言式删除 如果一个子句中同时包含互补文字对,该子句称为重言式 重言式是永真的,它的删除不影响子句集的不可满足性,包孕删除 设子句C1和C2,如果存在代换,使得C1 C2,称C1包孕于C2 删除包孕子句,不影响子句集的不可满足性
30、支持集策略 每次归结时,亲本子句中至少有一个是由目标公式的否定所得到的子句或者它们的后裔 线性输入策略 每次参加归结的两个子句中至少有一个是初始子句集(第一次归结前的子句集)中的子句 单文字子句策略 每次参加归结的两个子句中至少有一个是单文字子句 祖先过滤策略 每次参加归结的两个子句须满足下列条件之一 至少有一个是初始子句集中的子句 一个子句是另一个子句的后裔,其它问题 完备性 任意一个不可满足的子句集,如果通过使用某个推理规则可以确定其不可满足,称该推理规则是否证完备的 任意一个不可满足的子句集,如果通过使用某种策略和否证完备推理规则可以保证发现一个否证(确定其不可满足),称该策略是完备的
31、可以证明 归结原理是否证完备的 广度优先策略是完备的 支集策略是完备的 祖先过滤策略是完备的 线性输入策略、单文字策略是不完备的,不足 子句不如逻辑公式直观,不便于理解 例: (x)(Bird(x) Canfly(x) 与 Bird(x) Canfly(x) 子句可能丢失控制信息 例 (AB) C (AC) B (BC) A A (BC) B (AC) C (AB) 有相同的子句: ABC,4、与/或形演绎推理,与/或形 定义:公式F中不含有蕴涵符号“” ,称F为与/或形公式 公式F转换为与/或形的算法 (1)利用P Q P Q 消去公式F中的“” (2)将移动到紧靠谓词的位置上 (3)重新命
32、名变元,使不同量词约束的变元有不同的名字 (4)引入Skolem函数,消去存在量词 (5)移去全称量词,且使各主要合取式中的变元具有不同的名字,与/或形正向演绎推理 事实的表示 公式表示:将事实转换成与/或形公式 与/或形公式F的与/或树表示方法: 根节点为公式F 中间节点为F的一个子表达式 叶节点为F中的文字 子表达式E1 E2. En的后继节点用一个n连接符(半圆弧)连接 子表达式E1 E2 . En的后继节点不需要连接,例 事实的与/或形公式 F=Q(z,a)R(y)P(y) S(a,y) 公式F的与/或树表示,F规则的表示 F规则的形式 L W 其中:L为文字,W为与/或形公式 知识转
33、换为F规则的算法 利用公式 P Q P Q,暂时消去蕴涵符号“” 将移动到紧靠谓词的位置 引入Skolem函数,消去存在量词 移去全称量词 利用公式 P Q P Q ,恢复为蕴涵式 目标公式的表示 目标公式的形式:子句 目标公式转换为子句的算法:见第3节 推理过程 推理的目的 证明目标公式,推理过程 用与/或树将已知事实表示出来 用F规则的左部和与/或树的叶节点进行匹配,将匹配成功的规则的右部作为叶节点的儿子加入到与/或树中 重复上步,直达产生一个含有目标公式中所有子句的与/或树,目标公式获证;或者目标公式不能证明 例 已知事实: P(a) Q(a)R(a) F规则 R1: P(x) S(x)
34、 R2:Q(y) N(y) 目标公式: S(z)N(z),与/或形逆向演绎推理 目标公式的表示 目标公式用与/或形表示 与/或形 注:前面关于求与/或形的算法的第4、5步修改为: (4)用存在量词约束的变元的Skolem函数替换由全称量词约束的相应变元,消去全称量词 (5)移去存在量词,且使各主要合取式中的变元具有不同的名字 例 目标公式:(y)(x)P(x) Q(x,y) (R(x) S(y) 与/或形: P(f(y)Q(f(y),y)(R(f(y)S(y) 问题 目标公式: (x) (y)P(x) Q(x,y) (R(x) S(y) 与/或形: 与/或形的树表示 用n连接符把具有合取关系的
35、子表达式连接起来 例:书p147,图4-17,B规则的表示 形式:W L 其中:W为与/或形公式,L为文字 当规则不满足上述要求时,可采用与F规则类似的算法将规则的右部转换为要求的形式。 例 W (L1L2) 可转换为两条规则: W L1 和 W L2 事实的表示 事实要求表示为合取范式的形式: F1 F1 F1,推理过程 基本思路 从目标公式的与/或形出发,通过运用B规则,最终得到某个终止在事实节点上一致的图解 推理过程 (1)用与/或树将目标公式表示出来 (2)用B规则的右部和与/或树的叶节点进行匹配,并将匹配成功的B规则加到与/或树中 (3)重复(2),直到产生某个终止在事实节点上的一致
36、图解 一致图解:指推理过程中所用到的代换是一致的 例 事实 f1:DOG(Fido) Fido是只狗 f2:BARKS(Fido) Fido不吠叫 f3:WAGS-TAIL( Fido) Fido摇尾巴 f4:MEOWS(Myrtle) Myrtle咪咪叫,规则 r1:(WAGS-TAIL(x1)DOG(x1) FRIENDLY(x1) 狗摇尾巴表示友好 r2:(FRIENDLY(x2)BARKS(x2) AFRAID(x2,y2) y2不怕友好且不叫的狗x2 r3:DOG(x3) ANIMAL(x3) 狗是动物 r4:CAT(x4) ANIMAL(x4) 猫是动物 r5:MEOWS(x5)
37、CAT(x5) 咪咪叫的是猫 目标: 描述:是否有一只猫和一条狗,且这只猫不怕这条狗 公式表示:(x)(y)CAT(x)DOG(y)AFRAID(x,y),与/或树推理过程,与/或形双向演绎推理 要求 由正向的与/或形推理和逆向的与/或形推理组成,其要求分别与正向与/或形推理和逆向与/或形推理一致 难点在于终止条件的选择 例:书p.149 推理策略 代换一致性 定义(代换一致性)设代换集合=1,2,n的第i个代换为:i=ti1/xi1, ti2/xi2 , tim(i)/xim(i) 。代换集合是一致的充分必要条件是如下两个元组 T=t11,t12,t1m(1),t21,t2m(2),tnm(n) X=x11,x12,x1m(1),x21,x2m(2),xnm(n) 可合一 例:x/y,y/z是一致的,a/x,x/b是不一致的,剪支策略 思路 每当选用一条规则时,就进行一次一致性检查,如果当前的部分图解是一致的,则继续进行推理,否则就放弃该规则而选用其它候选规则。这样一来就能保证最后得到的图解是一致的。 方法 每次使用规则时所用的代换与原有的代换构成的代换集合必须是一致的。 例:书p.151 评价 优点 保持了连接词的直观性,比较自然 不足 增加了对规则表示的限制,同时正向推理限制目标表达式为文字的析取式,逆向推理限制事实表达式为文字的合取式,
链接地址:https://www.31doc.com/p-1996025.html