人工智能原理及其应用

1、ARTIFICIAL INTELLIGENCE 人工智能原理及其应用 GOYAL990.NET 2001.9第三章确确定性性推理一、推理理的基本本概念定义推理：已知事事实结结论知识推理理是指在计计算机或或智能机机器中，在知识识表达的的基础上上，利用用形式化化的知识识模型，进行机机器思维维求解问问题，实实现状态态转移的的智能操操作序列列。策略第三章确确定性性推理基本问题题：推理的的方法和和控制的的策略推理方法法及分类类根据知识识表示方方式分类类“图搜索索”方法法如如：状状态空间间法、与与或图“逻辑论论证”方方法如如：谓词逻逻辑等推理算法法与推理理步骤算法：完备性性如如宽度度优先步骤：不完备备如如

2、深度度优先启发式与与非启发发式启发性知知识：即解决决问题的的策略、技巧、窍门等等实践经经验和知知识。例例：瞎子子爬山第三章确确定性性推理按逻辑基基础演绎推理理：一般到个个别三段论归纳推理理：个别到一一般完全归纳纳、不完完全归纳纳枚举归纳纳、类比比归纳等等默认（缺缺省）推推理：知知识不完完备按知识的的确定性性确定性推推理：知知识和结结论都是是精确的的非确定性性推理第三章确确定性性推理按推理过过程的单单调性单调推理理非单调推推理：加入新新知识会会否定原原来推出出的结论论，使推推理过程程回退控制策略略及分类类推理的控控制策略略：指如何何使用领领域知识识使推理理过程尽尽快达到到目标的的策略。推理策略略

3、：推理方方向控制制策略、求解策策略、限限制策略略、冲突突消解策策略搜索策略略（第五章章）：推推理线路路、推理理效果、推理效效率第三章确确定性性推理正向推理理知识库、综合数数据库、推理机机正向推理理的过程程（图3-1）优点：直观。适合于于诊断、监控、设计、预测等等领域。缺点；推理无无明确目目标，效效率较低低。逆向推理理逆向推理理的过程程（图3-2）优点：目标明明确，效效率较高高缺点：情况不不明时，选择假假设目标标的盲目目性比较较大，可可能多次次提出假假设，降降低系统统效率第三章确确定性性推理混合推理理方法先正后逆逆（图3-3）先逆后正正（图3-4）双向（图图3-5）适用场合合事实不够够充分正向推

4、理理推出的的结论可可性度不不高希望得到到更多结结论第三章确确定性性推理冲突消解解策略基本思想想：对可可用知识识排序特殊知识识优先新鲜知识识优先差异性大大的知识识优先领域特点点优先上下文关关系优先先前提条件件少者优优先第三章确确定性性推理二、推理理的逻辑辑基础基本概念念谓词公式式的解释释对所包含含的常量量、函数数、谓词词赋值谓词公式式的永真真性与可可满足性性非空个体体域上的的任一解解释（在D上永真）；任何何非空个个体域（永真）谓词公式式的等价价性与永永真蕴含含性在D上等价与等价PQ,永真蕴蕴含PQ常用的等等价式、永真蕴蕴含式（牢记）第三章确确定性性推理谓词公式式的范式式前束范式式：前前缀母母式置

5、换与合合一已知：W1(A),(x)(W1(x)W2(x)结论：W2(A)置换：在在表达式式中用置置换项置置换变量量。t1/x1,t2/x2, ,tn/xn,量词串无量词公公式第三章确确定性性推理置换的例例置换的合合成(Ls1)s2=L(s1s2)置换一般般不可交交换s1s2s2s1例：表达式P(x,g(y),c)置换s1=f(y)/x,z/ys2=a/x,b/y,y/zPs1=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/zPs2s1=P(a,g(b),c)s2s1=a/x,b/y第三章确确定性性推理合一：

6、寻寻找项对对变量的的置换，以使表表达式一一致。Pg(x),f(y),B,Ph(x),f(B),B不可合一一尽管s=A/x,B/y是Px,f(y),B,Px,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：

7、定义谓词词：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，证明PQ永真PQ与PQ等价只需证明明（PQ）即P Q不可满足足。第三章确确定性性推理子句集概念文字：原子谓词词公式及及其否定定子句：任何文字字的析取取式空子句NIL：永假、不不可满足足化为子句句集消去蕴涵涵和等价价符号减少否定定符号的的辖域对变量标标准化，保证每每个量词词有其唯唯一的哑哑元消去存在在量词s

8、kolem函数第三章确确定性性推理化为前束束形前缀（全全称量词词串）母式（元元量词公公式）把母式化化为合取取范式消去全称称量词消去连词词符号更换变量量名称第三章确确定性性推理例（x）P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y) 第三章确确定性性推理二、p9398:只要求记记住两条条有用的的结论：原谓词公公式不可可满足，其标准准子句集集则一定定不可满满足。Herbrand(海伯伦)定理：子句集集S不可满足足的充要要条件是是存在一一个有限限的不可可满足的的基子句句集S。第三章确确定性性推理三、鲁宾宾逊（ Robinson）归结原原理基本思想想否定结论论，加入入前提子子句集，应用

9、归归结原理理，是否否能导出出空子句句，若存存在，证证明否定定结论错错误，即即原结论论得证。（反证证法）实际上归归结原理理不仅应应用在定定理证明明，还可可应用于于问题求求解过程程。归结原理理互补文字字：P、 P归结式：分为命命题逻辑辑归结和和谓词逻逻辑归结结.第三章确确定性性推理命题逻辑辑归结定义：L1、L2分别是子子句C1、C2中的文字字，并并且L1、L2互补，即即L1L2，将它们们从C1、C2中消去，并将两两子句余余下部分分按析取关系系组成新子子句C12，即归结式。C1、C2叫做亲本子句句。例：p993.15、3.16、3.17第三章确确定性性推理定理：归结式式C12是亲本子子句C1和C2的

10、逻辑结结论。定理：子句集集S是不可满满足的，当且仅仅当存在在一个从从S到空子句句的归结结过程。第三章确确定性性推理归结反演演定理证证明过程程：公式集S，目标公式式G否定G，得到G把G添加到S中去新产生G，S化为子句句集应用归结结原理，力图推推导出一一个矛盾盾空子句句例：p1013.18第三章确确定性性推理谓词逻辑辑归结定义：对含有有变元的的子句C1、C2中文字L1、L2，如果L1、L2存在最一一般合一一者，则有归归结式C12C1L1 C2-L2二元归结结式不作作要求例：p102谓词逻辑辑归结反反演定理理证明例：p103105第三章确确定性性推理谓词逻辑辑归结反反演问题题求解答案求取取涉及到到把一棵棵根部有有空子句句的反演树变变换为在根部带带有可用用作答案案的某个个语句的的一棵证明树把由目标标公式的的否定产产生的每每个子句句添加到到目标公公式否定定的否定定的子句句中去按照反演演树，执执行和以以前相同同的消解解，直至至在根部部得到某某个子句句止。用根部的的子句作作为一个个回答语语句例：p110第三章确确定性