我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:管家婆六肖中特 > 非单调推理 >

第4章-确定性推理讲述ppt

归档日期:06-10       文本归类:非单调推理      文章编辑:爱尚语录

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

  4.1.2 推理方式及其分类 按推理过程中推出的结论是否单调地增加,或推出的结论是否越来越接近目标,可分为单调推理和非单调推理。 单调推理:在推理过程中随着推理的向前及新知识的加入,推出的结论是呈单调增加的趋势,并且越来越接近最终目标,在推理过程中不出现反复的情况,即不会由于新知识的加入否定了前面推出的结论,从而使推理又回到前面的某一步。 4.1.2 推理方式及其分类 非单调推理:在推理过程中由于新知识的加入,不仅没有加强已推出的结论,反而要否定它,使得推理退回到前面的某一步,重新开始。 注意:非单调推理是在知识不完全的情况下发生的。由于知识不完全,为使推理进行下去,就要先做某些假设,并在此基础上进行推理,当以后由于新知识的加入发现原先的假设不正确的时候,就需要推翻该假设以及基于此假设而推出的一切结论,再用新的知识重新进行推理。 4.1.2 推理方式及其分类 按推理时所用知识的确定性来划分,推理可分为确定性推理、不确定性推理。 确定性推理(精确推理):如果在推理中所用的知识都是精确的,即可以把知识表示成必然的因果关系,然后进行逻辑推理,推理的结论或者为真,或者为假,这种推理就称为确定性推理。 如:在MYCIN中采用确定性方法是一种简单有效的方法,仅采用一些简单直观的证据合并规则,其缺点是缺乏良好的理论基础。 4.1.2 推理方式及其分类 按推理时所用知识的确定性来划分,推理可分为确定性推理、不确定性推理。 不确定性推理(不精确推理):在人类知识中,有相当一部分属于人们的主观判断,是不精确的和含糊的。由这些知识归纳出来的推理规则往往是不确定的。基于这种不确定的推理规则进行推理,形成的结论也是不确定的,这种推理称为不确定性推理。 在专家系统中,主要使用的是不确定性推理。 4.1.2 推理方式及其分类 不确定性研究的重点可能会: 一是:解决现有处理不确定性的理论中存在的问题; 二是:大力研究人类高效、准确的识别能力和判断机智,开拓新的处理不确定性的理论和方法; 三是:探索可以综合处理多种不确定性的放法和技术。 4.1.2 推理方式及其分类 按推理过程中推出的结论是否单调地增加,或推出的结论是否越来越接近目标,可分为单调推理和非单调推理。 单调推理:在推理过程中随着推理的向前及新知识的加入,推出的结论是呈单调增加的趋势,并且越来越接近最终目标,在推理过程中不出现反复的情况,即不会由于新知识的加入否定了前面推出的结论,从而使推理又回到前面的某一步。 4.1.2 推理方式及其分类 按推理过程中推出的结论是否单调地增加,或推出的结论是否越来越接近目标,可分为单调推理和非单调推理。 非单调推理:在推理过程中由于新知识的加入,不仅没有加强已推出的结论,反而要否定它,使得推理退回到前面的某一步,重新开始。 注意:非单调推理是在知识不完全的情况下发生的。由于知识不完全,为使推理进行下去,就要先做某些假设,并在此基础上进行推理,当以后由于新知识的加入发现原先的假设不正确的时候,就需要推翻该假设以及基于此假设而推出的一切结论,再用新的知识重新进行推理。 4.1.2 推理方式及其分类 如果按推理程中是否运用于问题有关的启发性知识,推理可分为启发式推理与非启发式推理。 启发式推理:如果在推理过程中,运用了与问题有关的启发性知识,即解决问题的策略、技巧及经验,以加快推理过程,提高搜索效率,这种推理过程就被称为启发式推理。 如第三章的A*、AO*等算法就属于此类推理。 4.1.2 推理方式及其分类 非启发式推理:如果在推理过程中,不运用启发性知识,只按照一般的控制逻辑进行推理,这种推理过程就被称为非启发式推理。 注意:这种推理缺乏对待求解问题的针对性,所以推理效率较低,容易出现组合爆炸问题。如图搜索策略头重的宽度优先搜索法,虽然是完备的算法,但是对复杂问题的求解,将出现组合爆炸现象,其搜索效率较低。 4.1.3 推理的控制策略 推理的控制策略主要包括推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。 1、推理方向 推理方向用于确定推理的驱动方式,分为四种: 正向推理 逆向推理 混合推理 双向推理 4.1.3 推理的控制策略 正向推理 正向推理是从初始状态出发,使用规则,到达目标状态。又称为数据驱动推理、前向链推理、模式制导推理及前件推理。 逆向推理 逆向推理是以某个假设目标为出发点的一种推理,又称为目标驱动推理、逆向链推理、目标制导推理及后件推理。 4.1.3 推理的控制策略 混合推理 已知的事实不充分。通过正向推理先把其运用条件不能完全匹配的知识都找出来,并把这些知识可导出的结论作为假设,然后分别对这些假设进行逆向推理。 推理的形式: 先正向再逆向,通过正向推理,即从已知事实演绎出部分结果,然后再用逆向推理证实该目标或提高其可信度。 先逆向再正向,先假设一个目标进行逆向推理,然后再利用逆向推理中得到的信息进行正向推理,以推出更多的结论。 4.1.3 推理的控制策略 双向推理 双向推理是指正向推理与逆向推理同时进行,且在推理过程中的某一步骤上“碰头”的一种推理。 正向推理所得的中间结论恰好是逆向推理此时要求的证据 2、求解策略 推理是只求一个解还是求所有解以及最优解等 3、限制策略 对推理的深度、宽度、时间、空间等进行限制 4.1.3 推理的控制策略 4、冲突消解策略 在推理过程中,匹配会出现三种情况: 已知事实不能与知识库中的任何知识匹配成功 已知事实恰好只与知识库中的一个知识匹配成功 已知事实可与知识库中的多个知识匹配成功;或者有多个(组)已知事实都可与知识库中某一知识匹配成功;或者有多个(组)已知事实可与知识库中的多个知识匹配成功 4.1.3 推理的控制策略 4、冲突消解策略 出现冲突的情况 对正向推理而言,如果有多条产生式规则的前件都和已知的事实匹配成功;或者有多组不同的已知事实都与同一条产生式规则的前件匹配成功;或者两种情况同时出现 对逆向推理而言,如果有多条产生式的后件都和同一假设匹配成功,或者有多条产生式后件可与多个假设匹配成功。 4.1.3 推理的控制策略 冲突消解策略 按就近原则排序 该策略把最近被使用过的规则赋予较高的优先级。 按已知事实的新鲜性排序 一般我们认为新鲜事实是对旧知识的更新和改进,比老知识更有效,即后生成的事实比先生成的事实具有较大的优先性。 4.1.3 推理的控制策略 冲突消解策略 按匹配度排序 在不确定推理时,匹配度不仅可确定两个知识模式是否可匹配,还可用于冲突消解。根据匹配程度来决定哪一个产生式规则优先被应用。 按领域问题特点排序 该方法按照求解问题领域的特点将知识排成固定的次序 4.1.3 推理的控制策略 冲突消解策略 按上下文限制排序 该策略将知识按照所描述的上下文分成若干组,在推理过程中根据当前数据库中的已知事实与上下文的匹配情况,确定选择某组中的某条知识。 按条件个数排序 多条规则生成的结论相同的情况下,由于条件个数较少的规则匹配所花费的时间较少而且容易实现,所以将条件少的规则赋予较高的优先级,优先被启用。 4.1.3 推理的控制策略 冲突消解策略 按规则的次序排序 该策略是以知识库中预先存入规则的排列顺序作为知识排序的依据,排在前面的规则具有较高的优先级。 双重否定律(double negation law): ┓(┓P(x)) ≡P(x) 德·摩根定律(Mogen law): ┓(P(x))∨Q(x))≡ ┓P(x)∧ ┓Q(x) ┓(P(x))∧Q(x)) ≡ ┓P(x)∨ ┓Q(x) 逆否律(inverse-negation law): P(x) → Q(x) ≡ ┓Q(x) → ┓P(x) 分配律(assignment law): P(x)∧(Q(x)∨R(x))≡(P(x)∧Q(x))∨(P(x)∧R(x)) P(x)∨(Q(x)∧R(x))≡(P(x)∨Q(x))∧(P(x)∨R(x)) 结合律(association law): (P(x)∧Q(x))∧R(x)≡P(x)∧(Q(x)∧R(x)) (P(x)∨Q(x))∨R(x)≡P(x)∨(Q(x)∨R(x)) 蕴含等价式(implication law): P(x)→Q(x)≡┓P(x)∨Q(x) 易名规则(rename law): ?xP(x)∨?xQ(x)≡?x P(x)∨?yQ(y) 量词转换律(quantifier transform law): ┓?xP(x)≡?x┓P(x) ┓?xP(x)≡?x┓P(x) 量词分配律(quantifier assignment law): ?x(P(x)∨Q(x))≡?xP(x)∨?xQ(x) ?x(P(x)∧Q(x))≡?xP(x)∧?xQ(x) ?x(P→Q(x))≡P→?xQ(x) ?x(P→Q(x))≡P→?xQ(x) 量词交换律(quantifier commutative law): ?x?y(P(x, y))≡?y?x(P(x, y)) ?x?y(P(x, y) )≡?y?x(P(x, y)) ?x?y(P(x, y) )??y?x(P(x, y)) ?x?y(P(x, y) )??y?x(P(x, y)) 量词辖域变换等价式: ?xP(x)∨Q≡?x(P(x)∨Q) ?xP(x)∧Q≡?x(P(x)∨Q) ?xP(x)∧Q≡?x(P(x)∨Q) ?xP(x)∧Q≡?x(P(x)∨Q) Q中不含变量 全称量词消去规则: ?xP(x)≡P(y) 全称量词引入规则: P(y)≡?xP(x) 存在量词消去规则: ?xQ(x)≡Q(c)(c为常量) 存在量词引人规则: Q(c)≡?xQ(x) 有限域量词消去规则:设有限个体域为D?d1,d2,…,dn ?xP(x)≡P(d1)∧P(d2),……,∧P(dn) ?xQ(x)≡Q(d1) ∨Q(d2),……,∨Q(dn) 4.4.4 用归结反演求取问题的答案 (1/4) 归结原理出了可用于定理证明外,还可用来求取问题答案,其思想与定理证明相似。其一般步骤为: (1) 把问题的已知条件用谓词公式表示出来,并化为相应的子句集; (2) 把问题的目标的否定用谓词公式表示出来,并化为子句集; (3) 对目标否定子句集中的每个子句,构造该子句的重言式(即把该目标否定子句和此目标否定子句的否定之间再进行析取所得到的子句),用这些重言式代替相应的目标否定子句式,并把这些重言式加入到前提子句集中,得到一个新的子句集; (4) 对这个新的子句集,应用归结原理求出其证明树,这时证明树的根子句不为空,称这个证明树为修改的证明树; (5) 用修改的证明树的根子句作为回答语句,则答案就在此根子句中。 下面再通过一个例子来说明如何求取问题的答案。 例4.24 已知:“张和李是同班同学,如果x和y是同班同学,则x的教室也是y的教室,现在张在302教室上课。” 问:“现在李在哪个教室上课?” 解:首先定义谓词: C(x, y) x和y是同班同学; At(x, u) x在u教室上课。 把已知前提用谓词公式表示如下: C(zhang, li) (?x) (?y) (?u) (C(x, y)∧At(x, u)→At(y,u)) At(zhang, 302) 把目标的否定用谓词公式表示如下: ﹁(?v)At(li, v) 4.4.4 用归结反演求取问题的答案 (2/4) 把上述公式化为子句集: C(zhang, li) ﹁C(x, y)∨﹁At(x, u)∨At(y, u) At(zhang, 302) 把目标的否定化成子句式,并用重言式 ﹁At(li,v) ∨At(li,v) 代替之。 把此重言式加入前提子句集中,得到一个新的子句集,对这个新的子句集,应用归结原理求出其证明树。其求解过程如下图所示。 该证明树的根子句就是所求的答案,即“李明在302教室”。 4.4.4 用归结反演求取问题的答案 (3/4) ﹁At(li,v)∨At(li,v) ﹁C(x, y)∨﹁At(x, u)∨At(y, u) At(li,v)∨﹁ C(x, li)∨﹁At(x, v) C(zhang, li) ﹁ At(zhang,v)∨At(li, v) At(zhang, 302) At(li, 302) {li/y,v/u} {Zhang/x} {302/v} 4.4.4 用归结反演求取问题的答案 (4/4) 习题: 习题4: 4.5 4.6 对以上讨论做以下两点说明: (1) 这里之所以使用集合符号和集合的运算,目的是为了说明问题的方便。 即先将子句Ciσ和Liσ写成集合的形式,在集合表示下做减法和并集运算,然后再写成子句集的形式。 (2) 定义中还要求C1和C2无公共变元,这也是合理的。 例如C1=P(x),C2=﹁P(f(x)),而S={ C1, C2}是不可满足的。但由于C1和C2的变元相同,就无法合一了。没有归结式,就不能用归结法证明S的不可满足性,这就限制了归结法的使用范围。 如果对C1或C2的变元进行换名,便可通过合一,对C1和C2进行归结。如上例,若先对C2进行换名,即C2=﹁P(f(y)),则可对C1和C2进行归结,得到一个空子句,从而证明了S是不可满足的。 事实上,在由公式集化为子句集的过程中,其最后一步就是做换名处理。因此,定义中假设C1和C2没有相同变元是可以的。 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(5/20) 再看几个归结例子: 例4.13 设C1=P(x)∨﹁Q(b),C2=﹁P(a)∨Q(y)∨R(z) 解:对C1和C2通过最一般合一(σ={a/x, b/y})的作用,可以得到两个互补对。 注意: 求归结式不能同时消去两个互补对,这样的结果不是二元归结式。如在σ={a/x, b/y}下,若同时消去两个互补对,所得的R(z)不是C1和C2的二元归结式。 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(6/20) 例4.14 设C1=P(x)∨P(f(a))∨Q(x) ,C2=﹁P(y)∨R(b),求C12 解:对参加归结的某个子句,若其内部有可合一的文字,则在进行归结之前应先对这些文字进行合一。本例的C1中有可合一的文字P(x)与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σ称为C1的因子。一般来说,若子句C中有两个或两个以上的文字具有最一般合一σ,则称Cσ为子句C的因子。如果Cσ是一个单文字,则称它为C的单元因子。 应用因子概念,可对谓词逻辑中的归结原理给出如下定义: 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(7/20) 谓词逻辑中的二元归结原理(应用因子的概念) 定义4.21 若C1和C2是无公共变元的子句,则 ① C1和C2的二元归结式; ② C1和C2的因子C2σ2的二元归结式; ③ C1的因子C1σ1和C2的二元归结式; ④ C1的因子C1σ1和C2的因子C2σ2的二元归结式。 这四种二元归结式都是子句C1和C2的二元归结式,记为C12。 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(8/20) 例4.15 设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)) 对C1的因子和C2归结(σ={g(a)/x }),可得到C1和C2的二元归结式 C12=Q(g(g(a)))∨Q(b) 说明: 对谓词逻辑,定理4.3仍然适用,即归结式C12是其亲本子句C1和C2的逻辑结论。用归结式取代它在子句集S中的亲本子句,所得到的子句集仍然保持着原子句集S的不可满足性。 此外,对谓词逻辑定理4.4也仍然适用,即从不可满足的意义上说,一阶谓词逻辑的归结原理也是完备的 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(9/20) 谓词逻辑的归结反演步骤: 谓词逻辑的归结反演过程与命题逻辑的归结反演过程相比,其步骤基本相同,但每步的处理对象不同。例如,在步骤(3)化简子句集时,谓词逻辑需要把由谓词构成的公式集化为子句集;在步骤(4)按归结原理进行归结时,谓词逻辑的归结原理需要考虑两个亲本子句的最一般合一。 例4.16 已知 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的逻辑结论。 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(10/20) 证明:先把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}化成子句集,得到 (1) ﹁A(x,y)∨﹁ B(y) ∨C(f(x)) (2) ﹁ A(u,v)∨﹁ B(v) ∨D(u,f(u)) (3) ﹁ C(z) (4) A(m,n) (5) B(k) 其中,(1)、(2)是由F 化出的两个子句,(3)、(4)、(5)是由﹁G化出的3个子句。 最后应用谓词逻辑的归结原理对上述子句集进行归结,其过程为 (6) ﹁ A(x,y)∨ ﹁ B(y) 由(1)和(3)归结,取σ={f(x)/z} (7) ﹁ B(n) 由(4)和(6)归结,取σ={m/x,n/y} (8) NIL 由(5)和(7)归结,取σ={n/k} 因此,G是F 的逻辑结论。 上述归结过程可用如下归结树来表示 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(11/20) ﹁A(x,y)∨﹁ B(y)∨C(f(x)) ﹁ C(z) ﹁A(x,y)∨﹁ B(y) A(m,n) ﹁ B(n) B(k) NIL {f(x)/z} {m/x,n/y} {n/k} 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(12/20) 为了进一步加深对谓词逻辑归结的理解,下面再给出一个经典的归结问题 例4.17 “快乐学生”问题 假设:任何通过计算机考试并获奖的人都是快乐的,任何肯学习或幸运的人都可以通过所有考试,张不肯学习但他是幸运的,任何幸运的人都能获奖。 求证:张是快乐的。 解:先定义谓词: Pass(x, y) x可以通过y考试 Win(x, prize) x能获得奖励 Study(x) x肯学习 Happy(x) x是快乐的 Lucky(x) x是幸运的 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(13/20) 再将问题用谓词表示如下: “任何通过计算机考试并奖的人都是快乐的” (?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)) 结论“张是快乐的”的否定 ﹁Happy(zhang) 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(14/20) 将上述谓词公式转化为子句集如下: (1) ﹁Pass(x, computer)∨﹁Win(x, prize)∨Happy(x) (2) ﹁Study(y)∨Pass(y, z) (3) ﹁Lucky(u)∨Pass(u, v) (4) ﹁Study(zhang) (5) Lucky(zhang) (6) ﹁Lucky(w)∨Win(w, prize) (7) ﹁ Happy(zhang) (结论的否定) 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(15/20) 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(16/20) ﹁Pass(x, computer)∨﹁Win(x, prize)∨Happy(x) ﹁Lucky(w)∨Win(w, prize) ﹁Pass(w, Computer)∨Happy(w) ∨﹁Lucky(w) ﹁ Happy(zhang) Lucky(zhang) ﹁Pass(zhang, Computer)∨﹁Lucky(zhang) ﹁Pass(zhang, Computer) ﹁Lucky(u)∨Pass(u, v) ﹁Lucky(zhang) Lucky(zhang) NIL {w/x} {zhang/w} {zhang/u, computer/v} 为了进一步加深对谓词逻辑归结的理解,下面再给出一个经典的归结问题 例4.18 “激动人心的生活”问题 假设:所有不贫穷并且聪明的人都是快乐的,那些看书的人是聪明的。李明能看书且不贫穷,快乐的人过着激动人心的生活。 求证:李明过着激动人心的生活。 解:先定义谓词: Poor(x) x是贫穷的 Smart(x) x是聪明的 Happy(x) x是快乐的 Read(x) x能看书 Exciting(x) x过着激动人心的生活 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(17/20) 再将问题用谓词表示如下: “所有不贫穷并且聪明的人都是快乐的” (?x)((﹁Poor(x)∧Smart(x))→Happy(x)) “那些看书的人是聪明的” (?y) (Read(y) → Smart(y)) “李明能看书且不贫穷” Read(Liming)∧﹁Poor(Liming) “快乐的人过着激动人心的生活” (?z) (Happy(z)→Exciting(z)) 目标“李明过着激动人心的生活”的否定 ﹁Exciting(Liming) 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(18/20) 将上述谓词公式转化为子句集如下: (1) Poor(x)∨﹁Smart(x)∨Happy(x) (2) ﹁Read(y)∨Smart(y) (3) Read(Liming) (4) ﹁Poor(Liming) (5) ﹁Happy(z)∨Exciting(z) (6) ﹁Exciting(Liming) (结论的否定) 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(19/20) 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(20/20) ﹁Exciting(Liming) ﹁Happy(z)∨Exciting(z) ﹁Happy(Liming) Poor(x))∨﹁Smart(x)∨Happy(x) Poor(Liming)∨﹁Smart(Liming) ﹁Read(y)∨Smart(y ) Poor(Liming)∨﹁Read(Liming) ﹁Poor(Liming) ﹁Read(Liming) Read(Liming) NIL {Liming/z} {Liming/x} {Liming/y} 4.4.3 归结演绎推理的归结策略 归结演绎推理实际上就是从子句集中不断寻找可进行归结的子句对,并通过对这些子句对的归结,最终得出一个空子句的过程。由于事先并不知道哪些子句对可进行归结,更不知道通过对哪些子句对的归结能尽快得到空子句,因此就需要对子句集中的所有子句逐对进行比较,直到得出空子句为止。这种盲目的全面进行归结的方法,不仅会产生许多无用的归结式,更严重的是会产生组核爆炸问题。因此,需要研究有效的归结策略来解决这些问题。 目前,常用的归结策略可分为两大类,一类是删除策略,另一类是限制策略。删除策略是通过删除某些无用的子句来缩小归结范围;限制策略是通过对参加归结的子句进行某些限制,来减少归结的盲目性,以尽快得到空子句。为了说明选择归结策略的重要性,在讨论各种常用的归结策略之前,还是先提一下广度优先策略。 4.4.3 归结演绎推理的归结策略 1. 广度优先策略(1/3) 广度优先是一种穷尽子句比较的复杂搜索方法。设初始子句集为S0,广度优先策略的归结过程可描述如下: (1) 从S0出发,对S0中的全部子句作所有可能的归结,得到第一层归结式,把这些归结式的集合记为S1; (2) 用S0中的子句与S1中的子句进行所有可能的归结,得到第二层归结式,把这些归结式的集合记为S2; (3) 用S0和S1中的子句与S2中的子句进行所有可能的归结,得到第三层归结式,把这些归结式的集合记为S3; 如此继续,直到得出空子句或不能再继续归结为止。 例4.19 设有如下子句集: S={﹁I(x)∨R(x), I(a), ﹁R(y)∨L(y), ﹁L(a) } 用宽度优先策略证明S为不可满足。 宽度优先策略的归结树如下: ﹁ I(x)∨R(x) I(a) ﹁R(y)∨L(y) ﹁L(a) R(a) ﹁I(x) ∨L(x) ﹁R(a) L(a) L(a) ﹁I(a) ﹁I(a) NIL S S1 S2 4.4.3 归结演绎推理的归结策略 1. 广度优先策略(2/3) 从这个例子可以看出,宽度优先策略归结出了许多无用的子句,既浪费事间,又浪费空间。但是,这种策略由一个有趣的特性,就是当问题有解时保证能找到最短归结路径。 因此,它是一种完备的归结策略。宽度优先对大问题的归结容易产生组合爆炸,但对小问题却仍是一种比较好的归结策略。 4.4.3 归结演绎推理的归结策略 1. 广度优先策略(3/3) 4.4.3 归结演绎推理的归结策略 2. 支持集策略(1/3) 支持集策略是沃斯(Wos)等人在1965年提出的一种归结策略。它要求每一次参加归结的两个亲本子句中,至少应该有一个是由目标公式的否定所得到的子句或它们的后裔。可以证明支持集策略是完备的,即当子句集为不可满足时,则由支持集策略一定能够归结出一个空子句。也可以把支持集策略看成是在宽度优先策略中引入了某种限制条件,这种限制条件代表一种启发信息,因而有较高的效率 例4.20 设有如下子句集: S={﹁I(x)∨R(x), I(a),﹁ R(y)∨L(y), ﹁L(a) } 其中,﹁I(x)∨R(x)为目标公式的否定。用支持集策略证明S为不可满足。 ﹁I(x)∨R(x) I(a) ﹁ R(y)∨L(y) ﹁L(a) R(a) ﹁I(x)∨L(x) L(a) L(a) ﹁I(a) NIL 4.4.3 归结演绎推理的归结策略 2. 支持集策略(2/3) 从上述归结过程可以看出,各级归结式数目要比宽度优先策略生成的少,但在第二级还没有空子句。就是说这种策略限制了子句集元素的剧增,但会增加空子句所在的深度。此外,支持集策略具有逆向推理的含义,由于进行归结的亲本子句中至少有一个与目标子句有关,因此推理过程可以看作是沿目标、子目标的方向前进的。 4.4.3 归结演绎推理的归结策略 2. 支持集策略(3/3) 4.4.5 归结演绎推理的归结策略 3. 删除策略(1/3) 主要想法是:归结过程在寻找可归结子句时,子句集中的子句越多,需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉,这就会缩小搜索范围,减少比较次数,从而提高归结效率。 常用的删除方法有以下几种(纯文字、重言式、包孕) 纯文字删除法 如果某文字L在子句集中不存在可与其互补的文字﹁L,则称该文字为纯文字。 在归结过程中,纯文字不可能被消除,用包含纯文字的子句进行归结也不可能得到空子句,因此对包含纯文字的子句进行归结是没有意义的,应该把它从子句集中删除。 对子句集而言,删除包含纯文字的子句,是不影响其不可满足性的。例如,对子句集 S={P∨Q∨R, ﹁Q∨R, Q, ﹁R} 其中P是纯文字,因此可以将子句P∨Q∨R从子句集S中删除。 重言式删除法 如果一个子句中包含有互补的文字对,则称该子句为重言式。例如 P(x)∨﹁P(x), P(x)∨Q(x)∨﹁P(x) 都是重言式,不管P(x)的真值为真还是为假,P(x)∨﹁P(x)和P(x)∨Q(x)∨﹁P(x)都均为真。 重言式是真值为真的子句。对一个子句集来说,不管是增加还是删除一个真值为真的子句,都不会影响该子句集的不可满足性。 因此,可从子句集中删去重言式。 4.4.5 归结演绎推理的归结策略 3. 删除策略(2/3) 包孕删除法 设有子句C1和C2,如果存在一个置换σ,使得C1σ?C2,则称C1包孕于C2。例如 P(x) 包孕于 P(y)∨Q(z) σ={x/y} P(x) 包孕于 P(a) σ={a/x} P(x) 包孕于 P(a)∨Q(z) σ={a/x} P(x) ∨Q(a) 包孕于 P(f(a))∨Q(a)∨R(y) σ={f(a)/x} P(x) ∨Q(y) 包孕于 P(a)∨Q(u)∨R(w) σ={a/x, u/y} 对子句集来说,把其中包孕的子句删去后,不会影响该子句集的不可满足性。 因此,可从子句集中删除哪些包孕的子句。 4.4.5 归结演绎推理的归结策略 3. 删除策略(3/3) 4.4.3 归结演绎推理的归结策略 4. 单文字子句策略(1/2) 如果一个子句只包含一个文字,则称此子句为单文字子句。单文字子句策略是对支持集策略的进一步改进,它要求每次参加归结的两个亲本子句中至少有一个子句是单文字子句。 例4.21 设有如下子句集: S={﹁I(x)∨R(x), I(a), ﹁R(y)∨L(y), ﹁L(a) } 用单文字子句策略证明S为不可满足。 采用单文字子句策略,归结式包含的文字数将少于其亲本子句中的文字数,这将有利于向空子句的方向发展,因此会有较高的归结效率。但这种策略是不完备的,即当子句集为不可满足时,用这种策略不一定能归结出空子句。 ﹁I(x)∨R(x) I(a) ﹁R(y)∨L(y) ﹁L(a) R(a) ﹁R(a) NIL 4.4.3 归结演绎推理的归结策略 4. 单文字子句策略(2/2) 4.4.3 归结演绎推理的归结策略 5. 线) 这种策略要求每次参加归结的两个亲本子句中,至少应该有一个是初始子句集中的子句。所谓初始子句集是指开始归结时所使用的子句集。 例4.22 设有如下子句集: S={﹁I(x)∨R(x), I(a), ﹁R(y)∨L(y), ﹁L(a) } 用线性输入策略证明S为不可满足。 线性输入策略可限制生成归结式的数目,具有简单和高效的优点。但是,这种策略也是一种不完备的策略。例如,子句集 S={Q(u)∨P(a), ﹁Q(w)∨P(w), ﹁Q(x)∨﹁ P(x), Q(y)∨﹁ P(y)} 从S出发很容易找到一棵归结反演树,但却不存在线性输入策略的归结反演树。 ﹁I(x)∨R(x) I(a) ﹁R(y)∨L(y) ﹁L(a) R(a) ﹁I(x)∨L(x) ﹁ R(a) ﹁I(a) L(a) L(a) ﹁I(a) NIL 4.4.3 归结演绎推理的归结策略 5. 线 归结演绎推理的归结策略 6. 祖先过滤策略(1/2) 这种策略与线性输入策略有点相似,但是,放宽了对子句的限制。每次参加归结的两个亲本子句,只要满足以下两个条件中的任意一个就可进行归结: (1) 两个亲本子句中至少有一个是初始子句集中的子句。 (2) 如果两个亲本子句都不是初始子句集中的子句,则一个子句应该是另一个子句的先辈子句。所谓一个子句(例如C1)是另一个子句(例如C2)的先辈子句是指C2是由C1与别的子句归结后得到的归结式。 例4.23 设有如下子句集: S={﹁Q(x)∨﹁P(x), Q(y)∨﹁P(y),﹁Q(w)∨P(w) , Q(a)∨P(a) } 用祖先过滤策略证明S为不可满足 证明:从S出发,按祖先过滤策略归结过程如下图所示。 可以证明祖先过滤策略也是完备的。 上面分别讨论了几种基本的归结策略,但在实际应用中,还可以把几种策略结合起来使用。总之,在选择归结反演策略时,主要应考虑其完备性和效率问题。 ﹁Q(x)∨ ﹁P(x) Q(y)∨﹁P(y) ﹁ P(x) ﹁ Q(w)∨P(w) ﹁ Q(w) Q(a)∨P(a) P(a) NIL 4.4.3 归结演绎推理的归结策略 6. 祖先过滤策略(2/2) 4.3 自然演绎推理 例4.6 设已知如下事实: (1) 只要是需要编程序的课,王程都喜欢。 (2) 所有的程序设计语言课都是需要编程序的课。 (3) C是一门程序设计语言课。 求证:王程喜欢C这门课。 应用推理规则进行推理: Lang(y)→Prog(y) 全称固化 Lang(C),Lang(y)→Prog(y)? Prog(C) 假言推理 {C/y} Prog(C),Prog(x)→Like(Wang,x)?Like(Wang,C) 假言推理 {C/x} 因此,王程喜欢C这门课。 4.3 自然演绎推理 优点:定理证明过程自然,易于理解,并且有丰富的推理规则可用。 缺点:是容易产生知识爆炸,推理过程中得到的中间结论一般按指数规律递增,对于复杂问题的推理不利,甚至难以实现。 第4章 确定性推理 4.1 推理的基本概念 4.2 推理的逻辑基础 4.3 自然演绎推理 4.4 归结演绎推理 4.4 归结演绎推理 归结演绎推理是一种基于鲁宾逊(Robinson)归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理,是鲁宾逊于1965年在海伯伦(Herbrand)理论的基础上提出的一种基于逻辑的“反证法”。 在人工智能中,几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质,就是要对前提P和结论Q,证明P→Q永线节可知,要证明P→Q永真,就是要证明P→Q在任何一个非空的个体域上都是永真的。这将是非常困难的,甚至是不可实现的。 为此,人们进行了大量的探索,后来发现可以采用反证法的思想,把关于永真性的证明转化为关于不可满足性的证明。 即要证明P→Q永真,只要能够证明P∧﹁Q是不可满足的就可以了(原因是﹁ (P→Q) ? ﹁(﹁ P∨Q) ? P∧﹁ Q 。 这方面最有成效的工作就是鲁宾逊归结原理。它使定理证明的机械化成为现实。 4.4 归结演绎推理 4.4.1 子句集及其化简 4.4.2 鲁滨逊归结原理 4.4.3 归结反演推理的归结策略 4.4.4 用归结反演求取问题的答案 4.4.1 子句型 定义4.11 原子谓词公式及其否定统称为文字。 例如,P(x)、Q(x)、﹁ P(x)、 ﹁ Q(x)等都是文字。 定义4.12 任何文字的析取式称为子句。 例如,P(x)∨Q(x),P(x,f(x))∨Q(x,g(x))都是子句。 定义4.13 不含任何文字的子句称为空子句。 由于空子句不含有任何文字,也就不能被任何解释所满足,因此空子句是永假的,不可满足的。 空子句一般被记为□或NIL。 定义4.14 由子句或空子句所构成的集合称为子句集。 1. 子句与子句集 在谓词逻辑中,任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。其化简步骤如下: (1) 消去连接词“→”和“?” 反复使用如下等价公式: P→Q ?﹁ P∨Q P?Q ? (P∧Q)∨(﹁P∧﹁Q) 即可消去谓词公式中的连接词“→”和“?”。 例如公式 (?x)((?y)P(x,y)→﹁ (?y)(Q(x,y)→R(x,y))) 经等价变化后为 (?x)(﹁(?y)P(x,y)∨﹁ (?y)(﹁Q(x,y)∨R(x,y))) 4.4.1 子句型 2. 子句集的化简(1/6) (2) 减少否定符号的辖域 反复使用双重否定率 ﹁(﹁P) ? P 摩根定律 ﹁(P∧Q) ?﹁P∨﹁Q ﹁(P∨Q) ?﹁P∧﹁Q 量词转换率 ﹁ (?x)P(x) ? (?x) ﹁P(x) ﹁ (?x)P(x) ? (?x)¬P(x) 将每个否定符号“﹁”移到仅靠谓词的位置,使得每个否定符号最多只作用于一个谓词上。 例如,上式经等价变换后为 (?x)((?y)﹁P(x,y)∨(?y)( Q(x,y) ∧﹁R(x,y))) 2. 子句集的化简(2/6) 4.4.1 子句型 (3) 对变元标准化 在一个量词的辖域内,把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替,使不同量词约束的变元有不同的名字。 例如,上式经变换后为 (?x)((?y)﹁P(x, y)∨(?z)( Q(x,z) ∧﹁R(x, z))) (4) 化为前束范式 化为前束范式的方法:把所有量词都移到公式的左边,并且在移动时不能改变其相对顺序。由于第(3)步已对变元进行了标准化,每个量词都有自己的变元,这就消除了任何由变元引起冲突的可能,因此这种移动是可行的。 例如,上式化为前束范式后为 (?x)(?y) (?z)(﹁P(x, y)∨( Q(x, z) ∧﹁R(x, z))) 2. 子句集的化简(3/6) 4.4.1 子句型 (5) 消去存在量词 消去存在量词时,需要区分以下两种情况: 若存在量词不出现在全称量词的辖域内(即它的左边没有全称量词),只要用一个新的个体常量替换受该存在量词约束的变元,就可消去该存在量词。 若存在量词位于一个或多个全称量词的辖域内,例如 (?x1)…(?xn) (?y)P(x1,x2 ,…, xn ,y) 则需要用Skolem函数f(x1,x2 ,…, xn)替换受该存在量词约束的变元y,然后再消去该存在量词。 例如,上步所得公式中存在量词(?y)和(?z)都位于(?x)的辖域内,因此都需要用Skolem函数来替换。设替换y和z的Skolem函数分别是f(x)和g(x),则替换后的式子为 (?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x)))) 4.4.1 子句型 2. 子句集的化简(4/6) (6) 化为Skolem标准形 Skolem标准形的一般形式为 (?x1)…(?xn) M(x1,x2,……,xn) 其中, M(x1,x2,……,xn)是Skolem标准形的母式,它由子句的合取所构成。 把谓词公式化为Skolem标准形需要使用以下等价关系 P∨(Q∧R) ? (P∨Q)∧(P∨R) 例如,前面的公式化为Skolem标准形后为 (?x)((﹁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(x,f(x))∨﹁R(x,g(x))) 4.4.1 子句型 2. 子句集的化简(5/6) (8) 消去合取词 在母式中消去所有合取词,把母式用子句集的形式表示出来。其中,子句集中的每一个元素都是一个子句。 例如,上式的子句集中包含以下两个子句 ﹁P(x,f(x))∨Q(x,g(x)) ﹁P(x,f(x))∨﹁R(x,g(x)) (9) 更换变量名称 对子句集中的某些变量重新命名,使任意两个子句中不出现相同的变量名。由于每一个子句都对应着母式中的一个合取元,并且所有变元都是由全称量词量化的,因此任意两个不同子句的变量之间实际上不存在任何关系。这样,更换变量名是不会影响公式的真值的。 例如,对前面的公式,可把第二个子句集中的变元名x更换为y,得到如下子句集 ﹁P(x,f(x))∨Q(x,g(x)) ﹁P(y,f(y))∨﹁R(y,g(y)) 4.4.1 子句型 2. 子句集的化简(6/6) 例4.7 将合式公式化为子句形。 解:(1)消去蕴涵符号: 这可以利用等价式: 得到: ?x[(~P(x)?[?y[~P(y) ?P(f(x,y))]?~?y[~Q(x,y) ?P(y)]]] (2)减少否定符号的辖域,把“ ”移到紧 靠谓词的位置上: 这可以利用下述等价式: 例题分析 得到: ?x[(~P(x)?[?y[~P(y) ?P(f(x,y))]??y[Q(x,y) ?~P(y)]]] (3)变量标准化:重新命名变元名,使不同量词约束的变元有不同的名字: ?x[~P(x)?[?y[~P(y)?P(f(x,y))]??w[Q(x,w) ?~P(w)]]] (4)消去存在量词: ?x[~P(x)?[?y[~P(y)?P(f(x,y))]?[Q(x,g(x)) ?~P(g(x))]]] (5)化为前束形: ?x?y[~P(x)?[ [~P(y)?P(f(x,y))]?[Q(x,g(x))?~P(g(x))]]] (6)把母式化为合取范式: ?x ?y[~P(x)? ~P(y)?P(f(x,y))]?[~P(x)? Q(x,g(x))] ? [~P(x)? ~P(g(x))] (7)消去全称量词和合取连接词: [~P(x)? ~P(y)?P(f(x,y))] [~P(x)? Q(x,g(x))] [~P(x)? ~P(g(x))] (8)更改变量名,有时称为变量分离标准化。于是有: 必须指出: 一个子句内的文字可以含有变量,但这些变量总是被理解为全称量词量化了的变量。 在上述化简过程中,由于在消去存在量词时所用的Skolem函数可以不同,因此化简后的标准子句集是不唯一的。 这样,当原谓词公式为非永假时,它与其标准子句集并不等价。但当原谓词公式为永假(或不可满足)时,其标准子句集则一定是永假的,即Skolem化并不影响原谓词公式的永假性。 这个结论很重要,是归结原理的主要依据,可用定理的形式来描述。 定理4.1 设有谓词公式F,其标准子句集为S,则F为不可满足的充要条件是S为不可满足的。 3. 子句集的应用 4.4.1 子句型 作业: 习题:4.4 4.4.2 鲁滨逊归结原理 首先注意以下两个关键问题: 第一,子句集中的子句之间是合取关系。因此,子句集中只要有一个子句为不可满足,则整个子句集就是不可满足的; 第二,空子句是不可满足的。因此,一个子句集中如果包含有空子句,则此子句集就一定是不可满足的。 鲁滨逊归结原理基本思想 首先把欲证明问题的结论否定,并加入子句集,得到一个扩充的子句集S。然后设法检验子句集S是否含有空子句,若含有空子句,则表明S是不可满足的;若不含有空子句,则继续使用归结法,在子句集中选择合适的子句进行归结,直至导出空子句或不能继续归结为止。 鲁滨逊归结原理包括 命题逻辑归结原理 谓词逻辑归结原理 4.4.2 鲁滨逊归结原理 1. 基本思想 (1) 归结式的定义及性质 定义4.15 若P是原子谓词公式,则称P与﹁P为互补文字。 定义4.16 设C1和C2是子句集中的任意两个子句,如果C1中的文字L1与C2中的文字L2互补,那么可从C1和C2中分别消去L1和L2,并将C1和C2中余下的部分按析取关系构成一个新的子句C12,则称这一过程为归结,称C12为C1和C2的归结式,称C1和C2为C12的亲本子句。 例4.7 设C1=P∨Q∨R,C2=﹁P∨S,求C1和C2的归结式C12。 解:这里L1=P,L2=﹁P,通过归结可以得到 C12= Q∨R∨S 4.4.2 鲁滨逊归结原理 2. 命题逻辑的归结(1/8) (1) 归结式的定义及性质 定理4.3 归结式C12其亲本子句C1和C2的逻辑结论。 这个定理是归结原理中一个重要定理,由它可得到如下两个推论: 推论1:设C1和C2是子句集S中的两个子句, C12 是C1和C2的的归结式,若用C12代替C1和C2后得到新的子句集S1,则由S1的不可满足性可以推出原子句集S的不可满足性。即: S1的不可满足性 ? S的不可满足性 4.4.2 鲁滨逊归结原理 2. 命题逻辑的归结(2/8) (1) 归结式的定义及性质 定理4.3 归结式C12其亲本子句C1和C2的逻辑结论。 这个定理是归结原理中一个重要定理,由它可得到如下两个推论: 推论2:设C1和C2是子句集S中的两个子句, C12 是C1和C2的的归结式,若把C12加入S中得到新的子句集S2,则S与S2的不可满足性是等价的。即: S2的不可满足性 ? S的不可满足性 4.4.2 鲁滨逊归结原理 2. 命题逻辑的归结(3/8) 由此得到下列结论: ⑴ 为证明子句集S的不可满足性,只要对其中可进行归结的子句进行归结,并把归结式加入到子句集S中;或者用归结式代替它的亲本子句,然后对新的子句集证明其不可满足性就可以了。 ⑵ 如果经归结得到空子句,根据空子句的不可满足性,即可得到原子句集S是不可满足的结论。 在命题逻辑中,对不可满足的子句集S,其归结原理是完备的。 这种不可满足性可用如下定理描述: 定理4.4 子句集S是不可满足的,当且仅当存在一个从S到空子句的归结过程。 4.4.2 鲁滨逊归结原理 2. 命题逻辑的归结(4/8) 例4.9 设设C1 =﹁P ∨ Q ,C2=﹁Q,C3=P,求C1、C2、C3的归结式C123。 解:若先对C1、C2归结,可得到 C12=﹁P 然后再对C12和C3归结,得到 C123=NIL 如果改变归结顺序,同样可以得到相同的结果,即其归结过程是不唯一的。 其归结归结过程可用右图来表示,该树称为归结树。 ﹁P ∨ Q ﹁Q ﹁P P NIL ﹁P ∨ Q P Q ﹁Q NIL 4.4.2 鲁滨逊归结原理 2. 命题逻辑的归结(5/8) (2) 命题逻辑的归结反演 归结原理:假设F为已知前提,G为欲证明的结论,归结原理把证明G为F的逻辑结论转化为证明F∧﹁G为不可满足。 再根据定理4.3,在不可满足的意义上,公式集F∧﹁G与其子句集是等价的,即把公式集上的不可满足转化为子句集上的不可满足。 应用归结原理证明定理的过程称为归结反演。 4.4.2 鲁滨逊归结原理 2. 命题逻辑的归结(6/8) 命题逻辑归结反演的步骤: 在命题逻辑中,已知F,证明G为真的归结反演过程如下: ①否定目标公式G,得﹁G; ②把﹁G并入到公式集F中,得到{F,﹁G}; ③把{F,﹁G}化为子句集S。 ④ 应用归结原理对子句集S中的子句进行归结,并把每次得到的归结式并入S中。如此反复进行,若出现空子句,则停止归结,此时就证明了G为线 设已知的公式集为: {P, (P∧Q)→R, (S∨T)→Q, T} 求证结论R。 解:假设结论R为假, 将﹁R加入公式集,并化为子句集 S={P,﹁P∨﹁Q∨R, ﹁S∨Q, ﹁T∨Q, T, ﹁R} 其归结过程如右图的归结演绎树所示。该树根为空子句。 其含义为:先假设子句集S中的所有子句均为真,即原公式集为真,﹁R也为真;然后利用归结原理,对子句集进行归结,并把所得的归结式并入子句集中;重复这一过程,最后归结出了空子句。 根据归结原理的完备性,可知子句集S是不可满足的,即开始时假设﹁R为真是错误的,这就证明了R为真。 ﹁P ∨﹁Q∨R ﹁ R ﹁P ∨﹁Q P ﹁Q ﹁T ∨Q ﹁T T NIL 4.4.2 鲁滨逊归结原理 2. 命题逻辑的归结(8/8) 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(1/20) 在谓词逻辑中,由于子句集中的谓词一般都含有变元,因此不能象命题逻辑那样直接消去互补文字。而需要先用一个最一般合一(MGU) 对变元进行代换,然后才能进行归结。 可见,谓词逻辑的归结要比命题逻辑的归结麻烦一些。 谓词逻辑的归结原理: 谓词逻辑中的归结式可用如下定义来描述: 定义4.17 设C1和C2是两个没有公共变元的子句,L1和L2分别是C1和C2中的文字。如果L1和L2存在最一般合一σ,则称 C12=({C1σ}-{ L1σ})∪({ C2σ}-{ L2σ}) 为C1和C2的二元归结式,而L1和L2为归结式上的文字。 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(2/20) 谓词逻辑归结举例: 例4.11 设C1=P(a)∨R(x),C2=﹁P(y)∨Q(b),求 C12 解:取L1= P(a), L2=﹁P(y),则L1和L2的最一般合一是σ={a/y}。根据定义3.20,可得 C12=( {C1σ}-{L1σ}) ∪ ({C2σ}-{L2σ}) =({P(a), R(x)}-{P(a)})∪({﹁P(a), Q(b)}-{﹁P(a)}) =({R(x)})∪({Q(b)})= {R(x), Q(b)} =R(x)∨Q(b) 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(3/20) 谓词逻辑归结举例: 例4.12 设C1=P(x)∨Q(a),C2=﹁P(b)∨R(x) ,求 C12 解:由于C1和C2有相同的变元x,不符合定义4.17的要求。为了进行归结,需要修改C2中变元x的名字为,令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) 4.4.2 鲁滨逊归结原理 3. 谓词逻辑的归结(4/20) 4.2.1 谓词与个体 一元谓词:一个谓词,可以与一个个体相关联,这种谓词称作一元谓词,它刻画了个体的性质。 多元谓词:一个谓词,可以与多个个体相关联,这种谓词称作多元谓词,它刻画了个体间的关系。 谓词的一般形式可表示为: P(x1,x2, …,xn) 其中P是谓词,而x1,x2, …,xn是个体。谓词通常用大写字母表示,个体通常用小写字母表示。 4.2.1 谓词与个体 注意事项: 谓词的项:在谓词中,个体可以是常量,也可以是变量,还可以是一个函数。例如:“小刘的哥哥是个个人”,可以表示为worker(brother(Liu)),其中brother(Liu)是一个函数。个体常量、变量和函数统称为项。 谓词的语义:由使用者根据需要人为地定义。 谓词的元数:谓词中包含的个体变量的数目称为谓词的元数。 4.2.1 谓词与个体 注意事项: 谓词的阶数:在谓词P(x1,x2, …,xn)中,若xi(i=1,2, …,n)都是个体常量、变量或函数,则称它为一阶谓词。若某个xi本身又是一个一阶谓词,则称它为二阶谓词,依次类推。 谓词与函数的区别:谓词具有逻辑值“真”或“假”,而函数则是某个个体到另一个个体(数学上:自变量到因变量)之间的映射。 4.2.2 谓词公式的永线 设D是谓词公式P的非空个体域,若对P中的个体常量、函数和谓词按如下规定赋值: (1) 为每个个体常量指派D中的一个元素; (2) 为每个n元函数指派一个从Dn到D的一个映射,其中 Dn ={(x1, x2, …, xn) x1, x2, …, xn∈D} (3) 为每个n元谓词指派一个从Dn到{F,T}的映射。 则称这些指派为P在D上的一个解释。 1、谓词公式的解释 例4.1 设个体域D={1, 2},求公式A=(?x)(?y)P(x, y)在D上的解释,并指出在每一种解释下公式A的真值。 解:由于公式A中没有包含个体常量和函数,故可直接为谓词指派真值,设有 这就是公式A 在D 上的一个解释。从这个解释可以看出: 当x=1、y=1时,有P(x,y)的线时,有P(x,y)的真值为T; 即对x在D上的任意取值,都存在y=1使P(x,y)的真值为T。因此,在此解释下公式A的线) T F T F 4.2.2 谓词公式的永线、谓词公式的解释 说明:一个谓词公式在其个体域上的解释不是唯一的。例如,对公式A,若给出另一组真值指派 这也是公式A 在D 上的一个解释。从这个解释可以看出: 当x=1、y=1时,有P(x,y)的线时,有P(x,y)的真值为F; 即对x在D上的任意取值,不存在一个y使得P(x,y)的真值为T。因此,在此解释下公式A的真值为F。 实际上,A在D上共有16种解释,这里就不在一一列举。 P(1,1) P(1,2) P(2,1) P(2,2) T T F F 4.2.2 谓词公式的永线 如果谓词公式P对非空个体域D上的任一解释都取得真值T,则称P在D 上是永真的;如果P在任何非空个体域上均是永真的,则称P永真。 可见,要判定一谓词公式为永真,必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数为有限时,尽管工作量大,公式的永真性毕竟还可以判定,但当解释个数为无限时,其永线 谓词公式的永线、谓词公式的永线 如果谓词公式P对非空个体域D上的任一解释都取假值F,则称P在D上是永假的;如果P在任何非空个体域上均是永假的,则称P永假。 谓词公式的永假性又称不可满足性或不相容。 4.2.2 谓词公式的永线、谓词公式的永线 对于谓词公式P,如果至少存在D上的一个解释,使公式P在此解释下的真值为T,则称公式P在D上是可满足的。 谓词公式的可满足性也称为相容性。 按照定义4.4,对谓词公式P,如果不存在任何解释,使得P的取值为T,则称公式P是不可满足的。所以谓词公式P的永假与不可满足是等价的。 后面我们要给出的归结推理,就是采用一种逻辑上的反证法,将永真性转换为不可满足性的证明。 4.2.2 谓词公式的永线、谓词公式的可满足性 谓词公式的等价式可定义如下: 定义4.5 设P与Q是D上的两个谓词公式,D是它们共同的个体域。若对D上的任意解释,P与Q的取值都相同,则称公式P与Q在域D上是等价的。如果D是任意非空个体域,则称P与Q是等价的。记作:P?Q。 4.2.2 谓词公式的永线、谓词公式的等价性与永线:谓词演算的基本等价式 4.2.2 谓词公式的永线:谓词演算的基本等价式 4.2.2 谓词公式的永线:谓词演算的基本等价式 4.2.2 谓词公式的永线:谓词演算的基本等价式 4.2.2 谓词公式的永线:量词消去及引入规则 4.2.2 谓词公式的永线 对谓词公式P和Q,如果P→Q永真,则称P 永真蕴含Q,且称Q为P的逻辑结论,P为Q的前提。记作P ? Q。 4.2.2 谓词公式的永线、谓词公式的等价性与永真蕴含 推理规则: P规则:在推理的任何步骤上都可引入前提。 T规则:推理时,如果前面步骤中有一个或多个永真蕴含公式S,则可把S引入推理过程中。 CP规则:如果能从R和前提集合中推出S来,则可从前提集合推出R→S。 反证法: P ? Q,当且仅当P ∧﹁ Q ?F,即Q为P的逻辑结论,当且仅当P ∧﹁ Q 是不可满足的。 由此得到如下定理: 定理4.1:Q为P1,P2,…,Pn的逻辑结论,当且仅当( P1∧P2 ∧… ∧ Pn)∧﹁Q是不可满足的。 常用的永线) 化简式 P∧Q ? P, P∧Q ? Q (2) 附加式 P ? P∨Q, Q ? P∨Q (3) 析取三段论 ﹁ P, P∨Q ? Q (4) 假言推理 P, P→Q ? Q (5) 拒取式 ?Q, P→Q ? P (6) 假言三段论 P→Q, Q→R ?P→R (7) 二难推理 P∨Q, P→R, Q→R ? R (8) 全称固化 (?x)P(x) ? P(y) 其中,y是个体域中的任一个体,依此可消去谓词公式中的全称量词。 (9) 存在固化 (?x)P(x) ? P(y) 其中,y是个体域中某一个可以使P(y)为真的个体,依此可消去谓词公式中的存在量词。 4.2.2 谓词公式的永线、谓词公式的等价性与永线.2.2 谓词公式的永线 置换与合一 置换可简单的理解为是在一个谓词公式中用置换项去替换变量。 定义4.7 置换是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中,t1,t2,…,tn是项;x1,x2,…,xn是互不相同的变元;ti/xi表示用ti替换xi。并且要求ti与xi不能相同,xi不能循环地出现在另一个ti中。 例如, {a/x, c/y, f(b)/z} 是一个置换。 但{g(y)/x, f(x)/y}不是一个置换。原因是它在x与y之间出现了循环置换现象。通常,置换是用希腊字母θ、σ、 α、 λ等来表示的。 不含任何元素的置换称为空置换,以 表示。 4.2.3 置换与合一 1、置换 (1) 空置换 是左么元和右么元,即对任意的置换 , 恒有 = = (2) 对任意表达式E,恒有E( )=(E ) 。 (3) 若对任意表达式E恒有E =E ,则 = 。 (4) 对任意置换 , , , 恒有 即置换的合成满足结合律。 (5) 设A和B为表达式集合,则 注意: 置换的合成不满足交换律。 2、置换的性质 4.2.3 置换与合一 3、置换乘法 定义4.8 设 θ={t1/x1,t2/x2,…,tn/xn} λ={ u1/y1, u2/y2, … , um/ym } 是两个置换。则θ与λ的合成也是一个置换,记作θ°λ,也称置换乘法。它是从集合 { t1λ/x1, t2λ/x2, … , tnλ/xn, u1/y1, u2/y2, … , um/ym } 中删去以下两种元素 ① 当tiλ=xi时,删去tiλ/xi (i=1, 2 ,…, n); ② 当yj∈{ x1, x2 ,…, xn }时,删去uj/yj (j=1, 2 ,…, m) 最后剩下的元素所构成的集合。 4.2.3 置换与合一 例4.2 设θ={ f(y)/x, z/y },λ={a/x, b/y ,y/z },求θ与λ的合成。 解:先求出集合 {f(y)λ/x, (zλ)/y, a/x, b/y , y/z}={f(b)/x, y/y, a/x, b/y , y/z} 其中,f(b)/x中的f(b)是置换λ作用于f(y)的结果;y/y 中的y是置换λ作用于z的结果。在该集合中,y/y满足定义中的条件①,需要删除;a/x和b/y满足定义中的条件②,也需要删除。最后得:θ°λ={f(b)/x, y/z} 3、置换乘法 4.2.3 置换与合一 合一可理解为是寻找项对变量的置换,使两个谓词公式一致。可定义为: 定义4.9 设有公式集F={F1, F2,…,Fn},若存在一个置换θ,可使 F1θ=F2θ=…=Fnθ, 则称θ是F的一个合一。称F1,F2,…,Fn是可合一的。 例4.3 设有公式集F={P(x,y,f(y)), P(a,g(x),z)},则 λ={a/x, g(a)/y, f(g(a))/z} 是它的一个合一。 一般来说,一个公式集的合一不是唯一的。 4、合一 4.2.3 置换与合一 定义4.10 设σ是公式集F的一个合一,如果对F的任一个合一θ都存在一个置换λ,使得θ=σ°λ,则称σ是一个最一般合一(MGU)。 一个公式集的最一般合一是唯一的。 5、最一般合一(MGU, Most General Unifier) 4.2.3 置换与合一 6、MGU算法 4.2.3 置换与合一 定义4.11 表达式的非空集合W的差异集(difference set)是按下述方法得出的子表达式的集合: (1)在W的所有表达式中找出对应符号不全相同的第一个符号(自左算起)。 (2)在W的每个表达式中,提取出占有该符号位置的子表达式。这些子表达式的集合便是W的差异集D。 例4.4:W={P(x,f(y,z)),P(x,a),P(x,g(h(k(x))))},在W的3个表达式中,前4个符号---“P(x,”是相同的,第5个符号不全相同,所以W的不一致集合(差异集)为: {f(y,z),a,g(h(k(x)))}. 假设D是W的差异集,显然有下面的结论。 (1) 若D中无变量符号,则W是不可合一的。 例: (2) 若D中只有一个元素,则W是不可合一的 例: (3) 若D中有变量符号x和项t,且x出现在t中,则W是不可合一的。 例: 4.2.3 置换与合一 (1) 置 。 (2) 若Wk中只有一个元素,终止,并且 为W的最一般合一。否则求出Wk的差异集Dk。 (3) 若Dk中存在元素vk和tk,并且vk是不出现在tk中的变量,则转向第(4)步。否则终止,并且W是不可合一的。 (4)置 (注意: ) (5) 置k=k+1,转向第(2)步。 4.2.3 置换与合一 6、MGU算法 第4章 确定性推理 4.1 推理的基本概念 4.2 推理的逻辑基础 4.3 自然演绎推理 4.4 归结演绎推理 4.3 自然演绎推理 自然演绎推理:从一组已知为真的事实出发,直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 自然演绎推理最基本的推理规则是三段论推理,它包括: 假言推理 P, P→Q ? Q 拒取式 ﹁ Q, P→Q ? P 假言三段论 P→Q, Q→R ? P→R 4.3 自然演绎推理 避免两类错误:肯定后件的错误和否定前件的错误。 肯定后件的错误:当P→Q为真时,希望通过肯定后件Q为真来推出前件P为真,这是不允许的。原因是指当P→Q及Q为真时,前件P既可能为真,也可能为假。 否定前件的错误:当P→Q为真时,希望通过否定前件P为假来推出后件Q为假,这也是不允许的。原因是指当P→Q及P为假时,后件Q既可能为线 自然演绎推理 自然演绎推理的例子 例4.5 设已知如下事实: A, B, A→C, B∧C→D, D→Q 求证:Q为真。 证明:因为 A, A→C? C 假言推理 B, C? B∧C 引入合取词 B∧C,B∧C→D ? D 假言推理 D, D→Q ? Q 假言推理 因此,Q为线 设已知如下事实: (1) 只要是需要编程序的课,王程都喜欢。 (2) 所有的程序设计语言课都是需要编程序的课。 (3) C是一门程序设计语言课。 求证:王程喜欢C这门课。 证明:首先定义谓词 Prog(x) x是需要编程序的课。 Like(x,y) x喜欢y。 Lang(x) x是一门程序设计语言课。 把已知事实及待求解问题用谓词公式表示如下: Prog(x)→Like(Wang, x) (?x)(Lang(x)→Prog(x)) Lang(C) 第4章 确定性推理 智能系统的推理过程实际上就是一种思维过程。按照推理过程所用知识的确定性,推理可分为确定性推理和不确定性推理。对于推理的这两种不同类型,本章重点讨论前一种,不确定性推理放到下一章讨论。 4.1 推理的基本概念 4.2 推理的逻辑基础 4.3 自然演绎推理 4.4 归结演绎推理 4.1 推理的基本概念 4.1.1 什么是推理 4.1.2 推理方法及其分类 4.1.3 推理的控制策略及其分类 4.1.1 什么是推理 推理的概念 是指按照某种策略从已知事实出发去推出结论的过程。 推理所用的事实: 初始证据:推理前用户提供的 中间结论:推理过程中所得到的 推理过程:由推理机来完成,所谓推理机就是智能系统中用来实现推理的那些程序。 推理的两个基本问题 推理的方法:解决前提和结论的逻辑关系,不确定性传递 推理的控制策略:解决推理方向,冲突消解策略 4.1.2 推理方法及其分类 可分为演绎推理

  2005年-普通高等学校招生全国统一考试-语文-辽宁卷(附答案).pdf

  2005年-普通高等学校招生全国统一考试-语文-江苏卷(附答案).pdf

  2005年-普通高等学校招生全国统一考试-语文-湖北卷(附答案).pdf

  2005年-普通高等学校招生全国统一考试-语文-福建卷(附答案).pdf

  2005年普通高等学校招生全国统一考试-语文-山东卷(附答案).pdf

  《城镇燃气设计规范》GB50028-2006(局部修订)征求意见稿.pdf

本文链接:http://meghanmbiro.com/feidandiaotuili/599.html