《人工智能基础》第三章课件

人工智能基础第三章经典人工智能经典人工智能知识表示方法搜索技术知识推理不确定性推理知识表示方法知识表示方法：人工智能问题的求解是以知识为基础的将已获得的有关知识以计算机内部代码形式加以合理地描述、存储，以使有效地利用这些知识知识、信息、数据：有格式的数据经过处理、解释过程会形成信息有关的信息关联到一起，经过处理就形成了知识知识是用信息表达的，信息则是用数据表达的知识的特性相对正确性不确定性可表示性可利用性知识的分类有可从不同的角度分，得到不同的分类结果按作用范围分类通用性知识、领域性知识按作用及表示分类事实性知识、规则性知识、控制性知识、元知识按确定性分类确定知识、不确定知识按人类的思维及认识方法分类逻辑性知识、形象性知识知识的表示研究用机器表示知识的可行性、有效性的一般方法一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用陈述性知识表示描述事实性知识优点：简洁灵活缺点：工作效率低，推理过程不透明，不易理解过程性知识表示描述规则性知识和控制结构知识优点：推理过程直接清晰，模块化，效率高缺点：不够严格，知识间有交互重叠，灵活性差，知识的增减不方便知识表示的方法一阶谓词逻辑表示法产生式表示法语义网络表示法一阶谓词逻辑表示法一阶谓词逻辑表示法：以数理逻辑为基础,是到目前为止能够表达人类思维活动规律的一种最精确的形式语言与人类的自然语言比较接近，可方便地存储到计算机中去，并被计算机做精确处理是一种最早应用于人工智能中的表示方法知识的谓词逻辑表示法：人类的一条知识可以由具有完整意义的一句或几句话表示出来这些知识要用谓词逻辑表示出来，用的是一个或多个谓词公式谓词公式表示知识的步骤例1：事实性知识“小明是学生，小红也是学生”的谓词逻辑表示IsStudent(Xiaoming)∧IsStudent(Xiaohong)例2：规则性知识“如果a，则b”用蕴含式表示：a→b定义谓词及个体，确定每个谓词及个体的确切含义“小明是学生”：“小明”是个体，“是学生”是谓词，可以定义谓词为IsStudent(x)根据要表达的事物或概念，为每个谓词中的变元赋以特定值IsStudent(Xiaoming)根据所要表达的知识的语义，用适当的联接符号将各个谓词连接起来，形成谓词公式IsStudent(Xiaoming)∧IsStudent(Xiaohong)一阶谓词逻辑表示法的特点自然性：谓词逻辑是一种接近于自然语言的形式语言用它表示问题易于被人理解和接受精确性：谓词逻辑适宜于精确性知识的表示，而不适宜于不确定性知识的表示谓词公式的逻辑值只有“真”和“假”两种结果，而对某一知识有百分之几的可能性为“真”或“假”的情况无法表示易实现：用谓词逻辑法表示的知识可以比较容易地转换为计算机的内部形式易于模块化，便于对知识的添加、删除和修改产生式表示法美国数学家Post，1943年提出了一种计算形式体系里所使用的术语。主要是使用类似文法的规则，对符号串做替换运算。这就是最早的一个产生式系统到了60年代，产生式系统成为认知心理学研究人类心理活动中信息加工过程的基础，由此心理学家认为，人脑对知识的存储就是产生式形式。因此，用它来建立人类认知模型到目前为止，产生式系统已发展成为人工智能系统中最典型最普遍的一种结构。产生式表示方法是专家系统的第一选择的知识表达方式产生式表示法可表示知识的种类：表达具有因果关系的知识，包括事实型知识和规则性知识根据知识是确定性的还是不确定性的分别进行表示产生式的基本形式：P→Q

或IFPTHENQP是产生式前提，Q是一组结论或操作产生式与谓词逻辑中蕴涵式的区别：产生式可以表示精确与不精确知识，蕴涵式只能表示精确知识产生式没有真值，蕴涵式有真值产生式可以不精确匹配，蕴涵式需要精确匹配产生式表示不同种类的知识

确定性规则知识：P→Q或IFPTHENQ例如，所有动物都会死，甲是动物，所以甲也会死产生式表达的知识：所有动物都会死∧甲是动物→甲会死

不确定性规则知识：P→Q（置信度）或IFPTHENQ（置信度）例如，如果乌云密布，那么将要下雨的置信度是80%产生式表达式：乌云密布→将要下雨（0.8）产生式表示不同种类的知识

确定性事实性知识：三元组（对象，属性，值）三元组（关系，对象1，对象2）例如“老李年龄是55岁”，可以写成（李，年龄，55）“老李、老王是朋友”则可写成（朋友，李，王）

不确定性事实性知识：四元组（对象，属性，值，可信度）四元组（关系，对象1，对象2，可信度）例如“老李年龄可能是30岁，可能性70％”，可以用四元组（李，年龄，30，0.7）来表示产生式系统

专家系统：以产生式表示知识的，相应的系统称作产生式系统由规则库、推理机、和综合数据库三部分组成规则库规则库：规则是以产生式表示的，规则集蕴涵着将问题从初始状态转换成目标状态的那些变换规则规则库是某领域知识（规则）的存储器，是专家系统的核心，是产生式系统进行问题求解和推理的基础规则库中知识的完整性、一致性、准确性、灵活性以及知识组织的合理性，都是规则库的关键特性，会对产生式系统的性能和运行效率产生直接的影响综合数据库综合数据库：存放输入的事实、外部数据库输入的事实以及推理的中间结果（事实）和最后结果当规则库中的某条规则的前提与综合数据库中的某些事实匹配时，该产生式规则被激活，并把它的结论放入综合数据库中，作为推理的中间结果和后面推理的前提综合数据库是动态的，不断有新的推理结果添加进来推理机推理机：一个解释程序，负责整个产生式系统的运行，控制和协调规则库与数据库运行包含了推理方式和控制策略控制策略就是确定如何选择或应用规则，包括匹配、冲突解决和操作这三个步骤用综合数据库中的事实与产生式规则的前提条件进行匹配按冲突消解策略从匹配的规则中选择一条规则

执行选中规则的动作，修改综合数据库推理方式有正向推理、反向推理和双向推理产生式系统的运行过程建立产生式规则更新数据库，将已知的事实放入综合数据库考察每一条产生式规则，如果条件部分和综合数据库中的数据匹配，则规则的结论放入综合数据库一个实际的产生式系统，其目标条件一般不会只经一步推理就可满足，往往要经过多步推理才能满足或者证明问题无解产生式系统的运行过程就是从初始事实出发，寻求到达目标条件的通路的过程产生式系统的运行过程也是一个搜索的过程，但一般把产生式系统的整个运行过程也称为推理

产生式系统实例动物分类问题的产生式系统描述及其求解规则库r1：若某动物有奶，则它是哺乳动物。r2：若某动物有毛发，则它是哺乳动物。r3：若某动物有羽毛，则它是鸟。r4：若某动物会飞且生蛋，则它是鸟。r5：若某动物是哺乳动物且有爪且有犬齿且目盯前方，则它是食肉动物。r6：若某动物是哺乳动物且吃肉，则它是食肉动物。r7：若某动物是哺乳动物且有蹄，则它是有蹄动物。产生式系统实例规则库（续）r8：若某动物是有蹄动物且反刍食物，则它是偶蹄动物。r9：若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。r10：若某动物是食肉动物且黄褐色且有黑色斑点，则它是金钱豹。r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点，则它是长颈鹿。r12：若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。r13：若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是驼鸟。r14：若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。r15：若某动物是鸟且善飞且不怕风浪，则它是海燕。产生式系统实例综合数据库f1：某动物有毛发。f2：吃肉。f3：黄褐色。f4：有黑色条纹。目标条件为：该动物是什么？产生式系统实例解：该动物分类问题的正向推理树语义网络表示法语义网络：通过概念及其语义关系来表示知识的一种带标注的有向网络图最简单的语义网络可由一个三元组表示：（结点A，弧R，结点B）或由有向图表示结点表示概念、事物、事件、情况等弧有方向、有标注的。方向体现主次，结点A为主，结点B为辅弧上的标注表示结点A的属性或结点A和结点B之间的关系。基本语义关系语义网络的基本语义关系：

类属关系：指不同事物间的分类关系、成员关系或实例关系，常用有三种：ISA:(Isa)、AMO:(A-Member-Of)、AKO：(A-Kind-Of)

包含关系：又叫聚类关系，是指部分与整体之间的关系。它和类属关系最主要的区别是包含关系一般不具备属性的继承性。常用的包含关系是：Part-of，含义为“是一部分”

占有关系：占有关系是事物或属性之间的“具有”关系。常用的占有关系是Have

时间关系：时间关系是指不同事件在其发生时间方面的先后次序关系，节点间的属性不具有继承性。常用的时间关系有三种：Before,After,During基本语义关系语义网络的基本语义关系：

位置关系：位置关系是指不同事物在位置方面的空间关系，常用有Located-on(at,under,inside,outside)

因果关系：因果关系是用于表示规则性知识，常用If-then联系表示两个节点间的因果关系

相近关系：相近关系指不同事物的某些特征的相似和接近。常用的相近关系有：Similar-to,Near-to

推论关系：推论关系是指从一个概念推出另一个概念的语义关系

组成关系：组成关系是一种一对多联系，用于表示某一事物由其他一些事物构成，常用Composedof联系表示

属性关系：属性关系用于表示一个节点是另一个节点的属性关系语义网络的组成部分语义网络的组成部分：1)词法部分：决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。2)结构部分：叙述符号排列的约束条件，指定各弧线连接的节点对。3)过程部分：说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。4)语义部分：确定与描述相关的（联想）意义的方法即确定有关节点的排列及其占有物和对应弧线经典人工智能知识表示方法搜索技术知识推理不确定性推理搜索技术搜索的概念及种类盲目搜索状态空间图的一般搜索算法宽度优先搜索策略深度优先搜索策略代价树的宽度优先搜索策略代价树的深度优先搜索策略启发式搜索局部最佳优先搜索全局最佳优先搜索A*启发式搜索算法搜索的概念及种类

搜索：找到从初始事实到问题最终答案的一条推理路线，而且是时间和空间复杂度最小的求解路线搜索种类：

盲目搜索：系统根据事先确定好的某种固定排序（依次或随机）调用规则

启发式搜索：考虑问题领域可应用的知识，根据具体情况动态地确定规则的排序，优先调用较合适的规则使用盲目搜索策略为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来。不同的知识表示对应着相应的求解方法和搜索相对应的知识表示法有两种：状态空间表示法与/或树表示法状态空间表示法状态空间表示法：用来表示问题及其搜索过程的一种方法

状态空间由一个四元组构成（1）状态，描述问题求解过程中不同时刻状况的数据结构。（2）算符：使问题由一个状态变为另一个状态的操作。（3）状态空间：一个问题的全部状态及一切可用算符构成的集合。一般包括3部分（初始状态集合S，算符集合F，目标状态集合G）(S,F,G)（4）问题的求解：从S出发经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用算符的序列构成了问题的一个求解。状态空间表示法状态空间图状态空间图：把状态空间的问题求解过程用图的形式表示出来节点代表状态，弧代表算符四皇后问题：每行、每列和对角线上只允许出现一枚棋子，即棋子之间不许相互攻击状态空间搜索的几个概念

扩展：用合适的算符对某个节点进行操作，生成一组后继节点，扩展过程就是求后继节点的过程。

已扩展节点：已经求出了其后继节点的节点。

未扩展节点：尚未求出后继节点的节点。

OPEN表：存放未扩展的节点，记录当前节点及其父节点。

CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点。状态空间的一般搜索算法一般搜索算法的描述：建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中建立CLOSED表，且置为空表判断OPEN表是否为空表，若为空，则问题无解，退出选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到S0的路径得到。若不是转⑥状态空间的一般搜索算法（续）一般搜索算法的描述（续）：扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点，设置一个指向父节点n的指针，并把这些节点放入OPEN表中；对于已在G中出现过的M中的节点，确定是否需要修改指向父节点的指针；对于已在G中出现过并已在closed表中的M中的节点，确定是否需要修改通向他们后继节点的指针。按某一任意方式或某种策略重排OPEN表中节点的顺序转③状态空间的搜索策略流程图宽度优先搜索策略定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-firstsearch)特点这种搜索是逐层进行的。在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点性质当问题有解时，一定能找到解当问题为单位消耗值，且问题有解时，一定能找到最优解算法与问题无关，具有通用性时间效率和空间效率都比较低

宽度优先搜索算法把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。如果OPEN是个空表，则没有解，失败退出；否则继续。把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。扩展节点n。如果没有后继节点，则转向上述第(2)步。

把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。宽度优先算法流程图宽度优先搜索实例例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：

1238

4765宽度优先搜索实例23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654深度优先搜索策略定义在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列特点

首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径

深度界限为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处

深度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出(5)如果没有后继节点，则转向上述第(2)步。(6)扩展节点n，把n的所有后继节点放到OPEN表前端，并提供从这些后继节点回到n的指针。转向第(2)步。深度优先算法流程图深度优先搜索实例代价树的宽度优先搜索1、定义状态空间图中各节点之间有向边的代价是不同的，有向边上标有代价的搜索树成为代价搜索树2、特点每次从OPEN表中选择一个代价最小的节点，移入CLOSED表3、连线代价C(i,j):从节点i到其后继节点j的连线代价路径代价g(x):从初始节点到任意节点x的路径代价

g(j)=g(i)+C(i,j)代价树的宽度优先搜索算法(1)把起始节点放到OPEN表中，令g(S0)=0(2)如果OPEN是个空表，则没有解，失败退出；否则继续(3)把OPEN表中代价最小的节点（即排在最前端的节点n），移入CLOSED的扩展节点表中(4)如果n是目标节点，问题得解，退出；否则继续(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)(6)对节点n进行扩展，将他们的所有后继节点放到OPEN表中，并对每个后继节点j计算其总代价g(j)=g(i)+C(i,j),为每个后继节点指向n节点的指针，然后根据节点的代价大小对OPEN表中的所有节点进行从小到大的排序(7)转向第(2)步代价树的宽度优先搜索的流程图代价树的深度优先搜索

代价树的宽度优先搜索每次从OPEN表中的全体节点中选择代价最小的节点移入CLOSED表进行扩展或判断。

代价树的深度优先搜索从刚刚扩展的节点的后继节点中选择一个代价最小的节点移入CLOSED表中，并进行扩展或判断。代价树的深度优先搜索算法(1)把起始节点放到OPEN表中，令g(S0)=0(2)如果OPEN是个空表，则没有解，失败退出；否则继续(3)把OPEN表中的第一个节点（代价最小的节点n），移入CLOSED表(4)如果n是目标节点，问题得解，退出。否则继续(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)(6)对节点n进行扩展，并将其后继节点按有向边代价（C(i,j)）从小到大排序后放到OPEN表前端，并为每个后继节点设置指向n节点的指针(7)转向第(2)步代价树的深度优先搜索的流程图启发式搜索

盲目搜索的一个特点就是它们的搜索路线是事先决定好的，没有利用被求解问题的任何特性信息能否找到一种方法，能够充分利用待求解问题的某些特性，以指导搜索朝着最有利于问题求解的方向发展，即在选择那些最有希望的节点加以扩展，那么搜索的效率就会大大提高这种利用问题的自身特性信息来提高搜索效率的搜索策略，称为启发式搜索启发信息与估价函数启发信息利用与问题有关的知识（即：启发信息）来引导搜索，达到减少搜索范围，降低问题复杂度的搜索过程称为启发式搜索方法核心问题启发信息应用，启发能力度量和如何获得启发信息启发信息的强度强：降低搜索工作量，但可能导致找不到最优解。弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解启发式搜索目的引入启发知识，在保证找到最佳解的前提下，尽可能减少搜索范围，提高搜索效率搜索算法的效果：可以用启发能力的强弱来度量考虑解路径的消耗值和求得路径所需搜索的消耗值两者的某种组合最小考虑搜索方法对求解所有可能遇见的问题，其平均的组合消耗最小如何寻找最有希望的节点要对OPEN表进行排序，就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度。希望能找到最有希望通向目标节点的待扩展节点优先扩展估价函数定义一个估价函数f（EvaluationFunction），对当前的搜索状态进行评估，找出一个“最有希望”的节点来扩展。估价函数的格式：

f(n)=g(n)+h(n) f(n)：估价函数

g(n)：代价函数初始节点到节点n已实际付出的代价

h(n)：启发函数从节点n到目标节点的最优路径的估计代价局部最佳优先搜索(1)把起始节点放到OPEN表中，并计算估价函数f(S0)(2)如果OPEN是个空表，则没有解，失败退出；否则继续(3)把OPEN表中的第一个节点（股价函数最小的节点n），移入CLOSED表(4)如果n是目标节点，问题得解，退出。否则继续(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)(6)对节点n进行扩展，并对其所有后继节点计算估价函数f(n)的值，并按其值从小到大排序后放到OPEN表前端，并为每个后继节点设置指向n节点的指针(7)转向第(2)步局部最佳优先搜索流程图搜索技术搜索的概念及种类盲目搜索状态空间图的一般搜索算法宽度优先搜索策略深度优先搜索策略代价树的宽度优先搜索策略代价树的深度优先搜索策略启发式搜索局部最佳优先搜索全局最佳优先搜索A*启发式搜索算法全局最佳优先搜索(1)把起始节点放到OPEN表中，并计算估价函数f(S0)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中的第一个节点（股价函数最小的节点n），移入CLOSED表。(4)如果n是目标节点，问题得解，退出。否则继续。(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。(6)对节点n进行扩展，并对其所有后继节点计算估价函数f(n)的值，并为每个后继节点设置指向n节点的指针。把这些后继节点都送入OPEN表，然后对OPEN表中的全部节点按照估价函数值从小到大的顺序排序。(7)转向第(2)步。全局最佳优先搜索流程图全局最佳优先搜索实例定义评价函数：

f(n)=g(n)+h(n)=d(n)+h(n)

d(n)：代表节点的深度，表示从初始节点到当前节点的消耗值

h(n)：为当前节点“不在位”的牌数

h(n)=4全局最佳优先搜索实例A*算法A*算法是一种有序搜索算法，其特点在于对估价函数的定义令k(ni，nj)表示任意两个节点ni和nj之间最小代价路径的实际代价从节点n到某个具体的目标节点ti，某一条最小代价路径的代价可由k(n,ti)给出令h*(n)表示整个目标节点集合｛ti｝上所有k(n,ti)中最小的一个h*(n)就是从n到目标节点最小代价路径的代价从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径对于任何不能到达目标节点的节点n，函数h*没有定义A*算法的估价函数估价函数f(n)=g(n)+h(n)是对下列函数的估计或近似：

f*(n)=g*(n)+h*(n)f*(n)：从初始节点到节点n的一条最佳路径的实际代价加上节点n到目标节点的最佳路径的代价之和。g*(n)：从初始节点到节点n之间最小路径的实际代价h*(n)：从节点n到目标节点的最小代价路径上代价恒有：g*(n)≤g(n)A*算法中，要求启发函数h(n)是h*(n)的下界h(n)≤h*(n)极端情况下，若h(n)=0，一定能找到最佳解路径A*条件举例8数码问题h(n)=“不在位”的牌数h*(n)=“不在位”牌的距离和2831647512345768将牌1：1将牌2：1将牌6：1将牌8：2知识推理推理概述命题逻辑谓词逻辑自然演绎推理推理概述推理的基本概念推理是指从已知事实出发，运用已掌握的知识，推导出其中蕴含的事实性结论或归纳出某些新的结论的过程推理所用的事实与求解问题有关的初始证据推理过程中所得到的中间结论，这些中间结论可以作为进一步推理的已知事实或证据确定性推理分类按推理时所用知识的确定性来划分确定性推理不确定性推理按推理过程的单调来划分单调推理：非单调推理按照推理的逻辑基础来划分演绎推理归纳推理演绎推理和归纳推理演绎推理一般原理到特殊事实的推理方法从已知的一般性知识出发，推理出适合于特殊条件的结论三段论推理是演绎推理中的一种最常用形式，包括大前提（已知的一般原理）、小前提（所研究的特殊情况）和结论（符合一般原理的特殊情况判断）三部分归纳推理从特殊事例中概括出一般性结论的推理关于个别事物的观点推广到范围较大的观点归纳结论不具备逻辑必然性按特殊事例考察范围分为完全归纳推理、不完全归纳推理按使用的方法可分为枚举归纳推理、类比归纳推理等方法确定性推理演绎推理所得出的结论蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识归纳推理所推出的结论是没有包含在前提中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程归纳是我们获得关于这个实在世界的一般性事实的一种方法人工智能系统的推理过程人工智能系统的构成推理机：一些程序来完成的综合数据库：存放有用于推理的事实或证据知识库：存放有用于推理所必须的知识人工智能系统不仅受推理方法影响，也和推理的控制策略有关推理的控制策略：推理方向搜索策略冲突消解策略求解策略限制策略确定性推理正向推理（证据驱动）反向推理（目标驱动）双向推理正向推理正向推理又称数据驱动推理、演绎推理由条件推出结论的方向进行的推理方式，从一组事实出发，使用一定的推理规则，来证明目标事实或命题的成立基本算法（1）从初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可用知识集KS（2）按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中作为下一步推理的已知事实，再在KB中选取可适用知识构成KS。（3）重复（2），直到求得问题的解或KB中再无可适用的知识。正向推理流程图正向推理的问题实现正向推理需要解决的问题确定匹配（知识与已知事实）的方法按什么策略搜索知识库冲突消解策略

优点正向推理简单易实现

缺点目的性不强效率低反向推理反向推理目标驱动推理由结论出发，逐级验证该结论的正确性，直至已知条件基本算法（1）选定一个假设目标（2）寻找支持该假设的证据，若所需的证据都能找到，则原假设成立（3）若无论如何都找不到所需要的证据，说明原假设不成立的，为此需要另作新的假设KS反向推理流程图反向推理的问题实现反向推理需要解决的问题如何判断一个假设是否是证据？导出假设的知识有多条时，如何确定先选哪一条？一条知识的运用条件一般都有多个，当其中的一个经验证成立后，如何自动地换为对另一个的验证？

优点不必使用与目标无关的知识，目的性强还有利于向用户提供解释

缺点目标的选择有盲目性双向推理双向推理包括既自顶向下的和自底向上的双向推理，直至在某个中间界面上两个方向的推理结果相符便成功结束和正向及反向推理相比较，双向推理所形成的推理网络来得小，时间和空间的浪费也少，从而推理效率更高。推理机的一次推理过程示意图命题逻辑命题逻辑

命题逻辑与谓词逻辑是最先应用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的自动证明发挥了重要作用命题逻辑是指以逻辑运算符结合原子命题来构成表示“命题”的公式，以及允许某些公式建构成“定理”的“证明规则”谓词逻辑是命题逻辑基础上发展起来的，是命题逻辑的扩充命题命题：能够分辨真假的语句称作命题原子命题一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为原子命题原子命题是命题中最基本的单位一般用P、Q、R、…大写拉丁字母表示命题命题的真与假分别用“T”与“F”表示

命题常量是一个特定的命题，有明确的逻辑值

命题变量是一个抽象的命题，只有把确定的命题代入后，才可能有明确的逻辑值（T或F）复合命题复合命题：通过连接词，将一些原子命题连接起来，构成一个复合命题以表示比较复杂的定义

连接词～：称为“非”或“否定”。

∨：称为“析取”。∧：称为“合取”。

→：称为“条件”或者“蕴含”。

：称为“双条件”，如P

Q表示“P当且仅当Q”命题逻辑真值表PQP∨QP∧QP→QP

Q~PTTTTTTFTFTFFFFFTTFTFTFFFFTTT命题公式命题公式：以下面的递归形式给出命题公式的定义（1）原子命题是命题公式。（2）A是命题公式，则～A也是命题公式。（3）若A和B都是命题公式，则A∧B、A∨B、A→B、AB（4）只有按（1）—（3）所得的公式才是命题公式。命题公式的缺点：无法把所描述的客观事物的结构和逻辑特征反映出来不能把不同事物的共同特征反映出来为了克服命题逻辑的局限性，引入了谓词逻辑命题公式命题公式：以下面的递归形式给出命题公式的定义（1）原子命题是命题公式。（2）A是命题公式，则～A也是命题公式（3）若A和B都是命题公式，则A∧B、A∨B、A→B、AB（4）只有按（1）—（3）所得的公式才是命题公式

命题公式的缺点：无法把所描述的客观事物的结构和逻辑特征反映出来不能把不同事物的共同特征反映出来为了克服命题逻辑的局限性，引入了谓词逻辑谓词与个体个体：在原子命题中，所描述的对象称为个体个体是指可以独立存在的物体，可以是抽象或具体谓词：描述个体的性质或个体间关系的部分，称为谓词谓词用于刻画个体的性质、状态或个体间的关系实例：“李白是诗人”可表示为：poet(LiBai)poet称为谓词，刻画“是诗人”；LiBai称为个体多元谓词一元谓词：一个谓词可以与一个个体相关联，称作一元谓词一元谓词刻画了个体的性质，例如P(a)多元谓词：一个谓词也可以与多个个体相关联，称为多元谓词多元谓词刻画了个体间的“关系”，Teacher(a,b)命题的谓词形式中的个体出现的次序影响命题的真值，不能随意变动，否则真值会有变化，例如，Teacher(b,a)是假谓词的一般形式谓词的一般形式：

P(x1,x2,…,xn)P是谓词，而x1,x2,…,xn是个体个体可以是常量，可以是变量，可以是一个函数谓词的语义：由使用者根据需要人为地定义个体常数、变量和函数统称为项例如，“小刘的哥哥是个工人”，可以表示为worker(brother(Liu))，其中brother(Liu)是一个函数。谓词的基本概念

谓词的元数：谓词中包含的个体数目称为谓词的元数，例如P(x)是一元谓词，P(x,y)是二元谓词，而P(x1,x2,…,xn)则是n元谓词

谓词的阶数：在谓词P(x1,x2,…,xn)中，若xi(i=1,2,…,n)都是个体常量、变元或函数，则称它为一阶谓词。如果某个xi本身又是一个一阶谓词，则称它为二阶谓词，依次类推

谓词和函数的区别：谓词具有逻辑值“真”或“假”函数则是某个个体到另一个个体（按数学上的概念是自变量到因变量）之间的映射谓词公式

谓词公式实例谓词演算谓词演算的合式公式：（1）原子谓词公式是合式公式（2）若A是合式公式，则～A也是合式公式（3）若A和B都是合式公式，则A∧B、A∨B、A→B、A

B也都是合式公式（4）若A是合式公式，x是任一个体变元，则(

x)A和(

x)A也都是合式公式（5）只有按（1）—（4）所得的公式才是合式公式量词辖域和变元量词辖域：在一个公式中，如果有量词出现，位于量词后面的单个谓词或者用括弧括起来的合式公式称为量词的辖域变元：在辖域内与量词中同名的变元称为约束变元不受约束的称为自由变元(

x)(N(x)→(

y)(N(y)∧G(y,x)))x,y皆为约束变元(

x)(P(x)→(R(x,y))y为自由变元谓词逻辑的翻译谓词逻辑的翻译：把一个文字叙述的命题，用谓词公式表示出来，称为谓词逻辑的翻译或符号化；反之亦然符号化的步骤：①正确理解给定命题.必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来②把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词③找出恰当量词.应注意全称量词(

)后跟条件式，存在量词(

)后跟合取式④用恰当的联结词把给定命题表示出来谓词公式的解释谓词公式的解释：设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按照如下规定赋值：（1）为每个个体常量指派D中的一个元素；（2）为每个n元函数指派一个从Dn到D的映射，其中

Dn={(x1,x2,…,xn)|x1,x2,…,xn

D}（3）为每个n元谓词指派一个从Dn到{F,T}的映射；则称这些指派为公式P在D上的一个解释永真性谓词公式的永真：如果谓词公式P，对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真谓词公式的永假：如果谓词公式P对于个体域D上的所有解释都取得假值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假若解释的个数无限时，公式的永真或永假很难判断可满足性谓词公式的可满足性：对于谓词公式P，如果至少存在一个解释使得公式P在此解释下的真值为T，则称公式P是可满足的谓词公式的不可满足：对谓词公式P，如果不存在任何解释，使得P的取值为T，则称公式P是不可满足的。谓词公式P永假与不可满足是等价的。若P永假，则也可称P是不可满足的等价性

永真蕴含

推理规则

置换

合一置换

不一致集

最一般合一置换

自然演绎推理自然演绎推理：自然演绎推理是指从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑的推理规则推出结论的过程

假言三段论：P→Q，Q→R

P→R它表示如果谓词公式P→Q和Q→R均为真，则谓词公式P→R也为真自然演绎推理：

假言推理：

P，P→Q

Q如果谓词公式P和P→Q都为真，则可推得Q为真结论

拒取式：P→Q，～Q

～P

它表示如果谓词公式P→Q为真且Q为假，则可推得P为假的结论自然演绎推理的易犯错误

自然演绎推理的实例例子：设已知如下事实：①只要是需要室外活动的课，郝亮都喜欢②所有的公共体育科都是需要室外活动的课③篮球是一门公共体育科求证：郝亮喜欢篮球这门课。证明：（1）首先定义谓词及常量：Outdoor(x)：x是需要室外活动的课；Like(x,y)：x喜欢y；Sport(x)：x是一门公共体育课Xiaoliang：小亮Ball：足球自然演绎推理的实例

不确定性推理不确定性推理概述可信度方法模糊推理粗糙集理论非单调推理不确定性推理概述人工智能系统由于知识本身的不精确和不完全，常采用非标准逻辑意义下的不确定性推理方法和非单调推理方法不确定性并非专家的习惯或爱好所至，而是客观现实的要求：推理所需的信息不完备背景知识不足信息描述模糊信息中含有噪声规划是模糊的推理能力不足解题方案不唯一不确定性推理方法的分类模型方法控制方法数值方法非数值方法启发式搜索相关性制导回溯基于概率的方法方法模糊推理方法可信度方法主观Bayse方法证据理论方法不确定性推理的基本问题不确定性的表示:证据和知识的不确定性，通常为一个数值推理计算:不确定性的传播和更新。也是获取新信息的过程不确定性的量度：用一定的数值表示不确定程度时，这种数值的取值方法和取值范围不确定性推理不确定性推理概述可信度方法模糊推理粗糙集理论非单调推理可信度的概念人们在实际生活中根据自己的经验或观察对某一现象为真的相信程度

可信度称做确定性因子具有较大的主观性和经验性，其准确性是难以把握的但是却可以很好的解决人工智能中的难题知识（规则）的不确定性度量

P(B│A)

知识（规则）的不确定性度量

P(B│A)

知识（规则）的不确定性度量

P(B│A)

单个证据的不确定性度量单个证据A的不确定性CF(A)－1≤CF(A)≤1A肯定为真时CF(A)＝1A肯定为假时，CF(A)＝－1对A一无所知时，CF(A)＝0CF(A)>0表示A以CF(A)程度为真CF(A)<0表示A以CF(A)程度为假实际使用时，初始证据的CF值由专家提供其它证据的CF值是需使用规则经推理求得P(B│A)

多个证据的不确定性度量

P(B│A)

不确定性的推理计算

P(B│A)

不确定性的推理计算

P(B│A)

不确定性的推理计算

P(B│A)

不确定性的推理计算

P(B│A)

可信度方法实例

P(B│A)

可信度方法实例(2)利用合成算法计算B1的综合可信度

CF(B1)=CF１(B)+CF２(B)-CF１(B)*CF２(B)=0.85(3)计算B2的可信度

CF（B2)=CF（B2，B1∧A3)*MAX(0,CF（B1∧A3）)=0.595P(B│A)

可信度方法可信度方法宗旨不是理论的严密性，是处理实际问题的可用性可信度方法不可一成不变地用于任何领域，甚至也不能适用于所有科学领域可信度方法推广至一个新领域时必须根据情况修改P(B│A)

不确定性推理不确定性推理概述可信度方法模糊推理粗糙集理论非单调推理模糊表达的定义

隶属度关系的建立

模糊规则模糊规则一般常用IFTHEN表达的规则：

单一的模糊规则是不具备分类能力的。通常对样本类别的判决结果是在一组模糊规则上获得的。这需要计算同一个样本对所有模糊规则的隶属度值，然后由隶属度值最大的规则决定样本的类别。这一计算过程实质上遵循了模糊推理中的前件取小后件取大的“极小极大”原则。

模糊控制是以模糊表达、模糊规则和模糊推理为基础的一种计算机数字控制技术。模糊控制与其他经典控制的重要区别是它不必建立受控对象的精确数学模型,而把控制经验用模糊变量来表示成控制规则,再用这些模糊规则实施系统的控制。模糊控制的优势是模糊控制的计算量小，控制精度不一定很高但控制过程平滑。模糊化：

将输入变量的精确数值根据其模糊度划分和隶属度函数转换为模糊度描

述。可采

用最常用的“三角波”隶属函数来定义变量的模糊隶属度。模糊规则推理：

采用IF...THEN...模糊规则来表示控制器输入与输出关系。模糊推理运算普遍采用的是MAX-MIN推理。

主要步骤是：1)分别求出输入量的隶属度(即模糊化)。2)当有多个输入量时，同一规则中(对于AND)取输入量隶属度最小值作为前件部的隶属度(即：规则的强度)。3)前件部隶属度与后件部隶属度函数进行MIN运算，得到各规则的结论。4)对所有规则的结论取MAX运算，得到模糊推理的结果。

反模糊化：

将经模糊规则推理得到的输出变量的模糊度，转换为精确数值。最简单的方法是最大隶属度方法。在控制技术中最常用的方法则是面积重心法，面积重心法的计算式为：粗糙集理论Z.Pawlak提出的粗糙集理论是处理数据的不确定性和不完整性的重要工具。它的特点在于不需要预先给定数据的某些特征或属性的数量描述,如概率统计方法中的概率分布,模糊逻辑中的隶属度或隶属函数。其基本方法为直接从给定问题的描述集合出发,用正区域和负区域两个精确概念对不精确的概念进行描述,通过不可分辨关系和不可分辨类缺点给定问题的近似域,从而找出问题中的内在规律。

粗糙集理论是一种利用三值逻辑处理不精确或不完整信息的形式化方法，用两个精确的概念（正区域和负区域）对不精确概念进行描述，其研究基础是分类，经典粗糙集理论认为正区域包含了完全属于概念的对象，负区域包含了完全不属于概念的对象。正区域和负区域之间的部分称为边界，由不能确定