《人工智能第3章推理技术1讲述》由会员分享，可在线阅读，更多相关《人工智能第3章推理技术1讲述（40页珍藏版）》请在金锄头文库上搜索。
1、第第3 3章章 推理技术推理技术 * 人工智能 2 3.1 消解原理 3.2 规则演绎系统 3.3 产生式系统 3.4 基于概率的推理 3.5 可信度方法 3.6 证据理论 3.7 模糊推理(cut) 3.8 非单调推理 本章主要内容： * 人工智能 3 推理方式及其分类 1. 演绎推理、归纳推理、默认推理 演绎推理：从一般到特殊。例如三段论。 归纳推理：从个体到一般。 默认推理：缺省推理，在知识不完全的情况下假设某 些条件已经具备所进行的推理。 2. 确定性、不确定性推理 3. 单调性、非单调推理 推出的结论是否单调增加。 4. 基于知识的推理、统计推理、直觉推理 * 人工智能 4 谓词逻辑
2、基本概念 1. 一个谓词分为谓词名与个体两个部分。 n谓词名刻画个体的性质、状态或个体间的关系。 n个体表示独立存在的事物或者概念。 例如： Teacher(zhang)，Greater(5,3) n谓词的一般形式 P (x1, x2,xn) 其中，P是谓词名，x1, x2,xn是个体。谓词名通常用大 写的英文字母表示，个体通常用小写的英文字母表示。该 谓词是一个原子谓词公式。 * 人工智能 5 2. 个体可以是常量、变元或者函数。 例如： Less(x,5),x是一个变元。 Teacher(father(wang),其中father(wang)是一 个函数。 3.谓词的语义由人指定。 例如：
3、 S(x)可以表示x是一个人；也可以表示x是一朵花 * 人工智能 6 4. 连接词 非：；析取：；合取：；蕴含：； 双向蕴含： 谓词逻辑真值表 P Q PPQPQPQP Q T TFTTTT T FFTFFF F TTTFTF F FTFFTT * 人工智能 7 5. 谓词公式 (well formed formulas) 定义： 按下述规则得到的合式公式： (1) 单个谓词是合式公式，称为原子公式； (2) 若A是合式公式，则 也是合式公式； (3) 若A，B是合式公式，则 都是合式公式； (4) 若A是合式公式，x是任一个体变元，则 都是合式公式； (5) 运用有限步上述规则得到的公式是合
4、式公式。 * 人工智能 8 6.一些重要的等价式 * 人工智能 9 7.一些重要的永真蕴含式 * 人工智能 10 n所谓模式匹配是指对两个知识模式(例如两个谓词公 式)进行比较，以检查这两个知识模式是否完全一致 或者近似一致。 n模式匹配可分为确定性匹配与不确定性匹配。 n确定性匹配是指两个知识模式完全一致，或者经过 变量代换后变得完全一致。例如： 规则: IF father(x,y) and man(y) THEN son(y,x) 事实: father(李四，李小四) and man(李小四) 代换：= 李四/X,李小四/Y 结论：son(李小四,李四) n不确定性匹配是指两个知识模式不完
5、全一致，但是 它们的相似程度又在规定的限度内。 模式匹配 * 人工智能 11 变量代换 定义 代换是一个有限集合 t1/x1,t2/x2,tn/xn 其中t1,t2,tn是项，项可以是常量、变量、函数； x1,x2,xn是互不相同的变元; ti/xi表示用ti代换xi ; 一个合法的代换不允许ti与xi相同，也不允许变元xi 循环地出现在另一个tj中。例如： a/x,f(b)/y,w/z是一个代换 g(y)/x,f(x)/y不是代换 * 人工智能 12 令= t1/x1,t2/x2,tn/xn为一个代换，F为表达 式，则F表示对F用ti代换xi后得到的表达式。 F称为F的特例。 规则: IF
6、father(x,y) and man(y) THEN son(y,x) 事实: father(李四，李小四) and man(李小四) F=father(x,y) man(y) = 李四/X,李小四/Y F= father(李四，李小四) man(李小四) 结论: son(李小四,李四) * 人工智能 13 代换的复合 定义 设 = t1/x1,t2/x2,tn/xn = u1/y1,u2/y2,um/ym 是两个代换，则这两个代换的复合也是一个代换，它是从 t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,um/ym 中删去如下两种元素： ti/xi当ti=xi ui/yi当yi
7、x1,x2,xn 后剩下的元素所构成的集合，记为 。 nti表示对ti运用进行代换。 n就是对一个公式F先运用进行代换，然后再运用 进行代换：F（ ）=（F ） * 人工智能 14 代换复合的例子 设有代换 = f(y)/x,z/y = a/x,b/y,y/z 则 =f(y)/x, z/y, a/x, b/y, y/z =f(b)/x, y/y, a/x, b/y, y/z =f(b)/x,y/z * 人工智能 15 公式集的合一 定义 设有公式集F=F1,F2,Fn，若存在一个代换使 得 F1=F2=Fn 则称为公式集F的一个合一，且称F1,F2,Fn是可 合一的。 n设有公式集 F=P(x
8、,y,f(y),P(a,g(x),z) 则下式是它的一个合一： =a/x,g(a)/y,f(g(a)/z n一个公式集的合一一般不唯一。 * 人工智能 16 最一般的合一 定义 设是公式集F的一个合一，如果对任一个合一都 存在一个代换，使得=，则称是一个最一般的 合一。 代换过程是一个用项（常数，函数，变量）代替变元 的过程，因此是一个从一般到特殊的过程。 F= P(x,y) Q(y) = a/x,f(z)/y F=P(a,f(z) Q(f(z) 最一般合一是唯一的。 * 人工智能 17 求取最一般合一 n差异集：两个公式中相同位置处不同符号的集合。 例如：F1:P(x,y,z), F2:P(
9、x,f(a),h(b) 则D1=y,f(a), D2=z,h(b) 求取最一般合一的算法： 1.令k=0,Fk=F, k=。 是空代换。 2.若Fk只含一个表达式，则算法停止，k就是最一般合一。 3.找出Fk的差异集Dk。 4.若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk中出 现，则置： Fk+1=Fktk/xk K+1=ktk/xk k=k+1 然后转(2)。若不存在这样的xk和tk则算法停止。 1.算法终止，F的最一般合一不存在。 * 人工智能 18 求取最一般合一的例子 例如，设 F=P(a,x,f(g(y),P(z,f(z),f(u) 求其最一般合一。 令F0=
10、F, 0=。F0中有两个表达式，所以0不是最一般合一。 差异集：D0=a,z。代换： a/z F1= F0 a/z=P(a,x,f(g(y),P(a,f(a),f(u) 。 1=0a/z=a/z 差异集： D1=x,f(a) 。代换： f(a)/x F2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u) 。 2=1f(a)/x=a/z,f(a)/x 差异集： D2=g(y),u 。代换： g(y)/u F3=F2g(y)/u=P(a,f(a),f(g(y),P(a,f(a),f(g(y) 。 3=2g(y)/u=a/z,f(a)/x,g(y)/u F3=F3 * 人
11、工智能 19 3.1 3.1 消解原理消解原理 消解原理也叫做归结原理。主要内容包括子句集的求取、 消解推理的规则和消解反演问题求解方法。 消解原理的基础知识： u在谓词逻辑中，把原子谓词公式及其否定统称为文字。 例如： P(x), P(x,f(x) u任何文字的析取式称为子句（clause）。 例如： P(x)Q(x), P(x,f(x)Q(x,g(x) u不包含任何文字的子句称为空子句。 u合取范式：若干子句的合取（and） 例如： C1 C2 C3 Cn u子句集： S= C1 ,C2 ,C3 ,Cn * 人工智能 20 3.1.1 化为子句集 (1)消去蕴涵符号： 例如： (2)减少否
12、定符号的辖域：每个否定符号“”最多只用到一 个谓词符号上，即利用等价关系把“”移到紧靠谓词的 位置上。上式经等价变换后 在进行消解过程之前, 首先需要将谓词演算公式化为一 个子句集。其变换过程由下列几个步骤组成： * 人工智能 21 (3)对变量标准化 ：使不同量词约束的变元有不同的名字 ，通过变量更名来完成。例如，上式经变换后 (4)消去存在量词：分两种情况 a）存在量词不出现在全称量词的辖域内，则只要用一个新的 个体常量替换受该量词约束的变元。 b）存在量词位于一个或者多个全称量词的辖域内，此时要用 Skolem函数f(x1,x2,xn)替换受该存在量词约束的变元。 上式中存在量词(y)及
13、(z)都位于(x)的辖域内，所以需要 用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和 g(x)，则替换后得到 3.1.1 化为子句集（2） * 人工智能 22 (5)化为前束形 ：把所有全称量词移到公式的左边，并使 每个量词的辖域包括这个量词后面公式的整个部分。 所得公式称为前束形。 3.1.1 化为子句集（3） (6)化为合取范式 (7) 消去全称量词 ：到了这一步，所有余下的量词均被 全称量词量化了。同时全称量词的次序也不重要了。 因此，我们可以消去全称量词。 * 人工智能 23 (8)获取子句集： 3.1.1 化为子句集（4） (9)更换变量名称：使一个变量符号不
14、出现在一个以上的 子句中。上式在更改变量名后，可以得到子句集： * 人工智能 24 子句集S的不可满足性：对于任意论域中的任意 一个解释，S中的子句不能同时取得真值T。 谓词公式F的不可满足性：对于任意论域中的任意一 个解释，F都不能取得真值T，即F是永假的。 定理 设有谓词公式F，其子句集为S，则F不可满足 的充要条件是S不可满足。 * 人工智能 25 定义：设L1为任一原子公式，L2为另一原子公式，且具有 相同的谓词名，但一般具有不同的变量。已知两子句 L1和L2，如果L1和L2具有最一般合一， 那么通过消解可以从这两个子句推导出一个新子句 。这个新子句叫做消解式（归结式）。 3.1.2
15、消解推理规则 * 人工智能 26 C1=P(x)Q(x), C2= P(a)R(y) 最一般合一：=a/x C1 = P(a)Q(a) C2 = P(a)R(y) 对它们进行归结，得到归结式：Q(a)R(y) 若某个子句C含有可合一的文字，则在进行归结之前应先 对这些文字进行合一。 C1=P(x) P(f(a) Q(x), C2= P(y) R(b) = f(a)/x C1=P(f(a) Q(f(a) C12 = Q(f(a) R(b) * 人工智能 27 推论1 设C1与C2是子句集S中的两个子句，C12是它们 的消解式。若用C12代替C1和C2后得到新子句 集S1，则由S1的不可满足性可推出原子句集S 的不可满足性，即 S1的不可满足性S的不可满足性 推论2 设C1与C2是子句集S中的两个子句，C12是它们的 消解式。若把C12加入S中得到新子句集S2，则S 与S2在不可满足的意义上是等价
