第三章 确定性推理方法

1、第第 3 章章 确定性推理方法确定性推理方法知识知识 智能智能？ 知识知识 推理推理智能智能！5个房间的问题（给福尔摩斯出的问题）个房间的问题（给福尔摩斯出的问题）5个不同颜色的房间，每间有个不同国籍的人，每人有自己喜欢的饮个不同颜色的房间，每间有个不同国籍的人，每人有自己喜欢的饮料，香烟和宠物，已知信息料，香烟和宠物，已知信息：1.英国人住在红房间里；英国人住在红房间里；2.西班牙人有一条狗；西班牙人有一条狗；3.挪威人住在左边第一个房间里；挪威人住在左边第一个房间里；4.黄房间的人在抽库尔斯牌香烟；黄房间的人在抽库尔斯牌香烟；5.抽切斯菲尔德牌香烟的人是养了一只狐狸的人的邻居；抽切斯菲尔德

2、牌香烟的人是养了一只狐狸的人的邻居；6.挪威人住在蓝房间隔壁；挪威人住在蓝房间隔壁；7.抽温斯顿牌香烟的人有一只蜗牛；抽温斯顿牌香烟的人有一只蜗牛；8.抽幸运牌香烟的人喝橘子汁；抽幸运牌香烟的人喝橘子汁；9.乌克兰人喝茶；乌克兰人喝茶；10.日本人抽国会牌香烟；日本人抽国会牌香烟；11.抽库尔斯牌香烟的人的房间在有匹马的房间隔壁；抽库尔斯牌香烟的人的房间在有匹马的房间隔壁；12.绿房间的人喝咖啡；绿房间的人喝咖啡；13.中间房间的人喝牛奶中间房间的人喝牛奶14.绿房间的人在白房间的隔壁绿房间的人在白房间的隔壁F问题：问题： 哪个房间的人喝水？斑马在哪个房间？哪个房间的人喝水？斑马在哪个房间？房

3、间号房间号12345颜色颜色国籍国籍香烟香烟饮料饮料宠物宠物3.挪威人住在左边第一个房间挪威人住在左边第一个房间6.挪威人住在蓝房间旁边挪威人住在蓝房间旁边13.中间房间的人喝牛奶中间房间的人喝牛奶挪威人挪威人蓝色蓝色牛奶牛奶12.绿房间的人喝咖啡绿房间的人喝咖啡14.绿房间的人在白房间的隔壁绿房间的人在白房间的隔壁绿色绿色白色白色咖啡咖啡1.英国人住在红色的房间英国人住在红色的房间红色红色英国人英国人黄色黄色4.黄房间的人抽库尔斯牌香烟黄房间的人抽库尔斯牌香烟11.抽库尔斯牌烟的房间在有匹马的房间的隔壁抽库尔斯牌烟的房间在有匹马的房间的隔壁库尔斯牌库尔斯牌马马水水2.西班牙人有一条狗西班牙人

4、有一条狗8.抽幸运牌香烟的人喝橘子汁抽幸运牌香烟的人喝橘子汁9.乌克兰人喝茶乌克兰人喝茶10.日本人抽国会牌香烟日本人抽国会牌香烟橘子汁是谁喝的？橘子汁橘子汁狗狗幸运牌幸运牌西班牙人西班牙人茶茶乌克兰人乌克兰人日本人日本人国会牌国会牌7.抽温斯顿牌香烟的人有一只蜗牛抽温斯顿牌香烟的人有一只蜗牛温斯顿温斯顿蜗牛蜗牛切斯菲尔德切斯菲尔德5.抽切斯菲尔德香烟的人的抽切斯菲尔德香烟的人的是养了一只狐狸的人的邻居是养了一只狐狸的人的邻居狐狸狐狸斑马斑马8.抽幸运牌香烟的人喝橘子汁抽幸运牌香烟的人喝橘子汁9.乌克兰人喝茶乌克兰人喝茶用用Prolog语言编的程序，一秒钟都不到就知道了语言编的程序，一秒钟都不

5、到就知道了答案答案, ,不过它的推理过程和人的完全不一样；不过它的推理过程和人的完全不一样；Prolog：Programm Logic ( (逻辑程序设计语言逻辑程序设计语言) )推理方法：确定性推理推理方法：确定性推理：（演绎推理）：（演绎推理） （1 1）谓词公式化为子句集谓词公式化为子句集 （2 2）鲁宾逊归结原理（消解原理）鲁宾逊归结原理（消解原理） （3 3）归结反演）归结反演机器证明机器证明归归结结演演绎绎推推理理第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法 3.4 海伯伦定理

6、海伯伦定理 3.5 鲁宾逊归结原理鲁宾逊归结原理 3.6 归结反演归结反演 3.7 应用归结反演求解问题应用归结反演求解问题 3.1 推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1.4 冲突消解策略冲突消解策略推 理 机数 据 库知 识 库专 家病 人医疗专家系统医疗专家系统3.1.1 推理的定义某 种 策 略已 知 事 实（ 证 据 ）知 识结 论知识知识专家的经验、医学常识专家的经验、医学常识初始初始证据证据病人的症状、化验结果病人的症状、化验结果证据证据中间结论中间结论推理：推理：3.1 推理的基本概念3.

7、1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1.4 冲突消解策略冲突消解策略（1）演绎推理演绎推理 (deductive reasoning) : 一般一般 个别个别 三段论式三段论式（三段论法）（三段论法） 足球运动员的身体都是强壮的足球运动员的身体都是强壮的 ； 高波是一名足球运动员；高波是一名足球运动员； 所以，高波的身体是强壮的。所以，高波的身体是强壮的。3.1.2 推理方式及其分类1.演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（ 大前提大前提 ）（ 小前提小前提 ）（ 结结 论论 ）3.1.2 推理方式及其

8、分类1.演绎推理、归纳推理、默认推理（按推出结论的途径演绎推理、归纳推理、默认推理（按推出结论的途径）（2）归纳推理归纳推理 (inductive reasoning): 个别个别 一般一般 完全归纳推理（完全归纳推理（必然性推理）必然性推理） 不完全归纳推理不完全归纳推理（非必然性推理）（非必然性推理）检查全部产品合格检查全部产品合格该厂产品合格该厂产品合格完全归纳推理完全归纳推理检查全部样品合格检查全部样品合格该厂产品合格该厂产品合格不完全归纳推理不完全归纳推理 3.1.2 推理方式及其分类（3）默认推理默认推理（default reasoning，缺省推理），缺省推理）n 知识不完全知识

9、不完全的情况下假设的情况下假设某些条件已经具备某些条件已经具备所进行的推理所进行的推理。 结结 论论 A 成立成立 B 成立？成立？（在不能证明（在不能证明B不成立的情况下，默认不成立的情况下，默认B成立）成立）鸟笼要鸟笼要有盖子有盖子 制造鸟笼制造鸟笼 鸟会飞？鸟会飞？（正常情况下默认鸟会飞成立）（正常情况下默认鸟会飞成立）1.演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理3.1.2 推理方式及其分类 2. 确定性推理、不确定性推理（按知识的确定性）确定性推理、不确定性推理（按知识的确定性）似然推理近似推理或模糊推理不确定性推理（概率论）（模糊逻辑）（1）确定性推理确定性推理：推理

10、时所用的知识与证据都是确定的，推推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。出的结论也是确定的，其真值或者为真或者为假。 （2）不确定性不确定性推理推理：推理时所用的知识与证据不都是确定的，推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。推出的结论也是不确定的。X：鸟：鸟 X：会飞：会飞3.1.2 推理方式及其分类 3. 单调推理、非单调推理（按靠近结论的方式）单调推理、非单调推理（按靠近结论的方式） （1）单调推理单调推理：随着推理向前推进及新知识的加入：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。，推出的结论越来越接近最终目

11、标。 （2）非单调推理非单调推理：由于新知识的加入，不仅没有加：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。面的某一步，重新开始。 默认推理是非单调推理默认推理是非单调推理 基于经典逻辑的演绎推理基于经典逻辑的演绎推理 X：企鹅：企鹅X：不会飞：不会飞X：不会飞：不会飞3.1.2 推理方式及其分类4启发式推理、非启发式推理（是否运用启发式知识）启发式推理、非启发式推理（是否运用启发式知识） 启发性知识启发性知识：与问题有关且能加快推理过程、提高搜索效率与问题有关且能加快推理过程、提高搜索效率的知识。的

12、知识。 目标：在脑膜炎、肺炎、流感中选择一个目标：在脑膜炎、肺炎、流感中选择一个 产生式规则产生式规则 r1：脑膜炎：脑膜炎 r2：肺：肺 炎炎 r3：流：流 感感 启发式知识：启发式知识：“脑膜炎危险脑膜炎危险”、“目前正在盛行流目前正在盛行流感感”。3.1 推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1.4 冲突消解策略冲突消解策略3.1.3 推理的方向正向推理逆向推理( 反向推理)双向推理混合推理推理方向3.1.3 推理的方向n 正向推理（事实驱动推理）正向推理（事实驱动推理）: 已知事实已知事实 结论结论

13、 基本思想基本思想（1）从初始已知事实出发，在知识库）从初始已知事实出发，在知识库KB中找出当前可适用的中找出当前可适用的知识，构成可适用知识集知识，构成可适用知识集KS。（2）按某种冲突消解策略从）按某种冲突消解策略从KS中选出一条知识进行推理，并中选出一条知识进行推理，并将推出的新事实加入到数据库将推出的新事实加入到数据库DB中作为下一步推理的已知事中作为下一步推理的已知事实，再在实，再在KB中选取可适用知识构成中选取可适用知识构成KS 。（3）重复（）重复（2），直到求得问题的解或），直到求得问题的解或KB中再无可适用的知中再无可适用的知识。识。1. 正向推理正向推理3.1.3 推理的方

14、向n 实现正向推理需要解决的问题：实现正向推理需要解决的问题：l 确定匹配（知识与已知事实）的方法。确定匹配（知识与已知事实）的方法。l 按什么策略搜索知识库。按什么策略搜索知识库。l 冲突消解策略。冲突消解策略。 正向推理简单，易实现，但目的性不强，效正向推理简单，易实现，但目的性不强，效率低。率低。1. 正向推理正向推理3.1.3 推理的方向n 逆向推理（目标驱动推理）：以逆向推理（目标驱动推理）：以某个假设目标某个假设目标作为出发点。作为出发点。 基本思想：基本思想： 选定一个假设目标。选定一个假设目标。 寻找支持该假设的证据，若所需的证据都能找到，则原假设寻找支持该假设的证据，若所需的

15、证据都能找到，则原假设成立；若无论如何都找不到所需要的证据，说明原假设不成立成立；若无论如何都找不到所需要的证据，说明原假设不成立的；为此需要另作新的假设。的；为此需要另作新的假设。 主要优点：不必使用与目标无关的知识，目的性强，同时它主要优点：不必使用与目标无关的知识，目的性强，同时它还有利于向用户提供解释。还有利于向用户提供解释。 主要缺点：起始目标的选择有盲目性。主要缺点：起始目标的选择有盲目性。2. 逆向推理逆向推理3.1.3 推理的方向n 逆向推理需要解决的问题：逆向推理需要解决的问题：u 如何判断一个假设是否是证据？如何判断一个假设是否是证据？u 当导出假设的知识有多条时，如何确定

16、先选哪一条？当导出假设的知识有多条时，如何确定先选哪一条？ u一条知识的运用条件一般都有多个，当其中的一个经一条知识的运用条件一般都有多个，当其中的一个经验证成立后，如何自动地换为对另一个的验证？验证成立后，如何自动地换为对另一个的验证？u . 逆向推理：目的性强，利于向用户提供解释，但选择初始逆向推理：目的性强，利于向用户提供解释，但选择初始目标时具有盲目性，比正向推理复杂。目标时具有盲目性，比正向推理复杂。2. 逆向推理逆向推理3.1.3 推理的方向n 正向推理正向推理: 盲目、效率低。盲目、效率低。 逆向推理逆向推理: 若提出的假设目标不符合实际，会降低效率。若提出的假设目标不符合实际，

17、会降低效率。 正反向混合推理：正反向混合推理：（1）先正向后逆向：先正向后逆向：先进行正向推理，帮助选择某个目标，即先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；提高其可信度；（2）先逆向后正向：先逆向后正向：先假设一个目标进行逆向推理，然后再利先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论用逆向推理中得到的信息进行正向推理，以推出更多的结论。3. 混合推理混合推理n 双向推理双向推理：正向推理与逆向推理同时进行，且在推理过程中正向推理与逆向

18、推理同时进行，且在推理过程中的某一步骤上的某一步骤上“碰头碰头”的一种推理。的一种推理。已知事实已知事实 假设目标假设目标3.1.3 推理的方向4. 双向推理双向推理中间结论中间结论证证 据据3.1 推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1.4 冲突消解策略冲突消解策略3.1.4 冲突消解策略 已知事实与知识的三种匹配情况已知事实与知识的三种匹配情况：（1）恰好匹配成功（一对一）；）恰好匹配成功（一对一）；（2）不能匹配成功；）不能匹配成功；（3）多种匹配成功多种匹配成功（一对多、多对一、多对多）（一对多、

19、多对一、多对多）冲突消解冲突消解3.1.4 冲突消解策略 多种冲突消解策略：多种冲突消解策略：（1）按针对性排序）按针对性排序（2）按已知事实的新鲜性排序）按已知事实的新鲜性排序（3）按匹配度排序）按匹配度排序（4）按条件个数排序）按条件个数排序（5）按上下文限制排序）按上下文限制排序（6）按冗余限制排序）按冗余限制排序（7）根据领域问题的特点排序）根据领域问题的特点排序r1: IF A1 AND A2 THEN H1r2: IF A1 AND A2 AND A3 AND A4 THEN H2第3章 确定性推理方法 3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3

20、 谓词公式化为子句集的方法谓词公式化为子句集的方法 3.4 海伯伦定理海伯伦定理 3.5 鲁宾逊归结原理鲁宾逊归结原理 3.6 归结反演归结反演 3.7 应用归结反演求解问题应用归结反演求解问题 27 定义定义1 设P与Q是两个谓词公式，D是它们共同的个体域，若对D上的任何一个解释，P与Q都有相同的真值，则称公式P和Q在D上是等价的。如果D是任意个体域，则称P和Q是等价的，记为P Q 。常用的等价式见P32（4）德.摩根律(De. Morgen) （8）连接词化规律（蕴含、等价等值式）连接词化规律（蕴含、等价等值式） （10）量词转换律）量词转换律 3.2 自然演绎推理自然演绎推理自然演绎推理

21、：从一组已知为真的事实出发，运用从一组已知为真的事实出发，运用经典经典逻辑的推理规则逻辑的推理规则推出结论的过程。推出结论的过程。28 定义定义2 对于谓词公式对于谓词公式P与与Q，如果，如果PQ永真，则称公式永真，则称公式P永永真蕴含真蕴含Q，且称，且称Q为为P的逻辑结论，称的逻辑结论，称P为为Q的前提，记为的前提，记为P Q。常用的永真蕴含式见常用的永真蕴含式见P33（3）假言推理）假言推理 （4）拒取式推理）拒取式推理 （5）假言三段论）假言三段论 3.2 自然演绎推理29谓词逻辑的其他推理规则谓词逻辑的其他推理规则1. P规则：在推理的任何步骤上都可引入前提。规则：在推理的任何步骤上都

22、可引入前提。2. T规则：在推理过程中，如果前面步骤中有一个或多个规则：在推理过程中，如果前面步骤中有一个或多个公式永真蕴含公式公式永真蕴含公式S，则可把，则可把S引入推理过程中引入推理过程中。3. CP规则：如果能从任意引入的命题规则：如果能从任意引入的命题R和前提集合中推出和前提集合中推出S来，则可从前提集合推出来，则可从前提集合推出R S来。来。3.2 自然演绎推理30 所有的人都是会死的，所有的人都是会死的， 因为诸葛亮是人，因为诸葛亮是人， Human（Zhugeliang） 所以诸葛亮是会死的。所以诸葛亮是会死的。 Die（Zhugeliang） 1 P规则规则 2 Human（Z

23、hugeliang） P规则规则 1, 2 Die（Zhugeliang） T规则规则 QQPP , )3()()(xDiexHumanx)()(xDiexHumanx3.2 自然演绎推理31谓词逻辑的其他推理规则谓词逻辑的其他推理规则：4.4.反证法：反证法：PQ ，当且仅当当且仅当 PQF，即即Q为为P的逻辑结的逻辑结论，当且仅当论，当且仅当PQ是不可满足的是不可满足的。 定理：定理：Q为为P1,P2,Pn 的逻辑结论的逻辑结论，当且仅当当且仅当 P1 P2, Pn Q 是不可满足的是不可满足的。3.2 自然演绎推理推理规则推理规则：P规则、规则、T规则、假言推理、拒取式推理规则、假言推理

24、、拒取式推理 3.2 自然演绎推理n 假言推理假言推理： P, PQ Q n “如果如果x是金属，则是金属，则x能导电能导电” , “铜是金属铜是金属” 推出推出 “铜能导铜能导电电” n 拒取式推理拒取式推理： PQ, Q Pn “如果下雨，则地下就湿如果下雨，则地下就湿” , “地上不湿地上不湿” 推出推出 “没有下雨没有下雨”（1） 如果下雨，则地上是湿的（如果下雨，则地上是湿的（ PQ ）；（2）没有下雨（）没有下雨（P ）；）； （3）所以，地上不湿（所以，地上不湿（Q ）。 3.2 自然演绎推理 错误错误1否定前件否定前件： PQ, P Q（1）如果行星系统是以太阳为中心的，则金星

25、会显示出位相变如果行星系统是以太阳为中心的，则金星会显示出位相变化（化（ PQ ）；（2）金星显示出位相变化（金星显示出位相变化（ Q ）；）；（3） 所以，行星系统是以太阳为中心（所以，行星系统是以太阳为中心（ P ）。 错误错误2肯定后件肯定后件： PQ, Q P3.2 自然演绎推理 例例1 已知事实：已知事实： （1）凡是容易的课程小王凡是容易的课程小王( Wang )都喜欢；都喜欢； （2）C 班的课程都是容易的；班的课程都是容易的； （3）ds 是是 C 班的一门课程。班的一门课程。 求证：小王喜欢求证：小王喜欢 ds 这门课程。这门课程。3.2 自然演绎推理 证明：证明：定义谓词定

26、义谓词： EASY ( x )：x 是容易的是容易的 LIKE ( x, y )：x 喜欢喜欢 y C ( x )：x 是是 C 班的一门课程班的一门课程 已知事实和结论用谓词公式表示已知事实和结论用谓词公式表示： ( x) ( EASY ( x ) LIKE ( Wang, x ) ) ( x) ( C ( x ) EASY ( x ) C ( ds ) LIKE ( Wang, ds ) 3.2 自然演绎推理 应用推理规则进行推理应用推理规则进行推理： ( x)（EASY ( x ) LIKE ( Wang, x ) EASY (z) LIKE ( Wang, z ) 全称固化全称固化 (

27、 x ) (C ( x ) EASY ( x ) C ( y ) EASY ( y ) 全称固化全称固化 所以 C (ds), C (y) EASY (y) EASY (ds) P规则及假言推理规则及假言推理 所以 EASY (ds), EASY (z) LIKE (Wang，z) LIKE ( Wang, ds ) T规则及假言推理规则及假言推理 优点：优点：n表达定理证明过程自然，易理解。表达定理证明过程自然，易理解。n拥有丰富的推理规则，推理过程灵活。拥有丰富的推理规则，推理过程灵活。n便于嵌入领域启发式知识便于嵌入领域启发式知识。3.2 自然演绎推理 缺点缺点：易产生组合爆炸，得到的中

28、间结论一般呈指易产生组合爆炸，得到的中间结论一般呈指数形式递增。数形式递增。归归结结演演绎绎推推理理第3章 确定性推理方法 3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法 3.4 海伯伦定理海伯伦定理 3.5 鲁宾逊归结原理鲁宾逊归结原理 3.6 归结反演归结反演 3.7 应用归结反演求解问题应用归结反演求解问题 3.3 谓词公式化为子句集的方法 原子（原子（atom）谓词公式：）谓词公式： 一个不能再分解的命题。一个不能再分解的命题。 文字（文字（literal）：原子谓词公式及其否定。）：原子谓词公式及其否定

29、。 ：正文字，：正文字， ：负文字。：负文字。（封闭世界假设）（封闭世界假设） 子句（子句（clause）：任何文字的）：任何文字的析取式析取式。任何文字本身也都是子句。任何文字本身也都是子句。 空子句（空子句（NIL）：不包含任何文字的子句。）：不包含任何文字的子句。 子句集：由子句子句集：由子句构成的集合。构成的集合。PP)(,()(,(),()(xgxQxfxPxQxP空子句是永假的，不可满足的。空子句是永假的，不可满足的。3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法)()()()(),()()()()(xBxPxxQyxSyxQxPx 例例2 将下列将下列谓词公式化为子句集

30、。谓词公式化为子句集。解：（1）消去谓词公式中的“ ”和“ ”符号,QPQP)()(QPQPQP)()()()(),()()()()(xBxPxxQyxSyxQxPx （2）把否定符号）把否定符号” ” 移到紧靠谓词的位置上移到紧靠谓词的位置上双重否定律双重否定律 德德.摩根律摩根律 量词转换律量词转换律 PP )(,)(QPQPQPQP)(PxPx)()(,)()(PxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx （3）变量标准化）变量标准化 )()()()(yPyxPx),()()()(yPyxPx)()()()(),()()()()(wBwPwxQyxSyx

31、QxPx （4）消去存在量词）消去存在量词 a. 存在量词不出现在全称量词的辖域内。存在量词不出现在全称量词的辖域内。 b. 存在量词出现存在量词出现在一个或者多个全称量词的辖域内。在一个或者多个全称量词的辖域内。Skolem1212()()()() (, ).)nnxxxy P x xxyy 对对于于一一般般情情况况存存在在量量词词 的的函函数数为为),(21nxxxfySkolem化：用化：用Skolem函数代替每个存在量词量化的变量的过程。函数代替每个存在量词量化的变量的过程。 （5）化为前束形）化为前束形 前束形前束形=（前缀）（前缀）母式母式（前缀）：全称量词串。（前缀）：全称量词串

32、。 母式母式：不含量词的谓词公式。：不含量词的谓词公式。 3.3 谓词公式化为子句集的方法)()()()()(,()()()(wBwPwxQxfxSxQxPx)( xfy )()()()(,()()()(wBwPxQxfxSxQxPwx)()()()(),()()()()(wBwPwxQyxSyxQxPx 3.3 谓词公式化为子句集的方法（6）化为）化为 Skolem 标准形标准形 Skolem 标准形：M：子句的合取式，称为Skolem标准形的母式。 Mxxxn)()(21)()()(RPQPRQP)()()(RPQPRQP（7）略去全称量词）略去全称量词 （8）消去合取词）消去合取词 （9

33、）子句变量标准化）子句变量标准化 )()()(,()()()()(wBwPxfxSxQxPxQwx)()()(,()()()(wBwPxfxSxPxQwx)()()(,()()(wBwPxfxSxPxQ)()(wBwP),(xQ),(,()(xfxSxP),(xQ),(,()(yfySyP)()(wBwP3.3 谓词公式化为子句集的方法 例例3 将下列谓词公式化为子句集。将下列谓词公式化为子句集。解：（解：（1）消去蕴含符号）消去蕴含符号（2）把否定符号移到每个谓词前面）把否定符号移到每个谓词前面 （3）变量标准化）变量标准化 （4）消去存在量词，）消去存在量词，),(),()(),()(yx

34、RyxQyyxPyx),(),()(),()()(yxRyxQyyxPyx),(),()(),()(yxRyxQyyxPyx),(),()(),()(zxRzxQzyxPyx)(),(xgzxfy )(,()(,()(,()(xgxRxgxQxfxPx 例例3 将下列将下列谓词公式化为子句集。（续）谓词公式化为子句集。（续）（5）化为前束形）化为前束形( (没变化没变化) ) （6）化为标准形）化为标准形 （7）略去全称量词）略去全称量词 （8）消去合取词，把母式用子句集表示）消去合取词，把母式用子句集表示 （9）子句变量标准化）子句变量标准化 3.3 谓词公式化为子句集的方法)(,()(,(

35、)(,()(xgxRxgxQxfxPx)(,()(,()(,()(,()(xgxRxfxPxgxQxfxPx)(,()(,()(,()(,(xgxRxfxPxgxQxfxP)(,()(,(,)(,()(,(xgxRxfxPxgxQxfxP)(,()(,(,)(,()(,(ygyRyfyPxgxQxfxP3.3 谓词公式化为子句集的方法 练习练习: 将下列谓词公式化为子句集。将下列谓词公式化为子句集。解：（解：（1）消去蕴含符号）消去蕴含符号（2）把否定符号移到每个谓词前面）把否定符号移到每个谓词前面 （3）变量标准化）变量标准化 （4）消去存在量词，）消去存在量词，),(),(),()()(y

36、xRyxQyxPyx),(),(),()()(yxRyxQyxPyx),(),(),()()(yxRyxQyxPyx)(xfy )(,()(,()(,()(xfxRxfxQxfxPx),(),(),()()(yxRyxQyxPyx 例例3 将下列将下列谓词公式化为子句集。（续）谓词公式化为子句集。（续）（5）化为前束形）化为前束形 （6）化为标准形）化为标准形 （7）略去全称量词）略去全称量词 （8）消去合取词，把母式用子句集表示）消去合取词，把母式用子句集表示 （9）子句变量标准化）子句变量标准化 3.3 谓词公式化为子句集的方法)(,()(,()(,()(,()(xfxRxfxQxfxRx

37、fxPx)(,()(,()(,()(,()(xfxRxfxQxfxRxfxPx)(,()(,()(,()(,(xfxRxfxQxfxRxfxP)(,()(,(),(,()(,(yfyRyfyQxfxRxfxP归归结结演演绎绎推推理理第3章 确定性推理方法 3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法 3.4 海伯伦定理海伯伦定理 3.5 鲁宾逊归结原理鲁宾逊归结原理 3.6 归结反演归结反演 3.7 应用归结反演求解问题应用归结反演求解问题 定理：定理： PQ当且仅当当且仅当P Q F 即即 Q为为 P 的逻辑

38、的逻辑结论，当且仅当结论，当且仅当P Q 是不可满足的。是不可满足的。 定理：定理：Q 为为 ， ， 的逻辑结论，当且仅的逻辑结论，当且仅当当 是不可满足的。是不可满足的。1P2PnPQPPPn)(213.5 鲁宾逊归结原理定理定理 : 谓词公式不可满足的谓词公式不可满足的充要条件充要条件是其子句集不可满足。是其子句集不可满足。谓词公式谓词公式不可满足性不可满足性子句集子句集不可满足性不可满足性？3.5 鲁宾逊归结原理思路：定理思路：定理 不可满足不可满足 子句集不可满足子句集不可满足 海伯伦定理海伯伦定理 鲁宾逊归结原理鲁宾逊归结原理QP QP3.5 鲁宾逊归结原理3.5 鲁宾逊归结原理u

39、鲁宾逊归结原理（消解原理）鲁宾逊归结原理（消解原理）的基本思想：基本思想：p检查子句集检查子句集 S 中是否包含空子句，若包含，则中是否包含空子句，若包含，则 S 不可满足。不可满足。p若不包含，在若不包含，在 S 中选择合适的子句进行归结，一旦归结出空中选择合适的子句进行归结，一旦归结出空子句，就说明子句，就说明 S 是不可满足的。是不可满足的。u 子句集中子句之间是合取关系，只要有一个子句不可满足，子句集中子句之间是合取关系，只要有一个子句不可满足， 则子句集就不可满足。则子句集就不可满足。 3.5 鲁宾逊归结原理1. 命题逻辑中的归结原理（基子句的归结）命题逻辑中的归结原理（基子句的归结

40、） 归结归结：设：设C1与与C2是子句集中的任意两个子句，如果是子句集中的任意两个子句，如果 C1中的文中的文字字L1与与 C2中的文字中的文字L2互补，那么从互补，那么从C1和和 C2中分别消去中分别消去L1和和L2，并将二个子句中余下的部分，并将二个子句中余下的部分析取析取，构成一个新子句，构成一个新子句C12 。C12 称为称为C1 和和C2 的的归结式归结式;C1 和和C2 为为C12的亲本子句。的亲本子句。3C1C2C（归结）（归结）12C（归结）（归结）123C123CPQCQRCP 设设，例例： P QPR Q R P Ru 推论推论1：设：设C1与与C2是子句集是子句集S中的两

41、个子句，中的两个子句，C12是它们的归结是它们的归结式，若用式，若用C12代替代替C1与与C2后得到新子句集后得到新子句集S1，则由，则由S1不可满足性不可满足性可推出原子句集可推出原子句集S的不可满足性，即：的不可满足性，即： u 推论推论2：设设C1与与C2是子句集是子句集S中的两个子句，中的两个子句，C12是它们的归结式，是它们的归结式，若若C12 加入原子句集加入原子句集S，得到新子句集，得到新子句集S1，则，则S与与S1在不可满足的意在不可满足的意义上是等价的，即：义上是等价的，即： u 定理定理1：归结式：归结式C12是其亲本子句是其亲本子句C1与与C2的逻辑结论。即如果的逻辑结论

42、。即如果 C1与与C2为真，则为真，则C12为真。为真。3.5 鲁宾逊归结原理S1的不可满足性的不可满足性 S 的不可满足性的不可满足性S1的不可满足性的不可满足性 S的不可满足性的不可满足性3.5 鲁宾逊归结原理2. 谓词逻辑中的归结原理（含有变量的子句的归结）谓词逻辑中的归结原理（含有变量的子句的归结） )()(1xQxPC)()(2yRaPC/xa)()(1aQaPC)()(2yRaPC)()(12yRaQC？最一般合一最一般合一最一般合一最一般合一例：例：3.5 鲁宾逊归结原理 例例4设设： 求其二元归结式。求其二元归结式。),()(1aQxPC)()(2yRbPC 解：解：令令)()

43、(2yRbPC)()(aQxP)()(yRbP)()(yRaQ/xbC1C2C123.5 鲁宾逊归结原理则得：则得： 解：解：f(a)是个体常项，令是个体常项，令/ )(xaf),()(1afQafPC/ )(yaf求其二元归结式。求其二元归结式。),()()(1xQafPxPC)()(2bRyPC 例例5：设设再令：再令：),()(2bRafPC得：得：),()(1afQafPC),()(2bRafPC)()(12afQbRC3.5 鲁宾逊归结原理注：注：对于谓词逻辑，归结式是其亲本子句的逻辑结论。对于谓词逻辑，归结式是其亲本子句的逻辑结论。 对于一阶谓词逻辑，即若子句集是不可满足的，则必存

44、在对于一阶谓词逻辑，即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结演绎；若从子句集存在一一个从该子句集到空子句的归结演绎；若从子句集存在一个到空子句的演绎，则该子句集是不可满足的。个到空子句的演绎，则该子句集是不可满足的。如果没有归结出空子句，如果没有归结出空子句，则既不能说则既不能说 S 不可满足，也不能不可满足，也不能说说 S 是可满足的。是可满足的。 归归结结演演绎绎推推理理第3章 确定性推理方法 3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法 3.4 海伯伦定理海伯伦定理 3.5 鲁宾逊归结

45、原理鲁宾逊归结原理 3.6 归结反演归结反演 3.7 应用归结反演求解问题应用归结反演求解问题 3.6 归结反演v应用归结原理证明定理的过程称为归结反演。应用归结原理证明定理的过程称为归结反演。v用归结反演证明的步骤是：用归结反演证明的步骤是：（1）将已知前提表示为谓词公式）将已知前提表示为谓词公式F。（2）将待证明的结论表示为谓词公式）将待证明的结论表示为谓词公式Q，并否定得到，并否定得到 Q 。（3）把谓词公式集）把谓词公式集F， Q 化为子句集化为子句集S。（4）应用归结原理对子句集）应用归结原理对子句集S中的子句进行归结，并把每次中的子句进行归结，并把每次 归结得到的归结式都并入到归结

46、得到的归结式都并入到S中。如此反复进行，若出中。如此反复进行，若出 现了现了空子句空子句，则停止归结，此时就证明了，则停止归结，此时就证明了Q为真。为真。3.6 归结反演 例例6 某公司招聘工作人员，某公司招聘工作人员，A，B ，C 三人应试，三人应试，经面试后公司表示如下想法：经面试后公司表示如下想法：（1） 三人中至少录取一人。三人中至少录取一人。（2） 如果录取如果录取 A 而不录取而不录取 B ，则一定录取，则一定录取 C。（3） 如果录取如果录取 B ，则一定录取，则一定录取 C 。 n 求证：公司一定录取求证：公司一定录取 C。 3.6 归结反演v证明：公司的想法用谓词公式表示：证

47、明：公司的想法用谓词公式表示： 。 xxP：录取)( 把要求证的结论用谓词公式表示出来并否定，得：把要求证的结论用谓词公式表示出来并否定，得：)()()(CPBPAP)()()(CPBPAP)()(CPBP（1）（2）（3） （4）)(CP 把上述公式化成子句集：把上述公式化成子句集： （1）)()()(CPBPAP)()()(CPBPAP（2）)()(CPBP（3）)(CP（4）3.6 归结反演P(A) P(B) P(C) P(A) P(B) P(C)P(B) P(C) P(B) P(C)P(C) P(C)NIL应用归结原理进行归结：应用归结原理进行归结： （1）（2）（3）（4）3.6 归

48、结反演归结反演 例例7 已知：已知： 规则规则1：任何人的兄弟不是女性；：任何人的兄弟不是女性； 规则规则2：任何人的姐妹必是女性。：任何人的姐妹必是女性。 事事 实：实：Mary 是是 Bill 的姐妹。的姐妹。 求证：求证： Mary 不是不是 Tom 的兄弟。的兄弟。 证明：定义谓词证明：定义谓词 brother ( x, y ) : x 是是 y 的兄弟的兄弟 sister ( x, y ) : x 是是 y 的姐妹的姐妹 woman ( x ) : x 是女性是女性 证明：将规则与事实用谓词公式表示：证明：将规则与事实用谓词公式表示： 把要求证的结论用谓词公式表示出来把要求证的结论用

49、谓词公式表示出来并否定并否定，得：，得： 把上述公式化成子句集：把上述公式化成子句集： （1）（2）（3）)(),()()(xwomanyxbrotheryx)(),()()(xwomanyxsisteryx),(BillMarysister（4）),(TomMarybrother)(),(1xwomanyxbrotherC)(),(2xwomanyxsisterC),(3BillMarysisterC ),(4TomMarybrotherC 3.6 归结反演归结反演（1）（2）（3）)(),()()(xwomanyxbrotheryx),(BillMarysister)(),()()(xwo

50、manyxbrotheryx),(BillMarysister（1）（2）（3）3.6 归结反演 sisiter(x,y) woman(x)sister(Mary,Bill)woman(Mary) brother(x,y) woman(x) brother(Mary,y)brother(Mary,Tom)NIL =Mary/x =Mary/x 将子句集进行归结：将子句集进行归结： （C2）（C3）（C1）（C4）归归结结演演绎绎推推理理第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 3.7 应用归结原理求解问题 应用归结原理求解问题的步骤：应用归结原理求解问题的步骤：（1）已知前提）已知前提 F 用谓词公式表示，并化为子句集用谓词公式表示，并化为子句集 S ；（3）把（）把（ Q ANSWER） 化为子句集，并入到子句集化为子句集，并入到子句集 S中，中，得到子句集得到子句集 ；S（4）对）对 应用归结原理进行归结；应用归结原理进行归结