《人工智能导论幻灯片(李俊丽)ch4-推理》由会员分享，可在线阅读，更多相关《人工智能导论幻灯片(李俊丽)ch4-推理（134页珍藏版）》请在金锄头文库上搜索。
1、1,第4 章 确定性推 理,2,本章学习要点,掌握谓词公式的概念及可满足性的定义、置换与合一的概念，掌握求取最一般合一置换的方法。 掌握归结原理及归结推理方法。（重点在谓词逻辑中） 掌握利用归结原理进行定理证明的方法。 掌握利用归结原理进行问题求解的方法。 了解归结过程中的控制策略。,3,4.1 概述,4.2 确定性推理,主 要 内 容,4,5,4.1.1 推理的基本概念 推理的定义 推理就是按照某种策略从已有事实和知识推出结论的过程。 一般来说，人工智能系统中的智能推理过程是由一些程序来完成的，这些程序在人工智能系统中称为推理机。,4.1 推理概述,6,4.1.2 推理的分类,按推理的逻辑基
2、础分类 1）演绎推理： 从已知的一般性知识出发，推理出适合于某种个别情况的结论过程。 即从一般到个别的推理。 常用形式：三段论法(大前提、小前提、结论),7,【演绎推理实例】,音乐系的学生至少会演奏一种乐器；（大前提） 李聪是音乐系的一名学生；（小前提） 李聪至少会演奏一种乐器。（结论）,8,2）归纳推理：,从大量特殊事例出发，归纳出一般性结论的推理过程。 即从个别到一般的推理过程。,9,3）默认推理：,在知识不完全的情况下，假设某些条件已经具备所进行的推理。 默认推理过程中可能会出现一些无效推理，但默认推理解决了在一个不完备知识集中进行推理的问题。,10,1) 确定性推理 推理时所有用的知识
3、和证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假，没有第三种情况出现。 2) 不确定性推理 推理时所用的知识和证据不都是确定的，推出的结论也不确定的。,按所用知识的确定性分类,11,1) 单调推理 在推理过程中随着推理的向前推进及新知识的加入，推出的结论呈单调增加的趋势，并且越来越接近最终目标。 2) 非单调推理 在推理过程中随着推理的向前推进及新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。,按推理过程的单调性分类,12,1) 启发式推理 推理过程中应用与问题有关的启发性知识，即解决问题的的策略、技巧及经验，以加快推理过程，提高搜索效
4、率。 2) 非启发式推理 在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理。这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现“组合爆炸”问题。,按推理中所用知识是否具有启发性分类,13,4.1 概述,4.2 确定性推理,主 要 内 容,14,4.2 确定性推理,15,【推理的逻辑基础】,逻辑是推理科学的研究。逻辑研究主要是研究推理的过程是否正确，推理过程中各个语句之间的关系，而不考虑某一个语句是否正确。 命题逻辑和谓词逻辑属于经典逻辑，是最先应用于人工智能的两种逻辑。其中谓词逻辑是在命题逻辑的基础上发展起来的，是一种表达能力很强的形式语言。,16,命题 能够分辨真假的语句
5、称为命题。 一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为原子命题。 原子命题是命题中最基本的单位，常用大写字母P,Q,R等表示。,4.2.1 命题逻辑基础,17,是 不是 是 是 不是 是,18,命题逻辑真值表,2. 连接词,19,连接词的优先级别,20,原子命题是命题公式。 A是命题公式，则A也是命题公式。 若A 和B都是命题公式，则AB、AB、AB、A B也都是命题公式。 按照上述规则由原子命题、连接词及圆括号所组成的字符串称为命题公式。,3. 命题公式,21, 他既聪明又用功。 应届高中生，得过数学或物理竞赛的一等奖，保送上大学。, 设P：他聪明。Q：他用功
6、。转换为：P Q。 设P：应届高中生。Q：保送上大学。A：得过数学竞赛一等奖。B：得过物理竞赛一等奖。表示为： P (AB)Q,例：将陈述句转化为命题公式。,【命题公式实例】,22,1.基本概念,4.2.2 一阶谓词逻辑基础,个体：独立存在的物体（抽象或具体）,个体：独立存在的物体（抽象或具体）,谓词：用于刻画个体性质、状态或个体间关系。,23,3. 谓词公式,2. 连接词：，,单个谓词是谓词公式，称为原子谓词公式。 若A是谓词公式，则 A也是谓词公式。 若A，B都是谓词公式，则(AB)，(AB)， (AB)，(AB)也是谓词公式 。 若A是谓词公式，则 也是谓词公式。 只有有限次的应用上述4
7、条规则构成的符号串才是谓词公式。,24,位于量词后面的单个谓词或者用括弧括起来的的合式公式称为量词的辖域。 在辖域内与量词同名的变元称为约束变元，不受约束的变元称为自由变元。,4.量词辖域与约束变元,25,永真式: 如果谓词公式P在每个非空个体域上均取得真值T，则称P永真。 永假式:如果谓词公式P在每个非空个体域上均取得真值F，则称P永假。 可满足式: 对于谓词公式P，如果至少存在一个值使得P的真值为T，则称公式P是可满足的。 不可满足式: 对于谓词公式P，如果不存在任何值使得P的真值为T，则称公式P是不可满足的。,5. 谓词公式的永真性,26, 交换律：,6. 谓词公式的等价性,27, 结合
8、律：,28, 结合律：,29, 分配律：,30, 分配律：,31, 狄 摩根律：,32, 狄 摩根律：,33, 吸收律：,34, 吸收律：,35, 同一律：, 零律：,36, 双重否定律：, 排中律：, 矛盾律：,37, 蕴涵等值式：,38, 等价等值式：,39, 逆反律：,40, 归谬论：,41,合取式：P与Q，记做 PQ 析取式：P或Q，记做 PQ 蕴含式：如果P则Q，记做 PQ 等价式：P当且仅当Q，记做 PQ,7. 谓词公式型式：,42,简单合取式： 仅由有限个命题变量或其否定构成的合取式。 简单析取式： 仅由有限个命题变量或其否定构成的析取式。 合取范式： 仅由有限个简单析取式组成的
9、合取式。如：P (P Q) ( P Q) 析取范式： 仅由有限个简单合取式组成的析取式。如：P (P Q) ( P Q),43,例：求取P(QR)S的合取范式。,解：,44,5.换名规则,45, 约束变元换名规则:, 量词转换律:, 量词分配律:,6.基本规则和等价式,46, 消去量词等价式: 设个体域为有穷集合(a1,a2,an), 量词辖域收缩与扩张等价式:,47, 量词辖域收缩与扩张等价式(续):,48,4.2.3 自然演绎推理方法,从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程。 最基本的推理规则有： 假言三段论 T规则 假言推理 P规则 拒取式,49,
10、【演绎推理实例】,如果一个人大学毕业，则他就具有独立生活的能力。 如果一个人具有独立生活的能力，则他就可以离开父母。 如果一个人大学毕业，则他就可以离开父母。,假言三段论,50,【演绎推理实例】,如果S是音乐系学生，则S至少会演奏一样乐器。 张艺是音乐系学生。 张艺至少会演奏一样乐器。,假言推理,51,【演绎推理实例】,如果S是音乐系学生，则S至少会演奏一样乐器。 张艺不会演奏任何乐器。 张艺不是音乐系学生。,拒取式推理,52,【演绎推理常见错误】,如果S是音乐系学生，则S至少会演奏一样乐器。 张艺会演奏电子琴。 张艺是音乐系学生。,肯定后件错误,53,【演绎推理常见错误】,如果S是音乐系学生
11、，则S至少会演奏一样乐器。 张艺不是音乐系学生。 张艺不会演奏任何一样乐器。,否定前件错误,54,【实例】,设已知如下事实： R, S, RT, ST P, P Q 求证：Q为真。,证明：因为 所以Q为真。,P规则及假言推理 引入合取词 T规则及假言推理 T规则及假言推理,55,【演绎推理的特点】,只是将蕴涵在一般性知识前提中的事实揭示出来，不能增殖新的知识； 由已知事实推出的结论可能有多个； 优点在于符合人的思维习惯，易于理解； 缺点在于容易产生知识或规则爆炸，不利于对复杂问题的求解。,56,4.2.4 归结推理方法,归结法是与自然演绎法完全不同的新的逻辑演算算法。 归结法的基本原理是采用反
12、证法（也称为反演推理方法）：将待证明的表达式转换成为逻辑公式（谓词公式），然后再进行归结，归结能顺利完成，则证明原公式是正确的。,57,1. 范式,谓词演算公式的标准型，即范式。一般有2种范式： 前束型范式 一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式之末，同时公式中不出现连接词、，这种形式的谓词公式称为前束型范式。,58,优点：量词全部集中在公式的前面； 缺点：其首标杂乱无章，量词排列没有一定的规则。,59,例：求下式的前束范式,解：,60,从前束型范式中消去全部存在量词所得到的公式，称为Skolem范式，或Skolem标准型。 Skolem标准型的一
13、般形式为：,Skolem范式,61,62,【Skolem范式的获取步骤】,消去谓词公式G中的蕴涵（）和双条件（）符号； 减少否定符号（ ）的辖域，使否定符号最多只作用到一个谓词上； 重新命名变元，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。,63,消去存在量词（ ）。将该量词约束的变量用任意常量(a, b等)或任意变量的函数(f(x), g(y)等)代替。 如果存在量词左边没有任何任意量词，则只将其改写为个体常量； 如果存在量词的左边有任意量词，消去时该变量改写为任意量词的函数。,64,把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分； 母式化为合取范
14、式。 至此所得的公式就是谓词公式G的skolem标准型。,65,例：将下式化为Skolem标准形。,解： 消去符号 ，得：, 深入到量词内部，得：,【Skolem范式的获取实例】,66, 任意量词左移，利用分配律，得：, 变量易名，存在量词左移，直至所有的量词移到 前面，得：,67, 消去存在量词，略去任意量词， 得Skolem标准形 ：,68,例：将下式化为Skolem标准形。,解：,69,70,2.子句与子句集,原子公式：不含任何连接词的谓词公式。 文 字：原子或原子的否定。 子 句：由一些文字组成的析取式。 空 子 句：不包含任何文字的子句，表示为NIL。空子句是永假的。 子 句 集：由
15、子句构成的集合。,71,【子句集S的求取】,由于Skolem 标准型的母式已为合取式，从而母式的每一个合取项都是一个子句。 子句集的求取方法为： 将谓词公式G化为 Skolem 标准型； 消去Skolem 标准型前面的全称量词； 用“，”取代“”，并表示为成集合形式。,72,【实例】,73,定理1： G是不可满足的 S是不可满足的,【子句集S与谓词公式G的关系】,证明一个公式的不可满足性，转化为证明其子句集S的不可满足性。,74,3. Robinson归结原理（消解原理）,检查子句集S中是否有空子句，若有，则表明S是不可满足的；若没有，就在子句集中选择合适的子句对其进行归结推理，如果能推出空子句，就说明子句集是S是不可满足的。,什么是归结？ 如何进行归结推理？,75,（1）命题逻辑中的归结原理,若P是原子公式，则称P与 为互补文字。 设C1,C2是命题逻辑中的两个子句，C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1,C2中分别删除L1,L2，再将剩余部分进行析取，构成一个新子句为C12，这一过程称为归结，所得到的子句C12称为C1,C2的归结式(或消解式)，C1,C2称为其归结式C12的亲本子句， L1,L2称为消解基。,76,设： C1=乛PQR C2=乛QS 求： C1,C2的归结式。 解： 由于Q和乛Q是互补文字，则消去互补文字后得： C12=乛PRS,7
