《人工智能原理课件精编版》由会员分享，可在线阅读，更多相关《人工智能原理课件精编版（13页珍藏版）》请在金锄头文库上搜索。
1、Agenda,3.1 引言 3.2 命题逻辑中的归结原理 3.3 谓词逻辑中的归结原理,3.1 Introduction,证明的基本思想是： 设F1、Fn、G为公式，G为F1、Fn的逻辑推论，当且仅当公式（F1Fn）G）是有效的 也可以采用反证法的思想： 设F1、Fn、G为公式，G为F1、Fn的逻辑推论，当且仅当公式（F1Fn G）是不可满足的 归结法的本质上就是一种反证法，它是在归结推理规则的基础上实现的： 为了证明一个命题P恒真，它证明其反命题P恒假，即不存在使得P为真的解释,3.2 命题逻辑中的归结原理,3.2.1 子句和子句形 3.2.2 归结 3.2.3 归结反演 3.2.4 合理性
2、和完备性 3.2.5 归结反演的搜索策略,3.2.1 子句和子句形（1）,文字是原子或其否定 子句是文字的析取 完备连接符集合： 合取范式（CNF） （L11 L1n1) (Lm1 Lmnm) 析取范式（DNF） （L11 L1n1) (Lm1 Lmnm) 定理： 对任意公式，都有与之等值的合取范式和析取范式 转换方法：一般方法 真值表方法,3.2.2子句和子句形（2）,一般方法 Eliminate implication signs by using the equivalent form using Reduce the scopes of signs by using DeMorgans
3、 law and by eliminating double signs Convert to CNF by using the associative and distributive laws.,3.2.2 Resolution,对任意三个子句 p、q 和 r p r, q r p q 或者： for C1= P C1, C2=P C2 P C1, P C2 C1 C2 归结式： R(C1, C2)=C1 C2 证明：,3.2.3 Resolution Refutations（1）,定理证明的任务: 由前提A1 A2 . An 推出结论B 即证明:A1 A2 . AnB 永真 转化为证明:
4、 A1 A2 . An B为永假式 归结推理就是:从A1 A2 . An B出发,使用归结推理规则来找出矛盾,最后证明定理A1 A2 . AnB的成立,來自 中国最大的资料库下载,3.2.3 Resolution Refutations（2）,归结方法是一种机械化的,可在计算机上加以实现的推理方法 可认为是一种反向推理形式 提供了一种自动定理证明的方法,3.2.3 Resolution Refutations（3）,一般过程: 建立子句集S 从子句集S出发,仅对S的子句间使用归结推理规则 如果得出空子句, 则结束;否则转下一步 将所得归结式仍放入S中 对新的子句集使用归结推理规则 转(3) 空
5、子句不含有文字,它不能被任何解释满足,所以空子句是永假的,不可满足的 归结过程出现空子句,说明出现互补子句对,说明S中有矛盾,因此S是不可满足的.,3.2.3 Resolution Refutations（4）,例子:证明(P Q) Q p 首先建立子句集: (P Q)Q (P) (P Q) Q P S=PQ, Q , P 对S作归结: (1) P Q (2) Q (3) P (4) P (1)(2)归结 (5) (3)(4)归结,3.2.4 Soundness and Completeness,归结原理是合理的 归结原理是完备的,3.2.5 Resolution Refutation Sea
6、rch Strategies,有序策略（Order strategies） Refinement strategies 支持集（Set of support）: 每次归结时，参与归结的子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后裔 该策略是完备的 线性输入（Linear Input）： 参与归结的两个子句中至少有一个是初始子句集中的子句 该策略是不完备的 祖先过滤（Ancestry Filtering） ： 参与归结的两个子句中至少有一个是初始子句集中的句子，或者是另一个子句的祖先 该策略是完备的,1、有时候读书是一种巧妙地避开思考的方法。20.8.1420.8.14Fri
7、day, August 14, 2020 2、阅读一切好书如同和过去最杰出的人谈话。23:27:0923:27:0923:278/14/2020 11:27:09 PM 3、越是没有本领的就越加自命不凡。20.8.1423:27:0923:27Aug-2014-Aug-20 4、越是无能的人，越喜欢挑剔别人的错儿。23:27:0923:27:0923:27Friday, August 14, 2020 5、知人者智，自知者明。胜人者有力，自胜者强。20.8.1420.8.1423:27:0923:27:09August 14, 2020 6、意志坚强的人能把世界放在手中像泥块一样任意揉捏。20
8、20年8月14日星期五下午11时27分9秒23:27:0920.8.14 7、最具挑战性的挑战莫过于提升自我。2020年8月下午11时27分20.8.1423:27August 14, 2020 8、业余生活要有意义，不要越轨。2020年8月14日星期五11时27分9秒23:27:0914 August 2020 9、一个人即使已登上顶峰，也仍要自强不息。下午11时27分9秒下午11时27分23:27:0920.8.14 10、你要做多大的事情，就该承受多大的压力。8/14/2020 11:27:09 PM23:27:092020/8/14 11、自己要先看得起自己，别人才会看得起你。8/14/2020 11:27 PM8/14/2020 11:27 PM20.8.1420.8.14 12、这一秒不放弃，下一秒就会有希望。14-Aug-2014 August 202020.8.14 13、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Friday, August 14, 202014-Aug-2020.8.14 14、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。20.8.1423:27:0914 August 202023:27,谢谢大家,
