您现在的位置是: www.7168.com > www.3168.cc >

3根基推理方式(基于法则的演绎体系)

发布日期: 2019-08-03 浏览次数:

  典范推理----基于法则的演绎系统 3、根基推理方式 所讲的归结反演系统把所有的表达式都转换为子句形式,如许做虽然正在逻 辑上是等价的,但也了良多有用的消息。我们先看看子句布局存正在的缺陷: (1)子句表达的缺陷 取人们表达学问的习惯不分歧,因而未便阅读和理解。例如:可把语句“鸟能 飞”表告竣以下两种形式: ①?x(BIRD(x)?CANFLY(x)) ②?BIRD(x)?CANFLY(x) 明显,公式①表达间接、天然。因为公式②通过“对所有x,它或者不是鸟,或 者能飞”来间接反映“鸟能飞”这个概念,因而给阅读和理解带来了坚苦。 典范推理----基于法则的演绎系统 3、根基推理方式 (2)把逻辑蕴涵转换成子句形式可能丢失一些有用的节制消息。能够如许说: 数理逻辑只考虑语句的逻辑等价性,而AI问题求解需要“消息”守恒。尔后者 取求解问题的效率亲近相关。 将统一天然言语表告竣 分歧形式的逻辑公式,这正在逻辑上是等价的(即所含 逻辑学问不异),但节制消息可能是分歧的。 例如: ①?x?y{(G(x,0)?G(y,0) ?G(times(x,y),0)} 逻辑寄义:若是x和y都大于0,则二者之积大于0; 节制消息:利用现实x0和y0来证明二者之积大于0。 典范推理----基于法则的演绎系统 ②从逻辑上讲,以下蕴涵公式都等价于子句(A?B?C): (?A??B) ?C (?A??C) ?B (?B??C) ?A ?A ?(B?C) ?B ?(A?C) ?C ?(A?B) 但这些公式中现含的节制消息是分歧的,并且都无法正在(A?B?C)中表现出来。 针对子句表达的上述问题,人们提出了多种非子句归结证明方式。下面介 绍此中的一种,即Nilsson提出的基于法则的演绎推理(把这种基于法则的系统 简称为法则系统)。 3、根基推理方式 典范推理----基于法则的演绎系统 1.法则系统的根基布局 正在上述的子句归结系统中,子句形式的前提系统取求证的否认一 道形成发生式问题模子的全局数据库,而它的发生式法则只要一条,即归结规 则。问题求解的策略全现含正在推理(节制)机构中。 取子句归结系统分歧,法则系统将前提公式调集划分成以下两大部门: (1)法则,即逻辑蕴涵。这些法则形成系统的发生式法则库。 (2)现实,即非蕴涵公式。 法则系统的问题求解策略有两种表达式: (1)现含正在推理机构中。 (2)由用户正在法则中显式表达式或过程性节制学问。 3、根基推理方式 典范推理----基于法则的演绎系统 3、根基推理方式 按分歧的推理标的目的,又把法则系统分为以下三种形式: (1)前向演绎系统:这种系统的全局数据库为现实调集(FB),其发生式规 则为一组前向演绎法则( F法则),问题求解形式为 FB| F 法则-方针公 式() (2)后向演绎系统:这种系统的全局数据库为方针公式调集(GB),其产 生式法则为一组后向推理法则(B法则)。问题求解形式为:GB|B法则 -原问题PP?FB (3)双向演绎系统:即(1)(2)相连系的系统。 典范推理----基于法则的演绎系统 1. 前向演绎系统 前向演绎系统的布局如下: (1)AND/OR现实调集 任何前提公式都能够通过以下步调被转换成AND/OR形式: ① 消去蕴涵符 ② 缩小否认的感化范畴(到原子公式) ③ 沉定名变量,使量词间不含同名变量。 ④ 引入Skolem函数消去存正在量词。 ⑤ 去掉所有全称量词。 明显,AND/OR公式比子句更接近原公式形式,由于它不需转换成合取范式。 前向演绎系统中的现实都是AND/OR公式,这种公式可用AND/OR图/树来表达,例如 ,能够把AND/OR命题公式A?{(B??C)?D??E}?F 暗示成左图的AND/OR图/树 3、根基推理方式 典范推理----基于法则的演绎系统 A?{(B??C)?D??E}?F 3、根基推理方式 A (B??C)?D??E F B??C D ?E B ?C 典范推理----基于法则的演绎系统 前向演绎系统把AND/OR现实A1?A2?…?Am的每个子公式Ai(i=1,2,…,m)暗示成 OR结点(即1联合符),是由于它做为证明T的前提前提,只需由任一Ai可 推出T,即Ai-T,则T得证。 雷同地,把现实A1?A2?…?Am每个子公式暗示成AND结点(即n联合符),是由于 目前并不晓得哪些Ai,因而要由它证明T,必必要证明每个Ai都可推出 T. 逻辑公式的AND/OR图表达取子句表达有简单的对应关系:每个子句对应一解答 图的叶结点。例如,上图有4个解答图,其叶结点别离对应下面的4个子句: ① A ② B?D??E ③ ?C?D??E ④F 取或图暗示的一个主要性质,就是表达式本身所转换出的一组子句,能够从取 或图中读出,每个子句相当于取或图的一个解图。 3、根基推理方式 典范推理----基于法则的演绎系统 A?{(B??C)?D??E}?F 3、根基推理方式 A?{(B??C)?D??E}?F A B??C A?{(B??C)?D??E}?F (B??C)?D??E D ?E B A?{(B??C)?D??E}?F (B??C)?D??E B??C D ?C ?E F 典范推理----基于法则的演绎系统 3、根基推理方式 解答图的定义: 1)若是初始结点n也是一个终端结点。则G’只含结点n; 2)不然,若是存正在一个从n出发的k联合符,满脚每个子结点ni(i=1,…,k)都 有一个从它到终端结点的解答图Gi,则G’由结点ni,联合符k和所有Gi构成。 3)不然,不存正在从n出发的解答图。 典范推理----基于法则的演绎系统 3、根基推理方式 (2)F法则调集 常把前向演绎系统中的F法则(逻辑蕴涵)为以下形式: L?W此中,L是一个单文字,W是一个AND/OR公式。 法则左部为单个文字是由于:F法则感化于表达前提现实的AND/OR图,即 对AND/OR图(前提现实)进行扩展生成新的AND/OR图,但因为AND/OR图的叶结 点,都是单个文字现实,因而,若将法则左部为单个文字,则F法则就可 取AND/OR图正在端结点进行简单婚配(合一) 典范推理----基于法则的演绎系统 取AND/OR现实一样,F法则中的变量都是现含全称量词的。可通过以下步 骤将肆意逻辑蕴涵公式转换成的F法则形式: ①消去蕴涵符号(临时地) ②缩小否认符号的感化范畴(到原子公式) ③沉定名变量,使量词间不含同名变量。 ④引入Skolem函数,消去存正在量词。 ⑤去掉所有全称量词。 ⑥恢复成蕴涵形式。 3、根基推理方式 例如(?x)((?y?z P(x,y,z))?(?u)Q(x,u)) (?x)((? y ? z ?P(x,y,z))?(?u)Q(x,u)) (?x)((? y ?P(x,y,f(x,y)))?(?u)Q(x,u)) (?x) ? y ?u (?P(x,y,f(x,y))?Q(x,u)) ?P(x,y,f(x,y))?Q(x,u) P(x,y,f(x,y)) ? Q(x,u) 典范推理----基于法则的演绎系统 法则能够感化于取或图,构成一个新的取或图。 我们先申明没有变量的环境。例若有法则 S?(X?Y)?Z 取或图如下图所示。这条法则能够使用于该图的S叶结点上构成另一张图。图中 两个标有S的结点之间的弧称为婚配弧。留意到,重生成的取或图既暗示了原图 暗示的现实表达式,又暗示了由法则导出的所有新的现实表达式。 P Q T U X Y 3、根基推理方式 X?Y P?Q R S T?U S P (P?Q)?R S?(T?U) P?Q R S Q Z T U T?U [(P?Q)?R]V[S?(T?U)] (P?Q)?R S?(T?U) [(P?Q)?R]V[S?(T?U)] 典范推理----基于法则的演绎系统 起首调查上述法则可以或许推导出哪些子句。法则的子句形式为 ?S?X?Z ?S?Y?Z 由上图能够看出,现实表达式中可以或许取法则子句进行归结求解的子句为 S?R S?P?Q 使用归结道理,可得下列子句: R?X?Z R?Y?Z P?Q?X?Z P?Q?Y?Z 所有这4个子句全正在图中暗示出来了。使用一条法则获得了几个归结式,效率比 较高。 图中的结点S使用一条法则后不再是叶结点,但仍是文字结点,还可对该结点应 用其他法则。我们一个取或图暗示的子句集对应于竣事于文字结点上的解图 集。如许,使用法则后获得的取或图暗示了原取或图所暗示的表达式,也暗示了 新发生的表达式。 3、根基推理方式 典范推理----基于法则的演绎系统 3、根基推理方式 (3)操纵方针公式做竣事前提 正在正向演绎系统中,方针公式为文字的析取形式,当一个方针文字和取或图 中的一个文字婚配时,能够将暗示该方针文字的结点通过婚配弧毗连到取或图中 响应文字的结点上。暗示方针文字的结点称为方针结点。当演绎系统发生的取或 图包罗一个正在方针结点上竣事的解答图时,系统便成功竣事。 典范推理----基于法则的演绎系统 例如考虑下列问题: 现实表达式:A?B 法则:A?C?D和B?E?G 方针公式:C?G?F 使用法则后获得的取或图如下图所示,图中包罗一个正在方针结点上竣事的 解图,该解图对应的子句为C?G。 C C A A A?B D E B B G G 3、根基推理方式 典范推理----基于法则的演绎系统 含有变量的环境 正在正向演绎系统中,我们假设现实和法则中的所有的存正在量词量化的变量,均已 用Skolem函数替代,表达式中尚存的变量都是全称量词量化的变量。对于方针公 式,我们要求所有全称量词量化的变量都被Skolem函数代替,省略存正在量词,表 达式中尚存的变量都认为是存正在量词量化的变量。法则、方针公式取AND/OR图的 叶节点进行合一而不是间接婚配。 (?x)((?y)P(x,y)), 存正在量词x若被Skolem化,则为常量;全称量词y若被 Skolem化,则为f(x), ( ?y )(( ?x )P(x,y)),存正在量词x若被Skolem化,则为f(y),全称量词y若被 Skolem化,则为常量。 方针表达式的形式仍为文字的析取形式。因为存正在量词的性质: (?x)[X1(x)? X2(x) ]? (?x)X1(x) ?(?y) X2(y) 因而,方针公式中各析取文字的变量能够更名,从而利用分歧的变量符号。 3、根基推理方式 典范推理----基于法则的演绎系统 例如考虑如下问题: 现实表达式:P(A,B) ?[Q(x,A)?R(B,y)] 法则:P(x,y)?S(x) ?X(y) 方针公式:Q(C,A) ?R(z,B)?S(A)?X(B) 现实表达式和法则中的变量都是全称量词量化的,方针公式中的变量则是存正在 量词量化的,它们都满脚提出的要求。现实表达式的取或图如左图所示。 使用法则后的取或图如左图所示。图中还画出了取方针文字(用蓝色暗示)的 婚配。从概况上看,图中包罗两个正在方针文字上竣事的解图,对应的子句为 S(A) ?X(B) ?Q(C,A) S(A) ?X(B) ?R(z,B) 但现实上第一个子句是不成立的,由于该解图中利用的置换{A/x,B/y}和{ C/x}是不分歧的。可是,第二个子句对应的解图中,利用的置换{A/x,B/y }和{B/z,B/y}是分歧的,将两个置换的合成{A/x,B/y,B/z}感化于第二 个子句获得的例S(A) ?X(B) ?R(B,B)才是最初获得的子句。 3、根基推理方式 典范推理----基于法则的演绎系统 3、根基推理方式 Q(x,A) R(B,y) S(A) X(B) Q(C,A) R(z,B) (B/z,B/y) P(A,B) Q(x,A)?R(B,y) S(A) X(B) Q(x,A) (C/x) R(B,y) P(x,y) P(A,B) ?[Q(x,A)?R(B,y)] P(A,B) (A/x,B/y) Q(x,A)?R(B,y) P(A,B) ?[Q(x,A)?R(B,y)] 典范推理----基于法则的演绎系统 总之,我们只能考虑那些竣事正在方针结点上的具有分歧的婚配弧置换的解 图―――分歧解图,并以对该解图对应的子句使用置换的合成所获得的例 做为解答语句。下面给出置换的分歧性的定义。 定义 设有一个置换集 3、根基推理方式 ,每个Ui是一个置换对的调集。 U ? {u1 , u 2 ?u n } u i ? {t i1/vi1 , t i2 /vi2 ,...tim(i)/vim(i)} 令 U1 ? (v11 ,...,v1m(1) ,...,v n1 ,...,v nm(n) ) U 2 ? (t11 ,...,t 1m(1) ,...,t n1 ,...,t nm(n) ) 置换U称为分歧的,当且仅当U1和U2是可合一的,而U的合成u=mgu(U1,U2). 典范推理----基于法则的演绎系统 例若有置换u1={x/y,x/z}和u2=(A/z) 令 U1=(y,z,z) U2=(x,x,A) 能够求得U1和U2的最简合一者为 u=mgu(U1,U2)={A/x,A/y,A/z} 因而置换u1和u2是分歧的,且合成为u. 为了避免不需要的不分歧,使用中应留意以下几点: ①多次使用统一法则时,每次应把变量更名。 ②多次使用统一方针文字时,每次应把变量更名。 ③当存正在一个竣事于方针文字上的分歧解图时,证明成功地竣事。 3、根基推理方式 例子: FIDO叫且咬人,或者FIDO不是狗 所有猎犬都是狗,叫的都是喧闹的 证明:存正在某物或者不是猎犬或者是喧闹的 DOG(x),BITES(x),BARKS(x),NOISY(x),TERRIER(x) FIDO叫且咬人,或者FIDO不是狗 所有猎犬都是狗,叫的都是喧闹的 证明:存正在某物或者不是猎犬或者是喧闹的 现实:?DOG(Fido)?(BARKS(Fido)?BITES(Fido)) 法则:?x TERRIER(x)?DOG(x) ?y BARKS(y) ?NOISY(y) 方针:?z(?TERRIER(z)?NOISY(z)) 现实:?DOG(Fido)?(BARKS(Fido)?BITES(Fido)) 法则:TERRIER(x)?DOG(x) BARKS(y) ?NOISY(y) 方针:?TERRIER(z)?NOISY(z) 法则:TERRIER(x)?DOG(x) BARKS(y) ?NOISY(y) 方针:?TERRIER(z)?NOISY(z) NOISY(z) ?TERRIER(z) Fido/z NOISY(Fido) BARKS(y) Fido/y BARKS(Fido) Fido/x ?DOG(Fido) (BARKS(Fido)?BITES(Fido)) BITES(Fido) Fido/z ?TERRIER(Fido) ?DOG(x) ?DOG(Fido)?(BARKS(Fido)?BITES(Fido)) TERRIER(x)?DOG(x) 逆否律:?DOG(x)? ?TERRIER(x) 典范推理----基于法则的演绎系统 逆向演绎系统 逆向演绎系统是正向演绎系统的对偶形式。我们称正向系统中的法则为F法则, 称逆向系统中的法则为B法则,逆向系统从方针表达式出发,逆向使用法则,曲 到现实表达式。 (1)方针表达式 正在逆向演绎系统中,方针表达式可为无蕴涵的肆意取或形式。可用雷同于正向系 统中现实表达式的过程,将肆意形式的方针表达式转换为尺度的取或形式。 分歧的是,应Skolem化全称量词量化的变量,略去存正在量词,则方针表达式中尚 存的变量都认为是存正在量词量化的变量。从头定名变量,使次要析取式中含分歧 的变量名 ①消去蕴涵符 ② 缩小否认的感化范畴(到原子公式) ③ 沉定名变量,使量词间不含同名变量。 ④ 引入Skolem函数消去全称量词。 ⑤ 去掉所有存正在量词。 3、根基推理方式 典范推理----基于法则的演绎系统 3、根基推理方式 例若有方针表达式 (?y)(?x){P(x)?[Q(x,y)??[R(x) ?S(y)]]} 可为 ?P(f(y))?{Q(f(y),y) ?[?R(f(y)) ?? S(y)]} 从头定名变量后得 ?P(f(z))?{Q(f(y),y) ?[?R(f(y)) ?? S(y)]} 典范推理----基于法则的演绎系统 3、根基推理方式 取或形式的方针公式能够用取或图暗示。 把方针公式A1?A2?…?Am的每个子公式Ai(i=1,2,…,m)暗示成AND结点(即m联 结符),是由于要证明A1?A2?…?Am成立,必需证明每一个Ai都。 雷同地,把方针公式A1?A2?…?Am每个子公式暗示成OR结点(即1联合符),是 由于只需证明Ai即可。 对上一个公式的取或图为 典范推理----基于法则的演绎系统 ?P(f(z))?{Q(f(y),y) ?[?R(f(y)) ?? S(y)]} 3、根基推理方式 ?P(f(z)) Q(f(y),y) ?[?R(f(y)) ?? S(y)] Q(f(y),y) ?R(f(y)) ?? S(y) ?R(f(y)) ? S(y) 典范推理----基于法则的演绎系统 3、根基推理方式 图中m联合符用来毗连暗示合取关系的子表达式,1联合符用来毗连暗示析取关系的 子表达式。根结点暗示方针表达式,称为方针结点,其儿女称为子方针结点。叶结 点暗示单个文字。从图中竣事正在叶结点的解图中能够读出子句为 ?P(f(z)) Q(f(y),y) ??R(f(y)) Q(f(y),y) ?? S(y) 方针子句是文字的合取,此中的变量是存正在量词量化的。 典范推理----基于法则的演绎系统 3、根基推理方式 (2)法则使用 逆向演绎系统中的法则称为B法则,形式为 W?L 此中W为肆意的取或形式,L为单一文字。这个简化了B法则对取或 图的使用。某些不合适这一要求的法则能够变换成这种形式,例如 W?L1? L2形式的法则能够暗示成两个法则W?L1, W?L2 法则中应Skolem化存正在量词量化的变量,并略去全称量词,认为法则中 尚存的变量都是全称量词量化的变量。 典范推理----基于法则的演绎系统 3、根基推理方式 正在方针公式的取或图中,若是有一个文字L’可以或许取L合一, 则可使用B法则W?L.使用的成果是将L’结点通过一个标有L 取L’的最简合一者u的婚配弧取结点L相连,结点L做为W的 取或图的根结点。如许,新的取或图的解图所对应的子句就 添加了一个归结式的调集,即法则W?L否认式W??L获得的 子句取方针公式的子句对文字L进行归结获得的那些归结式。 一条法则能够使用多次,每次都利用分歧的变量。 典范推理----基于法则的演绎系统 3、根基推理方式 (3)竣事前提 逆向演绎系统的现实表达式为文字的合取,可暗示为文字的调集。对任一事 实表达式,该当用Skolem函数取代现实表达式中存正在量词量化的变量,将表达式 为尺度的文字的合取形式。当一个现实文字和取或图中的一个文字能够合一 时,可将该现实文字通过婚配弧毗连到取或图中响应的文字上,婚配弧应标明两 个文字的最简合一者。统一现实文字能够婚配多次,每次利用分歧的变量。 逆向系统的竣事前提就是取或图中包罗一个竣事正在现实结点上的分歧解图,该解 图的置换的合成感化于方针表达式就是解答语句。 设有以下现实: FIDO是一条狗,FIDO不叫,FIDO摇尾巴,MYRTLE喵喵叫 法则: 摇尾巴的狗是敌对的,敌对且不叫得是不令对方害怕的;狗是动物,猫是动 物,喵喵叫的是猫 证明: 能否存正在一只猫和一只狗,使这只猫不怕这只狗 DOG(x) BARKS(x),WAGS-TAIL(x),MEOWS(x) FRIENDLY(x),AFRAID(x,y),CAT(x),ANIMAL(x) 现实:DOG(Fido), ?BARKS(Fido), WAGS-TAIL(Fido), MEOWS(MYRTLE) 法则:?x1((WAGS-TAIL(x1) ? DOG(x1))?FRIENDLY(x1)) ?x2 ?y2((FRIENDLY(x2)) ? ?BARKS(x2))? ?AFRAID (y2,x2)) ?x3(DOG(x3) ?ANIMAL(x3)) ?x4(CAT(x4) ?ANIMAL(x4)) ?x5(MEOWS(x5) ?CAT(x5)) 方针:?x?y(CAT(x)?DOG(y) ??AFRAID(x,y)) CAT(x)?DOG(y) ??AFRAID(x,y) CAT(x) DOG(y) Fido/y DOG(Fido) ?AFRAID(x,y) x/y2,y/x2 ?AFRAID(y2, x2) x/x5 CAT(x5) MEOWS(x) MYRTLE/x MEOWS(MYRTLE) ?BARKS(y) Fido/y ?BARKS(Fido) FRIENDLY(y) y/x1 FRIENDLY(x1) WAGS-TAIL(y) Fido/y WAGS-TAIL(Fido) x/x5 MYRTLE/x Fido/y x/y2,y/x2 Fido/y y/x1 DOG(y) Fido/y DOG(Fido) Fido/y Fido/y x/x5 MYRTLE/x Fido/y x/y2,y/x2 Fido/y y/x1 Fido/y Fido/y U1=(x,MYRTLE,Fido,x,y,Fido,y,Fido,Fido) U2=(x5,x,y,y2,x2,y,x1,y,y) x/x5, U1=(x,MYRTLE,Fido,x,y,Fido,y,Fido,Fido) U2=(x,x,y,y2,x2,y,x1,y,y) MYRTLE/x U1=(MYRTLE,MYRTLE,Fido,MYRTLE,y,Fido,y,Fido,Fido) U2=(MYRTLE,MYRTLE,y,y2,x2,y,x1,y,y) MYRTLE/x5, MYRTLE/x Fido/y U1=(MYRTLE,MYRTLE,Fido,MYRTLE,Fido,Fido,Fido,Fido,Fido) U2=(MYRTLE,MYRTLE,Fido,y2,x2,Fido,x1,Fido,Fido) MYRTLE/x5, MYRTLE/x,Fido/y MYRTLE/y2 U1=(MYRTLE,MYRTLE,Fido,MYRTLE,Fido,Fido,Fido,Fido,Fido) U2=(MYRTLE,MYRTLE,Fido,MYRTLE,x2,Fido,x1,Fido,Fido) MYRTLE/x5, MYRTLE/x,Fido/y, MYRTLE/y2 Fido/x2 U1=(MYRTLE,MYRTLE,Fido,MYRTLE,Fido,Fido,Fido,Fido,Fido) U2=(MYRTLE,MYRTLE,Fido,MYRTLE,Fido,Fido,x1,Fido,Fido MYRTLE/x5, MYRTLE/x,Fido/y, MYRTLE/y2 ,Fido/x2 Fido/x1 U1=(MYRTLE,MYRTLE,Fido,MYRTLE,Fido,Fido,Fido,Fido,Fido) U2=(MYRTLE,MYRTLE,Fido,MYRTLE,Fido,Fido,Fido,Fido,Fido MYRTLE/x5, MYRTLE/x,Fido/y, MYRTLE/y2 ,Fido/x2,Fido/x1 现实表达式: P(A,B) ?[?x?y[ Q(C,x)? R (B,y)]]?[ ?z T(z) ] 法则:??x ?y [P(x,y)?S(x) ?X(y)] ??z [ T(z) ? X(z)] 方针公式:??z[Q(C,A) ?R(z,B)?S(A) ?X(B)]

  3根基推理方式(基于法则的演绎系统)_数学_天然科学_专业材料。典范推理----基于法则的演绎系统 3、根基推理方式 所讲的归结反演系统把所有的表达式都转换为子句形式,如许做虽然正在逻 辑上是等价的,但也了良多有用的消息。我们先看看子句布局存正在的缺陷: