(1.3)--第3章 确定性推理人工智能导论.ppt

第三章第三章 确定性推理方法确定性推理方法Deterministic Deterministic Reasoning MethodsReasoning MethodsPPT模板下载： 目录目录CONTENTS自然演绎推理一二谓词公式化为子句集的方法三推理的基本概念鲁宾逊归结原理四归结反演五一、推理的基本概念医疗专家系统推理知识专家的经验、医学常识初始证据病人的症状、化验结果证据中间结论1.1推理的定义（1）演绎推理(deductive reasoning):一般 个别三段论式（三段论法）足球运动员的身体都是强壮的；高波是一名足球运动员；所以，高波的身体是强壮的。1.演绎推理、归纳推理、默认推理（大前提）（小前提）（结 论）一、推理的基本概念1.2推理的方式及分类（2）归纳推理(inductive reasoning):个别 一般 完全归纳推理（必然性推理）不完全归纳推理（非必然性推理）检查全部产品合格该厂产品合格完全归纳推理随机抽查样品合格该厂产品合格不完全归纳推理1.演绎推理、归纳推理、默认推理一、推理的基本概念1.2推理的方式及分类（3）默认推理（default reasoning，缺省推理）知识不完全的情况下假设某些条件已经具备所进行的推理。结 论 A 成立 B 成立？（默认B成立）鸟笼要有盖子 制造鸟笼 鸟会飞？（默认成立）1.演绎推理、归纳推理、默认推理一、推理的基本概念1.2推理的方式及分类 2.确定性推理、不确定性推理似然推理近似推理或模糊推理不确定性推理（概率论）（模糊逻辑）（1）确定性推理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。（2）不确定性推理：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。一、推理的基本概念1.2推理的方式及分类 3.单调推理、非单调推理（1）单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。（2）非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。默认推理是非单调推理 基于经典逻辑的演绎推理 一、推理的基本概念1.2推理的方式及分类4.启发式推理、非启发式推理 启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。目标：在脑膜炎、肺炎、流感中选择一个 产生式规则 r1：脑膜炎 r2：肺 炎 r3：流 感 启发式知识：“脑膜炎危险”、“目前正在盛行流感”。一、推理的基本概念1.2推理的方式及分类1.3推理的方向一、推理的基本概念n 正向推理（事实驱动推理）:已知事实 结论 基本思想（1）从初始已知事实出发，在知识库KB 中找出当前可适用的知识，构成可适用知识集 KS。（2）按某种冲突消解策略从 KS 中选出一条知识进行推理，并将推出的新事实加入到数据库 DB 中作为下一步推理的已知事实，再在 KB 中选取可适用知识构成KS。（3）重复（2），直到求得问题的解或 KB 中再无可适用的知识。1.正向推理一、推理的基本概念1.3推理的方向1.正向推理一、推理的基本概念1.3推理的方向n 实现正向推理需要解决的问题：l 确定匹配（知识与已知事实）的方法。l 按什么策略搜索知识库。l 冲突消解策略。正向推理简单，易实现，但目的性不强，效率低。1.正向推理一、推理的基本概念1.3推理的方向n逆向推理（目标驱动推理）n以某个假设目标作为出发点。n基本思想n选定一个假设目标。n寻找支持该假设的证据，若所需的证据都能找到，则原假设成立；若无论如何都找不到所需要的证据，说明原假设不成立的；为此需要另作新的假设。2.逆向推理一、推理的基本概念1.3推理的方向2.逆向推理一、推理的基本概念1.3推理的方向n 逆向推理需要解决的问题：u如何判断一个假设是否是证据？u当导出假设的知识有多条时，如何确定先选哪一条？u一条知识的运用条件一般都有多个，当其中的一个经验证成立后，如何自动地换为对另一个的验证？u.逆向推理：目的性强，利于向用户提供解释，但选择初始目标时具有盲目性，比正向推理复杂。2.逆向推理一、推理的基本概念1.3推理的方向n 正向推理:盲目、效率低。逆向推理:若提出的假设目标不符合实际，会降低效率。正反向混合推理：（1）先正向后逆向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；（2）先逆向后正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。3.混合推理一、推理的基本概念1.3推理的方向一、推理的基本概念1.3推理的方向双向推理：正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰碰头头”的一种推理。已知事实 假设目标 反向推理 正向推理4.双向推理中间结论证 据一、推理的基本概念1.3推理的方向1.4冲突消解 已知事实与知识的三种匹配情况：（1）恰好匹配成功（一对一）；（2）不能匹配成功；（3）多种匹配成功（一对多、多对一、多对多）冲突消解一、推理的基本概念多种冲突消解策略：（1）按规则的针对性排序。（2）按已知事实的新鲜性排序。（3）按匹配度排序。（4）按条件个数排序。r1:IF A1 AND A2 THEN H1r2:IF A1 AND A2 AND A3 AND A4 THEN H2一、推理的基本概念1.4冲突消解二、自然演绎推理自然演绎推理：从一组已知为真的事实出发，运用经典逻辑的推理规则推出结论的过程。推理规则：P 规则、T 规则、假言推理、拒取式推理、.n 假言推理：P,PQ Q n“如果x是金属，则x能导电”,“铜是金属”推出“铜能导电”n 拒取式推理：PQ,Q Pn“如果下雨，则地下就湿”,“地上不湿”推出“没有下雨”p前提引入规则（P规则）p结论引入规则（T规则）p置换规则p假言推理规则p化简规则p假言三段论规则 p析取三段论规则p附加规则 p拒取式规则p构造性二难推理规则 p破坏性二难推理规则 p合取引入规则 p全称量词消去规则（固化）p存在量词消去规则（固化）p全称量词引入规则p存在量词引入规则推理规则二、自然演绎推理例1 已知事实：（1）凡是容易的课程小王(Wang)都喜欢；（2）C 班的课程都是容易的；（3）ds 是 C 班的一门课程。求证：小王喜欢 ds 这门课程。证明：定义谓词：EASY(x)：x 是容易的 LIKE(x,y)：x 喜欢 y C(x)：x 是 C 班的一门课程 已知事实和结论用谓词公式表示：（1）()(EASY(x)LIKE(Wang,x)（2）()(C(x)EASY(x)（3）C(ds)（4）LIKE(Wang,ds)二、自然演绎推理 应用推理规则进行推理（1）()（EASY(x)LIKE(Wang,x)（5）EASY(z)LIKE(Wang,z)全称固化（2）()(C(x)EASY(x)（6）C(y)EASY(y)全称固化 所以（3）C(ds),（6）C(y)EASY(y)（7）EASY(ds)P规则及假言推理 所以 （7）EASY(ds),（5）EASY(z)LIKE(Wang，z)（4）LIKE(Wang,ds)T规则及假言推理二、自然演绎推理优点n表达定理证明过程自然，易理解。n拥有丰富的推理规则，推理过程灵活。n便于嵌入领域启发式知识。缺点n易产生组合爆炸，得到的中间结论一般呈指数形式递增。二、自然演绎推理三、谓词公式化为子句集的方法反证法：，当且仅当 ，即 Q为 P 的逻辑结论，当且仅当 是不可满足的。定理：Q 为 ，的逻辑结论，当且仅当 是不可满足的。思路：定理 不可满足 子句集不可满足 鲁宾逊归结原理 p 原子（atom）谓词：一个不能再分解的命题。p 文字（literal）：原子谓词公式及其否定。p ：正文字，：负文字。p 子句（clause）：任何文字的析取式。任何文字本身也都是子句。p 空子句（NIL）：不包含任何文字的子句。p 子句集：由子句构成的集合。空子句是永假的，不可满足的。三、谓词公式化为子句集的方法例1 将下列谓词公式化为子句集。三、谓词公式化为子句集的方法例1 将下列谓词公式化为子句集。解：（1）消去谓词公式中的“”和“”符号三、谓词公式化为子句集的方法例1 将下列谓词公式化为子句集。解：（1）消去谓词公式中的“”和“”符号三、谓词公式化为子句集的方法例1 将下列谓词公式化为子句集。解：（1）消去谓词公式中的“”和“”符号双重否定律 德.摩根律 量词转换律 （2）把否定符号 移到紧靠谓词的位置上三、谓词公式化为子句集的方法例1 将下列谓词公式化为子句集。解：（1）消去谓词公式中的“”和“”符号（2）把否定符号 移到紧靠谓词的位置上三、谓词公式化为子句集的方法例1 将下列谓词公式化为子句集。解：（1）消去谓词公式中的“”和“”符号（2）把否定符号 移到紧靠谓词的位置上（3）变量标准化 三、谓词公式化为子句集的方法例1 将下列谓词公式化为子句集。解：（1）消去谓词公式中的“”和“”符号（2）把否定符号 移到紧靠谓词的位置上（3）变量标准化 三、谓词公式化为子句集的方法（4）消去存在量词 a.存在量词不出现在全称量词的辖域内。b.存在量词出现在一个或者多个全称量词的辖域内。三、谓词公式化为子句集的方法（4）消去存在量词 a.存在量词不出现在全称量词的辖域内。b.存在量词出现在一个或者多个全称量词的辖域内。Skolem化：用Skolem函数代替每个存在量词量化的变量的过程。三、谓词公式化为子句集的方法（4）消去存在量词 a.存在量词不出现在全称量词的辖域内。b.存在量词出现在一个或者多个全称量词的辖域内。三、谓词公式化为子句集的方法（4）消去存在量词 a.存在量词不出现在全称量词的辖域内。b.存在量词出现在一个或者多个全称量词的辖域内。（5）化为前束形 前束形=（前缀）母式三、谓词公式化为子句集的方法（4）消去存在量词 a.存在量词不出现在全称量词的辖域内。b.存在量词出现在一个或者多个全称量词的辖域内。（5）化为前束形 前束形=（前缀）母式（前缀）：全称量词串。母式：不含量词的谓词公式。三、谓词公式化为子句集的方法（6）化为 Skolem 标准形（7）略去全称量词（8）消去合取词，把母式用子句集表示（9）子句变量标准化 三、谓词公式化为子句集的方法例2 将下列谓词公式化为子句集。（1）消去蕴含符号（2）把否定符号移到每个谓词前面（3）变量标准化（4）消去存在量词，设y的函数是f(x)，则 三、谓词公式化为子句集的方法例2 将下列谓词公式化为子句集。（续）（5）化为前束形（6）化为标准形（7）略去全称量词（8）消去合取词，把母式用子句集表示（9）子句变量标准化 三、谓词公式化为子句集的方法四、鲁宾逊归结原理 p 鲁宾逊归结原理（消解原理）的基本思想：p检查子句集 S 中是否包含空子句，若包含，则 S 不可满足。p若不包含，在 S 中选择合适的子句进行归结，一旦归结出空子句，就说明 S 是不可满足的。p子句集中子句之间是合取关系，只要有一个子句不可满足，则子句集就不可满足。4.1命题逻辑中的归结原理（基子句的归结）定定义义3.1（归归结结）：设C1与C2是子句集中的任意两个子句，如果 C1中的文字L1与C2中的文字L2互补，那么从C1和 C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12，这一过程称为归结。C12称为C1与C2的归结式，C1与C2的称为C12的亲本子句。四、鲁宾逊归结原理（归结）（归结）四、鲁宾逊归结原理 4.1命题逻辑中的归结原理（基子句的归结）推论1：设C1与C2是子句集S 中的两个子句，C12是它们的归结式，若用C12代替C1与C2后得到新子句集S1，则由S1不可满足性可推出原子句集S 的不可满足性，即：推论2：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若C12加入原子句集S，得到新子句集S2，则S与S2在不可满足的意义上是等价的，即：定理3.2：归结式C12是其亲本子句C1与C2的逻辑结论。即如果 C1与C2为真，则C12为真。的不可满足性 S 的不可满足性。S 2的不可满足性 S的不可满足性。四、鲁宾逊归结原理 4.1命题逻辑中的归结原理（基子句的归结）4.2谓词逻辑中的归结原理（含有变量的子句的归结）例例2 2：？定义定义 3.23.2：设是 两个没有相同变元的子句，和 分别是 中的文字，若 是 的最一般合一，则称 为 的二元归结式。最一般合一最一般合一四、鲁宾逊归结原理 例3 设：求其二元归结式。得：解：令 选 则四、鲁宾逊归结原理 4.2谓词逻辑中的归结原理（含有变量的子句的归结）o对于谓词逻辑，归结式是其亲本子句的逻辑结论。o对于一阶谓词逻辑，即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结演绎；若从子句集存在一个到空子句的演绎，则该子句集是不可满足的。o如果没有归结出空子句，则既不能说 S 不可满足，也不能说 S 是可满足的。四、鲁宾逊归结原理 五、归结反演应用归结原理证明定理的过程称为归结反演。归结步骤将已知前提表示为谓词公式F将待证明的结论表示为谓词公式 ，并得到其否定把公式集 化为子句集S应用归集原理对子句集进行归结，每次归结式都并入S中。反复进行。若出现空子句，则停止归结，证明为真。例1：某公司招聘工作人员，A，B，C三人应试，经面试后公司表示如下想法：（1）三人至少录取一人；（2）如果录取A而不录取B，则一定录取C；（3）如果录取B，则一定录取C。求证：公司一定录取C。五、归结反演 把要求证的结论用谓词公式表示出来并否定，得：（4）把上述公式化成子句集：五、归结反演应用归结原理进行归结：（5）（1）与（2）归结（6）（3）与（5）归结（7）（4）与（6）归结 五、归结反演应用归结原理进行归结：（5）（1）与（2）归结（6）（3）与（5）归结（7）（4）与（6）归结 五、归结反演例2 已知：规则1：任何人的兄弟不是女性；规则2：任何人的姐妹必是女性。事 实：Mary 是 Bill 的姐妹。求证：Mary 不是 Tom 的兄弟。五、归结反演例2 已知：规则1：任何人的兄弟不是女性；规则2：任何人的姐妹必是女性。事 实：Mary 是 Bill 的姐妹。求证：Mary 不是 Tom 的兄弟。证明：定义谓词 brother(x,y):x 是 y 的兄弟 sister(x,y):x 是 y 的姐妹 woman(x):x 是女性五、归结反演证明：将规则与事实用谓词公式表示：把要求证的结论用谓词公式表示出来并否定，得：（1）（2）（3）（4）五、归结反演证明：将规则与事实用谓词公式表示：把要求证的结论用谓词公式表示出来并否定，得：把上述公式化成子句集：（1）（2）（3）（4）五、归结反演证明：将规则与事实用谓词公式表示：把要求证的结论用谓词公式表示出来并否定，得：把上述公式化成子句集：（1）（2）（3）（4）将子句集进行归结：五、归结反演用归结反演求解问题p 应用归结原理求解问题的步骤：（1）已知前提 F 用谓词公式表示，并化为子句集 S；（2）把待求解的问题 Q 用谓词公式表示，并否定 Q，再与 ANSWER 构成析取式（Q ANSWER）；（3）把（Q ANSWER）化为子句集，并入到子句集 S中，得到子句集 ；（4）对 应用归结原理进行归结；（5）若得到归结式 ANSWER，则答案就在 ANSWER 中。五、归结反演 例例3 已知：王（Wang）先生是小李（Li）的老师。：小李与小张（Zhang）是同班同学。：如果 与 是同班同学，则 的老师也是 的老师。求：小张的老师是谁？五、归结反演解：定义谓词：是 的老师。：与 是同班同学。把已知前提表示成谓词公式：把目标表示成谓词公式，并把它否定后与 ANSWER 析取：五、归结反演 把上述公式化为子句集：（1）（2）（3）（4）（5）（1）与（3）归结（6）（4）与（5）归结（7）（2）与（6）归结五、归结反演(1)(3)(5)(4)(2)(6)(7)五、归结反演