人工智能原理及其应用

ARTIFICIALINTELLIGENCE人工智能原理及其应用[e-mail]2001.9第三章确定性推理一、推理的基本概念1.定义推理：已知事实结论知识推理是指在计算机或智能机器中，在知识表达的基础上，利用形式化的知识模型，进行机器思维求解问题，实现状态转移的智能操作序列。策略第三章确定性推理基本问题：推理的方法和控制的策略2.推理方法及分类1)根据知识表示方式分类“图搜索”方法如：状态空间法、与或图“逻辑论证”方法如：谓词逻辑等2)推理算法与推理步骤算法：完备性如宽度优先步骤：不完备如深度优先3)启发式与非启发式启发性知识：即解决问题的策略、技巧、窍门等实践经验和知识。例：瞎子爬山第三章确定性推理4)按逻辑基础演绎推理：一般到个别三段论归纳推理：个别到一般完全归纳、不完全归纳枚举归纳、类比归纳等默认（缺省）推理：知识不完备5)按知识的确定性确定性推理：知识和结论都是精确的非确定性推理第三章确定性推理6)按推理过程的单调性单调推理非单调推理：加入新知识会否定原来推出的结论，使推理过程回退3.控制策略及分类推理的控制策略：指如何使用领域知识使推理过程尽快达到目标的策略。推理策略：推理方向控制策略、求解策略、限制策略、冲突消解策略搜索策略（第五章）：推理线路、推理效果、推理效率第三章确定性推理1)正向推理知识库、综合数据库、推理机正向推理的过程（图3-1）优点：直观。适合于诊断、监控、设计、预测等领域。缺点；推理无明确目标，效率较低。2)逆向推理逆向推理的过程（图3-2）优点：目标明确，效率较高缺点：情况不明时，选择假设目标的盲目性比较大，可能多次提出假设，降低系统效率第三章确定性推理3)混合推理a)方法i.先正后逆（图3-3）ii.先逆后正（图3-4）iii.双向（图3-5）b)适用场合i.事实不够充分ii.正向推理推出的结论可性度不高iii.希望得到更多结论第三章确定性推理4)冲突消解策略基本思想：对可用知识排序a)特殊知识优先b)新鲜知识优先c)差异性大的知识优先d)领域特点优先e)上下文关系优先f)前提条件少者优先第三章确定性推理二、推理的逻辑基础1.基本概念1)谓词公式的解释对所包含的常量、函数、谓词赋值2)谓词公式的永真性与可满足性非空个体域上的任一解释（在D上永真）；任何非空个体域（永真）3)谓词公式的等价性与永真蕴含性在D上等价与等价P＜﹦＞Q,永真蕴含P﹦＞Q常用的等价式、永真蕴含式（牢记）第三章确定性推理2.谓词公式的范式前束范式：前缀＋母式3.置换与合一已知：W1(A),(x)(W1(x)→W2(x))结论：W2(A)1)置换：在表达式中用置换项置换变量。{t1/x1,t2/x2,…,tn/xn,}量词串无量词公式第三章确定性推理置换的例置换的合成(Ls1)s2=L(s1s2)置换一般不可交换s1s2≠s2s1例：表达式P(x,g(y),c)置换s1={f(y)/x,z/y}s2={a/x,b/y,y/z}Ps1=P(f(z),g(z),c)Ps2=P(a,g(b),c)Ps1s2=P(f(b),g(b),c)s1s2={f(b)/x,b/y,y/z}Ps2s1=P(a,g(b),c)s2s1={a/x,b/y}第三章确定性推理2)合一：寻找项对变量的置换，以使表达式一致。{P[g(x),f(y),B],P[h(x),f(B),B]}不可合一尽管s={A/x,B/y}是{P[x,f(y),B],P[x,f(B),B]}的一个合一者，但是最简单的合一者是g={B/y}最一般(通用)合一者(mgu)：置换最少的变量以使表达式一致。分歧集：例：F={P(x,y,z),P(x,f(a),h(b))}的分歧集D1={y,f(a)}D2={z,h(b)}第三章确定性推理合一算法(p89)例：F={P(a,x,f(g(y))),P(z,h(z,u),f(u))}第三章确定性推理三、自然演绎推理已知事实结论注意肯定前件、否定后件的错误例3.8：定义谓词：Prog(x)Like(x,y)Lang(x)事实：Prog(x)→Like(Wang,x)(x)(Lang(x)→Prog(x))Lang(C)结论：Like(Wang,C)经典逻辑推理规则第三章确定性推理四、归结演绎推理（Robinson消解原理）对前提P，结论Q，证明P→Q永真P→Q与﹁P∨Q等价只需证明﹁（﹁P∨Q）即P∧﹁Q不可满足。第三章确定性推理1.子句集1)概念文字：原子谓词公式及其否定子句：任何文字的析取式空子句NIL：永假、不可满足2)化为子句集a)消去蕴涵和等价符号b)减少否定符号的辖域c)对变量标准化，保证每个量词有其唯一的哑元d)消去存在量词skolem函数第三章确定性推理e)化为前束形前缀（全称量词串）＋母式（元量词公式）f)把母式化为合取范式g)消去全称量词h)消去连词符号i)更换变量名称第三章确定性推理例（x）{P(x)→{(y)[P(y)→P(f(x,y))]∧﹁(y)[Q(x,y)→P(y)]}}第三章确定性推理二、p93~98:只要求记住两条有用的结论：原谓词公式不可满足，其标准子句集则一定不可满足。Herbrand(海伯伦)定理：子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S’。第三章确定性推理三、鲁宾逊（Robinson）归结原理1.基本思想否定结论，加入前提子句集，应用归结原理，是否能导出空子句，若存在，证明否定结论错误，即原结论得证。（反证法）实际上归结原理不仅应用在定理证明，还可应用于问题求解过程。2.归结原理互补文字：P、﹁P归结式：分为命题逻辑归结和谓词逻辑归结.第三章确定性推理1)命题逻辑归结a)定义：L1、L2分别是子句C1、C2中的文字，并且L1、L2互补，即L1＝﹁L2，将它们从C1、C2中消去，并将两子句余下部分按析取关系组成新子句C12，即归结式。C1、C2叫做亲本子句。例：p993.15、3.16、3.17第三章确定性推理b)定理：归结式C12是亲本子句C1和C2的逻辑结论。定理：子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。第三章确定性推理c)归结反演定理证明过程：公式集S，目标公式GI.否定G，得到﹁GII.把﹁G添加到S中去III.新产生{﹁G，S}化为子句集IV.应用归结原理，力图推导出一个矛盾空子句例：p1013.18第三章确定性推理2)谓词逻辑归结a)定义：对含有变元的子句C1、C2中文字L1、L2，如果L1、﹁L2存在最一般合一者ɑ，则有归结式C12＝{C1－L1}ɑ∨{C2-L2}ɑ二元归结式不作要求例：p102b)谓词逻辑归结反演定理证明例：p103～105第三章确定性推理c)谓词逻辑归结反演问题求解答案求取涉及到把一棵根部有空子句的反演树变换为在根部带有可用作答案的某个语句的一棵证明树I.把由目标公式的否定产生的每个子句添加到目标公式否定的否定的子句中去II.按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。III.用根部的子句作为一个回答语句例：p110第三章确定性推理3.归结演绎推理的归结策略广度优先策略1)删除策略：缩小归结范围a)纯文字删除法b)重言式删除法c)包孕删除法2)限制策略：加入启发信息，减少盲目性a)支持集策略b)单文字子句策略c)线性输入策略d)祖先过滤策略第三章作业P119:3-1、3-5、3-9、3-10、3-13(1)(3)(5)、3-15、3-18、3-19