您好、欢迎来到现金彩票网!
当前位置:刘伯温四肖中特料 > 推理子句 >

第三讲(经典逻辑推理)ppt

发布时间:2019-07-10 03:11 来源:未知 编辑:admin

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

  4.4 与/或形演绎推理 归结演绎推理要求把有关问题的知识及目标的否定都化成子句形式,然后通过归结进行演绎推理,其推理规则只有一条,即归结规则; 与/或形演绎推理不再把有关知识转化成子句集,而把领域知识及已知事实分别用蕴含式及与/或形表示出来,然后通过运用蕴含式进行演绎推理,从而证明某个目标公式。 与/或形演绎推理的特点 优点: 不必把公式化为子句集,保留了连接词“→”。这就可直观地表达出因果关系,比较自然。 缺点: 对正向演绎推理而言,目标表达式被限制为文字的析取式; 对逆向演绎推理,已知事实的表达式被限制为文字的合取式; 正、逆双向演绎推理虽然可以克服以上两个问题,但其“接头”的处理却比较困难。 完 谢谢 4.3.2 Herbrand理论 为了判断子句集的不可满足性,需要对所有可能论域上的所有解释进行判定。只有当子句集对任何非空个体域上的任何一个解释都是不可满足的,才可断定该子句集是不可满足的。 海伯伦构造了一个特殊的论域(海伯伦域),并证明只要对这个特殊域上的一切解释进行判定,就可知子句集是否不可满足。 海伯伦域 定义4.7 设S为子句集,则按下述方法构造的域H∞称为海伯伦域,记为H域。 (1)令H0是S中所有个体常量的集合,若S中不包含个体常量,则令H0={a},其中a为任意指定的一个个体常量。 (2)令Hi+1=Hi∪{S中所有n元函数f(x1,…,xn)xj(j=1,…,n)是Hi中的元素},其中i=0,1,2,…。 例4.3 求子句集S={P(x)∨Q(x),R(f(y))}的H域。 解:此例中没有个体常量,任意指定一个常量a作为个体常量,得到 H0={a} H1={a,f(a)} H2={a,f(a),f(f(a))} H3={a,f(a),f(f(a)),f(f(f(a)))} … H∞={a,f(a),f(f(a)),f(f(f(a))),…} 为研究子句集的永假性,引入H域上的原子谓词公式实例集A: A={所有出现于S中原子谓词公式的实例} 若原子公式是命题(不包含变量),则其实例就是其本身; 若原子公式形如P(t1, t2,…, tm), ti是变量(i=1,2,…m),则其实例通过让ti=ki∈H(即H∞)来形成(i=1,2,…,m)。例如,对于上述例4.3,有: A={P(a), Q(f(a)), Q(f(f(a))),…} 我们称A中的元素为基原子,进而A也称为基原子集。鉴于这些元素都是原子命题,只要给它们每个指派一个真值(T或F),就可建立子句集在H域上的一个解释,记为I*。就以基原子自身指示取真值T,前面加取反符号指示取真值F, 则对于上述第一例,有 I*1 ={ P(a), Q(f(a)), Q(f(f(a))),…} I*2 ={ P(a), ~Q(f(a)), Q(f(f(a))),…} … 一个子句集的基原子有无限多个,它在H域上的解释也有无限多个。 在H域上进行解释的意义 意义:对于S任意可能论域D上的任意一个解释I,总存 在H域上的一个解释I’与它对应,且子句集在这两个解 释下具有相同的线 子句集S不可满足的充要条件是S对H域上一切 解释都为假。 4.3.3 鲁滨逊归结原理 鲁滨逊归结原理的基本思想:检查子句集S中是否包含空子句。若包含,则S不可满足;若不包含,就在子句集中选择合适的子句进行归结,一旦通过归结能推出空子句,就说明子句集S是不可满足的。 子句集S的不可满足性:对于任意论域中的任意一个解释,S中的子句不能同时取得真值T。一旦S中包含空子句,则S必不可满足。 命题逻辑中的归结原理 定义4.9 若P是原子谓词公式,则称P与?P为互补文字。 在命题逻辑中,P为命题。 定义4.10 设C1与C2是子句集中的任意两个子句。如果C1中的文字L1与C2中文字L2互补,那么从C1和C2中分别消去L1和L2,并将两个子句中余下的部分析取,构成一个新子句C12,则称这一过程为归结。称C12为C1和C2的归结式,C1和C2为C12的亲本子句。 例4.9 设 C1=?P∨Q, C2=?Q∨R, C3=P C1与C2归结得到:C12=?P∨R C12与C3归结得到:C123=R 定理4.4 C12是其亲本子句C1与C2的逻辑结论。 证明:设 C1=L∨C`1, C2=?L∨C`2, 则C12=C`1∨C`2 推论1 设C1与C2是子句集S中的两个子句,C12是它们的归结式。若用C12代替C1和C2后得到新子句集S1,则由S1的不可满足性可推出原子句集S的不可满足性,即 S1的不可满足性=S的不可满足性 推论2 设C1与C2是子句集S中的两个子句,C12是它们的归结式。若把C12加入S中得到新子句集S2,则S与S2在不可满足的意义上是等价的,即 S2的不可满足性=S的不可满足性 推论1及推论2保证了我们可以用归结的方法来证明子句集S的不可满足性。 为了要证明子句集S的不可满足性,只要对其中可进行归结的子句进行归结,并把归结式加入子句集S,或者用归结式替换它的亲本子句,然后对新子句集(S1或者S2)证明不可满足性就可以了。如果经过归结能得到空子句,则立即可得原子句集S是不可满足的结论。 在命题逻辑中,对不可满足的子句集S,归结原理是完备的。即,若子句集不可满足,则必然存在一个从S到空子句的归结演绎;若存在一个从S到空子句的归结演绎,则S一定是不可满足的。 谓词逻辑中的归结原理 在谓词逻辑中,由于子句中含有变元,所以不能像命题逻辑那样直接消去互补文字,而需要先用最一般合一对变元进行代换,然后才能进行归结。 例如,设有两个子句 C1=P(x)∨Q(x), C2= ?P(a)∨R(y) 由于P(x)与P(a)不同,所以C1与C2不能直接进行归结。但是若用最一般合一 σ={a/x} 对两个子句分别进行代换: C1σ =P(a)∨Q(a) C2σ = ?P(a)∨R(y) 就可对它们进行归结,得到归结式: Q(a)∨R(y) 二元归结式的定义 定义4.11 设C1与C2是两个没有相同变元的子句,L1和L2分别是C1和C2中的文字。若σ是L1和?L2的最一般合一,则称 C12=(C1σ-{L1σ})∪(C2σ-{L2σ}) 为C1和C2的二元归结式,L1和L2称为归结式上的文字。 例4.10 设 C1=P(a)∨?Q(x)∨R(x), C2=?P(y)∨Q(b) 若选L1=P(a),L2=?P(y),则有:L1=P(a), ?L2=P(y),σ={a/y}就是L1与 ?L2的最一般合一。可得: C12 =(C1σ-{L1σ})∪(C2σ-{L2σ}) = ?Q(x)∨R(x)∨Q(b) 若子句C含有可合一的文字,则在进行归结之前应先对这些文字进行合一。记其最一般的合一为σ,称Cσ子句C的因子。 C1=P(x)VP(f(a))VQ(x), C2= ?P(y) VR(b) σ={ f(a)/x } C1σ=P(f(a)) VQ(f(a)) C12 = Q(f(a)) VR(b) 定义4.12 子句C1和C2的归结式是下列二元归结式之一: C1与C2的二元归结式; C1与C2的因子C2σ2的二元归结式; C1的因子C1σ1与C2的二元归结式; C1的因子C1σ1与C2的因子C2σ2的二元归结式。 对于一阶谓词逻辑归结原理也是完备的。即,若子句集S不可满足,则必然存在一个从S到空子句的归结演绎;若存在一个从S到空子句的归结演绎,则S一定是不可满足的。 4.3.4 归结反演 如欲证明Q为P1,P2,…,Pn的逻辑结论,只需证 (P1∧P2∧…∧Pn)∧?Q 是不可满足的,或证明其子句集是不可满足的。而子句集的 不可满足性可用归结原理来证明。 应用归结原理证明定理的过程称为归结反演。 设F为已知前提的公式集,Q为目标公式(结论),用归结反演证明Q为真的步骤是: 否定Q,得到?Q; 把?Q并入到公式集F中,得到{F, ?Q}; 把公式集{F, ?Q}化为子句集S; 应用归结原理对子句集S中的子句进行归结,并把每次归结得到的归结式都并入S中。如此反复进行,若出现了空子句,则停止归结,此时就证明了Q为真。 归结反演的例子 例4.12 已知 求证:G是F的逻辑结论。 证明:首先把F和?G化为子句集: 然后进行归结: (6)?A(x,y)∨?B(y) 由(1)与(3)归结,{f(x)/z} (7)?B(b) 由(4)与(6)归结,{a/x,b/y} (8)NIL 由(5)与(7)归结 所以G是F的逻辑结论。 上述归结过程如右图归结树所示。 ?A(x,y)∨?B(y)∨C(f(x)) ?A(x,y)∨?B(y) ?B(b) NIL ?C(z) A(a,b) B(b) 4.3.5 应用归结原理求取问题的答案 求解的步骤: 把已知前提用谓词公式表示出来,并且化为相应的子句集。设该子句集的名字为S。 把待求解的问题也用谓词公式表示出来,然后把它否定并与谓词Answer构成析取式。Answer是一个为了求解问题而专设的谓词。 把此析取式化为子句集,并且把该子句集并入到子句集S中,得到子句集S`。 对S`应用归结原理进行归结。 若得到归结式Answer,则答案就在Answer中。 用归结原理求解问题的例子(1) 例4.16 设A,B,C三人中有人从不说真话,也有人从不说假话。某人向这三人分别提出同一个问题:谁是说谎者?A答:“B和C都是说谎者”;B答:“A和C都是说谎者”;C答:“A和B中至少有一个是说谎者”。求谁是老实人,谁是说谎者? 解:设用T(x)表示x说真话。 T(C)∨T(A)∨T(B) ?T(C)∨?T(A)∨?T(B) T(A)→?T(B)∧?T(C) ?T(A)→T(B)∨T(C) T(B)→?T(A)∧?T(C) ?T(B)→T(A)∨T(C) T(C)→?T(A)∨?T(B) ?T(C)→T(A)∧T(B) 用归结原理求解问题的例子(2) 把上述公式化成子句集,得到S: (1)?T(A)∨?T(B) (2)?T(A)∨?T(C) (3)T(C)∨T(A)∨T(B) (4)?T(B)∨?T(C) (5)?T(C)∨?T(A)∨?T(B) (6) T(A)∨T(C) (7)T(B)∨T(C) 下面先求谁是老实人。把?T(x)∨Ansewer(x)并入S得到S1。即多一个子句: (8)?T(x)∨Ansewer(x) 应用归结原理对S1进行归结: (9)?T(A)∨T(C) (1)和(7)归结 (10)T(C) (6)和(9)归结 (11)Ansewer(C) (8)和(10)归结 所以C是老实人,即C从不说假线)?T(A)∨?T(B) (2)?T(A)∨?T(C) (3)T(C)∨T(A)∨T(B) (4)?T(B)∨?T(C) (5)?T(C)∨?T(A)∨?T(B) (6) T(A)∨T(C) (7)T(B)∨T(C) 下面证明A不是老实人,即证明?T(A)。 对?T(A)进行否定,并入S中,得到子句集S2,即S2比S多如下子句: (8)?(?T(A)), 即T(A) 应用归结原理对S2进行归结: (9)?T(A)∨T(C) (1)和(7)归结 (10)?T(A) (2)和(9)归结 (11)NIL (8)和(10)归结 所以A不是老实人。同样可以证明B也不是老实人。 练习: 1.设已知: (1)如果x是y的父亲,y是z的父亲,则x是z的祖父; (2)每个人都有一个父亲。 试用归结演绎推理证明:对于某人u,一定存在一个人v,v是u的祖父。 2.张某被盗,公安局派出五个侦察员去调查。研究案情时,侦察员 A 说“赵与钱中至少有一人作案”;侦察员 B 说“钱与孙中至少有一人作案”;侦察员 C 说“孙与李中至少有一人作案”;侦察员 D 说“赵与孙中至少有一人与此案无关”;侦察员 E 说“钱与李中至少有一人与此案无关”。如果这五个侦察员的话都是可信的,试用归结演绎推理求出谁是盗窃犯。 归结时,并不要求把子句集中所有的子句都用到。 在归结过程中,一个子句可以多次被用来进行归结。 4.3.6 归结策略 归结策略可分为两大类: 一类是删除策略; 删除某些无用的子句来缩小归结的范围。 一类是限制策略。 通过对参加归结的子句进行种种限制,尽可能减小归结的盲目性,使其尽快地归结出空子句。 归结的一般过程 设有子句集S={C1,C2,C3,C4},则对此子句集归结的一般过程是: S内任意子句两两逐一进行归结,得到一组归结式,称为第一级归结式,记为S1。 把S与S1内的任意子句两两逐一进行归结,得到一组归结式,称为第二级归结式,记为S2。 S和S1内的子句与S2内的任意子句两两逐一进行归结,得到一组归结式,称为第三级归结式,记为S3。 如此继续,直到出现了空子句或者不能再继续归结为止。 一个归结的例子 例4.17 设有子句集S={P, ?R,?P∨Q,?Q∨R}。归结过程为: S: (1)P (2)?R (3)?P∨Q (4)?Q∨R S1: (5)Q (1)与(3)归结 (6)?Q (2)与(4)归结 (7)?P∨R (3)与(4)归结 S2: (8)R (1)与(7)归结 (9)?P (2)与(7)归结 (10)?P (3)与(6)归结 (11)R (4)与(5)归结 S3: (12) NIL (1)与(9)归结 删除策略 纯文字删除法 如果某文字L在子句集中不存在可与之互补的文字?L,则称该文字为纯文字。包含纯文字的子句可以删除。 重言式删除法 如果一个子句中同时包含互补文字对,则该字句称为重言式。重言式是永远为真的子句,可以删除。 支持集策略 对参加归结的子句提出如下限制:每一次归结时,亲本子句中至少有一个是由目标公式的否定所得到的子句,或者是它的后裔。可以证明,支持集策略是完备的。 例4.18 设有子句集S={?I(x)∨R(x),I(a),?R(y)∨?L(y),L(a)}其中?I(x)∨R(x)是目标公式否定后得到的子句。 用支持集策略进行归结的过程是: S: (1) ?I(x)∨R(x) (2) I(a) (3) ?R(y)∨?L(y) (4) L(a) S1: (5) R(a) (1)与(2)归结 (6) ?I(x)∨?L(x) (1)与(3)归结 S2: (7) ?L(a) (2)与(6)归结 (8) ?L(a) (3)与(5)归结 (9) ?I(a) (4)与(6)归结 S3: (10)NIL (2)与(9)归结 支持集策略示例 ?I(x)∨R(x) I(a) ?R(y)∨?L(y) L(a) R(a) ?L(a) ?I(x)∨?L(x) ?L(a) ?I(a) NIL 1 2 3 4 5 6 7 8 9 10 线性输入策略 限制:参加归结的两个子句中必须至少有一个是初始子句集中的子句。 线性输入策略可限制生成归结式的数量,具有简单、高效的优点。但是它是不完备的。 ?I(x)∨R(x) I(a) ?R(y)∨?L(y) L(a) R(a) ?L(a) ?I(x)∨?L(x) ?L(a) ?I(a) NIL 1 2 3 4 5 6 9 8 11 12 ?R(a) ?I(a) 7 10 单文字子句策略 如果一个子句只包含一个文字,则称它为单文字子句。 限制:参加归结的两个子句中必须至少有一个是单文字子句。 用单文字子句策略归结时,归结式比亲本子句含有较少的文字,这有利于朝着空子句的方向前进,因此它有较高的归结效率。但是,这种归结策略是不完备的。当初始子句集中不包含单文字子句时,归结就无法进行。 祖先过滤策略 该策略与线性策略比较相似,但放宽了限制。当对两个子句C1和C2进行归结时,只要它们满足下述任一个条件就可以归结。 C1和C2中至少有一个是初始子句集中的子句。 C1和C2中一个是另外一个的祖先子句。 祖先过滤策略是完备的。 优点: 简单,便于在计算机上实现。 缺点: 必须把逻辑公式化成子句集。 不便于阅读与理解。 ?P(x)∨Q(x)没有P(x)→Q(x)直观。 可能丢失控制信息。 下列逻辑公式: (?A∧?B)→C ?A→(B∨C) (?A∧?C)→B ?B→(A∨C) (?C∧?B)→A ?C→(B∨A) 化成子句后都是: A∨B∨C 归结演绎推理的特点 第四章 经典逻辑推理 4.1 基本概念 4.2 自然演绎推理 4.3 归结演绎推理 4.4 与或形演绎推理 4.1 基本概念 4.1.1 什么是推理 所谓推理就是按某种策略由已知判断推出另一个判断的思维过程。 在人工智能中,推理是由程序实现的,称为推理机。 4.1.2 推理方式及其分类 1. 演绎推理、归纳推理、默认推理 演绎推理:从一般到特殊。例如三段论。 归纳推理:从个体到一般。 默认推理:缺省推理,在知识不完全的情况下假设某些条件已经具备所进行的推理。 2. 确定性、不确定性推理 3. 单调推理、非单调推理 推出的结论是否单调增加 4. 启发式、非启发式推理 所谓启发性知识是指与问题有关且能加快推理进程、求得问题最优解的知识。 5. 基于知识的推理(专家系统) 、统计推理、直觉推理(常识性推理) 4.1.3 推理的控制策略 推理的控制策略主要包括:推理方向、搜索策略、冲突消解策略、求解策略及限制策略。 1. 正向推理(数据驱动推理) 正向推理的基本思想是:从用户提供的初始已知事实出发,在知识库KB中找出当前可适用的知识,构成可适用的知识集KS,然后按某种冲突消解策略从KS中选出一条知识进行推理,并将推出的新事实加入到数据库DB中,作为下一步推理的已知事实。在此之后,再在知识库中选取可适用的知识进行推理。如此重复进行这一过程,直到求得所要求的解。 正向推理示意图 2 逆向推理 逆向推理的基本思想是:首先选定一个假设目标,然后寻找支持该假设的证据,若所需的证据都能找到,则说明原假设是成立的;若找不到所需要的证据,则说明原假设不成立,此时需要另作新的假设。 逆向推理示意图 动物识别的例子 已知事实:一动物{有毛,吃草,黑条纹} R1:动物有毛 → 哺乳类 R2:动物产奶 → 哺乳类 R3:哺乳类 ∧ 吃肉 → 食肉类 R4:哺乳类 ∧ 吃草 → 有蹄类 R5:食肉类 ∧ 黄褐色 ∧ 有斑点→ 猎狗 R6:食肉类 ∧ 黄褐色 ∧ 黑条纹→ 虎 R7:有蹄类 ∧ 长脖 → 长颈鹿 R8:有蹄类 ∧ 黑条纹 → 斑马 3. 混合推理 先正向推理后逆向推理 先逆向推理后正向推理 4. 双向推理 正向推理与逆向推理同时进行,且在推理过程中的某一步上“碰头”。 5. 求解策略 只求一个解,还是求所有解以及最优解。 6. 限制策略 限制搜索的深度、宽度、时间、空间等等。 所谓模式匹配是指对两个知识模式(例如两个谓词公式、框架片断、语义网络片断)进行比较,检查这两个知识模式是否完全一致或者近似一致。 模式匹配可分为确定性匹配与不确定性匹配。 确定性匹配是指两个知识模式完全一致,或者经过变量代换后变得完全一致。 知识:IF father(x,y) and man(y) THEN son(y,x) 事实:father(李四,李小四) and man(李小四) 不确定性匹配是指两个知识模式不完全一致,但是它们的相似程度又在规定的限度内。 4.1.4 模式匹配 变量代换 定义4.1 代换是一个形如 {t1/x1,t2/x2,…,tn/xn} 的有限集合。 其中t1,t2,…,tn是项(常量、变量、函数); x1,x2,…,xn是(某一公式中)互不相同的变元; ti/xi表示用ti代换xi 不允许ti与xi相同,也不允许变元xi循环地出现在另一个tj中。 例如: {a/x,f(b)/y,w/z}是一个代换 {g(y)/x,f(x)/y}不是代换 {g(a)/x,f(x)/y}是代换 令θ= {t1/x1,t2/x2,…,tn/xn}为一个代换,F为表达 式,则Fθ表示对F用ti代换xi后得到的表达式。 Fθ称为F的特例。 规则: IF father(x,y) and man(y) THEN son(y,x) 事实: father(李四,李小四) and man(李小四) F=father(x,y) ∧ man(y) θ= {李四/X,李小四/Y} Fθ= father(李四,李小四) ∧ man(李小四) 结论: son(李小四,李四) 代换的复合 定义4.2 设 θ= {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 ui/yi 当yi∈{x1,x2,…,xn} 后剩下的元素所构成的集合,记为θ°λ 。 注: tiλ表示对ti运用λ进行代换。 θ°λ就是对一个公式F先运用θ进行代换,然后再运用λ进行代换:F( θ°λ )=(F θ)λ 代换的例子 例如,设有代换 θ= {f(y)/x,z/w} λ= {a/x,b/y,w/z} 则 θ°λ={f(y)λ/x, zλ/w, a/x, b/y, w/z} ={f(b)/x, w/w, a/x, b/y, w/z} ={f(b)/x, b/y, w/z} 公式集的合一 定义4.3 设有公式集F={F1,F2,…,Fn},若存在一个代换λ使得 F1λ=F2λ=…=Fnλ 则称λ为公式集F的一个合一,且称F1,F2,…,Fn是可合一的。 例如,设有公式集 F={P(x,y,f(y)),P(a,g(x),z)} 则下式是它的一个合一: λ={a/x,g(a)/y,f(g(a))/z} 一个公式集的合一一般不唯一。 最一般的合一 定义4.4 设σ是公式集F的一个合一,如果对任一个合一θ都存在一个代换λ,使得θ=σ°λ 则称σ是一个最一般的合一。 (1)代换过程是一个用项代替变元的过程,因此是一 个从一般到特殊的过程。 (2) 最一般合一是唯一的。 求取最一般合一 差异集:两个公式中相同位置处不同符号的集合。 例如:F1:P(x,y,z), F2:P(x,f(a),h(b)) 则D1={y,f(a)}, D2={z,h(b)} 求取最一般合一的算法: 令k=0,Fk=F, σk=ε。 ε是空代换。 若Fk只含一个表达式,则算法停止,σk就是最一般合一。 找出Fk的差异集Dk。 若Dk中存在元素xk和tk,其中xk是变元,tk是项,且xk不在tk中出现,则置: Fk+1=Fk{tk/xk} σK+1=σk°{tk/xk} k=k+1 然后转(2)。若不存在这样的xk和tk则算法停止。 算法终止,F的最一般合一不存在。 求取最一般合一的例子 例如,设 F={P(a,x,f(g(y))),P(z,f(z),f(u))} 求其最一般合一。 令F0=F, σ0=ε。 F0中有两个表达式,所以σ0不是最一般合一。 差异集:D0={a,z}。代换: {a/z} F1= F0 {a/z}={P(a,x,f(g(y))),P(a,f(a),f(u))} 。 σ1=σ0°{a/z}={a/z} D1={x,f(a)} 。代换: {f(a)/x} F2=F1{f(a)/x}={P(a,f(a),f(g(y))),P(a,f(a),f(u))} 。 σ2=σ1°{f(a)/x}={a/z,f(a)/x} D2={g(y),u} 。代换: {g(y)/u} F3=F2{g(y)/u}={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))} 。 σ3=σ2°{g(y)/u}={a/z,f(a)/x,g(y)/u} 4.1.5 冲突消解策略 冲突:多个知识都匹配成功。 正向推理: 多条产生式前件都与已知事实匹配成功 逆向推理: 多条规则后件都和同一个假设匹配成功 冲突消解的基本思想都是对知识进行排序。 几种冲突消解策略 按针对性排序 优先选用针对性强的产生式规则。 按已知事实的新鲜性排序 优先选用与较多新事实匹配的规则。 按匹配度排序 在不确定性匹配中,计算两个知识模式的相似度(匹配度),并对其排序,相似度高的规则先推。 按领域问题特点排序 按上下文限制排序 把规则按照下上文分组,并只能选取组中的规则。 按冗余限制排序 冗余知识越少的规则先推。 按条件个数排序 条件少的规则先推。 4.2 自然演绎推理 从一组已知为真的事实出发,直接运用经典逻辑的推理规则推出结论的过程,称为自然演绎推理。其中,基本的推理规则是P规则、T规则、假言推理、拒取式推理等。 假言推理的一般形式 拒取式推理的一般形式 P规则:在推理的任何步骤都可以引入前提。 T规则:推理时,如果前面步骤中有一个或者多个公式永真蕴含公式S,则可把S引入推理过程中。 4.3 归结演绎推理 定理证明即证明P→Q(?P∨Q)的永真性。根据反证法,只要证明其否定(P∧?Q) 不可满足性即可。 海伯伦(Herbrand)定理为自动定理证明奠定了理论基础;鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。 4.3.1 子句 在谓词逻辑中,把原子谓词公式及其否定统称为文字。如:P(x), ?P(x,f(x)), Q(x,g(x)) 定义4.5: 任何文字的析取式称为子句。 例如: P(x)∨Q(x), ?P(x,f(x))∨Q(x,g(x)) 定义4.6: 不包含任何文字的子句称为空子句。 子句集 (1) 合取范式:C1 ∧C2 ∧C3… ∧Cn (2) 子句集: S= {C1 ,C2 ,C3… ,Cn} (3)任何谓词公式F都可通过等价关系及推理规则化为相应的子句集S。 把谓词公式化成子句集的步骤(1) 1. 利用等价关系消去“→”和“?” 例如公式 可等价变换成 2. 利用等价关系把“?”移到紧靠谓词的位置上 上式经等价变换后 3. 重新命名变元,使不同量词约束的变元有不同的名字 上式经变换后 把谓词公式化成子句集的步骤(2) 4. 消去存在量词 a.存在量词不出现在全称量词的辖域内,则只要用一个新的个体常量替换受该量词约束的变元。 b.存在量词位于一个或者多个全称量词的辖域内,此时要用Skolem函数f(x1,x2,…,xn)替换受该存在量词约束的变元。 上式中存在量词(?y)及(?z)都位于(?x)的辖域内,所以需要用Skolem函数替换,设替换y和z的Skolem函数分别是f(x)和g(x),则替换后得到 5. 把全称量词全部移到公式的左边 把谓词公式化成子句集的步骤(3) 6. 利用等价关系把公式化为Skolem标准形 Skolem标准形的一般形式是 其中,M是子句的合取式,称为Skolem标准形的母式。 上式化为Skolem标准形后得到 7. 消去全称量词 8. 对变元更名,使不同子句中的变元不同名 上式化为 9. 消去合取词,就得到子句集 子句集的性质 (1)子句集中子句之间是合取关系。 (2)子句集中的变元受全称量词的约束。 子句集的意义 子句集S的不可满足性:对于任意论域中的任意 一个解释,S中的子句不能同时取得线 设有谓词公式F,其子句集为S,则F不可满足的充要条件是S不可满足。 要证明P→Q永真,只需证明公式F=(P∧?Q)永假,即S不可满足。

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

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