第五章基于谓词的逻辑推理(新)(精品).ppt

《第五章基于谓词的逻辑推理(新)(精品).ppt》由会员分享，可在线阅读，更多相关《第五章基于谓词的逻辑推理(新)(精品).ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 基于谓词的逻辑推理 谓词逻辑亦称为经典逻辑推理,含命题逻辑与一阶谓词逻辑推理,其真值只有“真”和“假”两种，因此它是一种精确推理，或称为确定性推理。1第五章 基于谓词的逻辑推理 l 5.1 基本概念基本概念l 5.2 归结原理归结原理l 5.3 与与/或形演绎推理或形演绎推理2第五章 基于谓词的逻辑推理l 5.1 基本概念l 5.2 归结原理l 5.3 与/或形演绎推理 5.1.1 推理概念 5.1.2 推理方式及其分类 5.1.3 推理中的控制策略 5.1.4 模式匹配 5.1.5 谓词逻辑中的演绎 推理方法3第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理 按照某种策略由已知的知

2、识/判断推出另一知识/判断的思维过程。含两种判断：1、已知的判断：KB中知识及关于问题的已知事实。2、由已知判断推出的新判断，即推理的结论。推理是由程序实现，称为推理机。基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理 5.1.1 推理概念4第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理1、按照推理的途径分：1）演绎推理：从已知的判断出发，通过演绎推出结论，即结论就蕴含在已知的判断中，上一般到个别的推理。2）归纳推理：从个别到一般的推理，含不完全归纳推理和完全归纳推理。3）默认推理：亦称缺省推理。在知识不完全的情况下假设某些条件已经具备所进行的推理。5.1.2 推理方式及其分

3、类基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理5第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2、按照知识的确定性分：1）确定性推理：亦称精确性推理，知识、结论都是精确的，其真值或为“真”，或为“假”。2）不确定性推理：推理时用的知识不是精确的，其结论也不完全是肯定的，其真值是介于“真”与“假”之间。5.1.2 推理方式及其分类基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理6第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3、按照知识是否单调性分：1）单调性推理：随着推理的向前推进及新知识的加入，推出 的结论呈单调增加的趋势。2）非单调性推理：新知识的加

4、入，不仅没有加强已推出的结论，反而否定它，使得推理再回到前面的某一步，重新开始。5.1.2 推理方式及其分类基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理7第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理4、是否有启发性分：1）启发式推理2）非启发式推理 5.1.2 推理方式及其分类基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理8第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理1、推理路线：亦推理策略。初态到目态所启用的知识形成了一个推理链，称之为推理路线。2、推理方向：即推理的驱动方式。1）正向推理：亦称数据驱动推理、前件推理。以初始证据作为出发点。2）反

5、向推理：亦称目标驱动推理、后件推理。以假设结论作为出发点。5.1.3 推理中的控制策略基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理9第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3）双向推理：亦称混合推理。正向、反向推理结合起来。3、求解策略：指推理是求一个解，还是求所有解以及最优解等。4、限制策略：防止无穷的推理。5、冲突消解策略6、搜索策略 5.1.3 推理中的控制策略基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理10第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理对于两个知识模式的比较与耦合，即它们是否完全一致/近似一致。如：命题公式 谓词公式 语

6、义网络等1、可匹配的：两者完全一致/近似一致。否则为不可匹配。2、只有模式匹配，才能从KB中选出适当的知识，进而推理。3、确定性匹配/完全匹配/精确匹配：两知识模式完全一致，或经过变量代换完全一致。5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理11第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理4、变量代换：无论是确定性匹配还是不确定匹配，在进行匹配时一般都需要进行变量的代换。定义1：代换形如：t1/x1，t2/x2，t n/x n 的有限集合。其中：t1，t2，t n是项；x1，x2，x n是互不相同的变元；t i /x i是表示用t i代换x i，不允

7、许t i与x i相同，也不允许变元x i循环地出现在另一个t j中。5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理12第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例如：a/x,f(b)/y,w/z 是一个代换；但是 g(y)/x,f(x)/y 不是一个代换，如将其改成 g(x)/y,f(x)/y 就是一个代换，5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理13第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理定义2：设代换形如：=t1/x1，t2/x2，t n/x n 是一个代换，F 是一个公式，把 F 中出现的所有

8、x i同时换为t i（i=1,2,n）得到一个新的公式G，叫做 F 在代换 下的例式，记为G=。注：一个公式的任何例式都是其逻辑结论，即例：若则：5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理14第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理定义3：设代换形如：=t1/x1，t2/x2，t n/x n =u1/y1，u2/y2，un/y n 是两个代换，则此复合也是一个代换，它是从t1 /x1，t2 /x2，t n /x n，u1/y1，u2/y2 un/y n 中删去如下两中元素：t i /x i ，u i/y i 剩下的元素构成的集合，记为如 。5.

9、1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理15第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例如：若 =f(y)/x，z/y =a/x，b/y，y/z 则：=f(y)/x，y/z 因为：=f(y)/x，z /y，=f(b)/x，y/y，a/x，b/y，y/z 5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理16第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理定义4：设有一个公式集 若存在一个代换 ，可使 则称 为 F 的一个合一，且称F是可合一的。定理：F 的合一一般是不唯一的。5.1.4 模式匹配基本概念基本概念归结

10、原理归结原理与与/或形演绎推理或形演绎推理17第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例如：若则F的一个合一为：因为：5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理18第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理定义5：设 是一个公式集 F 的一个合一，若对任一个合一 都存在一个代换 ，可使 则称 一个最一般的合一。定理：最一般的合一是唯一的。5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理19第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理定义6：设公式集 从各 的第一个元素开始同时向右比较，用这些项的差

11、异部分组成一个集合，这个集合叫差异集，亦称为分歧集。例：F1：P（x,y,z）F2：P（x,f(a),h(b)）则：D1=（y,f(a)）D2=（z,h(b)）5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理20第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理 置 k=0,F k=F,k=。这里，F是欲求其最一般合一的公式集，是空代换，它表示不做代换。若 F k只含一个表达式，则算法停止，k 就是最一般的合一。求 F k 的差异集 D k;若D k中存在元素xk和tk，其中 xk 是变元，其中 tk 是项，且 xk 不在 tk 中出现，则置 k+1=k tk

12、/xk,Fk+1=F k tk/xk ,k=k+1,转步骤(2)算法停止，F 的最一般合一不存在。(若 F 是可合一的，算法总是在步停止)5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理21第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例：求公式集 F=P(a,x,f(g(y),P(z,f(z),f(u)的最一般合一。解：k=0 时 （1）令k=0;F 0=F;0=;因为F 0中含有两个表达式，所以0不是最一般的合一。（2）差异集D0=a,z;5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理22第五章第五章 基于谓词的逻辑

13、推理基于谓词的逻辑推理例：求公式集 F=P(a,x,f(g(y),P(z,f(z),f(u)的最一般合一。解：k=1 时 （3）1=0 a/z=a/z,F 1=P(a,x,f(g(y),P(a,f(a),f(u);（4）D1=x,f(a);5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理23第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例：求公式集 F=P(a,x,f(g(y),P(z,f(z),f(u)的最一般合一。解：k=2 时 （5）2=1 f(a)/x=a/z,f(a)/x,F 2=F 1 f(a)/x=P(a,f(a),f(g(y),P(a,f(

14、a),f(u);（6）D2=g(y),u ;5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理24第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例：求公式集 F=P(a,x,f(g(y),P(z,f(z),f(u)的最一般合一。解：k=3 时 （7）3=2 g(y)/u =a/z,f(a)/x,g(y)/u,F 3=F 2 g(y)/u =P(a,f(a),f(g(y);因为F 3 只含一个表达式，所以3最一般的合一，即a/z,f(a)/x,g(y)/u 是最一般的合一。5.1.4 模式匹配基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理25第

15、五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理以P63例5.1为例进行介绍谓词逻辑的演绎推理方法。小结：小结：推理、推理方法及其分类，推理中的控制策略，模式 匹配（含代换、例式、复合、差异集、最一般合一及其结论。谓词逻辑的演绎推理方法。基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理 5.1.5 谓词逻辑的演绎推理方法26第五章 基于谓词的逻辑推理l 5.1 基本概念l 5.2 归结原理l 5.3 与/或形演绎推理 5.2.1 子句 5.2.2 归结原理27第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理1、概念定义1：原子谓词公式及其否定统称为文字。定义2：任何文字的析取式

16、称为子句。定义3：不含任何文字的子句称为空子句。注：空子句是永假的，不可满足的。定义4：由子句构成的集合称为子句集。注：约定各子句间的关系是合取合取关系，子句集中出现的变元均受全称量词均受全称量词的约束。5.2.1 子句基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理28第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2、谓词公式化为子句集的步骤Step1:利用下列等价关系消去谓词公式中的“”、“”：PQ PQP Q (P Q)(P Q)Step2:利用等价关系把“”移到紧靠谓词的位置上，减小否定的辖域。Step3:变量标准化。重新命名变元名，使不同的量词约束的变元有不同的名字

17、。5.2.1 子句基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理29第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2、谓词公式化为子句集的步骤Step4:消去存在量词。这里分两种情况：1）存在量词不出现在全称量词的辖域内，此时只要用一个新的个体常量替换受该存在量词约束的变元就可消去存在量词。2）存在量词位于一个或多个全称量词的辖域内，此时需要用Skolem函数替换受该存在量词约束的变元，然后才能消去存在量词。5.2.1 子句基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理30第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2、谓词公式化为子句集的步骤Step

18、5:化为前束型，把全称量词全部移动到公式的左边。Step6:利用等价关系 P(QR)(PQ)(PR)把公式化为Skolem标准形。Skolem标准形的一般形式是 其中，M是子句的合取式，称为Skolem标准形的母式。Step7:消去全称量词。这时公式中所有的变量都是全称量词量化的变量。5.2.1 子句基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理31第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2、谓词公式化为子句集的步骤Step8:对变元更名，使不同子句中的变元不同名。Step9:消去合取词，即用子句集合表示。5.2.1 子句基本概念基本概念归结原理归结原理与与/或形演绎

19、推理或形演绎推理32第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3、谓词公式与相应子句集合的等价性 如果谓词公式是不可满足的，则其子句集也一定是不可满足的，反之亦然。两者在不可满足的意义上两者上等价的。下述定理不保证了它的正确性。定理：设有谓词公式定理：设有谓词公式F，其标准形的子句集为其标准形的子句集为S，则则F不可满不可满足的充要条件是足的充要条件是S不可满足。不可满足。5.2.1 子句基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理33第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3、谓词公式与相应子句集合的等价性例：求谓词公式的子句集:解：5.2.1 子句基本概

20、念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理34第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3、谓词公式与相应子句集合的等价性例：求谓词公式的子句集:解：5.2.1 子句基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理35第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3、谓词公式与相应子句集合的等价性例：求谓词公式的子句集:解：5.2.1 子句基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理36第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3、谓词公式与相应子句集合的等价性例：求谓词公式的子句集:解：5.2.1 子句基本概念基本概念归结原理

21、归结原理与与/或形演绎推理或形演绎推理37第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理1、思想1）用于实现定理证明，方法是利用反证法。即 若欲证明：则变为证明：为假，即不可满足。2）在证明 不可满足时，转化为证明其子句集不可满足。3）子句集中各子句间是合取关系，只要有一个子句不可满足即可。而空子句是不可满足的。即只要有空子句则不可满足。4）检查是子句集中是否含有空子句。若有即可得证。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理38第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2、方法1）否定Q，即可得证 Q。2）在证明 Q 并入谓词公式集P中，得

22、到P，Q。3）将P，Q 化为子句集S。4）利用归结原理对S进行归结，反复直到有空子句。即可得证 永真。若无空子句，则 不成立。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理39第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3、命题逻辑中的归结原理定义1：若P是原子谓词公式，则称P与 P 为互补文字。定义2：设C1与C2是子句集中的任意两个子句，C1与C2是，那么从C1和C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1 和C2为C12的亲本子句。5.2.2 归结原理基本概

23、念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理40第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例1：设C1=P Q R，C2=Q S，这里L1=Q，L2=Q，通过归结可得 C12=P R S 例2：设C1=P，C2=P，这里L1=P，L2=P，通过归结可得 C12=NIL NIL代表空子句。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理41第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理定理：归结式C12是其亲本子句C1和C2的逻辑结论。推论1：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1和C2得到的新子句集

24、S1，则由S1的不可满足性可推出原子句集S的不可满足性，即 S1的不可满足性=S的不可满足性推论1：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12加入S中，得到的新子句集S2，则S与S2在不可满足的意义上是等价的，即 S1的不可满足性 S的不可满足性 5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理42第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例1：证明(P Q)Q=P，解：5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理43第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例2：证明S=(P Q

25、，P Q，P Q，P Q)是不可满足的子句集。解：5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理44第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理4、谓词逻辑中的归结原理 在谓词逻辑中，由于子句中含有变元，所以不像命题逻辑那样可直接消去互补文字，要先用最一般合一对变元进行代换，然后才可归结。定义1：设C1与C2是两个设有相同变元的子句，L1和L2 分别是C1和C2的文字，若 是L1和L2 的最一般的合一，则称为C1和C2的二元归结式，L1和L2 称为归结上的文字。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理45第五章

26、第五章 基于谓词的逻辑推理基于谓词的逻辑推理例：设C1=P(x)Q(a)，C2=P(b)R(x)由于C1和C2有相同的变元，不符合定义1的要求。为了进行归结，需要修改C2中的变元的名字，令C2=P(b)R(y)。此时，L1=P(x)，L2=P(b)。L1 与 L2 最一般的合一 。则 5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理46第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理4、谓词逻辑中的归结原理定义2：若子句C中一些带有相同符号的文字有最一般合一存在，它是 ，则称 为C的因子。若 是单元子句，则称它上C的单元因子。定义3：若子句C1和C2的归结式

27、是下列二元归结式之一：1）C1和C2的二元归结式；2）C1和C2的因子 二元归结式；3）C1的因子 和C2二元归结式；5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理47第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理4）C1的因子 和C2的因子 二元归结式。注：l若在参加归结的子句中含有可合一的文字，则应先求出其因子，即对文字先合一。l归结式是谓词逻辑的亲本子句的逻辑结论，即C1C2=C12。l具有不可满足的保持性。l归结原理从不可满足的意义上说是完备的。l归结方法不唯一。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理4

28、8第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例1：设C1=P(x)P(f(a)Q(a)，C2=P(y)R(b)5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理49第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例2：5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理50第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例2：5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理51第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理5、用归结原理求解问题的答案 归结原理除了可用于定理证明外，还

29、可用来求解问题的答案，其思想与定理证明类似。求解的一般步骤详见P70。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理52第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理6、归结策略 归结过程中的盲目性以及产生的大量无用子句耗费了时间和空间，降低了效率。为此，人们研究研究出多种归结策略，含两大类：1）删除策略：把子句集中无用子句删除掉，缩小寻找范围，减少比较次数。l纯文字删除法：将与之无关的纯文字删除。l重言式删除法：子句中同时包含的互补文字对删除。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理53第五章第五章 基于谓词的

30、逻辑推理基于谓词的逻辑推理6、归结策略l包孕删除法：设有子句C1和C2，如果存在一个代换 ，使得 ，则称C1包孕于C2。2）限制策略l支持集策略：每一次归结时，亲本子句中至少应有一个是由目标公式的否定所得到的子句或者是它们的后裔。可以证明：支持集策略是完备的，即若子句集是不可满足的，则由支持集策略一定可以归结出空子句。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理54第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2）限制策略l线性输入策略：参加归结的两个子句中必须至少有一个是初始子句集中的子句。先行输入策略可限制生成归结式的数量，具有简单、高效的优点，但

31、是它是不完备的。l单文字子句策略：参加归结的子句中至少有一个是单文字子句。归结式比亲本子句含有较少的文字，有利于朝空子句的方向前进，但是是不完备的。l祖先过滤策略：参加归结的子句满足下列任意条件：5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理55第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2）限制策略至少有一个是初始子句集中的子句；如果两个子句都不是初始子句集中的子句，则一个应是另一个的祖先。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理56第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理小结:子句、化子句集的步骤

32、，命题逻辑与谓词逻辑的归结原理，及涉及的相关定义、定理等。用归结原理进行逻辑证明和问题求解，归结策略。5.2.2 归结原理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理57第五章 基于谓词的逻辑推理l 5.1 基本概念l 5.2 归结原理l 5.3 与/或形演绎推理 5.3.1 与/或形正向演绎推理 5.3.2 与/或形逆向演绎推理58第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理在前述的归结演绎推理中存在以下点：l要将所有的表达式转换为子句，虽然在逻辑上等价，但变换导致丧失了有用的信息（如 被 取代）。l转换表达式为子句时，降低了求解效率。在下述的与/或形演绎推理中：l尽

33、量采用表达式原来的形式。l将有关问题的知识和信息分成规则和事实。引言：基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理59第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理 从已知事实出发，正向地使用F规则（蕴含式）进行演绎推理，直至得到某个目标公式的一个终止条件为止。在这种推理中，对已知事实、F规则及目标公式的表示形式都有一定的要求，如果不是所要求的形式，就需要进行变换。5.3.1 与/或形正向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理60第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理1、事实表达式的与/或形变换及其树形表示 要求已知事实用不含蕴

34、含符号“”的与/或形表示。把一个公式化为与/或形的步骤与化子句集类似，只是不必把公式化为子句的合取形式，也不能消去公式中的合取词。具体为：1）利用等价公式 消去公式中的“”；2）利用德摩根律及量词转换律把“”移到紧靠谓词的位置。3）重新命名变元名，使不同量词约束的变元有不同的名字。5.3.1 与/或形正向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理61第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理1、事实表达式的与/或形变换及其树形表示4）引入Skolem函数消去存在量词；5）消去全称量词，且使各主要合取式中的变元不同名。例如对如下事实表达式：5.3.1 与/或形

35、正向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理62第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理1、事实表达式的与/或形变换及其树形表示事实表达式的与/或形可用一棵与/或树表示出来。5.3.1 与/或形正向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理63第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2、F规则表示形式 格式：LW说明：1）L为单文字，W为与/或形。2）L和W中的所有变量都是全称量词量化的，默认的全称量词作用于整个蕴含式。3）各条规则中的变量各不相同，且规则中的变量与事实表达 5.3.1 与/或形正向演绎推理基本概念基

36、本概念归结原理归结原理与与/或形演绎推理或形演绎推理64第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理式中的变量也不相同。4）规则作用于叶结点（即文字节点），且一个节点可应用多个规则。5.3.1 与/或形正向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理65第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理 5.3.1 与/或形正向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理66第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3、目标公式的表示形式 要求为文字的析取形式，若不满足要求就需转换。当一个目标文字和与/或途中的一个文字匹配时，将

37、该目标文字和与/或图中的文字用匹配弧“=”相连。表示目标文字的节点称为目标节点。当推理产生的与/或图包括一个在目标节点上结束的解图时，系统便成功结束。5.3.1 与/或形正向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理67第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理4、推理示例 主要用于定理证明。其一般过程是：从已知事实的与/或树出发，利用F规则推出欲证明的目标公式。例如：设已知事实为 AB F规则为：r1：ACB ，r1：B EG欲证明的公式为 CG 5.3.1 与/或形正向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理68第五章第五章

38、 基于谓词的逻辑推理基于谓词的逻辑推理方法一：用与/或图所得结论为 CG。5.3.1 与/或形正向演绎推理CGACDEGBABAB基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理69第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理方法二：用归结演绎推理来证明。已知事实，F规则及目标的否定，所形成的字句集如下：5.3.1 与/或形正向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理70第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理方法二：用归结演绎推理来证明。已知事实，F规则及目标的否定，所形成的字句集如下：5.3.1 与/或形正向演绎推理基本概念基本概

39、念归结原理归结原理与与/或形演绎推理或形演绎推理71第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理 与/或形逆向演绎推理是从待证明的问题(目标)出发,通过逆向地使用蕴含式(B规则)进行演绎推理,直到得到包含已知事实的终止条件为止。5.3.2 与/或形逆向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理72第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理1、目标表达式：为无蕴含的任何与/或形式 在将目标表达式转换成与/或表达式时注意：其变换过程与正向演绎推理中对已知事实的变换相似。用存在量词约束的变元的Skolem函数替换由全称量词约束的相应变元，并且消去全称量词。消

40、去存在量词。目标表达式中尚存在的变量都认为是存在量词量化的变量。同一变量名不出现在不同的主要析取式中。5.3.2 与/或形逆向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理73第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理例：目标表达式 5.3.2 与/或形逆向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理74第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理对应的与/或图为：5.3.2 与/或形逆向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理75第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理2、B规则的表示形式

41、 WL 说明：其中W为任一与/或形公式，L文字。若给定的表达式不满足B规则的规定形式，就需转换（转换方法类似于F规则中的转换）。如：W(L1 L2)这样的蕴含式可化为两个B规则：W L1 ,W L2 5.3.2 与/或形逆向演绎推理基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理76第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理3、已知事实的表示形式 WL 在逆向演绎推理中，要求已知事实是文字的合取式。推理示例：P81的例题5.17。小结：介绍了与/或形的正向和逆向演绎推理，特别注意其所 要求的标准形式，若不符合要进行变换。5.3.2 与/或形逆向演绎推理基本概念基本概念归结

42、原理归结原理与与/或形演绎推理或形演绎推理77第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理第五章总结：第五章总结：逻辑推理是指按逻辑规则进行推理，有经典逻辑推理和经典逻辑推理和非经典逻辑推理两大类非经典逻辑推理两大类。经典逻辑推理经典逻辑推理主要是指命题逻辑推命题逻辑推理和一阶谓词逻辑推理理和一阶谓词逻辑推理，由于其真值只有“真”和“假”这两个，因而经典逻辑推理中的已知事实以及推出的结论都是已知事实以及推出的结论都是精确的，或者为精确的，或者为“真真”，或者为，或者为“假假”，所以又称为经典逻辑推理为精确推理或确定性推理。非经典逻辑推理非经典逻辑推理是指除经典逻辑外的那些逻辑，如多值逻辑

43、、模糊逻辑、概率逻辑等，它是一种不确定性推理。基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理78第五章第五章 基于谓词的逻辑推理基于谓词的逻辑推理第五章总结：第五章总结：本章讨论了三个部分的内容：第一部分第一部分讨论了关于推理的一般概念，包括什么是推理、推理的方式及分类，推理的推理、推理的方式及分类，推理的控制策略、模式匹配控制策略、模式匹配等。人类有多种思维方式，相应也有多种推理方式，归结推理和演绎推理是用得较多的两种。第二第二部分部分归结原理是人们应用反证法的思想把关于永真性的证明把关于永真性的证明转换为不可满足的证明转换为不可满足的证明。其以子句集为背景开展研究，本部分介绍了子句及子句集子句及子句集的有关概念，然后把它们应用到演绎推理之中。第三部分第三部分与/或演绎推理不需要把有关知识转化为子句集，它把领域知识及已知事实分别用蕴含式及与把领域知识及已知事实分别用蕴含式及与/或形表或形表示示出来，然后运用蕴含式进行演绎推理运用蕴含式进行演绎推理，从而证明某个目标公式。基本概念基本概念归结原理归结原理与与/或形演绎推理或形演绎推理79