《人工智能》-第三章__确定性推理

1、华中科技大学 自动化学院人 工 智 能教材：教材： 蔡自兴等蔡自兴等人工智能及其应用人工智能及其应用（第（第4版）版） 清华大学出版社，清华大学出版社，2010. 5Powerpoint华中科技大学 自动化学院第 3 章 确定性推理方法3归归结结演演绎绎推推理理v3.1 推理的基本概念推理的基本概念 v3.2 自然演绎推理自然演绎推理 v3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法v3.4 鲁宾逊归结原理鲁宾逊归结原理v3.5 归结反演归结反演v3.6 应用归结反演求解问题应用归结反演求解问题 v3.7 盲目搜索盲目搜索v3.8 产生式系统产生式系统v3.9 启发式搜索启发式搜索v

2、3.10 非单调推理非单调推理v3.11 消解原理消解原理4v前面讨论了把知识用某种模式表示出来存储到计算前面讨论了把知识用某种模式表示出来存储到计算机中去。但是，为使计算机具有智能，还必须使它机中去。但是，为使计算机具有智能，还必须使它具有思维能力。推理是求解问题的一种重要方法。具有思维能力。推理是求解问题的一种重要方法。因此，推理方法成为人工智能的一个重要研究课题。因此，推理方法成为人工智能的一个重要研究课题。v下面首先讨论关于推理的基本概念，然后着重介绍下面首先讨论关于推理的基本概念，然后着重介绍鲁宾逊归结原理及其在机器定理证明和问题求解中鲁宾逊归结原理及其在机器定理证明和问题求解中的应

3、用。鲁宾逊归结原理使定理证明能够在计算机的应用。鲁宾逊归结原理使定理证明能够在计算机上实现。上实现。5知识智能?第3章 确定性推理方法经 典 逻 辑 推 理（ 确 定 性 推 理 ）不 确 定 性 推 理自 然 演 绎推 理归 结 演 绎推 理与 /或 形演 绎 推 理推理推理知识智能 !6归归结结演演绎绎推推理理v3.1 推理的基本概念推理的基本概念 v3.2 自然演绎推理自然演绎推理 v3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法v3.4 鲁宾逊归结原理鲁宾逊归结原理v3.5 归结反演归结反演v3.6 应用归结反演求解问题应用归结反演求解问题 v3.7 盲目搜索盲目搜索v3.8

4、 产生式系统产生式系统v3.9 启发式搜索启发式搜索v3.10 非单调推理非单调推理v3.11 消解原理消解原理73.1 推理的基本概念o3.1.1 推理的定义推理的定义o3.1.2 推理方式及其分类推理方式及其分类o3.1.3 推理的方向推理的方向o3.1.4 冲突消解策略冲突消解策略8推理机数据库知识库专家病人医疗专家医疗专家系统系统3.1.1 推理的定义v推理：推理：某 种 策 略已 知 事 实（ 证 据 ）知 识结 论某种策略93.1 推理的基本概念o3.1.1 推理的定义推理的定义o3.1.2 推理方式及其分类推理方式及其分类o3.1.3 推理的方向推理的方向o3.1.4 冲突消解策

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

6、oning): 个别个别 一般一般 完全归纳推理完全归纳推理（必然性推理）必然性推理） 不完全归纳推理不完全归纳推理（非必然性推理）（非必然性推理）检查全部产品合格检查全部产品合格该厂产品合格该厂产品合格完全归纳完全归纳推理推理检查全部样品合格检查全部样品合格该厂产品合格该厂产品合格不完全归纳不完全归纳推理推理123.1.2 推理方式及其分类o 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（3）默认推理默认推理（default reasoning，缺省推理），缺省推理）n 知识不完全的情况下假设某些条件已经具备所进行的推理知识不完全的情况下假设某些条件已经具备所进行的推理。 结结

7、论论 A 成立成立 B 成立？成立？（默认（默认B成立）成立）鸟笼要鸟笼要有盖子有盖子 制造鸟笼制造鸟笼 鸟会飞？鸟会飞？（默认成立）（默认成立）133.1.2 推理方式及其分类 2. 确定性推理、不确定性推理确定性推理、不确定性推理似然推理近似推理或模糊推理不确定性推理（概率论）（模糊逻辑）（1）确定性推理确定性推理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。 （2）不确定性不确定性推理推理：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。14X：鸟：鸟 X：会飞：会飞 X: 企鹅企鹅 3.1.2 推理方式及其分类 3. 单调推理、非单调推理

8、单调推理、非单调推理 （1）单调推理单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。 （2）非单调推理非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。 默认推理是非单调推理默认推理是非单调推理 基于经典逻辑的演绎推理基于经典逻辑的演绎推理 X：不会飞不会飞X：企鹅：企鹅153.1.2 推理方式及其分类4启发式推理、非启发式推理启发式推理、非启发式推理 启发性知识启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。 o 目标：在脑膜炎、肺炎、流感中选择一个目标：在脑膜炎、肺炎、流感中选择一个 产生式规则产生

9、式规则 r1：脑膜炎：脑膜炎 r2：肺：肺 炎炎 r3：流：流 感感 启发式知识：启发式知识：“脑膜炎危险脑膜炎危险”、“目前正在盛行流目前正在盛行流感感”。163.1 推理的基本概念o3.1.1 推理的定义推理的定义o3.1.2 推理方式及其分类推理方式及其分类o3.1.3 推理的方向推理的方向o3.1.4 冲突消解策略冲突消解策略173.1.3 推理的方向正向推理逆向推理(反向推理)双向推理混合推理推理方向推理机数据库知识库专家用户183.1.3 推理的方向n 正向推理（事实驱动推理）正向推理（事实驱动推理）: 已知事实 结论 基本思想基本思想（1）从初始已知事实出发，在知识库KB中找出当

10、前可适用的知识，构成可适用知识集KS。（2）按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中作为下一步推理的已知事实，再在KB中选取可适用知识构成KS 。（3）重复（2），直到求得问题的解或KB中再无可适用的知识。1. 正向推理正向推理19KBKS203.1.3 推理的方向n 实现正向推理需要解决的问题：实现正向推理需要解决的问题：l 确定匹配（知识与已知事实）的方法。确定匹配（知识与已知事实）的方法。l 按什么策略搜索知识库。按什么策略搜索知识库。l 冲突消解策略。冲突消解策略。 正向推理简单，易实现，但目的性不强，效率低。正向推理简单，易实现，但目的性不强

11、，效率低。1. 正向推理正向推理213.1.3 推理的方向n 逆向推理（目标驱动推理）：逆向推理（目标驱动推理）：以某个假设目标作为出发点。 基本思想：基本思想： 选定一个假设目标。 寻找支持该假设的证据，若所需的证据都能找到，则原假设成立；若无论如何都找不到所需要的证据，说明原假设不成立的；为此需要另作新的假设。 主要优点：主要优点：不必使用与目标无关的知识，目的性强，同时它还有利于向用户提供解释。 主要缺点：主要缺点：起始目标的选择有盲目性。2. 逆向推理逆向推理22233.1.3 推理的方向n 逆向推理需要解决的问题：逆向推理需要解决的问题：u 如何判断一个假设是否是证据？如何判断一个假

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

13、，会降低效率。 正反向混合推理：正反向混合推理：（1）先正向后逆向：先正向后逆向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；（2）先逆向后正向：先逆向后正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。3. 混合推理混合推理252627n 双向推理双向推理：正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰头碰头”的一种推理。已知事实已知事实 假设目标假设目标3.1.3 推理的方向4. 双向推理双向推理中间结论中间结论证证 据据283.1 推理的基本概念o3.1.1 推理的定义推

14、理的定义o3.1.2 推理方式及其分类推理方式及其分类o3.1.3 推理的方向推理的方向o3.1.4 冲突消解策略冲突消解策略293.1.4 冲突消解策略多种冲突消解策略：多种冲突消解策略：（1）按针对性排序）按针对性排序（2）按已知事实的新鲜性排序）按已知事实的新鲜性排序（3）按匹配度排序）按匹配度排序（4）按条件个数排序）按条件个数排序r1: IF A1 AND A2 THEN H1r2: IF A1 AND A2 AND A3 AND A4 THEN H2303.1.4 冲突消解策略 已知事实与知识的三种匹配情况已知事实与知识的三种匹配情况：（1）恰好匹配成功（一对一）；）恰好匹配成功（

15、一对一）；（2）不能匹配成功；）不能匹配成功；（3）多种匹配成功多种匹配成功（一对多、多对一、多对多）（一对多、多对一、多对多）冲突消解冲突消解31归归结结演演绎绎推推理理v3. 1 推理的基本概念推理的基本概念 v3.2 自然演绎推理自然演绎推理v3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法v3.4 鲁宾逊归结原理鲁宾逊归结原理v3.5 归结反演归结反演v3.6 应用归结反演求解问题应用归结反演求解问题 v3.7 盲目搜索盲目搜索v3.8 启发式搜索启发式搜索v3.9 产生式系统产生式系统v3.10 非单调推理非单调推理v3.11 消解原理消解原理32p自然演绎推理自然演绎推理：

16、从一组已知为真的事实出发，运用从一组已知为真的事实出发，运用经典经典逻辑的推理规则逻辑的推理规则推出结论的过程。推出结论的过程。p推理规则推理规则：P规则、规则、T规则、假言推理、拒取式推理规则、假言推理、拒取式推理 3.2 自然演绎推理n 假言推理假言推理： P, PQ Q n “如果如果x是金属，则是金属，则x能导电能导电” , “铜是金属铜是金属” 推出推出 “铜能导铜能导电电” n 拒取式推理拒取式推理： PQ, Q Pn “如果下雨，则地下就湿如果下雨，则地下就湿” , “地上不湿地上不湿” 推出推出 “没有下雨没有下雨”33（1） 如果下雨，则地上是湿的（如果下雨，则地上是湿的（

17、PQ ）；（2）没有下雨（）没有下雨（P ）；）； （3）所以，地上不湿（所以，地上不湿（Q ）。 3.2 自然演绎推理p错误错误1否定前件否定前件： PQ, P Q（1）如果行星系统是以太阳为中心的，则金星会显如果行星系统是以太阳为中心的，则金星会显示出位相变化（示出位相变化（ PQ ）；（2）金星显示出位相变化（金星显示出位相变化（ Q ）；）；（3） 所以，行星系统是以太阳为中心（所以，行星系统是以太阳为中心（ P ）。 错误错误2肯定后件肯定后件： PQ, Q P343.2 自然演绎推理p 例例3.3.1 已知事实：已知事实： （1）凡是容易的课程小王凡是容易的课程小王( Wang )

18、都喜欢；都喜欢； （2）C 班的课程都是容易的；班的课程都是容易的； （3）ds 是是 C 班的一门课程。班的一门课程。p 求证：小王喜欢求证：小王喜欢 ds 这门课程。这门课程。353.2 自然演绎推理p证明：证明：p定义谓词定义谓词： EASY ( x )：x 是容易的 LIKE ( x, y )：x 喜欢 y C ( x )：x 是 C 班的一门课程p 已知事实和结论用谓词公式表示已知事实和结论用谓词公式表示： ( ) ( EASY ( x ) LIKE ( Wang, x ) ) ( ) ( C ( x ) EASY ( x ) C ( ds ) LIKE ( Wang, ds ) x

19、x363.2 自然演绎推理p 应用推理规则进行推理：应用推理规则进行推理： ( )（EASY ( x ) LIKE ( Wang, x ) EASY (z) LIKE ( Wang, z ) 全称固化全称固化x ( ) (C ( x ) EASY ( x ) C ( y ) EASY ( y ) 全称固化全称固化x 所以 C (ds), C (y) EASY (y) EASY (ds) P规则及假言推理规则及假言推理 所以 EASY (ds), EASY (z) LIKE (Wang，z) LIKE ( Wang, ds ) T规则及假言推理规则及假言推理37p优点优点：n表达定理证明过程自然

20、，易理解。n拥有丰富的推理规则，推理过程灵活。n便于嵌入领域启发式知识。3.2 自然演绎推理p 缺点缺点：易产生组合爆炸，得到的中间结论一般呈指数形式递增。38归归结结演演绎绎推推理理v3.1 推理的基本概念推理的基本概念 v3.2 自然演绎推理自然演绎推理 v3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法v3.4 鲁宾逊归结原理鲁宾逊归结原理v3.5 归结反演归结反演v3.6 应用归结反演求解问题应用归结反演求解问题 v3.7 盲目搜索盲目搜索v3.8 产生式系统产生式系统v3.9 启发式搜索启发式搜索v3.10 非单调推理非单调推理v3.11 消解原理消解原理39归 结 演 绎

21、推 理v反证法：反证法： ，当且仅当 ， 即 Q为 P 的逻辑结论，当且仅当 是不可满足的。QP FQPQPo 定理：定理：Q 为为 ， ， 的逻辑结论，当且仅当的逻辑结论，当且仅当o 是不可满足的。是不可满足的。1P2PnPQPPPn)(2140v思路：定理思路：定理 不可满足 子句集不可满足 海伯伦定理海伯伦定理 鲁宾逊归结原理鲁宾逊归结原理归 结 演 绎 推 理QP QP413.3 谓词公式化为子句集的方法v 原子（原子（atom）谓词公式）谓词公式： 一个不能再分解的命题。v 文字（文字（literal）：原子谓词公式及其否定。v ：正文字， ：负文字。v 子句（子句（clause）：

22、任何文字的析取式。任何文字本身也都是子句。v 空子句（空子句（NIL）：不包含任何文字的子句。 v 子句集子句集：由子句构成的集合。PP)(,()(,(),()(xgxQxfxPxQxP空子句是永假的，不可满足的。空子句是永假的，不可满足的。42v 例例3.2 将下列将下列谓词公式化为子句集。谓词公式化为子句集。 解解：（：（1）消）消去谓词公式中的去谓词公式中的“ ”和和“ ”符号符号),(),()(),()(yxRyxQyyxPyx 双重否定律双重否定律 德德.摩根律摩根律 量词转换律量词转换律 PP )(,)(QPQPQPQP)(PxPx)()(,)()(PxPx （2）把否定符号）把否

23、定符号 移到紧靠谓词的位置上移到紧靠谓词的位置上,QPQP)()(QPQPQP),(),()(),()(yxRyxQyyxPyx（3）变量标准化）变量标准化 )()()()(yPyxPx),()()()(yPyxPx),(),()(),()(zxRzxQzyxPyx3.3 谓词公式化为子句集的方法),(),()(),()()(yxRyxQyyxPyx43 （4）消去存在量词）消去存在量词 a. 存在量词不出现在全称量词的辖域内。 b. 存在量词出现在一个或者多个全称量词的辖域内。)(,()(,()(,()(xgxRxgxQxfxPx)(),(xgzxfy函数为的存在量词对于一般情况Skolem

24、).),()()(2121yyxxxPyxxxnn),(21nxxxfySkolem化：用Skolem函数代替每个存在量词量化的变量的过程。 （5）化为前束形）化为前束形 前束形=（前缀）母式（前缀）：全称量词串。 母式：不含量词的谓词公式。 3.3 谓词公式化为子句集的方法),(),()(),()(zxRzxQzyxPyx443.3 谓词公式化为子句集的方法（6）化为）化为 Skolem 标准形标准形 Skolem 标准形：M：子句的合取式，称为Skolem标准形的母式。 Mxxxn)()(21)()()(RPQPRQP)()()(RPQPRQP)(,()(,()(,()(,()(xgxRx

25、fxPxgxQxfxPx（7）略去全称量词）略去全称量词 )(,()(,()(,()(,(xgxRxfxPxgxQxfxP（8）消去合取词）消去合取词 )(,()(,(,)(,()(,(xgxRxfxPxgxQxfxP（9）子句变量标准化）子句变量标准化 )(,()(,(,)(,()(,(ygyRyfyPxgxQxfxP453.3 谓词公式化为子句集的方法o 例例3.3 将下列谓词公式化为子句集。将下列谓词公式化为子句集。（1）消去蕴含符号）消去蕴含符号（2）把否定符号移到每个谓词前面）把否定符号移到每个谓词前面 （3）变量标准化）变量标准化 （4）消去存在量词，设）消去存在量词，设y的函数是

26、的函数是f(x)，则，则 )()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(wBwPwxQyxSyxQxPx)()()()()(,()()()(wBwPwxQxfxSxQxPx463.3 谓词公式化为子句集的方法o 例例3.3 将下列将下列谓词公式化为子句集。（续）谓词公式化为子句集。（续）（5）化为前束形）化为前束形 （6）化为标准形）化为标准形 （7）略去全称量词）略去全称量词 （8）消去合取词

27、，把母式用子句集表示）消去合取词，把母式用子句集表示 （9）子句变量标准化）子句变量标准化 )()()()(,()()()(wBwPxQxfxSxQxPwx)()()(,()()()()(wBwPxfxSxQxPxQwx)()()(,()()()(wBwPxfxSxPxQwx)()()(,()()(wBwPxfxSxPxQ),(xQ),(,()(xfxSxP)()(wBwP),(xQ),(,()(yfySyP)()(wBwP473.3 谓词公式化为子句集的方法o 例例3.5 将下列谓词公式化为不含存在量词的前束形。（1）消去存在量词）消去存在量词 （2）消去蕴含符号）消去蕴含符号 （3）设）设

28、z的函数是的函数是g(y)，则，则 )(,(),()()()()(afyxRzxQzPzyx)(,(),()()()(afybRzbQzPzy)(,(),()()()(afybRzbQzPzy)(,(),()()()(afybRzbQzPzy)(,()(,()()(afybRygbQygPy483.3 谓词公式化为子句集的方法定理定理 3.1: 谓词公式不可满足的充要条件是其子句集不可满足。谓词公式不可满足的充要条件是其子句集不可满足。谓词公式谓词公式不可满足性不可满足性子句集子句集不可满足性不可满足性？49归归结结演演绎绎推推理理v3.1 推理的基本概念推理的基本概念 v3.2 自然演绎推理

29、自然演绎推理 v3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法v3.4 鲁宾逊归结原理鲁宾逊归结原理v3.5 归结反演归结反演v3.6 应用归结反演求解问题应用归结反演求解问题 v3.7 盲目搜索盲目搜索v3.8 产生式系统产生式系统v3.9 启发式搜索启发式搜索v3.10 非单调推理非单调推理v3.11 消解原理消解原理503.4 鲁宾逊归结原理u 鲁宾逊归结原理（消解原理）鲁宾逊归结原理（消解原理）的基本思想：基本思想：p检查子句集检查子句集 S 中是否包含空子句，若包含，则中是否包含空子句，若包含，则 S 不可满足。不可满足。p若不包含，在若不包含，在 S 中选择合适的子句进行

30、归结，一旦归结出空中选择合适的子句进行归结，一旦归结出空子句，就说明子句，就说明 S 是不可满足的。是不可满足的。u 子句集中子句之间是合取关系，只要有一个子句不可满足，子句集中子句之间是合取关系，只要有一个子句不可满足， 则子句集就不可满足。则子句集就不可满足。 513.4 鲁宾逊归结原理1. 命题逻辑中的归结原理（基子句的归结）命题逻辑中的归结原理（基子句的归结） 定义定义3.1（归结归结）：设C1与C2是子句集中的任意两个子句，如果 C1中的文字L1与 C2中的文字L2互补，那么从C1和 C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12 。PQPRQRP R图

31、3-5 归结过程的树形表示1C2C3C的归结式和2112C :CC的亲本子句、1221 :CCC（归结）（归结）12C（）123CPCRQCQPC321，例，设52u 推论推论1：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1与C2后得到新子句集S1，则由S1不可满足性可推出原子句集S的不可满足性，即： u 推论推论2：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若C12 加入原子句集S，得到新子句集S1，则S与S1在不可满足的意义上是等价的，即： u 定理定理3.2：归结式C12是其亲本子句C1与C2的逻辑结论。即如果 C1与C2为真，则C12为真

32、。3.4 鲁宾逊归结原理的不可满足性的不可满足性 S 的不可满足性的不可满足性1SS1的不可满足性的不可满足性 S的不可满足性的不可满足性533.4 鲁宾逊归结原理2. 谓词逻辑中的归结原理（含有变量的子句的归结）谓词逻辑中的归结原理（含有变量的子句的归结） 例：例：)()(1xQxPC)()(2yRaPC/xa)()(1aQaPC)()(2yRaPC)()(12yRaQC？定义定义 3.2 ：设是 两个没有相同变元的子句， 和 分别是 中的文字，若 是 的最一般合一，则称 为 的二元归结式。 21LL和21CC 与1L2L21CC 和)()(221112LCLCC21CC 和最一般合一最一般

33、合一543.4 鲁宾逊归结原理v例例3.7 设：设： 求其二元归结式。求其二元归结式。得：得：),()(1aQxPC)()(2xRbPC)()(),()()(),(12bPyRbPbPaQbPC)(),(yRaQ)()(yRaQ 解：令解：令 选选 则则)(),(21bPLxPL/xb)()(2yRbPC)()(aQxP)()(yRbP)()(yRaQ/xbC1C2C12553.4 鲁宾逊归结原理v例例3.3.8 设：设： 求其二元归结式。求其二元归结式。则得：则得：),()()(1xQafPxPC)()(2bRyPC)()(12afQbRC 解：解： 选选)(),(21yPLafPL/ )(

34、xaf),()(1afQafPC/ )(yaf563.4 鲁宾逊归结原理v对于谓词逻辑，归结式是其亲本子句的逻辑结论。 v对于一阶谓词逻辑，即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结演绎；若从子句集存在一个到空子句的演绎，则该子句集是不可满足的。v如果没有归结出空子句，则既不能说 S 不可满足，也不能说 S 是可满足的。 57归归结结演演绎绎推推理理v3.1 推理的基本概念推理的基本概念 v3.2 自然演绎推理自然演绎推理 v3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法v3.4 鲁宾逊归结原理鲁宾逊归结原理v3.5 归结反演归结反演v3.6 应用归结反演求解问题应

35、用归结反演求解问题 v3.7 盲目搜索盲目搜索v3.8 产生式系统产生式系统v3.9 启发式搜索启发式搜索v3.10 非单调推理非单调推理v3.11 消解原理消解原理583.5 归结反演v应用归结原理证明定理的过程称为归结反演。v用归结反演证明的步骤是：（1）将已知前提表示为谓词公式F。（2）将待证明的结论表示为谓词公式Q,并否定得到 Q 。（3）把谓词公式集F， Q 化为子句集S。（4）应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入到S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。593.5 归结反演v 例3.9 某公司招聘工作人员，A，B ，C

36、三人应试，经面试后公司表示如下想法：（1） 三人中至少录取一人。（2） 如果录取 A 而不录取 B ，则一定录取 C。（3） 如果录取 B ，则一定录取 C 。 n 求证：公司一定录取求证：公司一定录取 C。 603.5 归结反演xxP：录取)( 把要求证的结论用谓词公式表示出来并否定，得：)()()(CPBPAP)()()(CPBPAP)()(CPBP（1）（2）（3） （4）)(CP 把上述公式化成子句集： （1）（2）（3）（4）)()()(CPBPAP)()()(CPBPAP)()(CPBP)(CP613.5 归结反演应用归结原理进行归结：应用归结原理进行归结： （5） （1）与（2）

37、归结（6） （3）与（5）归结（7） （4）与（6）归结 )()(CPBP)(CPNIL623.5 归结反演o 例例3.10 已知：已知： 规则规则1：任何人的兄弟不是女性；：任何人的兄弟不是女性； 规则规则2：任何人的姐妹必是女性。：任何人的姐妹必是女性。 事事 实：实：Mary 是是 Bill 的姐妹。的姐妹。o 求证：求证： Mary 不是不是 Tom 的兄弟。的兄弟。o 证明：定义谓词证明：定义谓词 brother ( x, y ) : x 是是 y 的兄弟的兄弟 sister ( x, y ) : x 是是 y 的姐妹的姐妹 woman ( x ) : x 是女性是女性63o 证明：

38、将规则与事实用谓词公式表示：证明：将规则与事实用谓词公式表示： 把要求证的结论用谓词公式表示出来并否定，得：把要求证的结论用谓词公式表示出来并否定，得： 把上述公式化成子句集：把上述公式化成子句集： （1）（2）（3）)(),()()(xwomanyxbrotheryx)(),()()(xwomanyxsisteryx),(BillMarysister（4）),(TomMarybrother)(),(1xwomanyxbrotherC)(),(2xwomanyxsisterC),(3BillMarysisterC ),(4TomMarybrotherC 将子句集进行归结：将子句集进行归结： )

39、(23MarywomanC),(123yMarybrotherCNILC123464归归结结演演绎绎推推理理v3.1 推理的基本概念推理的基本概念 v3.2 自然演绎推理自然演绎推理 v3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法v3.4 鲁宾逊归结原理鲁宾逊归结原理v3.5 归结反演归结反演v3.6 应用归结反演求解问题应用归结反演求解问题 v3.7 盲目搜索盲目搜索v3.8 产生式系统产生式系统v3.9 启发式搜索启发式搜索v3.10 非单调推理非单调推理v3.11 消解原理消解原理653.6 应用归结原理求解问题v 应用归结原理求解问题的步骤：应用归结原理求解问题的步骤：（1

40、）已知前提）已知前提 F 用谓词公式表示，并化为子句集用谓词公式表示，并化为子句集 S ；（2）把待求解的问题）把待求解的问题 Q 用谓词公式表示，并否定用谓词公式表示，并否定 Q，再与，再与 ANSWER 构成析取式（构成析取式（ Q ANSWER ）；）；（3）把（）把（ Q ANSWER） 化为子句集，并入到子句集化为子句集，并入到子句集 S中，中，得到子句集得到子句集 S ；（4）对）对 应用归结原理进行归结；应用归结原理进行归结；（5）若得到归结式）若得到归结式 ANSWER ，则答案就在，则答案就在 ANSWER 中。中。 S 66v 例例3.3.11 已知： F1：王（Wang）

41、先生是小李（Li）的老师。 F2：小李与小张（Zhang）是同班同学。 F3：如果 x与 y是同班同学，则x 的老师也是y 的老师。求：小张的老师是谁？ 3.6 应用归结原理求解问题673.6 应用归结原理求解问题v 解：解： 定义谓词：定义谓词： ： 是 的老师。 ： 与 是同班同学。),(yxT),(yxCxyxy 把已知前提表示成谓词公式：把已知前提表示成谓词公式： ),(1LiWangTF：),(2ZhangLiCF ：),(),(),()()()(3yzTxzTyxCzyxF： 把目标表示成谓词公式，并把它否定后与把目标表示成谓词公式，并把它否定后与 ANSWER 析取：析取： ）（

42、：xANSWERZhangxTxG(),()F1：王（：王（Wang）先生是小李（）先生是小李（Li）的老师。）的老师。F2：小李与小张（：小李与小张（Zhang）是同班同学。）是同班同学。F3：如果：如果 x与与 y 是同班同学，则是同班同学，则 x的老师也是的老师也是 y的的 老师。老师。求：小张的老师是谁？求：小张的老师是谁？683.6 应用归结原理求解问题（1） （2）（3）（4）),(LiWangT),(ZhangLiC),(),(),(yzTxzTyxC)(),(uANSWERZhanguT 应用归结原理进行归结：应用归结原理进行归结： （5） （1）与（3）归结（6） （4）与（

43、5）归结（7） （2）与（6）归结),(),(yWangTyLiC)(),(WangANSWERZhangLiC)(WangANSWER把上述公式转化为子句集：693.6 应用归结原理求解问题(1)(3)(5)(4)(2)(6)(7)70归归结结演演绎绎推推理理v3.1 推理的基本概念推理的基本概念 v3.2 自然演绎推理自然演绎推理 v3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法v3.4 鲁宾逊归结原理鲁宾逊归结原理v3.5 归结反演归结反演v3.6 应用归结反演求解问题应用归结反演求解问题 v3.7 盲目搜索盲目搜索v3.8 产生式系统产生式系统v3.9 启发式搜索启发式搜索v

44、3.10 非单调推理非单调推理v3.11 消解原理消解原理71 o3.7.1 回溯策略回溯策略o3.7.2 宽度优先搜索策略宽度优先搜索策略o3.7.3 深度优先搜索策略深度优先搜索策略3.7 搜索的概念723.7 搜索的概念 v问题求解：v问题的表示。 v求解方法。v问题求解的基本方法：搜索法、归约法、归结法、推理法及产生式等。733.7 搜索的基本问题与主要过程 v搜索中需要解决的基本问题搜索中需要解决的基本问题：（1）是否一定能找到一个解。（2）找到的解是否是最佳解。（3）时间与空间复杂性如何。（4）是否终止运行或是否会陷入一个死循环。743.7 搜索的基本问题与主要过程v搜索的主要过程

45、搜索的主要过程：(1) 从初始或目的状态出发，并将它作为当前状态。(2) 扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针 。(3) 检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索。 753.7 搜索策略v1. 搜索方向搜索方向： (1) 数据驱动数据驱动：从初始状态出发的正向搜索。 正向搜索正向搜索从问题给出的条件出发。逆向搜索逆向搜索：从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时

46、需要哪些条件。 (2) 目的驱动目的驱动：从目的状态出发的逆向搜索。双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。(3) 双向搜索双向搜索763.7.1 回溯策略v 带回溯策略的搜索带回溯策略的搜索： 从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或“不可解结点”，即“死胡同”为止。若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。773.7.1 回溯策略1 AB 2E 3J 57 K9 G6 F10 H11 D8 C

47、回溯搜索示意图回溯搜索示意图783.7.1 回溯策略v回溯搜索的算法回溯搜索的算法(1) PS（path states）表）表：保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。 (2) NPS（new path states）表）表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展 。(3) NSS（no solvable states）表）表：不可解状态集，列出了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。 793.7.1 回溯策略v图搜索算法（深度优先、宽度优先、最好优先搜索等）的回

48、溯思想：（1）用未处理状态表（NPS）使算法能返回（回溯）到其 中任一状态。 （2）用一张“死胡同”状态表（NSS）来避免算法重新搜索 无解的路径。 （3）在PS 表中记录当前搜索路径的状态，当满足目的时可 以将它作为结果返回。 （4）为避免陷入死循环必须对新生成的子状态进行检查， 看它是否在该三张表中 。800S123456789103.7.2 宽度优先搜索策略vopen表（NPS表）：已经生成出来但其子状态未被搜索的状态。vclosed表（ PS表和NSS表的合并）：记录了已被生成扩展过的状态。 宽度优先搜索法中状态的搜索次序宽度优先搜索法中状态的搜索次序81v例例5.4 通过搬动积木块，

49、希望从初始状态达到一个目的状态，即三块积木堆叠在一起。 3.7.2 宽度优先搜索策略BCAABC(a) 初始状态(b) 目的状态 积木问题积木问题82v操作算子为MOVE（X，Y）：把积木X搬到Y（积木或桌面）上面。3.7.2 宽度优先搜索策略MOVE（A，Table）：“搬动积木A到桌面上”。 操作算子可运用的先决条件：（1）被搬动积木的顶部必须为空。（2）如果 Y 是积木，则积木 Y 的顶部也必须为空。（3）同一状态下，运用操作算子的次数不得多于一次。83ABABACCBACCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(C,A)MOVE(A,C)MOVE

50、(B,A)MOVE(B,C) MOVE(C,A)MOVE(C,B) MOVE(C,B)MOVE(A,B)0S1S2S3S4S5S6S7S8S9S10S没有后裔，失败退出 积木问题的宽度优先搜索树3.7.2 宽度优先搜索策略843.7.3 深度优先搜索策略0S12345678910111213KK 深度优先搜索法中状态的搜索次序0S12345678910111213KK深度优先搜索法中状态的搜索次序85v在深度优先搜索中，当搜索到某一个状态时，它所有的子状态以及子状态的后裔状态都必须先于该状态的兄弟状态被搜索。 v为了保证找到解，应选择合适的深度限制值，或采取不断加大深度限制值的办法，反复搜索，

51、直到找到解。 3.7.3 深度优先搜索策略86v深度优先搜索并不能保证第一次搜索到的某个状态时的路径是到这个状态的最短路径。 v对任何状态而言，以后的搜索有可能找到另一条通向它的路径。如果路径的长度对解题很关键的话，当算法多次搜索到同一个状态时，它应该保留最短路径。 3.7.3 深度优先搜索策略87v例例5.5 卒子穿阵问题卒子穿阵问题，要求一卒子从顶部通过下图所示的阵列到达底部。卒子行进中不可进入到代表敌兵驻守的区域（标注1），并不准后退。假定深度限制值为5。 3.7.3 深度优先搜索策略000100100100000121342134行列图5.10阵列图000100100100000121

52、342134行列图5.10阵列图 阵列图阵列图 883.7.3 深度优先搜索策略open表：S17、S18closed表：S0S16 0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2,2(11S)1 ,2(12S)1 ,3(13S)3,2(15S)4,2(16S)4,3(17S)4,4(18S)4,1(死死死死深度限制解 0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2

53、,2(11S)1 ,2(12S)1 ,3(13S)3,2(15S)4,2(16S)4,3(17S)4,4(18S)4,1(死死死死深度限制解卒子穿阵的深度优先搜索树89归归结结演演绎绎推推理理v3.1 推理的基本概念推理的基本概念 v3.2 自然演绎推理自然演绎推理 v3.3 谓词公式化为子句集的方法谓词公式化为子句集的方法v3.4 鲁宾逊归结原理鲁宾逊归结原理v3.5 归结反演归结反演v3.6 应用归结反演求解问题应用归结反演求解问题 v3.7 盲目搜索盲目搜索v3.8 产生式系统产生式系统v3.9 启发式搜索启发式搜索v3.10 非单调推理非单调推理v3.11 消解原理消解原理903.8

54、启发式图搜索策略o3.8.1 启发式策略启发式策略o3.8.2 启发信息和估价函数启发信息和估价函数o3.8.3 A搜索算法搜索算法o3.8.4 A*搜索算法及其特性分析搜索算法及其特性分析913.8.1 启发式策略v“启发启发”（heuristic）：关于发现和发明操作算子及搜索方法的研究。v在状态空间搜索中，启发式启发式被定义成一系列操作算子，并能从状态空间中选择最有希望到达问题解的路径。v启发式策略启发式策略：利用与问题有关的启发信息进行搜索。923.8.1 启发式策略v运用启发式策略的两种基本情况运用启发式策略的两种基本情况： （1）一个问题由于在问题陈述和数据获取方面固有的模糊性，可

55、能会使它没有一个确定的解。 （2）虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索 的深度呈指数级增长。93v 例例5.6 一字棋一字棋。在九宫棋盘上，从空棋盘开始，双方轮流在棋盘上摆各自的棋子 或 （每次一枚），谁先取得三子一线（一行、一列或一条对角线）的结果就取胜。 3.8.1 启发式策略 和 能够在棋盘中摆成的各种不同的棋局就是问题空间中的不同状态。 9个位置上摆放空， ， 有 39 种棋局。 可能的走法 ： 。1789943.8.1 启发式策略赢的几率赢的几率赢的几率图5.12 启发式策略的运用赢的几率赢的几率赢的几率图5.12 启发式策略的运用 启发式

56、策略的运用启发式策略的运用95图5.13启发式搜索下缩减的状态空间启发式搜索下缩减的状态空间启发式搜索下缩减的状态空间963.8.2 启发信息和估价函数v在具体求解中，能够利用与该问题有关的信息来简化搜索过程，称此类信息为启发信息启发信息。v启发式搜索启发式搜索：利用启发信息的搜索过程。973.8.2 启发信息和估价函数v 求解问题中能利用的大多是非完备的启发信息：（1）求解问题系统不可能知道与实际问题有关的全部信息，因而无法知道该问题的全部状态空间，也不可能用一套算法来求解所有的问题。（2）有些问题在理论上虽然存在着求解算法，但是在工程实践中，这些算法不是效率太低，就是根本无法实现。一字棋：

57、9！，西洋跳棋：1078，国际象棋：10120，围棋：10761。假设每步可以搜索一个棋局，用极限并行速度（10-104年/步）来处理，搜索一遍国际象棋的全部棋局也得1016年即1亿亿年才可以算完！ 983.8.2 启发信息和估价函数v启发信息的分类： （1）陈述性启发信息 （2）过程性启发信息 （3）控制性启发信息v利用控制性的启发信息的情况： （1）没有任何控制性知识作为搜索的依据，因而搜索的每一步完全是随意的。 （2）有充分的控制知识作为依据，因而搜索的每一步选择都是正确的，但这是不现实的。993.8.2 启发信息和估价函数v 估价函数的任务就是估计待搜索结点的“有希望”程度，并依次给它

58、们排定次序（在open表中）。o 估价函数 f(n)：从初始结点经过 n 结点到达目的 结点的路径的最小代价估计值，其一般形式是 f(n)=f(n)+h(n) 一般地，在 f(n)中，f(n)的比重越大，越倾向于宽度优先搜索方式，而 h(n)的比重越大，表示启发性能越强。100v 例例5.7 八数码的估价函数八数码的估价函数设计方法有多种，并且不同的估价函数对求解八数码问题有不同的影响。 最简单的估价函数：取一格局与目的格局相比，其位置不符的将牌数目。 较好的估价函数：各将牌移到目的位置所需移动的距离的总和。 第三种估价函数：对每一对逆转将牌乘以一个倍数。 第四种估价函数：克服了仅计算将牌逆转

59、数目策略的局限，将位置不符将牌数目的总和与3倍将牌逆转数目相加。 3.8.2 启发信息和估价函数1013.8.3 A搜索算法v启发式图搜索法的基本特点启发式图搜索法的基本特点：如何寻找并设计一个与问题有关的 h(n)及构出 f(n)=f(n)+h(n) 然后以 f(n) 的大小来排列待扩展状态的次序，每次选择f(n) 值最小者进行扩展。o open表：保留所有已生成而未扩展的状态。o closed表：记录已扩展过的状态。o 进入open表的状态是根据其估值的大小插入到表中合适的位置，每次从表中优先取出启发估价函数值最小的状态加以扩展。 102v一般启发式图搜索算法（一般启发式图搜索算法（简记为

60、简记为A）procedure heuristic_searchopen：=start；closed：= ；f(s)：=g(s)+h(s)；*初始化while open dobegin从open表中删除第一个状态，称之为n；if n=目的状态then return(success)；生成n的所有子状态；if n没有任何子状态then continue；for n的每个子状态docase子状态is not already on open表or closed表；begin计算该子状态的估价函数值；将该子状态加到open表中； end； 103case子状态is already on open表：if