您好、欢迎来到现金彩票网!
当前位置:如意彩票 > 非单调推理 >

第4篇 知识推理pdf

发布时间:2019-06-06 10:36 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  2011-12-26 第4章 知识推理 4.1 推理的基本概念 4.2 归结演绎推理 4.3 非归结演绎推理 4.4 不确定性推理方法 4.1 推理的基本概念 推理是以一个或几个命题为根据或理由,从而得出另一 个命题的思维过程。推理的根据或理由称为前提,得出的命 题称为结论。推理是由称做前提和结论的两部分命题组成的。 在智能系统中,推理是由程序实现的,称为推理机。 问题求解中的推理就是知识的使用过程,由于知识表示 有多种方法,相应地也就有多种推理方法,下面分别从不同 角度来探讨这些推理方法。 1. 经典推理和非经典推理 2. 演绎推理、归纳推理和缺省推理(默认推理) 3. 单调推理和非单调推理 4. 确定性推理和不确定性推理 1 2011-12-26 经典推理:通常采用演绎推理,是单调的;一般基于二值逻辑。 非经典推理: 演绎推理:从一般到特殊。又可分为:归结演绎推理、自然演绎 推理、基于规则的演绎推理。 归纳推理:从特殊到一般。 缺省推理(默认推理):在知识不完全的情况下按默认的假设进 行推理;或者没有证据证明“假”的时候就认为 “真”。 单调推理:系统中的知识随着推理的进行而总是非减的。如:基 于谓词逻辑的推理。 非单调推理:随着推理得到新知识,原有的知识可能被推翻。如: 默认推理。 确定性推理:给予确定性的知识(事实、规则)进行推理。 不确定性推理: 4.2 归结演绎推理 4.2.1 Herbrand理论 4.2.2 归结原理 4.2.3 归结反演 2 2011-12-26 定理证明的实质是证明F1 ∧F2 ∧…∧Fn→W 的永真性。 其证明方法可分为二类:一是直接证明F1 ∧F2 ∧…∧Fn→W 为永真,即演绎法;二是间接证明(F1 ∧F2 ∧…∧Fn→W)为 永假,即反证法。 20世纪60年代,人们把研究的注意力集中在证明永假 性,即证明 F1 ∧F2 ∧…∧Fn ∧W 的永假性,这实际上就是 要证明{F1,F2 ,…,Fn } ∪{W}是一个矛盾集。因此证明 F1 ∧F2 ∧…∧Fn ∧W永假,只需证明F1 ∧F2 ∧…∧Fn和W 是不可满足的就可以。海伯伦(J. Herbrand )和Robinson在 这个方向上先后作了卓越的研究工作。首先,由Herbrand提 出的Herbrand域和Herbrand定理,为自动定理证明奠定了理 论基础;然后,由Robinson提出的归结原理使自动定理证明 成为可能。 4.2.1 Herbrand理论 证明一个谓词公式的不可满足性是困难的,这是由于个 体变量论域的任意性,以及解释的个数的无限性。 但是,如果一个具体的谓词公式能够找到一个比较简单 的特殊的论域,使得只要在这个论域上该公式是不可满足的, 便能保证该公式在任一论域上也是不可满足的,这将对不可 满足性的证明是十分有益的。 Herbrand首先将合式公式标准化为子句集,然后在此基 础上引入Herbrand域 (简记为H域),并从理论上给出了证 明子句集永假的可行性及方法。 3 2011-12-26 1. 子句和子句集 在谓词逻辑中,把不含任何连接词的原子谓词公式及其 否定称为文字;把由文字的析取构成的合式公式称为子句; 把不包含任何文字的子句称为空子句;把由子句构成的集合 称为子句集。在谓词逻辑中,任何一个谓词公式都可以通过 应用等价关系和推理规则转化成相应的子句集。在子句集中 各子句之间具有合取关系。 鉴于子句集隐含地受到全称量词的约束,而全称量词又 可分配到有合取关系的各个子句,所以各子句中的变量实际 上都是全称量词的约束变量,且作用域只在子句范围内。为 消除子句间不必要的交互作用(即保持子句间的相互独立 性),需要作变量换名,使各子句都使用不同的变量。 补充 对一个谓词公式G,通过以下步骤所得的子句集合S (子句集中各子句之间具有合取关系),称为G 的子句集。 (1) 消去蕴含词→和等值词。可使用逻辑等价式: ① A→B 乛A ∨B ② AB  (乛A ∨B) ∧(乛B ∨A) (2) 缩小否定词的作用范围,直到其仅作用于原子公式。 可使用逻辑等价式: ① 乛(乛A) A ② 乛(A ∧B)  乛A ∨乛B ③ 乛(A ∨B)  乛A ∧乛B ④ 乛 xP(x)  x 乛P(x) ⑤ 乛 xP(x)  x 乛P(x) 4 2011-12-26 (3) 适当改名,使量词间不含同名指导变元和约束变元。 (4) 消去存在量词。 消去存在量词,要进行变元替换。分两种情况: ①若该存在量词在某些全称量词的辖域内 (如: xy ,则用这些全称量词指导变元的一个函数代 替该存在量词辖域中的相应约束变元,这样的函 数称为Skolem函数; ②若该存在量词不在任何全称量词的辖域内,则用一 个常量符号代替该存在量词辖域中的相应约束变 元,这样的常量符号称为Skolem常量。 (5) 消去所有全称量词。 (6) 化公式为合取范式。 可使用逻辑等价式: ①A ∨(B ∧C)  (A∨B) ∧(A∨C) ② (A ∧B) ∨C  (A ∨C) ∧(B∨C) (7) 消去合取词∧,以子句为元素组成一个集合S。 子句内的文字可含有变量,这些变量被理解为隐含 地受全称量词约束。 (8) 适当改名,使子句间无同名变元。 5 2011-12-26 例4-1 求下面谓词公式的子句集 x {yP (x ,y )→¬y [Q(x ,y )→R(x ,y )]} 解 (1) 消去蕴含词和等价词 x {¬yP (x ,y ) ∨¬y [¬Q(x ,y ) ∨R(x ,y )]} (2) 缩小否定词的作用范围,直到其仅作用于原子公式 x {y ¬P(x ,y ) ∨y [Q(x ,y ) ∧¬R(x ,y )]} (3) 适当改名,使量词之间不含同名指导变量和约束变量 x {y ¬P(x ,y ) ∨z [Q(x ,z) ∧¬R(x ,z)]} (4) 消去存在量词 如果该量词在某些全称量词的辖域内,则用这些全称量词指导变量的一个 函数代替该存在量词辖域中相应的约束变量,这样的函数成为Skolem函数; 如果该量词不在任何全称量词的辖域内,则用一个常量符号代替该存在量 词辖域中相应的约束变量,这样的函数成为Skolem常量。 x {¬P(x ,f (x)) ∨[Q(x ,g(x)) ∧¬R(x ,g(x))]} (5) 消去全称量词 ¬P(x ,f (x)) ∨[Q(x ,g(x)) ∧¬R(x ,g(x))] (6) 化公式为合取范式 [¬P(x ,f (x)) ∨Q(x ,g(x))] ∧[¬P(x ,f (x)) ∨¬R(x ,g(x))] (7) 适当改名,使子句间无同名变量 [¬P(x ,f (x)) ∨Q(x ,g(x))] ∧[¬P(y ,f (y )) ∨¬R(y ,g(y ))] (8) 消去合取词,以子句为元素组成一个集合S S={¬P(x ,f (x)) ∨Q(x ,g(x)), ¬P(y ,f (y )) ∨¬R(y ,g(y ))} 当一个谓词公式G化简为标准化的子句集S时,有一个 重要性质,即S的不可满足(对于任意论域上的任意解释, S中都至少有一个子句真值为假)成为G永假的充分必要条 件。注意,这并不意味着G与S间等价。由于在谓词公式G的 化简过程中,为消除存在量词而引入了Skolem函数,从而使 子句集S实际上只是G的一个特例。然而,可以证明G和S在 永假性上是等价的,这成为建立Herbrand定理的重要基础。 定理4-1 若G是给定的谓词公式,而相应的子句集为S, 则G是不可满足的当且仅当S是不可满足的。 6 2011-12-26 2. Herbrand域 及 Herbrand定理 子句集是子句的集合。为了判定子句集的不可满足性, 就需要对子句集中的子句进行判定。由谓词公式永假性的 定义可知,为判断一个子句的不可满足性,需要对个体域 上的一切解释逐个进行判定,只有当子句对任何非空个体 域上的任何一个解释都不是不可满足的时,才能判定该子 句是不可满足的,这是一件十分麻烦甚至难以实现的困难 工作。针对这一情况,Herbrand构造了一个特殊的域,并 证明只要对这个特殊域上的一切解释进行判定,就能得知 子句集是否不可满足,这个特殊的域称为Herbrand域,简 记为H域。 定义4-1 设S为子句集,则按下述方法构造的域H∞称为Herbrand 域: (1) 令H0是S中出现的所有个体常量的集合,若S中不包含个体 常量,则令就H0 ={a},其中,a为任意指定的一个个体常 量。 (2) 令Hi+1=Hi ∪{S中所有n元函数f (x 1,…,xn) xj (j =1,…,n)在Hi 中 的元素},i=1,2,… 。 例子见书上例4-2 、例4-3 。 定义4-2 子句集S在H域上的一个解释I *满足下列条件: (1) 在解释I *下,常量映射到自身。 (2) S中的任一个n元函数是Hn→{T,F}的映射。T和F是谓词的 线 设I 是S的论域D上的解释,存在对应于I 的H解释I *, 使得若有 SI=T ,必有SI *=T。 定理4-3 子句集S是不可满足的充要条件是S的H域上一切解 释都为假。 定理4-4 (Herbrand定理) 子句集S不可满足的充要条件是存 在一个有限的不可满足的基子句集S‘。 从理论上讲,根据Herbrand定理可以建立计算机程序去实 现自动定理证明。但设计这样的程序存在二个主要的困难: (1) 子句集的不可满足性是不可判的,即子句集的不可满 足性不能确保在有限的计算步范围内判定。 (2) 即使对于不可满足的子句集,能在有限的计算步范围 内加以证明,但依据H域上的每个解释判别不满足的 基子句,计算量也往往很大。 可以看出,虽然Herbrand从理论上给出了证明子句集不可 满足的可行性及方法,但在计算机上实现其证明过程却十分困 难。1965年Robinson提出归结原理,这才使自动定理证明变成 现实。 8 2011-12-26 4.2.2 归结原理 p.101 归结原理又称消解法。基本思路是通过归结方法不 断扩充待判定的子句集,并设法使空子句出现。空子句 是不可满足(即永假)的子句,既然子句集中的子句间 隐含着合取关系,空子句的出现就确定了子句集的不可 满足。 1. 归结方法 (1) 归结式 定义4-3 设L为一个文字,则称L和¬L为互补文字。 定义4-4 设有二个子句: C1=L ∨C1`,C2=¬L ∨C2 ` ,从C1和C2 中消去互补文字L和¬L,并通过析取将C1和C2 的剩余部分组成 新的子句: C= C1`∨C2 ` 则称C为C1和C2 的归结式(消解式),C1 ,C2称为其归结式的亲 本子句,L、L称为消解基。 (2) 归结式性质 定理4-5 二个子句C1和C2 的归结式C是C1和C2 的逻辑结论。 推论 设C1和C2 是子句集S中的两个子句,并以C作为它们的归 结式,则通过往S中加入C而产生的扩展子句集S与子句集S在 不可满足的意义上是等价的,即S的不可满足⇔S的不可满足。 9 2011-12-26 (3) 空子句 当C1=L和C2= ¬L时,归结式为空;通常以字母 “NIL” 或者符号 “□”指示为空的归结式,并称C=NIL表示C为空 子句。显然C1和C2 是一对矛盾子句——无论为子句集指派什 么解释,C1和C2 不可同时满足,所以空子句实际上是不可满 足的子句,进而导致子句集不可满足。 换言之,空子句就是归结原理判定子句集不可满足的 成功标志。 2. 命题逻辑中的归结 例4-7 利用归结原理判定子句集S={¬P ∨Q,P ∨R, ¬Q, ¬R} 是否可满足。 P ∨Q P ∨R Q∨R Q R R NIL 图4-1 命题逻辑的归结演绎树 10 2011-12-26 3. 谓词逻辑中的归结 在谓词逻辑情况下,由于子句中含有变量,不能像命 题逻辑那样直接发现和消去互补文字,往往需对潜在的互 补文字中的变量做置换与合一处理后,才能进行归结。 1) 置换与合一 (1) 置换 置换可以简单的理解为是在一个谓词公式中用置换 项去置换相应的变量。 定义4-5 置换是形如{t1/x1,t2/x2 ,…,tn/xn }的有限集合, ti/xi表示用ti 置换xi ;其中x1,x2 ,…,xn 是互不相同的变量, t1,t2 ,…,tn 是不同于xi 的项(常量、变量、函数),而且xi 不 能循环地出现在另一个tj (i,j =1,2,…,n )中。 定义4-6 设θ={t1/x1,t2/x2 ,…,tn/xn },λ={u1/y 1,u2/y 2 ,…,un/y n }是两 个置换,则θ与λ的合成也是一个置换,记作θ·λ。θ·λ是从 集合{t1 ·λ/x1,t2 ·λ/x2 ,…,tn ·λ/xn ,u1/y 1,u2/y 2 ,…,un/yn }中删去以下两 种元素: ① 当tiλ=xi 时,删去tiλ/xi (i=1,2, …,n); ② 当y i {x1,x2 ,…,xn }时,删去uj /yj (j =1,2, …,m) 最后剩下的元素所构成的集合。 11 2011-12-26 (2)合一 合一可以简单地理解为“寻找相对变量的置换,使两 个原子谓词公式一致”。 定义4-7 设有原子谓词公式集F={F1,F2 ,…,Fn },若存 在一个置换θ,可使F1θ=F2θ=… Fnθ,则称θ是F 的一个合一。 同时称F1,F2 ,...,Fn 是可合一的。 一般说来,一个原子谓词公式集的合一不是唯一的。 定义4-8 设σ是原子谓词公式集F 的一个合一,如果 对F 的任意一个合一θ都存在一个置换λ,使得θ=σ·λ,则称σ 是一个最一般合一(Most General Unifier ,简记为MGU )。 2) 谓词逻辑中的归结原理的应用 定义4-9 设C1和C2 是两个没有相同变量的子句,L1和L2分 别是C1和C2 的文字,如果σ是L1和¬L2 的最一般合一,则子句 (C1σ- {L1σ}) ∪(C2σ- {L2σ}) 称作子句C1和C2 的一个二元归结式,C1和C2称作归结式的亲 本子句,而L1和L2称为被归结的文字。 12 2011-12-26 例4-9 设有两个子句: C = P(y) ∨P(f(x)) ∨Q(g(x)) 1 C = ¬P(f(g(a))) ∨Q(b) 2 在C 中有可合一的文字P(y)与P(f(x)) ,那么,取最一般合 1 一 ={f(x)/y} ,则得 C  =P(f(x)) ∨Q(g(x)) 1 现在再用C 与C 进行归结,可得C 与C 的归结式 1 2 1 2 Q(g(g(a)))∨Q(b) 定义4-10 若子句 C 中有两个或两个以上文字存在一个最一般合 一,则称 C 为子句 C的因子。如果 C 为一个单文字,则称它 为C的单元因子。 定义4-11 若C1和C2 是无公共变量的子句,则 ① C1和C2 的二元归结式; ② C1 的因子和C2 的二元归结式; ③ C1和C2 的因子的二元归结式; ④ C1 的因子和C2 的因子的二元归结式。 这四种二元归结式都叫子句C1和C2 的归结式,仍记作R(C1,C2) 。 13 2011-12-26 在谓词逻辑的归结演绎推理中只需对原子谓词公式作合一处理, 所以实际上只需通过一个匹配过程去检查两个原子谓词公式的可合一 性,并同时建立用于实现合一的置换。匹配过程可归纳如下: (1) 二个公式必须具有相同的谓词和参数项个数; (2) 从左到右逐个检查参数项的可合一性: ① 若一对参数项中有一个变量v (不必关注另一个参数是否为变 量),并初次出现,则这对参数项可合一,并以另一参数t为置 换项,与该变量一起构成一个置换元素t/v ; ② 若该变量出现过,则已建立相应的置换元素,就取其置换项, 代替该变量,检查是否与另一参数合一;若不能合一,则合一 处理失败。 ③ 若一对参数项中没有一个是变量(往往都是常量),则它们必 须相同,否则合一处理失败。 (3) 若每对参数项都可合一,则合一处理成功,并构成用于实现合一 的置换。 例3.21 求证G是A 和A 的逻辑结果。 1 2 A : x(P(x)→(Q(x) ∧R(x))) 1 A : x(P(x) ∧S(x)) 2 G: x(S(x) ∧R(x)) 证: 我们用反证法/归谬法,即证明A1 ∧A2 ∧乛G不 可满足。 首先求得子句集S: 14 2011-12-26 (1) 乛P(x) ∨Q(x) (A ) (2) 乛P(y) ∨R(y) 1 (3) P(a) S (A ) 2 (4) S(a) (5) 乛S(z)∨乛R(z) (乛G) 然后应用消解原理,得 (6) R(a) [(2),(3), = {a/y }] 1 (7) 乛R(a) [(4),(5), = {a/z }] 2 (8) □ [(6),(7) ] 所以S是不可满足的,从而G是A 和A 的逻辑结果。 1 2 4. 归结原理的完备性 对于一阶谓词逻辑,从不可满足的意义上讲,归结原理 是完备的。 定理4-7 设子句集S是不可满足的,当且仅当存在一个 由S应用归结原理推出空子句的推理过程。 15 2011-12-26 4.2.3 归结反演 归结原理给出了证明子句集不可满足性的方法。欲证明 Q为P1,P2 ,…,Pn 的逻辑结论,只需证明(P1 ∧P2 ∧…∧Pn) ∧Q 是不可满足的。因此,可用归结原理来进行定理的自动证明。 这种应用归结原理证明定理的过程,我们称为归结反演。 1. 归结反演系统 归结反演的基本思路是:要从作为事实的公式集F证 明目标公式W为真,可以先将W取反,加入公式集F, 然 后将F标准化为子句集S,再通过归结演绎证明S不可满足, 并由此得出W为真的结论。 因此,一个归结反演系统应由二个部分组成:标准化 部件和归结演绎部件。 – 前者将每条事实和取反的目标公式分别标准化为子 句集,再合并为子句集S; – 后者遵从归结演绎方法,控制定理证明的全过程。 16 2011-12-26 设F为已知前提的公式集,W为目标公式,用归结反 演证明W为线) 否定W,得W; (2) 把W添加到F 中去; (3) 把新产生的集合{W,F}化成子句集S; (4) 应用归结原理对子句集S中的子句进行归结,力图 推导出一个表示矛盾的空子句NIL 。如果出现空子 句,则停止归结,此时就证明W为线. 归结演绎推理的控制策略 机器实现归结演绎的时候,如何选择子句进行归结?如 果盲目地选择子句进行归结,不仅耗费许多时间,而且可能 归结出很多无用的归结式而无意义地扩张子句集、降低效率。 如果穷举所有可能的归结更会产生组合爆炸问题。 所以,关键是要选择有利于尽快产生空子句的子句进行 归结;这就涉及到归结策略。 定义4-10 一个归结策略是完备的,如果对于不可满足 的子句集,使用该策略进行归结,最终必导出空子句。 17 2011-12-26 归结策略归纳起来大致可以分为三类:简化性策略、有 序性策略和限制性策略。 – 简化性策略的思想是尽量简化子句和子句集,以减少 和避免无效归结。如后面提到的删除策略。 – 有序性策略的思想是给子句安排一定的顺序,以便能 尽快推出空子句。如后面提高的宽度优先策略、单元 优先策略。 – 限制性策略的思想使尽量缩小搜索范围,以提高搜索 效率。如后面提到的支持集策略、语义归结策略、线 性归结策略、输入归结策略、单元归结策略、祖先过 滤形策略。 1) 删除策略 定义4-11 设C1和C2 是两个子句,若存在置换θ,使 得C1θC2 ,则称子句C1类含C2或子句C2把C1归类。 归类算法: (1) 令W={L 1θ, …, Lmθ} (2) 令k=0 ,U0={C2} (3) 如果Uk包含空子句,则停止,这时C2把C1归类。 否则令Uk+1={C1和C2 的归结式C2 Uk , C1 W} (4) 如果Uk+1 是空集,则停止,这时C2 不能把C1归类。 否则k+1→k转(3) 18 2011-12-26 删除策略的主要思想:归结过程在寻找可归结子句 时,子句集中的子句越多,需要付出的代价就会越大。 如果在归结时能把子句集中无用的子句删除掉,这些无 用子句的后代将不能出现,就会缩小搜索范围,减少比 较次数,从而提高归结效率。 删除策略是完备的,即对于不可满足的子句集,使 用该策略进行归结,最终必然导出空子句。 2) 宽度优先策略 基本思想:先从基本子句集生成所有的归结式,再从 基本子句集和第一级归结式生成第二级归结式,以此类推。 宽度优先策略是完备的,但是低效的。 3) 支持集策略 基本思想:每次归结时,两个亲本子句中至少要有一 个是是目标公式的否定或其后代。这里的目标公式否定的 子句集即为支持集。支持集策略是完备的。 4) 语义归结策略 基本思想:将子句集S按照一定的语义分成两部分,约 定每部分内的子句间不允许作归结。同时还引入了文字次 序,约定归结时其中的一个子句的被归结文字只能是该子 句中 “最大”的文字。语义归结策略是完备的。 19 2011-12-26 5) 单元归结策略 基本思想:每次归结选取单文字的子句(称作单元) 作为一个亲本子句。 6) 输入归结策略 基本思想:在归结过程中,每一次归结的两个亲本子 句中必须有一个是子句集S 的原始子句。输入归结策略是不 完备的。 7) 线性归结策略 在归结过程中,除第一次归结可都用给定子句集S 中 的子句外,其后的各次归结则至少要有一个亲本子句是上 次归结的结果。线性归结策略不仅本身是完备的,高效的, 而且还可以与许多别的策略兼容。 8) 祖先过滤形策略 基本思想:参加归结的两个子句,要么至少有一个是 初始子句集中的子句;要么一个是另一个的祖先(或者说 一个是另一个的后裔)。该策略是完备的 。 20 2011-12-26 3. 归结演绎推理的缺点 (1) 归结演绎推理必须将合式公式标准化为高度统一的子 句集,从而丢失了隐含于合式公式的启发性知识。 (2) 归结演绎并非人类的自然思维方式,不利于人们从自 然思维的角度组织问题的求解和提供问题求解所需的 知识,从而难以建立高水平的问题求解系统,如专家 系统。 4.3 非归结演绎推理 p. 113 4.3.1 基于规则的演绎推理 4.3.2 Bledsoe 自然演绎法 4.3.3 Boyer-Moore定理证明方法 4.3.4 王浩算法 21 2011-12-26 4.3.1 基于规则的演绎推理 基于规则的演绎推理是一种非归结推理。这种推理只 要将问题求解的依据 (事实或公式)和目标以合式公式加 以形式化描述,就可交由演绎推理系统和问答系统执行。 基于规则演绎推理的系统,称为规则演绎系统。实际上, 它是一种基于谓词逻辑的产生式系统。 规则演绎系统将求解问题所需的知识分为二类:规则 和事实。 – 规则表示为蕴含式,作为启发式知识(表示应用域 中存在的规律和法则),引导演绎推理过程。 – 事实则表示为非蕴含形式的合式公式,作为应用规 则进行推理时参考的有关问题状态和环境的知识。 规则演绎的任务就是基于给定的事实(即问题的状态 和环境知识)和规则,证明某个目标公式成立。 基于规则的演绎推理可以区分为二大类:正向演绎和 逆向演绎。 – 正向演绎从事实出发、应用规则,推目标公式; – 逆向演绎从目标出发,找支持其成立的事实依据。 22 2011-12-26 1.基于规则的正向演绎推理 正向演绎推理要求将问题求解的描述分为三个部分:事 实、规则集和目标。为便于演绎推理,需将表示它们的合式 公式简化为下述标准形式,并加以适当限制。 (1) 事实表达式 在基于规则的正向演绎系统中,把事实表示为不 含蕴含符号的文字与/或形 (所含的变量被理解为隐 含地受全称量词约束)。 Steps to transform facts into AND/OR form: 1. Eliminate (temporarily) implication symbols. 2. Reverse quantification of variables in first disjunct by moving negation symbol. 3. Skolemize existential variables. 4. Move all universal quantifiers to the front an drop. 5. Rename variables so the same variable does not occur in different (main) conjuncts. 例如:事实表达式: uv ( Q(u,v) ∧( (R(v) ∨P(v)) ∧S(u,v) ) ) 化为: Q(A ,v) ∧( (R(v) ∧P(v)) ∨S(A ,v) ) 再对变量更名标准化,使得同一变量不出现在事实表达式的 不同(主要)合取式中,即将Q(A ,v) 中的v更名为w ,则表达式 为 Q(A,w) ∧((R(v) ∧P(v)) ∨S(A ,v)) 23 2011-12-26 (2) F规则 这些规则是建立在某个问题辖域中普通陈述性知识的蕴含公式 基础上的。 正向演绎推理以正向方式使用规则(称为F规则),规则化简 为以下形式:L → W ,其中,L为单文字,W是与/或形。之所 以限制规则左部为单文字,是为了在演绎推理过程中便于通过 L 和 与/或图的叶节点(对应单文字)的匹配来激活规则。 Steps to transform the rules into a free-quantifier form: 1. Eliminate (temporarily) implication symbols. 2. Reverse quantification of variables in first disjunct by moving negation symbol. 3. Skolemize existential variables. 4. Move all universal quantifiers to the front and drop. 5. Restore implication. All variables appearing on the final expressions are assumed to be universally quantified. 如:表示规则的原始蕴含式为: x( y zP(x ,y ,z) →u(Q(x ,u) ∨R(x ,u)) ) 则先暂时消去蕴含符号并化简为文字与/或形: P(x ,y ,f (x ,y )) ∨Q(x ,u) ∨R(x ,u) 再恢复蕴含式表示:P(x ,y ,f (x ,y ))→Q(x ,u) ∨R(x ,u) 有时化简的结果会出现形如 L1 ∨L2→W 的情况,可以进一 步化简为与其等价的两条规则:L1→W ,L2→W 24 2011-12-26 (3) 目标公式 目标公式化简后限定表示为文字的析取式,即称为子句形。在 正向推理系统中,这种目标表达式只限于可证明的表达式。 目标公式化简时,量词消去方法是取事实表达式的对偶形式, 即将全称量词的约束变量以Skolem函数或常量取代,并使子句 隐含地受存在量词约束。例如目标公式: xy z(P(x ,y ,z) ∨Q(x ,y )) 则先以Skolem常量A 和Skolem函数g(y )分别取代约束变量x和z , 再消去全称量词,于是得: y (P(A ,y ,g(y )) ∨Q(A ,y )) 然后消去存在量词,并隐含着y 是存在量词的约束变量。 最后,子句中变量须做换名处理,使各文字不含同名变量。所 以上式化为: P(A ,y ,g(y )) ∨Q(A ,w) 一个基于规则的正向演绎系统,其演绎过程就是不断地 调用匹配上的F规则对与/或图进行变换,直到生成的与/或 图含有目标表达式为止,也就是要用目标公式作为系统的结 束条件。 正向演绎系统的目标表达式要限制为文字析取式的一类 公式,当目标公式中有一个文字同与/或图中某一个端节点 所标记的文字匹配上时,和规则匹配时做法一样,通过匹配 弧把目标文字添加到图上,这个匹配弧的后裔节点称为目标 节点。 这样,当产生一个与/或图,并且包含有终止在目标节 点上的一个解图时,系统便成功结束演绎。 25 2011-12-26 A full example: (a) Fido barks and bites, or(否则) Fido is not a dog. (b)All terriers(一种小猎狗) are dogs. (c) Anyone who barks is noisy. Based on these facts, prove that: “there exists someone who is not a terrier or who is noisy.” Logic representation: (barks(fido)  bites(fido))  ~dog(fido) R1: terrier(x)  dog(x) R2: barks(y)  noisy(y) goal: w (~terrier(w)  noisy(w)) AND/OR Graph for the „terrier‟problem [barks(fido)  bites(fido)] v ~dog(fido) barks(fido)  bites(fido) ~dog(fido) R1 barks(fido) bites(fido) ~terrier(fido) R2 noisy(fido) goal nodes {fido/z} {fido/z} noisy(z) ~terrier(z) 26 2011-12-26 2. 基于规则的逆向演绎推理 逆向演绎推理与正向演绎推理形成对偶关系,从目标 公式出发,逆向应用规则对相应于目标公式的原始与/或图 进行变换,直至得到一个所有叶节点都是事实节点(以事 实表达式中的文字作为节点内容的节点)的一致解图为止。 逆向演绎推理情况下问题求解的描述也分为三部分:目标 公式、规则和事实,它们的标准化表示形式与正向演绎呈 现对偶关系。 (1) 目标表达式 逆向演绎推理情况下,目标公式的表示不受限制,化 简为不含蕴含符号的文字与/或形。例如有目标表达式: y x( P(x)  ( Q(x ,y ) ∧(R(x) ∧S(y )) ) ) 先化简为: P(f (y )) ∨((Q(f (y ),y ) ∧(R(x) ∨S(y )))) 重新命名变量后得 P(f (z)) ∨((Q(f (y ),y ) ∧(R(x) ∨S(y )))) 27 2011-12-26 (2) B规则 逆向演绎推理以逆向方式使用规则(称为B规则),要求规 则化简为以下形式:W→L,其中,L为单文字,W是与/或 形;规则的激活取决于L和与/或图叶节点的匹配。设表示规 则的原始蕴含式为: x(y z(P(x ,y ,z) ∧Q(y ,z)) →uR(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) 有时化简的结果会出现形如W→L1 ∧L2 的情况,可以进一 步化简为与其等价的两条规则W→L1 ,W→L2 。 (3) 事实表达式 逆向系统中的事实表达式限定表示为文字的合取式,它 可以表示为一个文字集。消去量词时将存在量词的约束变量 以Skolem函数或常量取代,并使合取式隐含地受全称量词约 束。 一个基于规则的逆向演绎系统,调用匹配上的B规则去 对与/或图进行变换,使与/或图不断扩展。被激活规则的右 部单文字通过匹配弧插入,而规则左部则以与/或图子图的 方式插入。当事实表达式包含的文字和与/或图叶节点匹配 时,事实文字作为事实节点插入与/或图。当获得一个叶节 点全是事实节点的一致解图时,演绎推理成功结束。 28 2011-12-26 Examples Facts: dog(fido) ~barks(fido) wags-tail(fido) meows(myrtle) Rules: R1: [wags-tail(x1)  dog(x1)]  friendly(x1) R2: [friendly(x2)  ~barks(x2)]  ~afraid(y2,x2) R3: dog(x3)  animal(x3) R4: cat(x4)  animal(x4) R5: meows(x5)  cat(x5) Suppose we want to ask if there are a cat and a dog such that the cat is unafraid of the dog. The goal expression is: x y [cat(x)  dog(y)  ~afraid(x,y)] cat(x)  dog(y)  ~afraid(x,y) {myrtle/x} {myrtle/x} {fido/y} ~ afraid(x,y) cat(x) dog(y) R2 {myrtle/x} R5 {fido/y} {fido/y} {fido/y} meows(myrtle) dog(fido) friendly(y) ~barks(y) R1 {Fido/y} ~barks(fido) wags_tail(y) dog(y) {fido/y} {fido/y} wags_tail(fido) dog(fido) 29 2011-12-26 3. 基于规则演绎推理的应用讨论 两种方向的演绎推理技术具有共同的特点,即都以与/ 或 形和相应的与/或图来表示和支持推理过程,推理控制的 基本策略都是通过不断匹配规则去变换与/或图,直至搜索 到某个一致解图为止。 表4-1正、逆向演绎推理的特点比较 正向演绎推理 逆向演绎推理 问题 事实表达式 任意形式 事实表达式 文字合取式 求解的 规则 L → W或L ∨ L → W 规则 W → L或W →L ∧L 描述 1 2 1 2 目标 文字析取式 目标 任意形式 化简 (1)用Skolem函数消去事实表达式中的存 (1)用Skolem函数(对偶形)消去目标公 过程 在量词,化简的公式受全称量词的 式中的全称量词,化简的公式受存在 约束 量词的约束 (2)对规则的处理同 (1) (2)对规则的处理同 (3) (3)用Skolem函数(对偶形)消去目标公 (3)用Skolem函数消去事实表达式中的存 式中的全称量词,化简的公式受存 在量词,化简的公式受全称量词的约 在量词约束 束 初始与 事实表达式的与/或树 目标公式的与/或树 /或图 (∨对应为与关系,∧对应为或关系) (∨对应为或关系,∧对应为与关系) 从事实出发,正向应用规则(变量改名, 从目标出发,逆向应用规则(变量改名, 演绎 前项与事实文字匹配,后项代替前项), 后项与子目标文字匹配,前项代替后 推理 直至得到目标节点为结束条件的一致解 项),直至得到事实节点为结束条件的 图为止 一致解图为止 30 2011-12-26 4.3.2 Bledsoe 自然演绎法 自然演绎法符合人的思维推理方式,直观易懂。对于 一阶谓词逻辑来说,存在着完备的自然演绎系统,但如果 直接应用这类系统,其效率非常低。 1975年,W.W.Bledsoe等研制的IMPLY 系统中使用了 带启发式规则的自然演绎法。Bledsoe 自然演绎法是效率较 高的一种推理方法,它采用多条推理规则,试图模拟人脑 的推理证明方式,从前提推导出结论。 Bledsoe 自然演绎过程中保留了联结词→ 。另外,与归 结原理中标准化过程不同,它消去了全称量词而不是存在 量词。 1.命题的标准化方法 首先了解一些简单公式的标准化,标准化的形式称为Skolem*标准 形。它与Skolem标准形的确别是保留了联结词 “→ ”,而且也没要求 化为前束范式。 1)一些简单公式的标准化 原公式 Skolem*标准形 xP(x) P(x) Q→xP(x) Q→P(x) x(Q→P(x)) Q→P(x) x(P(x)→C) P(x)→C xP(x) P(x ) 0 Q→xP(x) Q→P(x ) 0 x(P(x)→C) P(x )→C 0 xy (P(x ,y )→C) P(x ,g(x))→C H→uvQ(u,v) H→uvQ(u,h(u)) xy P(x ,y )→uvQ(u,v) P(x ,g(x))→Q(u,h(u)) y )xP(x ,y )→uvQ(u,v) P(x ,y )→Q(u,v ) 0 0 31 2011-12-26 2) 符号规则 对于一般公式Skolem*标准形,需定义公式的正负概念以及 公式间的符号规则。对于一个公式E来说,其正负如何依赖 于它的子公式的正负,有如下规定: (1) 如果A ∧B是正(负),那么A 和B均为正(负)。 (2) 如果A ∨B是正(负),那么A 和B均为正(负)。 (3) 如果A 是正(负),那么A 是负(正)。 (4) 如果A →B是正(负),那么A 是负(正)而B是正(负)。 (5) 如果xA 是正(负),那么A 是正(负)而是正(负) 量词。 (6) 如果xA 是正(负),那么A 是正(负)而是负(正)量 词。 3) 消量词规则 (1) 对于只有一个量词的简单公式,规定: xP(x) ,为正时,Skolem*标准形为P(x0) 为负时,Skolem*标准形为P(x) xP(x) ,为正时,Skolem*标准形为P(x) 为负时,Skolem*标准形为P(x0) (2) 一般情形(不含情形(1) ),若公式E 中变量x 由正量词 所约束,而该量词左边所有负量词为(Qs 1xs 1) …(Qsrxsr) 当r=0 时,则x 以常量代入。 当r≠0 时,则x 以f (xs 1,…, xsr)代入,其中f 是E 中未出现过的函 数符号。 对E 中所有变量依次做这样的代入,便可消去全部量词, 便得E 的Skolem*形。 32 2011-12-26 2. 推理规则 自然演绎法是直接来证明公式的成立。例如,要证明(x)P(x) ,只需论域中 有个x0 ,使P(x0)成立。在这种观点下,把(x)P(x)化成了Skolem*形P(x) ,认 为x 是受存在量词约束。这种理解下可引入一条推理规则,若有置换θ使Pθ 为真就有P(x)为真,即(x)P(x)得证。这样就不难理解下述规则了。符号[E], 表示规则应用于E是成立的。我们仅介绍一下这几条规则。 (1) MATCH :[H→C] 如果Hθ=Cθ,则θ为所求。这是最简单的规则了,要求目标C 同前提H匹配, 如果找到一个置换θ使Hθ=Cθ。 (2) AND-SPLIT :[H→A∧B] 如果[H→A]在θ下,而[H→Bθ]在λ下成立,则θ·λ为所求。 (3) CASES :[H 1 ∨H2 →C] 如果[H 1→C]在θ下,而[H2θ→C]在λ下成立,则θ·λ为所求。 (4) OR-FORK :[A∧B→C] 如果[A→C]在θ下成立,则θ为所求,否则需证[B→C]成立。 (5) BACK-CHAIN :[H∧(A→B)→C] 如果[B→C]在θ下,而且[H→Aθ]在λ下成立,则θ·λ为所求。 4.3.3 Boyer-Moore定理证明方法 1979年,博耶 (R. S. Boyer )和莫尔 (J. S. Moore )提出 了计算逻辑,在此基础上讨论了具有归纳结构的这种难度较 大的定理证明问题,建立了归纳证明方法,给出了定理证明 程序BMTP 。 1. 基本公理 BMTP是由两个函数IF和EQUAL 以及两个常量T和F (对 应谓词演算中的真和假)出发进行讨论的。BMTP 中出现的 表达式仅使用函数和变量,不用谓词也不出现量词,所出现 的变量可视为是受某论域上的全称量词约束,它不考虑存在 量词约束下的变量。它们通过如下的公理体系被定义。 33 2011-12-26 公理4-1 (1) T≠F (2) X=Y→(EQUAL X Y)=T (3) X≠Y→(EQUAL X Y)=F (4) X=F→(IF X Y Z)=Z (5) X≠F→(IF X Y Z)=Y 函数EQUAL可用来判明两变量是否相等,函数IF从逻辑上可理解为 (X ∧Y) ∨(¬X ∧Z) 。在此基础上,不难定义如下的逻辑运算: (1) (NOT P)=(IF P F T ) (2) (AND P Q)=(IF P (IF Q T F) F) (3) (OR P Q)=(IF P T (IF Q T F )) (4) (IMPLIES P Q)=(IF P (IF Q T F ) T) 当AND和OR有多个参数时,(AND a b c)表示(AND a (AND b c)) , (OR a b c)表示(OR a (OR b c)) ,这些表示都容易理解。 2. 外壳原理 Boyer-Moore通过所谓的外壳原理来引进各种数据结构及其基本的运算 原理。每一种新的数据结构即是一个新的外壳。一般由n个变量构成外壳。 外壳原理的建立,相当于把一些公理加进了BMTP 中。 增加一个新的外壳需要说明: (1) 构造符const ; (2) const 的变量个数n ; (3) (不是必需的)底元素btm ; (4) 识别符a ; (5) 访问符ac 1,…,can ; (6) 类型限制tr1,…,trn ; (7) 缺省值dv 1,…,dvn ; (8) 良基关系r 。 其中所有符号都是新的,都不相同。符号a,ac 1,…,can是单变量的函数符 号,r是双变量的函数符号。每个tri是一个项,它只能含xi 为其变量,且只 能含IF,T,F,a及在此之前已引进的外壳识别符为其函数符号。 34 2011-12-26 外壳中的良基关系相当于小于关系,在这种意义下外壳有 唯一的最小元。可如下定义良基关系,设r是集合S上的一 个二元关系,若对于S中任意元素x ,y ,z有: ① (r x x)=F ② 若(r x y )≠F,则(r y x )=F ③ 若(r x y )≠F,(r y z )≠F ,则(r x z)=F 满足上述三个条件,则称r是为一个序关系。 ④若不存在S中的无穷序列x 1,x2 ,x3,…,使得对任一i0有(r xi+1 xi)≠F, 满足上述四个条件,则称序r为S上的一个良基关系。 3. 定义原理 定义原理是在外壳中依基本函数定义新函数的方法。计 算逻辑的句法采用了类似于LISP语言的句法结构,不使用谓 词,函数描述如同LISP语言函数的前辍形式。 引进一个具有n个变量的新函数f ,可以写成Definition(f x 1 …xn)=body,其中body是函数体。规定: (1) f 不同于所有它的引进的符号,既是新的n元函数符。 (2) x 1 …xn均为不同的变量。 (3) 函数体是一个项,其中不包含除x 1 …xn 以外的变量。 (4) 存在由r定义的良基关系和由n元函数m定义的度量, 使得对于函数体中任何形如(f y 1 …y n) 的出现,以及所 有控制此出现的无f 项t1,…,tk , (IMPLIES (AND t1,…,tk) (r (m y 1 …y n)(m x 1 …xn)))是一 条定理。 35 2011-12-26 4. 归纳原理 归纳模板组成如下: (1) p 是一个项(写成项形式的待证定理) (2) r是一个表示良基关系的函数符号 (3) m是具有n个变量的度量函数符号 (4) x 1, …, xn是n个不同的变量 (5) q1, …, qk 是k个项 (6) h1, …, hk 是k个整数 (7) 对1≤i≤k ,1≤j ≤hi ,si,j 是一个置换,且 (IMPLIES qi(r (m x 1…xn)/si,j (m x 1…xn))) (4-1) 是一个已知为真的定理。 置换s 的一般定义是:把函数调用(f x 1…xn ) 中的每个xi 同时换以某个项ti ,

http://mj-sports.net/feidandiaotuili/289.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有