第三章知识处理

1、第三章 问题求解问题推理：在知识表达的基础上，进行机器思维，求解问题。是知识利用的基础。推理技术：问题求解（从初始状态到目标状态）的方法和途径。与知识表达技术密切相关。图搜索方法：基于图的知识表达。从图中相当于初始状态的出发到相当于目标状态的终止节点的路线搜索过程。广度优先搜索，深度优先搜索.逻辑论证法：基于谓词逻辑或其他形式逻辑方法的知识表达。不确定性推理非单调推理推理方法：是否完备：推理算法：推理过程完备，能找到解。推理步骤：推理过程不完备，不一定能求解问题的解。是否加入启发性知识：启发推理：在推理过程中，运用与问题有关的启发性知识，即解决问题的策略、技巧、窍门，对解的特性及规律的估计等实

2、践经验和知识，加快推理过程，提高搜索效率； 非启发推理：在问题求解的推理过程中，不运用启发性知识，只按一般的逻辑法则或控制性知识，进行通用性的推理。3.1 一般搜索原理一 一般性图搜索策略1 图搜索：在图中寻求从初始状态到目标状态的路径。2 盲目搜索：无信息搜索，非启发性搜索。3 搜索策略：（1）相关数据结构及概念：OPEN表：用于存放刚生成的节点；CLOSED表：用于存放将要扩展或已扩展的节点；扩展：用定义的算子或算符对节点进行操作，生成子节点；指针：用以记录子节点被扩展的路径，反向指向父节点；搜索图：通过搜索所得的图；搜索树：由搜索图中所有节点及反向指针所构成的集合。（2）一般性图搜索策略

3、开始OPEN空？OPEN表的第一个节点n从表中移出，放入CLOSED表n为目标节点？N可扩展？扩展n，将其子节点放入OPEN表，并为每个子节点配置指向节点n的指针失败，退出成功，退出S0移入OPEN表YNYYNN不同的搜索方法不同在于：后继节点不同的扩充方式，对应OPEN表不同的排列顺序。n宽度优先搜索搜索按层进行，在对下一层节点进行搜索之前，必须搜索完本层的所有节点。1234567扩展出来的子节点放在OPEN表的尾部OPEN表 CLOSED表(1) (2)(3) (1) (3)(4)(5) (1)(2) (4)(5)(6)(7) (1)(2)(3)三 深度优先搜索搜索按深度进行，首先扩展最新

4、产生的节点。OPEN表 CLOSED表 (1) (2)(3) (1) (4)(5)(3) (1)(2) (5)(3) (1)(2)(4)1234567扩展出来的子节点放在OPEN表的头部有界深度优先搜索:深度优先搜索不完备,可能陷入无限分支中,引入搜索深度界限。四 代价树搜索1 代价树：将搜索扩展的代价考虑进入。2 代价树的广度优先搜索：总选择代价最小的节点为待扩展节点。3 代价树的深度优先搜索：从刚扩展的子节点中选择代价最小的为待扩展节点。例：如图五城市间的交通路线图，A是出发地，E是目的地，两城市间的交通费用（代价）如图中数字所示。求从A到E的最小费用的交通路线。ABCDE432453AC

5、1B1D1E2B2D2E1C2E3E434234545233.2 启发式搜索一 思想找到一种有效的方法处理节点（排列待扩展节点），利用问题本身的特性进行扩展，提高搜索效率。有信息搜索。有序搜索：选择最有希望的节点作为待扩展节点。通过定义某一衡量标准决定希望程度。n估价函数估算节点希望的量度。一般形式为：f (x) = g (x) + h (x)f 为估价函数，f (x)表示节点x的估价函数值。g (x)表示从初始节点到x已实际付出的代价；h(x)是从节点x到目标节点的估计代价，利用问题本身的信息进行估价。宽度优先：深度小者优先；深度优先：深度深者优先；代价优先：代价小者优先。局部择优搜索（深度

6、）：对新扩展的节点按代价大小重排；全局择优搜索（广度）：对OPEN表中所有节点按代价大小重排。对于f的选择，没有适用的准确的希望量度，则：（1）时间和空间之间的折衷；（2）保证有一个最优解或任意解。解的三种情况：（1）求得最优（最小代价）解答；（2）适当的搜索找到好的，而非最优。但优与最优很难界定。（3）找到一个解即可。2 8 31 6 47 51 2 38 47 6 5例：八数码棋，定义估价函数：f (n) = d(n) + w(n)d(n) 为搜索树中节点n的深度；w(n)用以计算节点n对应于目标状态错放的棋子数。2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7

7、 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标1234561 2 38 47 6 5nA*算法A*算法：选择一个特定的估价函数f(n)，定义为通过节点n的一条最小代价路径的代价的一个估计。先定义： f *(n) = g *(n)

8、 + h *(n),其中： g *(n) 为从初始节点到节点n的一条最优路径的代价； h *(n)为从n到目标节点最小代价路径的代价。定义估价函数： f (n) = g (n) + h (n)其中g是对g*的估计，h是对h*的估计。g(n)可以是实际值，而h(n)则依赖有关问题的领域的启发信息，h叫启发函数。A*算法定义：（1）估价函数依据f (x) = g (x) + h (x)进行；（2）h(x)=h*(x), h(x)为h*(x)的下界；（3）利用h*(x)的下界h(x)为启发函数的A算法，为A*算法。A*算法的一些特性：（1） A*算法能在有限步内终止，并能找到最优解；（2）在满足h(

9、x)=h*(x)的前提下，h(x)的值越大越好。 f 1(x) = g 1(x) + h 1(x) f 2(x) = g 2(x) + h 2(x) A1* ， A2*分别是以f 1(x) ，f 2(x) 为估价函数的A*算法，且对所有的非目标节点有h 1(x)=深度界限，则标示节点n为不可解节点。四 与或树的有序搜索依据代价决定搜索路线。1 代价计算（1）x为终叶节点，h(x) = 0;（2）x不可扩展，且为非终叶节点h(x) = （3）x后继节点（y1,y2,yn)为或逻辑, 则h(x) =minc (x,yi)+h(yi) （4）x后继节点（y1,y2,yn)为与逻辑，则h(x) = (

10、 c (x,yi)+h(yi)或h(x) = maxc (x,yi)+h(yi) ABCDEFGHI J L NM 222224311311最大法： h左（A)=6 h右（A)=7求和法： h左（A)=9 h右（A)=82 希望树最优解树：代价最小的解树。希望树T：在扩展搜索求解中，有可能成为最优解树一部分的待扩展树，当前代价最小的解树。T包含： （1）初始节点； （2）节点x在T中，其或后继节点中代价值最小的节点也在T中； （3）节点x在T中，其所有与后继节点也在T中；3 有序搜索过程（1）找到希望树T；（2）扩展其端节点n，n为可解节点，进行可解标识；不可解，则进行不可解标识；（3）重新计

11、算代价，回到（1）。ABCDEFG1111113332HIJKLM1111113222h左（A）=9*h右（A）=8h（A）=8h(F) = 7h(C) = 11*h左（A）=9*h右（A）=12h（A）=9五 博弈树的启发式搜索1 博弈：智能性的竞争活动。“二人零和，非偶然，全信息”二人零和：得分函数之和为零，三种结局，我胜、我败、平局；非偶然：双方皆可根据全信息进行分析，选取胜数最大的方案；全信息：当前格局及过去，双方皆知。2 博弈树：描述此类过程的与或树（始终站在某一方的立场上）（1）初始格局：初始节点；（2）与或节点交替出现；（3）我方扩展节点-或关系（可选择一个值大的）敌方扩展节点-

12、与关系（对方可能选择对我方最不利的方案）双方轮流；（4）使我方获胜的节点：终叶节点，可解节点；使队方获胜的节点：不可解节点。选出对自己最为有利的方案（树）。3 极大极小分析法基本思想：预先生成一定深度博弈树；定义估价函数，计算端节点的值（得分），静态估值，再（倒推）计算出父节点的倒推值；根据值选定合适的分支扩展一定的深度。例：一字棋。A、B对弈，先使自己的棋子成一线者为胜。A方：我方，先走。定义估价函数：e(p) = 棋局P上A方有可能成一线的数目棋局P上B方有可能成一线的数目A必胜的棋局P,e (P)= +；A必负的棋局P,e (P)= ；每次扩展两步。baaaababababa baba

13、bababaabab101-10-1-1-20012-1-2114 - 剪枝技术基本思想：根据倒推值的计算方法，或中取大，与中取小，在扩展和计算过程中，能剪掉不必要的分枝，提高效率。定义： 值：有或后继的节点，取当前子节点中的最大倒推值为其下界，称为值。节点倒推值= ； 值：有与后继的节点，取当前子节点中的最小倒推值为其上界，称为值。节点倒推值Q PQ （2）减少否定的辖域： P Q (PQ) P Q (P Q) ( P ) P x ( P ) (x)P (x) ( P ) (x )P （3）变量标准化：使不同变量约束的变元具有不同的名字； x (P(x) ) x (Q(x) x (P(x)

14、) y(Q(y)（4）消去存在量词：两种情况： a) 若存在量词不在任何全称量词的辖域内，则化为一常量； x (Q(x)- Q (A) b)出现在某一全称量词内，以斯克林函数代替每个出现的存在量词的量化变量，函数中的变量由那些全称量词所约束的全称量词量化： y (x P(x, y) ) - y ( P(g(y), y) ) (5) 化为前束形，即将全称量词移到前面：前束形 = （前缀） （母式） 全称量词串 无量词公式(6) 将母式化为合取范式，重新分配：P （Q W） （P Q） （P W）(7) 消去全称量词；(8) 消去合取；P1 P2 Pn - P1 , P2, , Pn(9) 更换变

15、量名称，使不同的子句中变量不同名。以上所得即为子句形式。例： (x) P(x) (y) P(y) P( f (x, y) (y)Q(x,y) P(y) 消去蕴涵：(x) P(x) (y) P(y) P( f (x, y) (y) Q(x,y) P(y) 减少否定辖域：(x) P(x) (y) P(y) P( f (x, y) (y )Q(x,y) P(y) 变量：(x) P(x) (y) P(y) P( f (x, y) (w)Q(x,w) P(w) 存在量词：(x) P(x) (y) P(y) P( f (x, y) Q(x,g(x) P(g(x) 全称量词：(x) (y) P(x) P(y

16、) P( f (x, y) Q(x,g(x) P(g(x) 消去合取：(x) (y) P(x) P(y) P( f (x, y) P(x) （ Q(x,g(x) P(g(x) (x) (y) P(x) P(y) P( f (x, y) P(x) Q(x,g(x) P(x) P(g(x) 更换变量名，变为子句形式： P (x1) P (y1) P ( f (x1, y1) P (x2) Q(x2,g (x2) ) P (x3) P(g (x3) ) 四 归结演绎推理1 归结：命题：C1、C2是子句集S中的任两子句，C1中文字L1与C2中文字L2互补（L1， L1），从C1，C2中分别消去L1，L

17、2，剩下的部分析取，构成新子句C12，此过程称为归结。C1：L1 L2C2： L1 L3C12：L2 L3谓词逻辑：C1,C2是两个没有相同变元的子句，L1，L2分别为C1，C2中的文字，若 是L1， L2的最一般合一，则：C12=（C1 -L1 （C2 -L2 ）为C1，C2的二元归结式。例：C1=P(a) Q(x) R(x)C2= P(y) Q(b) C12 = Q(x) R(x) Q(b) = a / yC12= P(a) R(b) P(y) = b / x2 归结原理定理：（1）C1、C2是子句集S中的两子句，C12是其归结式，若将C12加入S中，得到新子句集S2，S与S2在不可满足的

18、意义上等价：S2的不可满足性 S的不可满足性（2） C1、C2是子句集S中的两子句，C12是其归结式，若用C12代替C1和C2后得到新子句集S1，则：S1不可满足性 S不可满足性3 归结反演方法将永真性的证明转化为不可满足性：将P Q转化为 P Q不可满足。（永真：如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的； 不可满足：若P对D上的任何一个解释都为假，则P在D上是永假的。）对于一阶谓词逻辑，若子句集是不可满足的，则必存在一个从该子句集到空子句集的归结演绎；若从子句集存在一个到空子句集的演绎，则该子句集是不可满足的。4 归结反演证明 a) 基本过程：已知：条件公式

19、集P，求证：目标公式L将P化为子句集S；否定L为L，化为子句集L；将L添加到S中，得到子句集S；对S做归结过程，每次得到的归结式并入S中，反复直至推出一个空子句。b) 例：某公司招聘工作人员，A、B、C三人应试，经面试后，决定： （1）三人中至少录取一人； （2）若录取A而不录取B，则一定录取C； （3）若录取B，则一定录取C；则公司一定录取C。解：定义谓词逻辑来表达问题。P(x)：表示公司录取C，则用谓词公式来表达问题和结论：（1）P(A) P(B) P(C)（2）P(A) P(B) P(C)（3）P(B) P(C)L：P(C)化为子句集的形式：（1） P(A) P(B) P(C)（2） P

20、(A) P(B) P(C)（3） P(B) P(C)（4） P(C)进行归结过程： （5） P(B) （3）（4）（6） P(A) P(C)（2）（5）（7） P(B) P(C)（1）（6）（8）P (C)（3）（7）（9）NIL（4）（8） P(B) P(C) P(C) P(A) P(B) P(C)P(B) P(A) P(C)P(A) P(B) P(C)P(B) P(C) P(B) P(C)P(C) P(C)NIL归结树5 归结反演求解 a) 基本过程 已知：条件公式集P，求解：目标公式L将P化为子句集S；否定L为L，将L Answer化为子句集S（Answer中的变元与L中的变元一致） ；

21、将L添加到S中，得到子句集S；对S做归结过程，每次得到的归结式并入S中，反复直至归结出归结式Answer。L Answer：目标公式和目标公式的否定，重言式。b) 例： 已知： （1）王是李的老师； （2）李和张是同班同学； （3）若X与Y是同班同学，则X的老师也是Y的老师； 求：张的老师是谁？解：定义谓词逻辑表达问题：T(x , y): x是y的老师；C(x , y): x与y是同班同学；（1）T(wang, li)（2）C(li, zhang)（3） C(x, y) T(z , x)T(z , y)（4）T(u, zhang)化为子句形式，并变换目标子句：（1）T(wang, li)（2）

22、C(li, zhang)（3） C(x, y) T(z , x) T(z , y)（4） T(u, zhang) Answer(u)进行归结过程：（5） C(li, y) T(wang , y) (1) (3) (wang/z,li/x)（6） C(li, zhang) Answer(wang)(4) (5) (wang/u, zhang/y)（7）Anwser (wang) (2) (6)归结出的归结式Answer中包含问题的解答，为：王是张的老师。T(wang, li) C(x, y) T(z , x) T(z , y) T(u, zhang) Answer(u) C(li, y) T(w

23、ang , y) C(li, zhang) Answer(wang)C(li, zhang)Answer(wang)wang/z,li/xwang/u, zhang/ywang/u, zhang/y归结树6 归结策略 a) 归结一般过程：从初试子句集开始，每两个子句间进行比较和归结；产生的归结式加入原子句集中，与原来子句及新的子句间两两比较归结；如此一级一级，直到产生空子句。缺点：效率不高，产生许多无用和重复的子句。b) 处理策略：（1）删除策略：纯文字，单一文字；重言式；包含删除，（C1 C2,称C1包含于C2，把子句集中包含的子句删除，不影响子句集的不可满足性）；（2）支持集策略（完备）：

24、每一次归结时，亲本子句（父子句）中至少应有一个是由目标公式的否定所得的子句或是其后继。（3）线性输入（不完备）：参加归结的两子句必须至少一个是初始子句中的一个；（4）单文字子句（不完备）参加归结的两个子句必须至少有一个是单文字子句；（5）祖先过滤形策略（完备）：参加归结的两子句满足以下两条件之一：C1、C2至少有一个为初始子句；一个是另一个的祖先。练习：设A，B，C三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。求：谁说真话，谁说谎？某处被盗，五个侦察员去调查。研究

25、案情时，A说：“赵与钱中至少有一人作案”，B说：“钱与孙中至少有一个作案”，C说：“孙与李中至少有一人作案”，D说：“赵与孙中至少有一人与此案无关”，E说：“钱与李中至少有一人与此案无关”。如果这五个侦察员说的都可信，试用归结演绎推理求出谁是盗窃犯。 3.7 与或形演绎推理已知事实、规则，求取目标；正向推理：从事实或状况向目标或动作进行操作；逆向推理：从目标向事实或状况进行操作。一 与或形正向推理1 事实表达式与或形变换在系统中，将事实转化为与或形。步骤：（1）消去蕴涵；（2）减少否定辖域；（3）量词变换，存在量词；（4）主要合取式的变量不同名；（5）删去全称量词。例：x y Q(y, x)

26、(R(y) P(y) S(x, y) 变换为： Q(z, a) R(y) P(y) S(a, y) 2 与或图表示事实表达式 （1）方法析取：用K线连接符来分解析取式，连接到父辈节点；合取：单线连接符连接到父辈节点上；性质：读取叶节点上的析取，可以构成表达式的子句集。例：Q(z, a) R(y) P(y) S(x, y) Q(z, a) R(y) P(y) S(x, y) R(y) P(y) S(x, y) R(y) P(y)读取子句：Q( z,a )S(x, y) R(y) S(x, y) P(y)3 与或图的F规则变换 在正向推理中，把允许用作规则推理的公式类型限制为： L W 其中L是单

27、文字，W为与或形的公式，而且规则中都为全称量化于整个蕴涵式。F规则变换步骤：（1）消去蕴涵；（2）减少否定辖域；（3）量词变换，存在量词；（4）删去全称量词；（5）再转换为蕴涵的形式。目标公式：转换为子句的形式。推理过程：（1）将事实转换成与或树的形式；（2）将F规则运用到与或树上：将L与其能合一的叶节点相匹配，扩展与或树，将W作为新的节点扩展；（3）重复（2），直到产生一个含有以目标节点为终止节点的一致解图。例： 已知事实： P(a) (Q (a) R(a) ) F规则：r1: P(x) S(x) r2: Q(y) N(y)求证： S(a) N(a) P(a) (Q (a) R(a) ) P

28、(a)Q (a) R(a) Q (a) R(a) S(a)N(a) P(x) a/xQ(y) a/y读取子句：S(a) N(a)S(a) R(a) r1: P(x) S(x) r2: Q(y) N(y)例：公司招聘（1）P(A) P(B) P(C)（2）P(A) P(B) P(C) P(A) P(B) P(C) （3）P(B) P(C)P(A) P(B) P(C)P(A)P(B)P(C)P(A)P(B)P(C)P(B)P(C)P(B)P(C)二 与或形逆向推理1 目标表达式的与或形与正向推理的事实变换类似，有一点区别：用斯柯林涵数消去存在量词中的全称量词，并使各主要析取式具有不同变元。例：yx

29、 Q(y, x) (R(y) P(y) S(x, y) 变换为： Q(z, f(z) R(y) P(y) S(f(y), y) 2 目标表达式与或图表示合取：用K线连接符来分解合取式，连接到父辈节点；析取：单线连接符连接到父辈节点上；性质：读取叶节点上的析取，可以构成目标表达式表达式的子句集。目标表达式表达式的子句集：合取的析取式。Q(z, f(z) R(y) P(y) S(f(y), y) Q(z, f(z) R(y) P(y) S(f(y), y) R(y) P(y) S(f(y), y) R(y) P(y)读取子句：Q( z,f(z) )S(f(y), y) R(y) S(f(y), y

30、) P(y)3 B规则的表示形式在逆向推理中，把允许用作规则推理的公式类型限制为： W L 其中L是单文字，W为与或形的公式。B规则变换步骤：（1）消去蕴涵；（2）减少否定辖域；（3）量词变换，全称量词；（4）删去存在量词；（5）再转换为蕴涵的形式。4 事实表达式 为文字的合取式，能单独起作用。推理过程：（1）将目标转换成与或树的形式；（2）将B规则运用到与或树上：将L与其能合一的叶节点相匹配，扩展与或树，将W作为新的节点扩展；（3）重复（2），直到产生一个含有以事实节点为终止节点的一致解图。例：同学老师问题。已知：（1）T(wang, li)（2）C(li, zhang)（3） C(x, y

31、) T(z , x)T(z , y)求证目标：T(wang, zhang)T(wang,zhang)T(z,y)C(x, zhang)T(wang, x)C(Li, zhang)T(wang, Li)Wang/z,zhang/yLi/xLi/x三 双向推理1 单向的局限性：正向：事实无限制，而目标为文字析取组成的表达式；逆向：事实为文字合取组成的表达式，而目标无限制。 双向建立在以上二者结合的基础之上，由表示事实和表示目标的两个与或图结构组成，这样目标和事实均不受限制。2 关键问题：终止条件的判定，即涉及到两个图结构之间的适当交接处。3 结束判定：CANCEL定义：设若（n , m）中有一个为

32、事实节点，另一个为目标节点，且若(n, m )都由可以合一的文字标记，或者n有K线连接符接至一个后继节点集合Si，使得此集合中每个元Cancel（Si, m）都成立，那么称这两个节点n和m互相抵消即Cancel。事实图的根节点和目标图的根节点可互相CANCEL时，即得一解。 P(f(y) R(f(y) S(y) Q(f(y), y) P(f(y) R(f(y) S(y) Q(f(y), y) R(f(y) S(y)Q(f(y), y) R(f(y) S(y) R(v) S(A) Q(v, A) Q(v, A) R(v) S(A) R(v) S(A)f(y)/vA/yf(y)/vA/y四 置换一

33、致性 在推理过程中，要求所用的置换具有一致性。 定义：设置换集合 =1， 2， n，其中i=ti1/xi1,tim/xim,置换为一致的充要条件为如下两元组：T=t11,t12,t1m, t21, , t2m, .tnmX=x11,x12,x1m, x21, , x2m, .xnm可合一。例：（1） 1=x/y, 2=y/zT=x,yX=y,z（2） 1=a/x, 2=b/xT=a,bX=x,x3.8 不确定性推理n基本概念1 不确定推理：根据不确定的初始条件，运用不确定性的知识，得到近似合理的不确定性结论的过程。2 基本问题（1）证据/条件不确定性：用户提供，中间结论；（2）知识/规则不确定

34、性：条件和结论之间的一种关系，专家给出；（3）表示：一般以一定取值范围表示-1,1；表示方法要直观、表达充分、便于推理；（4）计算推理：不确定性推理模型选择（数值、非数值；概率、模糊理论）；匹配；多个证据组合；传递算法。可信度方法可信度：用以表示事物为真的可相信程度。可信度方法是结合概率论，基于可信度的不确定性表示方法。知识/规则的不确定性表示：IF E THEN H： E为条件，H为结论。CF（H，E）表示规则/知识的可信度-1，1，表示E为真时，对结论H为真的支持程度。再引入： MB（H，E）：表示因条件/证据E，使H为真的信任增长度； MD（H，E）：表示因条件/证据E，使H为真的不信任

35、增长度；有：（1） P(H/E) 0 ，E削弱H；（2） P(H/E) P (H)，则MD(H,E) = 0，MB(H,E) 0， E支持H ；（3） P(H/E)= P (H)，则MD(H,E) = 0，MB(H,E) = 0， E与H无关。 1 PH=1MB（H，E）= max P(H/E), P(H) P(H) 1 P(H)1 PH=0MD（H，E）= min P(H/E), P(H) P(H) P(H)定义：CF（H，E）=MB（H，E）MD（H，E）有：（1）CF（H，E）0，表示E以CF（H，E）的可信度支持H；（2）CF（H，E）0 (b) CF(H,E1)+CF(H,E2) +

36、CF(H,E1)*CF(H,E2) CF(H,E1),CF(H,E2)0 (c) CF(H,E1)+CF(H,E2) CF(H,E1),CF(H,E2)异号1 min|CF(H,E1)|, |CF(H, E2)|例：已知： rule1 ：if E1 then A with CF=0.9 rule2 ：if E2 then A with CF=0.7rule3 ：if E3 then A with CF= 0.8rule4 ：if E4 and E5 then E1 with CF=0.7 rule5 ：if E6 and (E7 or E8) then E2 with CF=1 CF(E3)=

37、0.3, CF(E4)=0.9, CF(E5)=0.6, CF(E6)=0.7, CF(E7)= 0.3, CF(E8)=0.3, 求CF（A）？解： （1）画出对应的与或图。0.9AE1E2E3E4E5E6E7E8-0.30.80.70.60.310.70.90.7-0.8（2）根据CF模型进行计算CF(E1) = min(CF(E4),CF(E5)*CF(r4) =0.6*0.7=0.42CF(A,E1)=CF(E1)*CF(r1)=0.42*0.9=0.378同理：CF(A,E2)=(0.7*1)*0.7=0.49CF(A,E3)=0.3*( 0.8)= 0.24CF(A,E1&

38、E2) = 0.49+0.378 0.49*0.378=0.68CF(A,E1&E2&E3)=(0.68 0.24)/1 0.24=0.583.9 非单调推理一 基本概念1 单调推理：已知为真的命题数目随时间而增加，新的命题（真命题）不会导致前面已知为真或已被证明的命题无效。 基于以上特点的系统是单调的，有以下优点：（1）当加入新的命题时，不必检查新命题与原有知识间的不相容性；（2）对每一个已证明的命题，不必保留一个命题表，不存在某些命题被取消的危险。2 非单调推理：随着时间的推移和推理的进行，推出的结论或证明为真的命题并不单调增加。非单调性推理研究四个代表性的理论或系统：（1

39、）赖特（Reiter)的缺省理论；（2）麦克德莫特（MeDermott）的界限理论；（3） J.麦卡锡(MeCarthy)的界限理论；（4）多伊尔(Doyle)的正确性维持系统。非单调逻辑适合于如下几种环境： （1）当知识不完备时，不得不做出缺省的假设，但当获得更多的知识时，该缺省假设可能是不成立的； （2）当情景发生变化时，原先的结论可能不再成立； （3）在问题求解时，有时需要作出临时的假设，随着问题的解决，这些假设可能不再成立。缺省推理1 知识工程涉及到的各种形式的缺省推理，即是在没有证据可以证明A不存在的情况下，就承认A的存在。2 缺乏信息时的几种假设： （1）若X不知道，那么得结论Y；

40、 （2）若X不能被证明，那么得结论Y； （3）若X不能在某个给定的时间被证明，那么得结论Y。非单调推理系统TMSTMS正确性维持系统是1979年由Doyle建立的，是一个已经实现的非单调推理系统1 结点及状态TMS中每个命题（规则）称为结点；每个结点有IN或OUT两种状态：IN表示相信为真；OUT状态表示不相信为真。支持表SL（Support-List justification)支持表证实的格式如下：命题/结点（SL（IN表）（OUT表）表示出结点对其它结点的依赖性。当且仅当IN表中每个结点为IN和OUT表中每个结点为OUT，证实才为有效的。SL为空，称为前提证实，总为有效；具有非空IN表和非空OUT表的证实表达了一般的推理。条件证明证实CP ( Condition-Proof justification)其形式为：（CP (