人工智能原理及其应用

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

2、问题的策略、技巧、窍门等实践经验和知识。例：瞎子爬山第3页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理按逻辑基础 演绎推理：一般到个别 三段论 归纳推理：个别到一般 完全归纳、不完全归纳 枚举归纳、类比归纳等 默认（缺省）推理：知识不完备按知识的确定性 确定性推理：知识和结论都是精确的 非确定性推理第4页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理按推理过程的单调性 单调推理 非单调推理：加入新知识会否定原来推出的结论，使推理过程回退控制策略及分类 推理的控制策略：指如何使用领域知识使推理过程尽快达到目标的策略。 推理策略：推理方向控制策

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

4、用场合事实不够充分正向推理推出的结论可性度不高希望得到更多结论第7页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理冲突消解策略 基本思想：对可用知识排序特殊知识优先新鲜知识优先差异性大的知识优先领域特点优先上下文关系优先前提条件少者优先第8页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理二、推理的逻辑基础基本概念谓词公式的解释 对所包含的常量、函数、谓词赋值谓词公式的永真性与可满足性 非空个体域上的任一解释（在D上永真）；任何非空个体域 （永真）谓词公式的等价性与永真蕴含性 在D上等价与等价PQ ,永真蕴含PQ 常用的等价式、永真蕴含式（牢记

5、）第9页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理谓词公式的范式 前束范式： 前缀 母式置换与合一 已知：W1(A), ( x)(W1(x) W2(x) 结论：W2(A)置换：在表达式中用置换项置换变量。 t1/x1, t2/x2, ,tn/xn,量词串无量词公式第10页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理 置换的例 置换的合成 (Ls1)s2=L(s1s2) 置换一般不可交换 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

6、) 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 第11页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理合一：寻找项对变量的置换，以使表达式一致。 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)的

7、分歧集 D1=y,f(a) D2=z,h(b)第12页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理 合一算法(p89) 例： F=P(a,x,f(g(y),P(z,h(z,u),f(u) 第13页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理三、自然演绎推理 已知事实 结论 注意肯定前件、否定后件的错误 例3.8： 定义谓词：Prog(x) Like(x,y) Lang(x) 事实：Prog(x) Like(Wang,x) ( x) (Lang(x) Prog(x) ) Lang(C) 结论：Like(Wang,C) 经典逻辑推理规则第14

8、页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理四、归结演绎推理（Robinson消解原理） 对前提P，结论Q，证明P Q永真 P Q与PQ等价 只需证明 （PQ）即P Q不可满足。第15页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理子句集概念 文字：原子谓词公式及其否定 子句：任何文字的析取式 空子句NIL：永假、不可满足化为子句集消去蕴涵和等价符号减少否定符号的辖域对变量标准化，保证每个量词有其唯一的哑元消去存在量词 skolem函数第16页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理化为前束形 前缀（全称量

9、词串） 母式（元量词公式）把母式化为合取范式消去全称量词消去连词符号更换变量名称第17页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理例（ x）P(x) ( y)P(y)P(f(x,y)( y)Q(x,y)P(y) 第18页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理二、p9398:只要求记住两条有用的结论：原谓词公式不可满足，其标准子句集则一定不可满足。Herbrand(海伯伦)定理：子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S。第19页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理三、鲁宾逊（

10、 Robinson ）归结原理基本思想 否定结论，加入前提子句集，应用归结原理，是否能导出空子句，若存在，证明否定结论错误，即原结论得证。（反证法） 实际上归结原理不仅应用在定理证明，还可应用于问题求解过程。归结原理 互补文字：P、 P 归结式：分为命题逻辑归结和谓词逻辑归结.第20页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理 命题逻辑归结定义： L1、L2分别是子句C1、C2中的文字， 并且L1、L2 互补，即L1 L2 ，将它们从C1、C2中消去，并将两子句余下部分按析取关系组成新子句C12，即归结式。 C1、C2叫做亲本子句。 例：p99 3.15、3.16

11、、3.17第21页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理定理：归结式C12是亲本子句C1和C2的逻辑结论。 定理：子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。第22页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理归结反演定理证明过程： 公式集S，目标公式G否定G，得到 G把 G添加到S中去新产生 G，S化为子句集应用归结原理，力图推导出一个矛盾空子句 例：p101 3.18第23页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理谓词逻辑归结定义：对含有变元的子句C1、C2中文字L1、L2，如果

12、L1、 L2存在最一般合一者，则有归结式 C12C1L1 C2-L2 二元归结式不作要求 例：p102谓词逻辑归结反演定理证明 例：p103105第24页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理谓词逻辑归结反演问题求解 答案求取涉及到把一棵根部有空子句的反演树变换为在根部带有可用作答案的某个语句的一棵证明树把由目标公式的否定产生的每个子句添加到目标公式否定的否定的子句中去按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部的子句作为一个回答语句 例：p110第25页，共27页，2022年，5月20日，10点55分，星期日第三章确定性推理归结演绎推理的归结策略 广度优先策略删除