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

ch4 经典逻辑 推 理 - 1

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

  第四章经典逻辑推理 2012-4-25 经典逻辑推理经典逻辑推理是根据经典逻辑的逻辑规则进行的一种推理,又称为机械-自动定理证 明(mechanical-automatictheoremproving),主要推理方法有自然演绎推理,归结演绎推理及与或 形演绎推理等。由于这种推理是基于经典逻辑的,其真值只有真和假两种,因此它是一种精确推理。 2012-4-25 推理——从已知事实出发,通过运用已掌握的知识,找出其中蕴含的事实,或归结出新的事实,这一过程称为推理。 推理的基本概念2012-4-25 推理中的两种判断:一种是已知的判断,它包括已掌握的与求解问题有关的知识以及关于问题的已知事实; 另一种是由已知判断推出的新判断,即推理的结论。 推理的基本概念2012-4-25 演绎推理——从全称判断推导出特称判断或单称判断的过程,即由一般性知识推出适合于某一具体情况的结论,是一种从一般到个别的推理。 演绎推理有多种形式,经常用的是三段论式,它包括: 结论,这是由大前提推出的适合于小前提所示情况的新判断。推理方式及分类 2012-4-25 所以,高波的身体是强壮的。它是一个三段论推理,其中,(1)是大前提,(2)是小前提,(3)是经演绎推出的结论。结论“高 波的身体是强壮的”事实上是蕴含于“足球运动员的身体都是强壮的”这一大前提中的。它没有超出大前 提所断定的范围。 推理方式及分类 2012-4-25 在任何情况下,由演绎推理导出的结论都是蕴含在大前提的一般性知识中的,这是演绎推理的一个典型特征。因此,只要大前提和小前提是正确的,则由它们推导出来的结论也必然是正确的。 演绎推理是人工智能中的一种重要推理方式,在直到目前研制成功的各类智能系统中,大多是用 演绎推理实现的。 推理方式及分类 2012-4-25 归结推理——归结推理是从足够多的事例中归结出一般性结论的推理过程,是一种从个别到一般的推理。归结推理又分为完全归结和不完全归结两种。 完全归结:指在进行归结时考察了相应事物的全部对象,并根据这些对象是否都有某种属性,从 而推出这种事物是否具有这个属性。 例如: 某厂进行产品质量检查,如果对每一件产品都进行了严格检查,并且是合格的,则推导 出结论该厂的产品是合格的。 推理方式及分类 2012-4-25 不完全归结:指只考察了相应事物的部分对象,就得出了结论。默认推理——又称缺省推理,它是在知识不完全的情况下假设某些条件已经具备所进行的推理。 在默认推理过程中,如果到某一时刻发现原先所作的默认不正确,则就要撤销所作默认,以及由 此默认推出的所有结论,重新按新情况进行推理。 推理方式及分类 2012-4-25 10 .确定性推理,不确定性推理(按推理时所用知识的确定性来划分) 确定性推理—— 指推理时所用的知识都是精确的,推出的结论也是确定的,其真值或为“真”, 或为“假”,没有第三种情况出现。例如:经典逻辑推理。 不确定性推理——指推理时所用的知识不都是精确的,推 出的结论也不完全是肯定的,其真值 位于“真”和“假”之间,命题的外延模糊不清。 推理方式及分类 2012-4-25 11 单调推理、非单调推理(按推理过程中推出的结论是否单调的增加来划分)单调推理——指在推理过程中随着推理的向前推进及新知识的加入,推出的结论呈单调增加的趋势, 并且越来越接近最终目标,在推理过程中不会出现反复的情况,即不会由于新知识的加入而否定了 前面推 出的结论,使推理又退回到前面的一步。 非单调推理——指在推理过程中由于新知识的加入,不仅没有加强已推出的结论,反而要否定它, 使得推理退回到前面的某一步,重新开始。 推理方式及分类 2012-4-25 12 启发式推理、非启发式推理(按推理中是否运用与问题有关的启发性知识分类)启发式推理——推理中运用与问题有关的启发性知识,即解决问题的策略、 技巧、窍门,对解的 特性及规律的估计等实践经验和知识,以加快推理过程、提高搜索效率,这种推理称为启发式推理。 非启发式推理——比如穷举式推理等。 推理方式及分类 2012-4-25 13 基于知识的推理、统计推理、直觉推理(从方法论的角度划分)基于知识的推理——根据已掌握的事实,通过运用知识进行的推理。 统计推理——根据对某事物的数据统计进行的推理(相当于归纳推理)。 直觉推理——又称常识性推理,是根据常识进行的推理。 推理方式及分类 2012-4-25 14 推理控制策略推理过程是一个思维过程,即求解问题的过程,求解问题的质量和效率不仅依赖于所采用 的求解方法,而且还依赖于求解问题的策略,即推理的控制策略。 推理的控制策略主要包括: 推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。 推理控制策略 2012-4-25 15 推理方向推理方向用于确定推理的驱动方式,分为正向推理、逆向推理、混合推理和双向推理四种。 无论按哪种方向进行推理,一般都要求系统具有一个存放知识的知识库, 一个存放初始 已知事实及问题状态的数据库和一个用于推理的推理机。 推理方向 2012-4-25 16 正向推理是以已知事实作为出发点的一种推理,又称数据驱动推理、前向链推理及前件推理等。 正向推理的基本思想从用户提供的初始已知事实出发,在知识库KB中找出当前可适用的知识,构成可适用知识集KS, 然后按某种冲突消解策略从KS中选出一条知识进行推理,并将推出的新事实加入到数据库中作为下一步 推理的已知事实,在此之后再在知识库中选取可适用的知识进行推理,如此重复,直到求得了所要求的 解,或者知识库中再无可适用的知识为止。 正向推理 2012-4-25 17 正向推理过程 算法描述: 开始 把初始已知事实送入DB DB中包含问题的解? KB中有可适用知识? KS空? 把KB中所有可适用知识都选出来送入KS 推出的是新事实? 按冲突消解策略从KS中选出一条知识进行推理 将该新事实加入到DB中 成功,退出 把用户提供的新事实加入DB中 用户 可补充新事实? 失败,退出 2012-4-2518 与正向推理相关的问题匹配方法——在以上推理过程中,需要从知识库 KB 中选出可适用的知识,这就要用知识库中 的知识与数据库中的已知事实进行匹配,为此需确定匹配方法。 搜索策略——为了进行匹配,就要查找知识,这就牵涉到按什么路线进行查找的问题,既按什么 搜索策略搜索知识库。 冲突消解策略——如果适用的知识只有一条,这比较简单,系统立即就可用它进行推理,并将推 出的新事实送入数据库DB中;但是,如果当前适用的知识有多条,应该先用那一条? 这是推理中的一个 重要问题,称为冲突消解策略。 正向推理 2012-4-25 19 逆向推理是以某个假设目标作为出发点的一种推理,又称为目标驱动推理、逆向链推理及后件推 逆向推理的基本思想首先选定一个假设目标,然后寻找支持该假设的证据,若所需的证据都能找到,则说明原假设成立; 若无论如何都找不到所需证据,说明原假设不成立,此时需要另作新的假设。 逆向推理 2012-4-25 20 开始 提出假设 该假设在数据库DB中? 该假设是证据? 在知识库中找出所有能 导出该假设的知识,形 成适用知识集KS 从KS中选出一条知识,并 将该知识的一个运用条件 作为一个新的假设目标。 该假设成立 询问用户 有此事实? 该假设成立, 并将此事实 存入数据库 还有假设? 退出 推理过程算法描述2012-4-25 21 逆向推理的优缺点优点:不必使用与目标无关的知识,目的性强,同时还有利于向用户提供解释。 缺点:初始目标的选择有盲目性,若不符合实际,就要多次提出假设,影响到系统效率。 逆向推理 2012-4-25 22 正、逆向推理存在的缺陷正向推理——具有盲目、效率低等缺点; 逆向推理——若提出的假设目标不符合事实,也会降低系统效率。 为解决这些问题,可把正向推理与逆向推理结合起来,取长补短;象这样既有正向又有逆向的推理称为混 合推理。 先正向再逆向先进行正向推理,帮助选择某 个目标,即从已知事实演绎出 部分结果,然后再用逆向推理 证实该目标或提高其可信度。 开始 进行正向推理 需要逆向推理? 还需要正向推理? 以正向推理所得结果 作为假设进行逆向推理 输出结果 退出 混合推理混合推理 2012-4-25 23 先逆向再正向先假设一个目标进行逆向推理,然后再利用逆向推理中得到的信息进行正向推理,以推出更 多的结论。 开始 进行逆向推理 需要正向推理? 还需要逆向推理? 进行正向推理 输出结果 退出 2012-4-2524 双向推理是指正向推理与逆向推理同时进行,且在推理过程中的某一步骤上“碰头”的一种推 理方式。 基本思想: 一方面根据已知事实进行正向推理,但并不推到最终目标;另一方面从某假设目标出发进行逆 向推理,但并不推至原始事实,而是让它们在中途相遇,即由正向推理所得的中间结论恰好是逆向推理 此时所需要的证据,这时推理就可结束,逆向推理时所做的假设就是推理的最终结论。 双向推理 双向推理 2012-4-25 25 求解策略所谓推理的求解策略是指,推理是只求一个解,还是求所有解以及最优解等。 (3)限制策略 为了防止无穷的推理过程,以及由于推理过程太长增加时间及空间的复杂性,可在控制策略中指定推 理的限制条件,以对推理的深度、宽度、时间和空间等进行限制。 2012-4-25 26 概念在推理过程中,系统要不断地用当前已知的事实与知识库中的知识进行匹配,此时可能发生如下三 种情况: 已知事实可以与知识库中的多个知识匹配成功;或者有多个(组)已知事实都可与知识库中的一个知识匹配成功;或者有多个(组)已知事实可与知识库中的多个知识匹配成功。 第三种情况为发生了冲突,此时需要按一定的策略解决冲突,以便从中挑选一个知识用于当前的推 理,称这一解决冲突的过称为冲突消解。解决冲突时所用的方法称为冲突消解策略。 2012-4-25 27 产生式系统冲突在产生式系统中,若出现下列情况就认为发生了冲突: 对正向推理而言,如果有多条产生式规则的前件都和已知事实匹配成功;或者有多组不同的已知事实都与同一条产生式规则的前件匹配成功;或者以上两种情况同时出现。 对逆向推理而言,如果有多条产生式规则的后件都和同一个假设匹配成功;或者有多条产生式规则的后件可与多个假设匹配成功。 冲突消解冲突消解的任务是解决冲突。 2012-4-25 28 对正向推理来说,它将决定选择哪一组已知事实来激活哪一条产生式规则,使它用于当前的推 理,产生其后件指出的结论或执行相应的操作。 对逆向推理来说,它将决定用哪一个假设与哪一个产生式规则的后件进 行匹配,从而推出相应 的前件,作为新的假设。 冲突消解策略目前已有多种消解冲突的策略,其基本思想都是对知识进行排序。 2012-4-25 29 冲突消解策略常用的有以下几种: 按针对性排序——本策略是优先选用针对性较强的产生式规则。设有如下两条产生式规则: 有更大的通用性。2012-4-25 30 在产生式的推理过程中,每应用一条产生式规则就会得到一个或多个结论或者执行某个操作,数据库就会增加新的事实。另外,在推理时还会向用户询问有关的信息,也使数据库的内容发生变化。我们把数 据库中后生成的事实称为新鲜的事实,即后生成的事实比先生成的事实具有较大的新鲜性。 若一条规则被应用后生成了多个结论,则即可以认为这些结论有相同的新鲜性,也可认为排在前 面的结论有较大的新鲜性,根据情况而定。 2012-4-25 31 匹配度大的知识优先选用。在不确定性匹配中,为了确定两个知识模式是否匹配,需要计算这两个模式的相似程度,当其达 到某个预先规定的值时,则认为它们是可匹配的。相似度又称为匹配度。 若产生式规则r 都可匹配成功,则可根据它们的匹配度决定哪个规则被优先选用。2012-4-25 32 根据领域问题的特点排序某些领域问题,预先可知道它的某些特点,此时可根据这些特点把知识排成固定的顺序。 例如: 当已知某些产生式规则被应用后会明显的有利于问题的求解时,就使这些产生式规则优先被应用。 2012-4-25 33 按上下文限制排序把产生式规则按它们所描述的上下文分成若干组,在不同的条件下,只能从相应的组中选取有关 的产生式规则。这样,不仅可以减少冲突的发生,而且由于搜索范围小,也提高了推理效率。 按冗余限制排序如果一条产生式规则被应用后将产生冗余知识,则降低了它被应用的优先级。产生的冗余知识越 多,优先级越低。 按条件个数排序如果有多条产生式规则生成的结论相同,则要求条件少的产生式规则被优先应用,因为要求条件 少的规则匹配时花费的时间较少。 2012-4-25 34 基本概念所谓模式匹配是指对两个知识模式(如两个谓词公式、两个框架片断或两个语义网络片断等) 的比较与耦合,即 检查这两个知识模式是否完全一致或近似一致。如果两者完全一致,或虽不完全一致 但其相似程度落在指定的限度内,就称它们是可匹配的,否则为不可匹配。 模式匹配是推理中必须进行的一项重要工作,因为只有经过模式匹配才能从知识库中选出当前 适用的知识,才能进行推理。 2012-4-25 35 分类若按匹配时两个知识模式的相似程度分,可分为确定性匹配与不确定性匹配两种。 确定性匹配——指两个知识模式完全一致,或经过变量代换后变的完全一致。 不确定性匹配——指两个知识模式不完全一致,但从总体上看,其相似程度又落在指定的限度内。 2012-4-25 36 变量代换无论是确定性匹配或不确定性匹配,在进行匹配时一般都需要进行变量的代换。 定义1: 代换就是形如 的有限集合。其中,t 相同,也不允许变元x 模式匹配2012-4-25 37 变量代换例如: {a/x,f(b)/y,w/z}是一个代换,但是{g(y)/x,f(x)/y}不是一个代换。 代换的目的是使某些变元被另外的变元、常量或函数取代,使之不再在公式中出现,而 {g(y)/x,f(x)/y}在x与y之间出现了循环代换的情况,它既没有消去x,也没有消去y。 如果将它改为 {g(a)/x,f(x)/y},则它是一个代换。它将把公式中的x用g(a)代换,y用f(g(a))代换, 从而消去了变元x和y。 模式匹配2012-4-25 38 定义2:设 }是两个代换,则此两个代换的复合也是一个代换,它是从 模式匹配2012-4-25 39 定义3:设有公式集F={F },若存在一个代换使得 是可合一的。例如,假设有公式集 一个公式集的合一一般来说是不唯一的。例如: 模式匹配2012-4-25 40 定义4:设 是公式集F的一个合一,如果对任一个合一 都存在一个代换 ,使得 是一个最一般的合一置换,记为mgu。例如: ={f(a)/y,a/z},θ={f(z)/y}都是合一置换,而θ是最一般合一 置换。 最一般合一置换不是唯一的。 例如:F={Q(y),Q(z)},θ={y/z}与θ={z/y}都是它们的最一般合一置换。 若用最一般合一去代换那些可合一的谓词公式,可使它们变成完全一致的谓词公式。 由此可知,为了使两个知识模式匹配,可用其最一般的合一对他们进行代换。 模式匹配2012-4-25 41 差异集(不一致集):对两个谓词公式中的项从左到右进行比较时,那些不同的项所构成的集合。 例如:设有如下两个谓词公式: 中的f(a)不同,它们构成了一个差异集: 模式匹配2012-4-25 42 求取最一般合一置换的算法: 。其中F是欲求其最一般合一置换的公式集,是空代换,它代表不作代换。 中出现,则置:k+1 k=k+1然后转(2)。 (5)算法中止,F的最一般合一不存在。 2012-4-25 43 2012-4-2544 经典逻辑推理经典逻辑推理是根据经典逻辑(命题逻辑和一阶谓词逻辑)的逻辑规则进行的一种推理,又称机 械—自动定理证明。主要推理方法有自然演绎推理、归结演绎推理和与/或形演绎推理等。这种推理是基于 经典逻辑的,其真值只有“真”与“假”两种,因此它是一种 精确推理,或称为确定性推理。 1.数学基础——谓词演算基础 谓词公式P(x1,x2,……,xn) 其中,P是谓词名, x1,x2,……,xn是个体。在谓词中,个体可以是常量、变元、也可以是函数;个 体变元的取值范围称为个体域。 2012-4-25 45 谓词公式的解释定义1:设D为谓词公式P的个体域,若对P中的个体常量、函数和谓词按如下规定赋值: F,T}的映射。则称这些指派为公式P在D上的一个解释。 谓词演算基础 2012-4-25 46 例如:设个体域 上的某一个解释,并指出在此解释下公式A的真值。 在公式中没有个体常量和函数,所以直接给谓词指派值,设为: P(1,1)=T, P(1,2)=F, P(2,1)=T, P(2,2)=F 这就是谓词公式A在D上的一个解释。 公式A的真值为:T 即对所有的x(1,2),都存在一个y(1),使P(x,y)=T 谓词演算基础2012-4-25 47 一个谓词公式的解释可能有很多个,对每一个解释,谓词公式都可以得到一个真值。 对公式A中的谓词可以指派另一组线)=F, 这是对公式A的另一种解释。在此解释下,公式A的真值为F,即对所有的x(1,2),不存在一个y,使 注:公式A在D上共有16种解释。谓词演算基础 2012-4-25 48 谓词公式的永线:如果谓词公式 在每个非空个体域上均永真,则称P永真。由定义可知,要判断一个公式永真,必须对每个个体域上的每一个解释逐一判定,工作量太大,经 常是无法完成的。 定义3:对于谓词公式P,如果至少存在一个解释使得公式P在此解释下真值为T,则称公式P是可满足 谓词演算基础2012-4-25 49 定义4: 如果谓词公式P对于个体域D上的任何一个解释都取得真值F,则称公式P在D上是永假的;如果P在每 谓词公式的永假性又可称为不可满足性或不相容性。谓词演算基础 谓词公式的等价性定义5:设 Q是两个谓词公式,D是它们共同的个体域,若对D上的任何一个解释, Q都有相同的真值,则称 D上是等价的。如果D是任意个体域,则称 2012-4-2550 一些相关的等价式: 交换律: 谓词演算基础2012-4-25 51 一些相关的等价式: 连接词化归律: 谓词演算基础2012-4-25 52 谓词公式的永线: 对于谓词公式 一些相关的永真蕴含式(推理规则):假言推理 谓词演算基础2012-4-25 53 谓词逻辑中另外的一些推理规则: P规则:在推理的任何步骤上都可引入前提。 T规则:推理时,如果前面步骤中有一个或多个永真蕴含公式 引入推理过程中。反证法:P 谓词演算基础2012-4-25 54 把反证法推广到谓词公式集,可得到如下反证法定理: [定理1] 是不可满足的。谓词演算基础 2012-4-25 55 原理从一组已知为真的事实出发,直接运用经典逻辑的推理规则推出 结论的 过程称为自然演绎推理。 基本的推理规则是 P规则、T规则、假言推理、拒取式推理等。 假言推理 推出铜能导电。 若x是金属,则x能导电; 铜是金属; 如果下雨,则地下湿; 地下不湿; 推出 没有下雨 例如: P规则:在推理的任何步骤上都可引入前提。 T规则:推理时,如果前面步骤中有一个或多个永真蕴含公式S 引入推理过程中。2012-4-25 56 避免出现的两类错误: 一是肯定后件(Q)的错误;另一是否定前件(P)的错误。 所谓肯定后件是指,当P Q为真时,希望通过肯定后件Q为真来推出前件P为真,这是不允许的。 例如: 伽利略在证明哥白尼的日心说时,曾使用了如下推理: 所以,行星系统是以太阳为中心的。这就是使用了肯定后件的推理,违反了经典逻辑的逻辑规则。 自然演绎推理 2012-4-25 57 例如: 下面的推理就使用了否定前件的推理,违反了逻辑规则: 所以地上不湿。这显然是错误的。 自然演绎推理 2012-4-25 58 用自然演绎推理求解问题例如:已知如下事实: ds是C班的一门课程;求证:小王喜欢ds这门课程。 证明:首先定义谓词: EASY(x):x 是容易的; LIKE(x, 班的一门课程。自然演绎推理 2012-4-25 59 把上述已知事实及待求证的问题用谓词公式表示出来: EASY(x) LIKE(Wang, C班的课程都是容易的;C(ds) ds是C班的一门课程; LIKE(Wang, ds) 小王喜欢ds这门课(待求证问题)。 应用推理规则进行推理: 因为: EASY(y)全称固化 因为: C(ds), EASY(y)EASY(ds) P规则及假言推理 所以: EASY(ds), EASY(x) LIKE(Wang, LIKE(Wang,ds) T规则 及假言推理 即:小王喜欢ds这门课程。 2012-4-25 60 自然演绎推理优缺点优点:表达定理证明过程自然,容易理解,而且其拥有丰富的推理规则,推理过程灵活,便于在 其推理规则中嵌入领域启发性知识。 缺点:容易产生组合爆炸,推理过程中得到的中间结论一般成指数形式递增。 自然演绎推理 2012-4-25 61 3.归结演绎推理 自动定理证明是人工智能的一个重要研究领域,这不仅是由于许多数学问题需要通过定理证明得以解决, 而且很多非数学问题(如医疗诊断、机器人行动规划等)也都可归结为一个定理证明问题。定理证明的实质是 对前提P和结论Q证明P Q的永真性,但是要证明一个谓词公式的永真性是很困难的。 通过研究发现应用反证法的思想可把关于永真性的证明转化为不可满足性的证明。 归结演绎推理 2012-4-25 62 欲证明 Q不满足就可以了。关于不可满足性的证明,海伯伦及鲁宾逊先后进行了卓有成效的研究,提出了相应的理论和方法。 鲁宾逊提出的归结原理对机械化推理有了重大的突破。无论是海伯伦还是鲁宾逊的理论,都是以子句集为背景开展研究的。 归结演绎推理 2012-4-25 63 子句在谓词逻辑中,把原子谓词公式及其否定统称为文字。 [定义1] 任何文字的析取式称为子句。 例如: [定义2]不包含任何文字的子句称为空子句,记为NIL。 由于空子句不含有文字,它不能被任何解释满足,所以空子句是永假的,不可满足的。 由子句构成的集合称为子句集。 在谓词逻辑中,任何一个谓词公式都可通过应用等价关系及推理规则化成相应的子句集。 归结演绎推理 2012-4-25 64 谓词公式化成子句集的步骤: (连接词化规律)例如:公式 (德.摩根律)上式经等价变换后得: 重新命名变元名,使不同量词约束的变元有不同的名字。上式经等价变换后得: 归结演绎推理2012-4-25 65 skolem)函数消去存在量词。分两种情况: 存在量词不出现在全称量词的辖域内,变量y不依赖于其它变量,y用 常量 x)的辖域内,所以都需要用skolem函数替换,设y和z的skolem函数分别为f(x)和 把所有的全称量词移到公式的左边。如果公式内部有全称量词,需要把它们都移到公式的左边。 上式只有一个全称量词,且已位于公式的最左边。 归结演绎推理 2012-4-25 66 (PQ)(PR)把公式化为skolem标准形。skolem标准形为: 其中,M是子句的合取式,称为skolem标准形的母式。上式经等价变换后得: 消去全称量词。由于此时公式中所有变量都是约束的,全称变量不必要,故可消去: 对变元更名,使不同子句中的变元不同名。上式经更名后得到: 消去合取词。消去合取词后,上式变为下述子句集: 归结演绎推理2012-4-25 67 [定理2] 设有谓词公式F,其标准形的子句集为S,则F不可满足的充要条件是S不可满足。 定理说明了谓词公式F与其子句集S在不可满足的意义下是等价的。 注意:谓词公式F与其子句集S并不等值,只是在不可满足的意义下是一致的。 例如:谓词公式 P(x),个体域D={1,2},此时,F=P(1)P(2)。有一解释为: P(1)=F,P(2)=T。在这一解释下,公式F的值为T;通过消去存在量词得到子句为P(a),若a=1,则子句集的值 归结演绎推理2012-4-25 68 海伯伦理论为了判断一个子句的不可满足性,需要对个体域上的一切解释逐个进行判定,只有当该子句对任何 非空的个体域上的任何一个解释都是不可满足的,才能判断该子句不可满足。这几乎是不可实现的。 对此,海伯伦构造了一个特殊的域,并证明只要对这个特殊域上的一切解释进行判定,就可得知子 句集是否不可满足。这个特殊域称为海伯伦域。 归结演绎推理 2012-4-25 69 [定义3] 设谓词公式的子句集为S,则按下述方法构造的域H称为海伯伦域,简记为H域。 ={a},其中a为任意指定的一个个体常量。 {S中所有形如f(t1,t2,…,tn)的元素}其中,f(t1,t2,…,tn)是出现于F中的任一函数符号,而t1,t2,…,tn是H 中的元素,这里i=1,2,…。归结演绎推理 2012-4-25 70 例1:求子句集S={P(x) 归结演绎推理2012-4-25 71 解:由于该子句集中既无个体常量,又无函数,所以可任意指定一个常量a作为个体常量,从而得到 归结演绎推理2012-4-25 72 子句集S的原子集: A={所有形如P(t1,t2,…,tn)的元素}, 其中P(t1,t2,…,tn)是出现在S中的任一谓词符号,而t1,t2,…,tn是H 中的任意元素。原子、文字、子句和子句集: 将没有变元出现的原子、文字、子句和子句集分别称为基原子、基文字、基子句和基子句集。 归结演绎推理2012-4-25 73 [定义4]若子句集S的原子集为A,则对A中各元素的真、假值的一个具体设定都是S的一个解释。 通过此定义,可以得到求子句集S的H解释的方法。 例如:设子句集S={P(x) 归结演绎推理2012-4-25 74 例如:设子句集 归结演绎推理2012-4-25 75 一般来说,一个子句集的基原子有无限多个,它在H域上的解释也有无限多个。 可以证明,对给定域D上的任一个解释,总能在H域上构造一个解释与它对应,如果D域上的解释能 满足子句集S,则在H域上的相应解释也能满足S,由此可推出如下两个定理: [定理3] 子句集S不可满足的充要条件是 H域上的一切解释为假。[定理4] 子句集S不可满足的充要条件是存在一个有限的不可满足的基例集S 。该定理称为海伯伦定理。海伯伦定理只从理论上给出了证明子句集不可满足性的可行性及方法,但要在计算机上实现其证明 过程是很困难的。 1965年鲁宾逊提出了归结原理,这才使机器定理证明变为现实。 归结演绎推理 2012-4-25 76 鲁宾逊归结原理归结原理又称为消解原理,是鲁宾逊提出的一种证明子句集不可满足性,从而实现定理证明的一种理 论及方法。 由谓词公式转化子句集的过程可以看出,在子句集中子句之间是合取关系,其中只要有一个子句不可满足,则子句集就不可满足; 空子句是不可满足的,若一个子句集包含空子句,则这个子句集一定是不可满足的。归结原理的基本思想: 检查子句集S中是否包含空子句,若包含,则S不可满足;若不包含,就在子句集中选择合适的子 句进行归结,一旦通过归结能推出空子句,就说明子句集 S是不可满足的。 归结演绎推理 2012-4-25 77 [定义5] 若P是原子谓词公式,则称P与 P为互补文字。 命题逻辑中的归结原理命题逻辑中的归结原理 [定义6] ,并将两个子句中余下的部分析取,构成一个新子句C12, 则称这一过程为归结,称 12的亲本子句。

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