《第3章确定性推理方法AI应用3版》由会员分享，可在线阅读，更多相关《第3章确定性推理方法AI应用3版（75页珍藏版）》请在金锄头文库上搜索。
1、Artificial Intelligence Principles and Applications第第 3 章章 确定性推理方法确定性推理方法教材：教材： 王万良王万良人工智能及其应用人工智能及其应用（第（第3版）版） 高等教育出版社，高等教育出版社，2016. 22前面讨论了把知识用某种模式表示出来存储到计算前面讨论了把知识用某种模式表示出来存储到计算机中去。但是，为使计算机具有智能，还必须使它机中去。但是，为使计算机具有智能，还必须使它具有思维能力。推理是求解问题的一种重要方法。具有思维能力。推理是求解问题的一种重要方法。因此，推理方法成为人工智能的一个重要研究课题。因此，推理方法成为
2、人工智能的一个重要研究课题。下面首先讨论关于推理的基本概念，然后着重介绍下面首先讨论关于推理的基本概念，然后着重介绍鲁宾逊归结原理及其在机器定理证明和问题求解中鲁宾逊归结原理及其在机器定理证明和问题求解中的应用。鲁宾逊归结原理使定理证明能够在计算机的应用。鲁宾逊归结原理使定理证明能够在计算机上实现。上实现。第3章确定性推理方法3第第3章章 确定性推理方法确定性推理方法第3章确定性推理方法4归归结结演演绎绎推推理理第3章确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5
3、鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 5归归结结演演绎绎推推理理第3章确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 63.1推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1.4 冲突消解策略冲突消解策略7医疗专家系统医疗专
4、家系统3.1.1推理的定义推理：推理：知识知识专家的经验、医学常识专家的经验、医学常识初始初始证据证据病人的症状、化验结果病人的症状、化验结果证据证据中间结论中间结论83.1推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1.4 冲突消解策略冲突消解策略9（1）演绎推理演绎推理 (deductive reasoning) : 一般一般 个别个别 三段论式三段论式（三段论法）（三段论法） 足球运动员的身体都是强壮的足球运动员的身体都是强壮的 ； 高波是一名足球运动员；高波是一名足球运动员； 所以，高波的身体是强壮的。所
5、以，高波的身体是强壮的。3.1.2推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（ 大前提大前提 ）（ 小前提小前提 ）（ 结结 论论 ）103.1.2推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（2）归纳推理归纳推理 (inductive reasoning): 个别个别 一般一般完全归纳推理（完全归纳推理（必然性推理）必然性推理） 不完全归纳推理不完全归纳推理（非必然性推理）（非必然性推理）检查全部产品合格检查全部产品合格该厂产品合格该厂产品合格完全归纳推理完全归纳推理检查全部样品合格检查全部样品合格该厂产品合格该厂产品合格
6、不完全归纳推理不完全归纳推理113.1.2推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（3）默认推理默认推理（default reasoning，缺省推理），缺省推理）n 知识不完全的情况下假设某些条件已经具备所进行的推理知识不完全的情况下假设某些条件已经具备所进行的推理。 结结 论论 A 成立成立 B 成立？成立？（默认（默认B成立）成立）鸟笼要鸟笼要有盖子有盖子 制造鸟笼制造鸟笼 鸟会飞？鸟会飞？（默认成立）（默认成立）123.1.2推理方式及其分类 2. 确定性推理、不确定性推理确定性推理、不确定性推理似然推理近似推理或模糊推理不确定性推理（概率论）（模
7、糊逻辑）（1）确确定定性性推推理理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。（2）不不确确定定性性推推理理：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。13X：鸟：鸟 X：会飞：会飞 X: 企鹅企鹅 3.1.2推理方式及其分类 3. 单调推理、非单调推理单调推理、非单调推理 （1）单调推理单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。 （2）非单调推理非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。 默认推理是非单调推理默认推理是非单调推理 基于经典逻辑的
8、演绎推理基于经典逻辑的演绎推理 X：不会飞不会飞X：企鹅：企鹅143.1.2推理方式及其分类4启发式推理、非启发式推理启发式推理、非启发式推理 启发性知识启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。 目标：在脑膜炎、肺炎、流感中选择一个目标：在脑膜炎、肺炎、流感中选择一个 产生式规则产生式规则 r1：脑膜炎：脑膜炎 r2：肺：肺 炎炎 r3：流：流 感感 启发式知识：启发式知识：“脑膜炎危险脑膜炎危险”、“目前正在盛行流感目前正在盛行流感”。153.1推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1
9、.4 冲突消解策略冲突消解策略163.1.3推理的方向173.1.3推理的方向n 正向推理（事实驱动推理）正向推理（事实驱动推理）: 已知事实 结论 基本思想基本思想（1）从初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集KS。（2）按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中作为下一步推理的已知事实，再在KB中选取可适用知识构成KS 。（3）重复（2），直到求得问题的解或KB中再无可适用的知识。1. 正向推理正向推理18193.1.3推理的方向n 实现正向推理需要解决的问题：实现正向推理需要解决的问题：l 确定匹配（知识与已知事实）
10、的方法。确定匹配（知识与已知事实）的方法。l 按什么策略搜索知识库。按什么策略搜索知识库。l 冲突消解策略。冲突消解策略。 正向推理简单，易实现，但目的性不强，效率低。正向推理简单，易实现，但目的性不强，效率低。1. 正向推理正向推理203.1.3推理的方向n 逆逆向向推推理理（目目标标驱驱动动推推理理）：以某个假设目标作为出发点。 基本思想：基本思想： 选定一个假设目标。 寻找支持该假设的证据，若所需的证据都能找到，则原假设成立；若无论如何都找不到所需要的证据，说明原假设不成立的；为此需要另作新的假设。 主主要要优优点点：不必使用与目标无关的知识，目的性强，同时它还有利于向用户提供解释。 主
11、要缺点：主要缺点：起始目标的选择有盲目性。2. 逆向推理逆向推理21223.1.3推理的方向n 逆向推理需要解决的问题：逆向推理需要解决的问题：u 如何判断一个假设是否是证据？如何判断一个假设是否是证据？u 当导出假设的知识有多条时，如何确定先选哪一条？当导出假设的知识有多条时，如何确定先选哪一条？ u一一条条知知识识的的运运用用条条件件一一般般都都有有多多个个，当当其其中中的的一一个个经经验证成立后，如何自动地换为对另一个的验证？验证成立后，如何自动地换为对另一个的验证？u . 逆逆向向推推理理：目目的的性性强强，利利于于向向用用户户提提供供解解释释，但但选选择择初初始始目标时具有盲目性，比
12、正向推理复杂。目标时具有盲目性，比正向推理复杂。2. 逆向推理逆向推理233.1.3推理的方向n 正向推理正向推理: 盲目、效率低。 逆向推理逆向推理: 若提出的假设目标不符合实际，会降低效率。 正反向混合推理：正反向混合推理：（1）先先正正向向后后逆逆向向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；（2）先先逆逆向向后后正正向向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。3. 混合推理混合推理242526n 双双向向推推理理：正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰
13、头碰头”的一种推理。已知事实已知事实 假设目标假设目标反向推理反向推理正向推理正向推理3.1.3推理的方向4. 双向推理双向推理中间结论中间结论证证 据据273.1推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1.4 冲突消解策略冲突消解策略283.1.4冲突消解策略 已知事实与知识的三种匹配情况已知事实与知识的三种匹配情况：（1）恰好匹配成功（一对一）；）恰好匹配成功（一对一）；（2）不能匹配成功；）不能匹配成功；（3）多种匹配成功多种匹配成功（一对多、多对一、多对多）（一对多、多对一、多对多）冲突消解冲突消解2
14、93.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 H230第3章确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式
15、化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 31自然演绎推理自然演绎推理：从一组已知为真的事实出发，运用从一组已知为真的事实出发，运用经典经典逻辑的推理规则逻辑的推理规则推出结论的过程。推出结论的过程。推理规则推理规则：P规则、规则、T规则、假言推理、拒取式推理规则、假言推理、拒取式推理 3.2自然演绎推理n 假言推理假言推理： P, PQ Q n “如果如果x是金属，则是金属，则x能导电能导电” , “铜是金属铜是金属” 推出推出 “铜能导铜能导电电” n 拒取式推理拒取式推理： P
16、Q, Q Pn “如果下雨，则地下就湿如果下雨，则地下就湿” , “地上不湿地上不湿” 推出推出 “没有下雨没有下雨”32（1） 如果下雨，则地上是湿的（如果下雨，则地上是湿的（ PQ ）；（2）没有下雨（）没有下雨（P ）；）； （3）所以，地上不湿（所以，地上不湿（Q ）。 3.2自然演绎推理错误错误1否定前件否定前件：PQ, P Q（1）如如果果行行星星系系统统是是以以太太阳阳为为中中心心的的，则则金金星星会会显显示出位相变化（示出位相变化（ PQ ）；（2）金星显示出位相变化（金星显示出位相变化（ Q ）；）；（3） 所以，行星系统是以太阳为中心（所以，行星系统是以太阳为中心（ P ）
17、。 错误错误2肯定后件肯定后件： PQ, Q P333.2自然演绎推理 例例1 已知事实：已知事实： （1）凡是容易的课程小王凡是容易的课程小王( Wang )都喜欢；都喜欢； （2）C 班的课程都是容易的；班的课程都是容易的； （3）ds 是是 C 班的一门课程。班的一门课程。 求证：小王喜欢求证：小王喜欢 ds 这门课程。这门课程。343.2自然演绎推理证明：证明：定义谓词定义谓词： EASY ( x )：x是容易的 LIKE ( x, y )：x喜欢 yC ( x )：x 是 C班的一门课程 已知事实和结论用谓词公式表示已知事实和结论用谓词公式表示：( ) ( EASY ( x ) LI
18、KE ( Wang, x ) ) ( ) ( C ( x ) EASY ( x ) C ( ds ) LIKE ( Wang, ds ) 353.2自然演绎推理 应用推理规则进行推理：应用推理规则进行推理： ( )（EASY ( x ) LIKE ( Wang, x ) EASY (z) LIKE ( Wang, z ) 全称固化全称固化 ( ) (C ( x ) EASY ( x ) C ( y ) EASY ( y ) 全称固化全称固化所以 C (ds), C (y) EASY (y) EASY (ds) P规则及假言推理规则及假言推理 所以 EASY (ds), EASY (z) LIK
19、E (Wang，z) LIKE ( Wang, ds ) T规则及假言推理规则及假言推理36优点优点：n表达定理证明过程自然，易理解。n拥有丰富的推理规则，推理过程灵活。n便于嵌入领域启发式知识。3.2自然演绎推理 缺缺点点：易产生组合爆炸，得到的中间结论一般呈指数形式递增。37归归结结演演绎绎推推理理第3章确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 38归 结
20、演 绎 推 理反证法：反证法： ，当且仅当，即Q为P的逻辑结论，当且仅当是不可满足的。 定理：定理：Q 为为 ， ， 的逻辑结论，当且仅当的逻辑结论，当且仅当 是不可满足的。是不可满足的。39归 结 演 绎 推 理思路：定理思路：定理 不可满足 子句集不可满足 海伯伦定理海伯伦定理 鲁宾逊归结原理鲁宾逊归结原理403.3谓词公式化为子句集的方法 原子（原子（atom）谓词公式）谓词公式：一个不能再分解的命题。文字（文字（literal）：原子谓词公式及其否定。：正文字，：负文字。子句（子句（clause）：任何文字的析取式。任何文字本身也都是子句。 空子句（空子句（NIL）：不包含任何文字的子
21、句。 子句集子句集：由子句构成的集合。空子句是永假的，不可满足的。空子句是永假的，不可满足的。413.3 谓词公式化为子句集的方法谓词公式化为子句集的方法 例例2将下列将下列谓词公式化为子句集。谓词公式化为子句集。 解解：（：（1）消）消去谓词公式中的去谓词公式中的“ ”和和“ ”符号符号 双重否定律双重否定律 德德.摩根律摩根律 量词转换律量词转换律 （2）把否定符号）把否定符号 移到紧靠谓词的位置上移到紧靠谓词的位置上（3）变量标准化）变量标准化 3.3谓词公式化为子句集的方法42 （4）消去存在量词）消去存在量词 a.存在量词不出现在全称量词的辖域内。b.存在量词出现在一个或者多个全称量
22、词的辖域内。Skolem化：用Skolem函数代替每个存在量词量化的变量的过程。（5）化为前束形）化为前束形 前束形=（前缀）母式（前缀）：全称量词串。母式：不含量词的谓词公式。 3.3谓词公式化为子句集的方法433.3谓词公式化为子句集的方法（6）化为）化为 Skolem 标准形标准形 Skolem标准形：M：子句的合取式，称为Skolem标准形的母式。 （7）略去全称量词）略去全称量词 （8）消去合取词）消去合取词 （9）子句变量标准化）子句变量标准化 443.3谓词公式化为子句集的方法 例例3将下列谓词公式化为子句集。将下列谓词公式化为子句集。（1）消去蕴含符号）消去蕴含符号（2）把否定
23、符号移到每个谓词前面）把否定符号移到每个谓词前面 （3）变量标准化）变量标准化 （4）消去存在量词，设）消去存在量词，设y的函数是的函数是f(x)，则，则 453.3谓词公式化为子句集的方法 例例3将下列将下列谓词公式化为子句集。（续）谓词公式化为子句集。（续）（5）化为前束形）化为前束形 （6）化为标准形）化为标准形 （7）略去全称量词）略去全称量词 （8）消去合取词，把母式用子句集表示）消去合取词，把母式用子句集表示 （9）子句变量标准化）子句变量标准化 463.3谓词公式化为子句集的方法 例例4将下列谓词公式化为不含存在量词的前束形。（1）消去存在量词）消去存在量词 （2）消去蕴含符号）
24、消去蕴含符号 （3）设）设z的函数是的函数是g(y)，则，则 473.3谓词公式化为子句集的方法定理定理 3.1: 谓词公式不可满足的充要条件是其子句集不可满足。谓词公式不可满足的充要条件是其子句集不可满足。谓词公式谓词公式不可满足性不可满足性子句集子句集不可满足性不可满足性？48归归结结演演绎绎推推理理第3章确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 49定义定
25、义3.1（ H 域）域）设S为子句集，则按下述方法构造的域称为海伯伦域，简记为H 域。（1）令是S中所有个体常量的集合，若S 中不包含个体常量，则令，其中为任意指定的一个个体常量。（2）令S中所有n 元函数是H中的元素，其中。3.4海伯伦（Herbrand）定理 503.4海伯伦（Herbrand）定理 p 例例5 求子句集 的 H 域。 解：指定一个常量 作为个体常量，则得：.513.4海伯伦（Herbrand）定理 p 例例6 求子句集 的 H 域。 解解：根据：根据 H 域的定义得：域的定义得：.523.4海伯伦（Herbrand）定理 p 例例7 求子句集 的 H 域。 解：根据解：根
26、据 H 域的定义得：域的定义得：p 例例8 求子句集 的 H 域。 解：根据解：根据 H 域的定义得：域的定义得：)(),(),(),(),(),(,)(),(),(),(),(),(12aggafgagfaffagafaggafgagagfffafHHaa=533.4海伯伦（Herbrand）定理 基子句：基子句：用用H 域中的元素代换子句中的变元后所得的子句，域中的元素代换子句中的变元后所得的子句，其中的谓词称为其中的谓词称为基原子基原子。原子集原子集：子句集中所有基原子构成的集合。：子句集中所有基原子构成的集合。子句集在子句集在 H 域上的解释域上的解释：对子句集中出现的常量、函数及：对
27、子句集中出现的常量、函数及谓词取值，一次取值就是一个解释。谓词取值，一次取值就是一个解释。 定理定理 3.2（海伯伦定理）（海伯伦定理）：子句集不可满足的充要条件是存在一个有限的不可满足的基子句集。54归归结结演演绎绎推推理理第3章确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 553.5鲁宾逊归结原理u 鲁宾逊归结原理（消解原理）鲁宾逊归结原理（消解原理）的基本思想
28、：基本思想：p检查子句集检查子句集 S 中是否包含空子句，若包含，则中是否包含空子句，若包含，则 S 不可满足。不可满足。p若若不不包包含含，在在 S 中中选选择择合合适适的的子子句句进进行行归归结结，一一旦旦归归结结出出空空子句，就说明子句，就说明 S 是不可满足的。是不可满足的。u子子句句集集中中子子句句之之间间是是合合取取关关系系，只只要要有有一一个个子子句句不不可可满满足足， 则子句集就不可满足。则子句集就不可满足。 563.5鲁宾逊归结原理1. 命题逻辑中的归结原理（基子句的归结）命题逻辑中的归结原理（基子句的归结）定定义义3.3（归归结结）：设C1与C2是子句集中的任意两个子句，如
29、果C1中的文字L1与C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12。（归结）（归结）（归结）（归结）57u 推推论论1：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1与C2后得到新子句集S1，则由S1不可满足性可推出原子句集S的不可满足性，即： u 推推论论2：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若C12 加入原子句集S，得到新子句集S1，则S与S1在不可满足的意义上是等价的，即： u 定定理理3.3：归结式C12是其亲本子句C1与C2的逻辑结论。即如果C1与C2为真，则C12为
30、真。3.5鲁宾逊归结原理的不可满足性的不可满足性 S 的不可满足性的不可满足性S1的不可满足性的不可满足性 S的不可满足性的不可满足性583.5鲁宾逊归结原理2. 谓词逻辑中的归结原理（含有变量的子句的归结）谓词逻辑中的归结原理（含有变量的子句的归结） 例：例：？定义定义 3.4 ：设是 两个没有相同变元的子句， 和 分别是 中的文字，若 是 的最一般合一，则称 为 的二元归结式。 最一般合一最一般合一593.5鲁宾逊归结原理例例10 设：设： 求其二元归结式。求其二元归结式。得：得： 解：令解：令 选选 则则603.5鲁宾逊归结原理例例11 设：设： 求其二元归结式。求其二元归结式。则得：则
31、得： 解：解： 选选613.5鲁宾逊归结原理对于谓词逻辑，归结式是其亲本子句的逻辑结论。对于一阶谓词逻辑，即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结演绎；若从子句集存在一个到空子句的演绎，则该子句集是不可满足的。如果没有归结出空子句，则既不能说S 不可满足，也不能说S 是可满足的。 62归归结结演演绎绎推推理理第3章确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结
32、反演求解问题 633.6归结反演应用归结原理证明定理的过程称为归结反演。用归结反演证明的步骤是：（1）将已知前提表示为谓词公式F。（2）将待证明的结论表示为谓词公式Q，并否定得到Q 。（3）把谓词公式集F，Q化为子句集S。（4）应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入到S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。643.6归结反演 例12某公司招聘工作人员，A，B ，C 三人应试，经面试后公司表示如下想法：（1）三人中至少录取一人。（2）如果录取A而不录取B，则一定录取C。（3）如果录取B，则一定录取C。n 求证：公司一定录取求证：公司一定
33、录取 C。 653.6归结反演证明：公司的想法用谓词公式表示： 。 把要求证的结论用谓词公式表示出来并否定，得：（1）（2）（3） （4） 把上述公式化成子句集： （1）（2）（3）（4）663.6归结反演应用归结原理进行归结：应用归结原理进行归结： （5） （1）与（2）归结（6） （3）与（5）归结（7） （4）与（6）归结 673.6归结反演 例例13 已知：已知： 规则规则1：任何人的兄弟不是女性；：任何人的兄弟不是女性； 规则规则2：任何人的姐妹必是女性。：任何人的姐妹必是女性。 事事 实：实：Mary 是是 Bill 的姐妹。的姐妹。 求证：求证： Mary 不是不是 Tom 的兄
34、弟。的兄弟。 证明：定义谓词证明：定义谓词 brother ( x, y ) : x 是是 y 的兄弟的兄弟 sister ( x, y ) : x 是是 y 的姐妹的姐妹 woman ( x ) : x 是女性是女性683.6归结反演证明：将规则与事实用谓词公式表示：证明：将规则与事实用谓词公式表示： 把要求证的结论用谓词公式表示出来并否定，得：把要求证的结论用谓词公式表示出来并否定，得： 把上述公式化成子句集：把上述公式化成子句集： （1）（2）（3）（4） 将子句集进行归结：将子句集进行归结： 69归归结结演演绎绎推推理理第3章确定性推理方法3.1 推理的基本概念推理的基本概念 3.2
35、自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 703.7应用归结原理求解问题 应用归结原理求解问题的步骤：应用归结原理求解问题的步骤：（1）已知前提）已知前提 F 用谓词公式表示，并化为子句集用谓词公式表示，并化为子句集 S ；（2）把待求解的问题）把待求解的问题 Q 用谓词公式表示，并否定用谓词公式表示，并否定 Q，再与，再与 ANSWER 构成析取式（构成析取式（ Q ANSWER ）；）；（3）把（）把（ Q ANSW
36、ER） 化为子句集，并入到子句集化为子句集，并入到子句集 S中，中，得到子句集得到子句集 ；（4）对）对 应用归结原理进行归结；应用归结原理进行归结；（5）若得到归结式）若得到归结式 ANSWER ，则答案就在，则答案就在 ANSWER 中。中。71 例例14 已知：王（Wang）先生是小李（Li）的老师。：小李与小张（Zhang）是同班同学。：如果与是同班同学，则的老师也是的老师。求：小张的老师是谁？ 3.7应用归结原理求解问题723.7应用归结原理求解问题 解：解： 定义谓词定义谓词： ： 是 的老师。 ： 与 是同班同学。 把已知前提表示成谓词公式把已知前提表示成谓词公式： 把目标表示成
37、谓词公式，并把它否定后与把目标表示成谓词公式，并把它否定后与 ANSWER 析取：析取： F1：王（：王（Wang）先生是小李（）先生是小李（Li）的老师。）的老师。F2：小李与小张（：小李与小张（Zhang）是同班同学。）是同班同学。F3：如果：如果 x与与 y 是同班同学，则是同班同学，则 x的老师也是的老师也是 y的的 老师。老师。求：小张的老师是谁？求：小张的老师是谁？73 把上述公式化为子句集：把上述公式化为子句集： 3.7应用归结原理求解问题（1）（2）（3）（4） 应用归结原理进行归结：应用归结原理进行归结： （5）（1）与（3）归结（6）（4）与（5）归结（7）（2）与（6）归结743.7应用归结原理求解问题(1)(3)(5)(4)(2)(6)(7)75THE ENDArtificial Intelligence Principles and Applications
