人工智能原理及其应用.ppt

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

2、窍门等实践经验和知识。例：瞎子爬山,第三章确定性推理,按逻辑基础 演绎推理：一般到个别 三段论 归纳推理：个别到一般 完全归纳、不完全归纳 枚举归纳、类比归纳等 默认（缺省）推理：知识不完备 按知识的确定性 确定性推理：知识和结论都是精确的 非确定性推理,第三章确定性推理,按推理过程的单调性 单调推理 非单调推理：加入新知识会否定原来推出的结论，使推理过程回退 控制策略及分类 推理的控制策略：指如何使用领域知识使推理过程尽快达到目标的策略。 推理策略：推理方向控制策略、求解策略、限制策略、冲突消解策略 搜索策略（第五章）：推理线路、推理效果、推理效率,第三章确定性推理,正向推理 知识库、综合数

3、据库、推理机 正向推理的过程（图3-1） 优点：直观。适合于诊断、监控、设计、预测等领域。 缺点；推理无明确目标，效率较低。 逆向推理 逆向推理的过程（图3-2） 优点：目标明确，效率较高 缺点：情况不明时，选择假设目标的盲目性比较大，可能多次提出假设，降低系统效率,第三章确定性推理,混合推理 方法 先正后逆（图3-3） 先逆后正（图3-4） 双向（图3-5） 适用场合 事实不够充分 正向推理推出的结论可性度不高 希望得到更多结论,第三章确定性推理,冲突消解策略 基本思想：对可用知识排序 特殊知识优先 新鲜知识优先 差异性大的知识优先 领域特点优先 上下文关系优先 前提条件少者优先,第三章确定

4、性推理,二、推理的逻辑基础 基本概念 谓词公式的解释 对所包含的常量、函数、谓词赋值 谓词公式的永真性与可满足性 非空个体域上的任一解释（在D上永真）；任何非空个体域 （永真） 谓词公式的等价性与永真蕴含性 在D上等价与等价PQ ,永真蕴含PQ 常用的等价式、永真蕴含式（牢记）,第三章确定性推理,谓词公式的范式 前束范式： 前缀 母式 置换与合一 已知：W1(A), ( x)(W1(x) W2(x) 结论：W2(A) 置换：在表达式中用置换项置换变量。 t1/x1, t2/x2, ,tn/xn,量词串,无量词公式,第三章确定性推理,置换的例 置换的合成 (Ls1)s2=L(s1s2) 置换一般

5、不可交换 s1s2s2s1 例： 表达式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,第三章确定性推理,合一：寻找项对变量的置换，以使表达式一致。 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

6、)：置换最少的变量以使表达式一致。 分歧集： 例：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),经典逻辑推理规则,第三章确定性推理,四、归结演

7、绎推理（Robinson消解原理） 对前提P，结论Q，证明P Q永真 P Q与PQ等价 只需证明 （PQ）即P Q不可满足。,第三章确定性推理,子句集 概念 文字：原子谓词公式及其否定 子句：任何文字的析取式 空子句NIL：永假、不可满足 化为子句集 消去蕴涵和等价符号 减少否定符号的辖域 对变量标准化，保证每个量词有其唯一的哑元 消去存在量词 skolem函数,第三章确定性推理,化为前束形 前缀（全称量词串） 母式（元量词公式） 把母式化为合取范式 消去全称量词 消去连词符号 更换变量名称,第三章确定性推理,例（ x）P(x) ( y)P(y)P(f(x,y)( y)Q(x,y)P(y),第

8、三章确定性推理,二、p9398: 只要求记住两条有用的结论： 原谓词公式不可满足，其标准子句集则一定不可满足。 Herbrand(海伯伦)定理：子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S。,第三章确定性推理,三、鲁宾逊（ Robinson ）归结原理 基本思想 否定结论，加入前提子句集，应用归结原理，是否能导出空子句，若存在，证明否定结论错误，即原结论得证。（反证法） 实际上归结原理不仅应用在定理证明，还可应用于问题求解过程。 归结原理 互补文字：P、 P 归结式：分为命题逻辑归结和谓词逻辑归结.,第三章确定性推理,命题逻辑归结 定义： L1、L2分别是子句C1、C2中的文

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