第3章-确定性推理方法-人工智能课件.ppt

1、Artificial Intelligence Principles and Applications第第 3 章章 确定性推理方法确定性推理方法2知识智能?第第3章章 确定性推理方法确定性推理方法第3章 确定性推理方法经典逻辑推理（确定性推理）不确定性推理自然演绎推理归结演绎推理与/或形演绎推理推理推理知识智能 !3归归结结演演绎绎推推理理第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反

2、演求解问题应用归结反演求解问题 4归归结结演演绎绎推推理理第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 53.1 推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1.4 冲突消解策略冲突消解策略6推理机数据库知识库专家病人医疗专家系统医疗专家系统3.1.1 推理的定义推理：推理：

3、某种策略已知事实（证据）知 识结论知识知识专家的经验、医学常识专家的经验、医学常识初始初始证据证据病人的症状、化验结果病人的症状、化验结果证据证据中间结论中间结论73.1 推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推理的方向3.1.4 冲突消解策略冲突消解策略8（1）演绎推理演绎推理 (deductive reasoning) : 一般一般 个别个别 三段论式三段论式（三段论法）（三段论法） 足球运动员的身体都是强壮的足球运动员的身体都是强壮的 ； 高波是一名足球运动员；高波是一名足球运动员； 所以，高波的身体是强壮的。所以

4、，高波的身体是强壮的。3.1.2 推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（ 大前提大前提 ）（ 小前提小前提 ）（ 结结 论论 ）93.1.2 推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（2）归纳推理归纳推理 (inductive reasoning): 个别个别 一般一般 完全归纳推理（完全归纳推理（必然性推理）必然性推理） 不完全归纳推理不完全归纳推理（非必然性推理）（非必然性推理）检查全部产品合格检查全部产品合格该厂产品合格该厂产品合格完全归纳推理完全归纳推理检查全部样品合格检查全部样品合格该厂产品合格该厂产品合

5、格不完全归纳推理不完全归纳推理103.1.2 推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（3）默认推理默认推理（default reasoning，缺省推理），缺省推理）n 知识不完全的情况下假设某些条件已经具备所进行的推理知识不完全的情况下假设某些条件已经具备所进行的推理。 结结 论论 A 成立成立 B 成立？成立？（默认（默认B成立）成立）鸟笼要鸟笼要有盖子有盖子 制造鸟笼制造鸟笼 鸟会飞？鸟会飞？（默认成立）（默认成立）113.1.2 推理方式及其分类 2. 确定性推理、不确定性推理确定性推理、不确定性推理似然推理近似推理或模糊推理不确定性推理（概率论

6、）（模糊逻辑）（1）确定性推理确定性推理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。 （2）不确定性不确定性推理推理：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。12X：鸟：鸟 X：会飞：会飞 X: 企鹅企鹅 3.1.2 推理方式及其分类 3. 单调推理、非单调推理单调推理、非单调推理 （1）单调推理单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。 （2）非单调推理非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。 默认推理是非单调推理默认推理是非单调推理 基于

7、经典逻辑的演绎推理基于经典逻辑的演绎推理 X：不会飞不会飞X：企鹅：企鹅133.1.2 推理方式及其分类4启发式推理、非启发式推理启发式推理、非启发式推理 启发性知识启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。 目标：在脑膜炎、肺炎、流感中选择一个目标：在脑膜炎、肺炎、流感中选择一个 产生式规则产生式规则 r1：脑膜炎：脑膜炎 r2：肺：肺 炎炎 r3：流：流 感感 启发式知识：启发式知识：“脑膜炎危险脑膜炎危险”、“目前正在盛行流目前正在盛行流感感”。143.1 推理的基本概念3.1.1 推理的定义推理的定义3.1.2 推理方式及其分类推理方式及其分类3.1.3 推理的方向推

8、理的方向3.1.4 冲突消解策略冲突消解策略153.1.3 推理的方向正向推理逆向推理(反向推理)双向推理混合推理推理方向推理机数据库知识库专家用户163.1.3 推理的方向n 正向推理（事实驱动推理）正向推理（事实驱动推理）: 已知事实 结论 基本思想基本思想（1）从初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集KS。（2）按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中作为下一步推理的已知事实，再在KB中选取可适用知识构成KS 。（3）重复（2），直到求得问题的解或KB中再无可适用的知识。1. 正向推理正向推理17KBKS183.1

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

10、；为此需要另作新的假设。 主要优点：主要优点：不必使用与目标无关的知识，目的性强，同时它还有利于向用户提供解释。 主要缺点：主要缺点：起始目标的选择有盲目性。2. 逆向推理逆向推理20213.1.3 推理的方向n 逆向推理需要解决的问题：逆向推理需要解决的问题：u 如何判断一个假设是否是证据？如何判断一个假设是否是证据？u 当导出假设的知识有多条时，如何确定先选哪一条？当导出假设的知识有多条时，如何确定先选哪一条？ u一条知识的运用条件一般都有多个，当其中的一个经一条知识的运用条件一般都有多个，当其中的一个经验证成立后，如何自动地换为对另一个的验证？验证成立后，如何自动地换为对另一个的验证？u

11、 . 逆向推理：目的性强，利于向用户提供解释，但选择初逆向推理：目的性强，利于向用户提供解释，但选择初始目标时具有盲目性，比正向推理复杂。始目标时具有盲目性，比正向推理复杂。2. 逆向推理逆向推理223.1.3 推理的方向n 正向推理正向推理: 盲目、效率低。 逆向推理逆向推理: 若提出的假设目标不符合实际，会降低效率。 正反向混合推理：正反向混合推理：（1）先正向后逆向：先正向后逆向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；（2）先逆向后正向：先逆向后正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，

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

13、；（2）不能匹配成功；）不能匹配成功；（3）多种匹配成功多种匹配成功（一对多、多对一、多对多）（一对多、多对一、多对多）冲突消解冲突消解283.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

14、 H229第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理 3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 30自然演绎推理自然演绎推理：从一组已知为真的事实出发，运用从一组已知为真的事实出发，运用经典经典逻辑的推理规则逻辑的推理规则推出结论的过程。推出结论的过程。推理规则推理规则：P规则、规则、T规则、假言推理、拒取式推理规则、假言推理、拒取式推理 3.2 自然演绎推理n 假言推理假言推理： P, PQ

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

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

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

18、) 全称固化全称固化x 所以 C (ds), C (y) EASY (y) EASY (ds) P规则及假言推理规则及假言推理 所以 EASY (ds), EASY (z) LIKE (Wang，z) LIKE ( Wang, ds ) T规则及假言推理规则及假言推理35优点优点：n表达定理证明过程自然，易理解。n拥有丰富的推理规则，推理过程灵活。n便于嵌入领域启发式知识。3.2 自然演绎推理 缺点缺点：易产生组合爆炸，得到的中间结论一般呈指数形式递增。36归归结结演演绎绎推推理理第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子

19、句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 37归 结 演 绎 推 理反证法：反证法： ，当且仅当 ， 即 Q为 P 的逻辑结论，当且仅当 是不可满足的。QP FQPQP 定理：定理：Q 为为 ， ， 的逻辑结论，当且仅当的逻辑结论，当且仅当 是不可满足的。是不可满足的。1P2PnPQPPPn)(2138归 结 演 绎 推 理思路：定理思路：定理 不可满足 子句集不可满足 海伯伦定理海伯伦定理 鲁宾逊归结原理鲁宾逊归结原理QP QP393.3 谓词公式化为子句集的方法

20、 原子（原子（atom）谓词公式）谓词公式： 一个不能再分解的命题。 文字（文字（literal）：原子谓词公式及其否定。 ：正文字， ：负文字。 子句（子句（clause）：任何文字的析取式。任何文字本身也都是子句。 空子句（空子句（NIL）：不包含任何文字的子句。 子句集子句集：由子句构成的集合。PP)(,()(,(),()(xgxQxfxPxQxP空子句是永假的，不可满足的。空子句是永假的，不可满足的。403.3 谓词公式化为子句集的方法谓词公式化为子句集的方法 例例2 将下列将下列谓词公式化为子句集。谓词公式化为子句集。 解解：（：（1）消）消去谓词公式中的去谓词公式中的“ ”和和“

21、”符号符号),(),()(),()(yxRyxQyyxPyx 双重否定律双重否定律 德德.摩根律摩根律 量词转换律量词转换律 PP )(,)(QPQPQPQP)(PxPx)()(,)()(PxPx （2）把否定符号）把否定符号 移到紧靠谓词的位置上移到紧靠谓词的位置上,QPQP)()(QPQPQP),(),()(),()()(yxRyxQyyxPyx),(),()(),()(yxRyxQyyxPyx（3）变量标准化）变量标准化 )()()()(yPyxPx),()()()(yPyxPx),(),()(),()(zxRzxQzyxPyx3.3 谓词公式化为子句集的方法41 （4）消去存在量词）消

22、去存在量词 a. 存在量词不出现在全称量词的辖域内。 b. 存在量词出现在一个或者多个全称量词的辖域内。)(,()(,()(,()(xgxRxgxQxfxPx)(),(xgzxfy函数为的存在量词对于一般情况Skolem).),()()(2121yyxxxPyxxxnn),(21nxxxfySkolem化：用Skolem函数代替每个存在量词量化的变量的过程。 （5）化为前束形）化为前束形 前束形=（前缀）母式（前缀）：全称量词串。 母式：不含量词的谓词公式。 3.3 谓词公式化为子句集的方法),(),()(),()(zxRzxQzyxPyx423.3 谓词公式化为子句集的方法（6）化为）化为

23、Skolem 标准形标准形 Skolem 标准形：M：子句的合取式，称为Skolem标准形的母式。 Mxxxn)()(21)()()(RPQPRQP)()()(RPQPRQP)(,()(,()(,()(,()(xgxRxfxPxgxQxfxPx（7）略去全称量词）略去全称量词 )(,()(,()(,()(,(xgxRxfxPxgxQxfxP（8）消去合取词）消去合取词 )(,()(,(,)(,()(,(xgxRxfxPxgxQxfxP（9）子句变量标准化）子句变量标准化 )(,()(,(,)(,()(,(ygyRyfyPxgxQxfxP433.3 谓词公式化为子句集的方法 例例3 将下列谓词公

24、式化为子句集。将下列谓词公式化为子句集。（1）消去蕴含符号）消去蕴含符号（2）把否定符号移到每个谓词前面）把否定符号移到每个谓词前面 （3）变量标准化）变量标准化 （4）消去存在量词，设）消去存在量词，设y的函数是的函数是f(x)，则，则 )()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(wBwPwxQyxSyxQxPx)()()()()(,()()()(wBwPwxQxfxSxQxPx443.3

25、谓词公式化为子句集的方法 例例3 将下列将下列谓词公式化为子句集。（续）谓词公式化为子句集。（续）（5）化为前束形）化为前束形 （6）化为标准形）化为标准形 （7）略去全称量词）略去全称量词 （8）消去合取词，把母式用子句集表示）消去合取词，把母式用子句集表示 （9）子句变量标准化）子句变量标准化 )()()()(,()()()(wBwPxQxfxSxQxPwx)()()(,()()()()(wBwPxfxSxQxPxQwx)()()(,()()()(wBwPxfxSxPxQwx)()()(,()()(wBwPxfxSxPxQ),(xQ),(,()(xfxSxP)()(wBwP),(xQ),(

26、,()(yfySyP)()(wBwP453.3 谓词公式化为子句集的方法 例例4 将下列谓词公式化为不含存在量词的前束形。（1）消去存在量词）消去存在量词 （2）消去蕴含符号）消去蕴含符号 （3）设）设z的函数是的函数是g(y)，则，则 )(,(),()()()()(afyxRzxQzPzyx)(,(),()()()(afybRzbQzPzy)(,(),()()()(afybRzbQzPzy)(,(),()()()(afybRzbQzPzy)(,()(,()()(afybRygbQygPy463.3 谓词公式化为子句集的方法定理定理 3.1: 谓词公式不可满足的充要条件是其子句集不可满足。谓词

27、公式不可满足的充要条件是其子句集不可满足。谓词公式谓词公式不可满足性不可满足性子句集子句集不可满足性不可满足性？47归归结结演演绎绎推推理理第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 48定义定义3.1（ H 域）域） 设 S 为子句集，则按下述方法构造的域 称为海伯伦域，简记为 H 域。（1）令 是 S 中所有个体常量的集合，若 S 中不包含个体常量，则

28、令 ，其中 为 任意指定的一个个体常量。（2）令 S 中所有 n 元函数 是 H 中的元素，其中 。 3.4 海伯伦（Herbrand）定理 H0H0HiiHH1),(1nxxf, 2 , 1 , 0i493.4 海伯伦（Herbrand）定理 p 例例5 求子句集 的 H 域。 )(),()(yfRxQxPS 解：指定一个常量 作为个体常量，则得：a0H)(,)()(01fffHH)(),(,)(),(12ffffffHH)(),(),(,3ffffffH ),(),(),(,ffffffH.503.4 海伯伦（Herbrand）定理 p 例例6 求子句集 的 H 域。 )(),()(yfR

29、bQaPS 解解：根据：根据 H 域的定义得：域的定义得：,0baH )(),(,)(),(01bfafbabfafHH)(),(),(),(,)(),(),(),(12bffaffbfafbabffaffbfafHH.513.4 海伯伦（Herbrand）定理 p 例例7 求子句集 的 H 域。 )(),(),(ygRxfQaPS 解：根据解：根据 H 域的定义得：域的定义得：0aH p 例例8 求子句集 的 H 域。 )()(),(yRyQxPS 解：根据解：根据 H 域的定义得：域的定义得：10HHH)(),(,)(),(01agafaagafHH)(),(),(),(),(),(,)(

30、),(),(),(),(),(12aggafgagfaffagafaggafgagagfffafHH523.4 海伯伦（Herbrand）定理 基子句：基子句：用用H 域中的元素代换子句中的变元后所得的子句，域中的元素代换子句中的变元后所得的子句，其中的谓词称为其中的谓词称为基原子基原子。原子集原子集：子句集中所有基原子构成的集合。：子句集中所有基原子构成的集合。子句集在子句集在 H 域上的解释域上的解释：对子句集中出现的常量、函数及谓：对子句集中出现的常量、函数及谓词取值，一次取值就是一个解释。词取值，一次取值就是一个解释。 例例 9 子句集子句集 , , H 域：域： S 的原子集：的原子

31、集： 则则 S 的解释为的解释为：)(),(xfQaPS ),(),(,affafa),(),(),(affQafQaP ),(),(),(1affQafQaPI ),(),(),(2affQafQaPI533.4 海伯伦（Herbrand）定理 定理定理 3.2（海伯伦定理）（海伯伦定理）： 子句集不可满足的充要条件是存在一个有限的不可满足的基子句集 。54归归结结演演绎绎推推理理第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3

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

33、。 563.5 鲁宾逊归结原理1. 命题逻辑中的归结原理（基子句的归结）命题逻辑中的归结原理（基子句的归结） 定义定义3.3（归结归结）：设C1与C2是子句集中的任意两个子句，如果 C1中的文字L1与 C2中的文字L2互补，那么从C1和 C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12 。PQP RQRP R图3-5 归结过程的树形表示1C2C3C的归结式和2112C :CC的亲本子句、1221 :CCC（归结）（归结）12C（归结）（归结）123CPCRQCQPC321，例，设57u 推论推论1：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12

34、代替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为真。3.5 鲁宾逊归结原理的不可满足性的不可满足性 S 的不可满足性的不可满足性1SS1的不可满足性的不可满足性 S的不可满足性的不可满足性583.5 鲁宾逊归结原理2. 谓词逻辑中的归结原理（含有变量的子句的归结）谓词逻辑中的归结原理（含有变量的子

35、句的归结） 例：例：)()(1xQxPC)()(2yRaPC/xa)()(1aQaPC)()(2yRaPC)()(12yRaQC？定义定义 3.4 ：设是 两个没有相同变元的子句， 和 分别是 中的文字，若 是 的最一般合一，则称 为 的二元归结式。 21LL和21CC 与1L2L21CC 和)()(221112LCLCC21CC 和最一般合一最一般合一593.5 鲁宾逊归结原理例例10 设设： 求其二元归结式。求其二元归结式。得：得：),()(1aQxPC)()(2xRbPC)()(),()()(),(12bPyRbPbPaQbPC)(),(yRaQ)()(yRaQ 解：令解：令 选选 则则

36、)(),(21bPLxPL/xb)()(2yRbPC)()(aQxP)()(yRbP)()(yRaQ/xbC1C2C12603.5 鲁宾逊归结原理例例11 设设： 求其二元归结式。求其二元归结式。则得：则得：),()()(1xQafPxPC)()(2bRyPC)()(12afQbRC 解：解： 选选)(),(21yPLafPL/ )(xaf),()(1afQafPC/ )(yaf613.5 鲁宾逊归结原理对于谓词逻辑，归结式是其亲本子句的逻辑结论。 对于一阶谓词逻辑，即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结演绎；若从子句集存在一个到空子句的演绎，则该子句集是不可满足的。如果

37、没有归结出空子句，则既不能说 S 不可满足，也不能说 S 是可满足的。 62归归结结演演绎绎推推理理第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演3.7 应用归结反演求解问题应用归结反演求解问题 633.6 归结反演应用归结原理证明定理的过程称为归结反演。用归结反演证明的步骤是：（1）将已知前提表示为谓词公式F。（2）将待证明的结论表示为谓词公式Q，并否定得到 Q 。（3）把谓词公式集F， Q 化为子句集S

38、。（4）应用归结原理对子句集S中的子句进行归结，并把每次 归结得到的归结式都并入到S中。如此反复进行，若出 现了空子句，则停止归结，此时就证明了Q为真。643.6 归结反演 例12 某公司招聘工作人员，A，B ，C 三人应试，经面试后公司表示如下想法：（1） 三人中至少录取一人。（2） 如果录取 A 而不录取 B ，则一定录取 C。（3） 如果录取 B ，则一定录取 C 。 n 求证：公司一定录取求证：公司一定录取 C。 653.6 归结反演证明：公司的想法用谓词公式表示： 。 xxP：录取)( 把要求证的结论用谓词公式表示出来并否定，得：)()()(CPBPAP)()()(CPBPAP)()

39、(CPBP（1）（2）（3） （4）)(CP 把上述公式化成子句集： （1）（2）（3）（4）)()()(CPBPAP)()()(CPBPAP)()(CPBP)(CP663.6 归结反演应用归结原理进行归结：应用归结原理进行归结： （5） （1）与（2）归结（6） （3）与（5）归结（7） （4）与（6）归结 )()(CPBP)(CPNIL673.6 归结反演 例例13 已知：已知： 规则规则1：任何人的兄弟不是女性；：任何人的兄弟不是女性； 规则规则2：任何人的姐妹必是女性。：任何人的姐妹必是女性。 事事 实：实：Mary 是是 Bill 的姐妹。的姐妹。 求证：求证： Mary 不是不是

40、Tom 的兄弟。的兄弟。 证明：定义谓词证明：定义谓词 brother ( x, y ) : x 是是 y 的兄弟的兄弟 sister ( x, y ) : x 是是 y 的姐妹的姐妹 woman ( x ) : x 是女性是女性683.6 归结反演证明：将规则与事实用谓词公式表示：证明：将规则与事实用谓词公式表示： 把要求证的结论用谓词公式表示出来并否定，得：把要求证的结论用谓词公式表示出来并否定，得： 把上述公式化成子句集：把上述公式化成子句集： （1）（2）（3）)(),()()(xwomanyxbrotheryx)(),()()(xwomanyxsisteryx),(BillMarys

41、ister（4）),(TomMarybrother)(),(1xwomanyxbrotherC)(),(2xwomanyxsisterC),(3BillMarysisterC ),(4TomMarybrotherC 将子句集进行归结：将子句集进行归结： )(23MarywomanC),(123yMarybrotherCNILC123469归归结结演演绎绎推推理理第3章 确定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演绎推理自然演绎推理3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法3.4 海伯伦定理海伯伦定理3.5 鲁宾逊归结原理鲁宾逊归结原理3.6 归结反演归结反演

42、3.7 应用归结反演求解问题应用归结反演求解问题 703.7 应用归结原理求解问题 应用归结原理求解问题的步骤：应用归结原理求解问题的步骤：（1）已知前提）已知前提 F 用谓词公式表示，并化为子句集用谓词公式表示，并化为子句集 S ；（2）把待求解的问题）把待求解的问题 Q 用谓词公式表示，并否定用谓词公式表示，并否定 Q，再与，再与 ANSWER 构成析取式（构成析取式（ Q ANSWER ）；）；（3）把（）把（ Q ANSWER） 化为子句集，并入到子句集化为子句集，并入到子句集 S中，中，得到子句集得到子句集 ；S（4）对）对 应用归结原理进行归结；应用归结原理进行归结；S（5）若得到

43、归结式）若得到归结式 ANSWER ，则答案就在，则答案就在 ANSWER 中。中。71 例例14 已知： ：王（Wang）先生是小李（Li）的老师。 ：小李与小张（Zhang）是同班同学。 ：如果 与 是同班同学，则 的老师也是 的老师。求：小张的老师是谁？ 3.7 应用归结原理求解问题1F2F3Fxxyy723.7 应用归结原理求解问题 解：解： 定义谓词定义谓词： ： 是 的老师。 ： 与 是同班同学。),(yxT),(yxCxyxy 把已知前提表示成谓词公式把已知前提表示成谓词公式： ),(1LiWangTF：),(2ZhangLiCF ：),(),(),()()()(3yzTxzTy

44、xCzyxF： 把目标表示成谓词公式，并把它否定后与把目标表示成谓词公式，并把它否定后与 ANSWER 析取：析取： ）（：xANSWERZhangxTxG(),()F1：王（：王（Wang）先生是小李（）先生是小李（Li）的老师。）的老师。F2：小李与小张（：小李与小张（Zhang）是同班同学。）是同班同学。F3：如果：如果 x与与 y 是同班同学，则是同班同学，则 x的老师也是的老师也是 y的的 老师。老师。求：小张的老师是谁？求：小张的老师是谁？73 把上述公式化为子句集：把上述公式化为子句集： 3.7 应用归结原理求解问题（1） （2）（3）（4）),(LiWangT),(ZhangLiC),(),(),(yzTxzTyxC)(),(uANSWERZhanguT 应用归结原理进行归结：应用归结原理进行归结： （5） （1）与（3）归结（6） （4）与（5）归结（7） （2）与（6）归结),(),(yWangTyLiC)(),(WangANSWERZhangLiC)(WangANSWER743.7 应用归结原理求解问题(1)(3)(5)(4)(2)(6)(7)75THE ENDArtificial Intelligence Principles and Applications