人工智能-第3章-推理技术课件

第3章推理技术2023/7/23《人工智能》23.1消解原理3.2规则演绎系统3.3产生式系统3.4基于概率的推理3.5可信度方法3.6证据理论3.7模糊推理(cut)3.8非单调推理本章主要内容：2023/7/23《人工智能》3

推理方式及其分类1.演绎推理、归纳推理、默认推理 演绎推理：从一般到特殊。例如三段论。 归纳推理：从个体到一般。 默认推理：缺省推理，在知识不完全的情况下假设某些条件已经具备所进行的推理。2.确定性、不确定性推理3.单调性、非单调推理 推出的结论是否单调增加。4.基于知识的推理、统计推理、直觉推理

2023/7/23《人工智能》4谓词逻辑基本概念1.一个谓词分为谓词名与个体两个部分。谓词名刻画个体的性质、状态或个体间的关系。个体表示独立存在的事物或者概念。例如：Teacher(zhang)，Greater(5,3)谓词的一般形式P(x1,x2,…,xn)

其中，P是谓词名，x1,x2,…,xn是个体。谓词名通常用大写的英文字母表示，个体通常用小写的英文字母表示。该谓词是一个原子谓词公式。2023/7/23《人工智能》52.个体可以是常量、变元或者函数。例如：

Less(x,5),x是一个变元。

Teacher(father(wang)),其中father(wang)是一个函数。3.谓词的语义由人指定。例如：S(x)可以表示x是一个人；也可以表示x是一朵花2023/7/23《人工智能》64.连接词 非：¬；析取：∨；合取：∧；蕴含：→； 双向蕴含：谓词逻辑真值表PQ

¬PP∨QP∧QP→QPQTTFTTTTTFFTFFFFTTTFTFFFTFFTT2023/7/23《人工智能》75.谓词公式(wellformedformulas)定义：按下述规则得到的合式公式：(1) 单个谓词是合式公式，称为原子公式；(2) 若A是合式公式，则也是合式公式；(3) 若A，B是合式公式，则 都是合式公式；(4) 若A是合式公式，x是任一个体变元，则 都是合式公式；(5)运用有限步上述规则得到的公式是合式公式。 2023/7/23《人工智能》86.一些重要的等价式2023/7/23《人工智能》97.一些重要的永真蕴含式2023/7/23《人工智能》10所谓模式匹配是指对两个知识模式(例如两个谓词公式)进行比较，以检查这两个知识模式是否完全一致或者近似一致。模式匹配可分为确定性匹配与不确定性匹配。确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。例如： 规则:IFfather(x,y)andman(y)THENson(y,x)事实:father(李四，李小四)andman(李小四)代换：θ={李四/X,李小四/Y}结论：son(李小四,李四)不确定性匹配是指两个知识模式不完全一致，但是它们的相似程度又在规定的限度内。

模式匹配2023/7/23《人工智能》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}不是代换2023/7/23《人工智能》12令θ={t1/x1,t2/x2,…,tn/xn}为一个代换，F为表达式，则Fθ表示对F用ti代换xi后得到的表达式。Fθ称为F的特例。

规则:IFfather(x,y)andman(y)THENson(y,x)事实:father(李四，李小四)andman(李小四)

F=father(x,y)∧man(y)θ={李四/X,李小四/Y}Fθ=father(李四，李小四)∧man(李小四)

结论:son(李小四,李四)2023/7/23《人工智能》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∈{x1,x2,…,xn}后剩下的元素所构成的集合，记为θ°λ。tiλ表示对ti运用λ进行代换。θ°λ就是对一个公式F先运用θ进行代换，然后再运用λ进行代换：F（θ°λ）=（Fθ）λ2023/7/23《人工智能》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}2023/7/23《人工智能》15公式集的合一定义设有公式集F={F1,F2,…,Fn}，若存在一个代换λ使得F1λ=F2λ=…=Fnλ

则称λ为公式集F的一个合一，且称F1,F2,…,Fn是可合一的。设有公式集F={P(x,y,f(y)),P(a,g(x),z)}则下式是它的一个合一：λ={a/x,g(a)/y,f(g(a))/z}一个公式集的合一一般不唯一。2023/7/23《人工智能》16最一般的合一定义

设σ是公式集F的一个合一，如果对任一个合一θ都存在一个代换λ，使得θ=σ°λ，则称σ是一个最一般的合一。代换过程是一个用项（常数，函数，变量）代替变元的过程，因此是一个从一般到特殊的过程。F=P(x,y)∧Q(y)θ={a/x,f(z)/y}

Fθ=P(a,f(z))∧Q(f(z))最一般合一是唯一的。2023/7/23《人工智能》17求取最一般合一差异集：两个公式中相同位置处不同符号的集合。例如：F1:P(x,y,z),F2:P(x,f(a),h(b))则D1={y,f(a)},D2={z,h(b)}求取最一般合一的算法：令k=0,Fk=F,σk=ε。ε是空代换。若Fk只含一个表达式，则算法停止，σk就是最一般合一。找出Fk的差异集Dk。若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk中出现，则置：Fk+1=Fk{tk/xk}σK+1=σk°{tk/xk}k=k+1然后转(2)。若不存在这样的xk和tk则算法停止。算法终止，F的最一般合一不存在。2023/7/23《人工智能》18求取最一般合一的例子例如，设F={P(a,x,f(g(y))),P(z,f(z),f(u))}求其最一般合一。令F0=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=σ0°{a/z}={a/z}

差异集：D1={x,f(a)}。代换：{f(a)/x}F2=F1{f(a)/x}={P(a,f(a),f(g(y))),P(a,f(a),f(u))}。

σ2=σ1°{f(a)/x}={a/z,f(a)/x}

差异集：D2={g(y),u}。代换：{g(y)/u}F3=F2{g(y)/u}={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))}。

σ3=σ2°{g(y)/u}={a/z,f(a)/x,g(y)/u}F3=Fσ3

2023/7/23《人工智能》193.1

消解原理

消解原理也叫做归结原理。主要内容包括子句集的求取、消解推理的规则和消解反演问题求解方法。消解原理的基础知识：在谓词逻辑中，把原子谓词公式及其否定统称为文字。例如：P(x),¬P(x,f(x))

任何文字的析取式称为子句（clause）。例如：P(x)∨Q(x),¬P(x,f(x))∨Q(x,g(x))不包含任何文字的子句称为空子句。合取范式：若干子句的合取（and）

例如：C1∧C2∧C3…∧Cn子句集：S={C1,C2,C3…,Cn}2023/7/23《人工智能》203.1.1化为子句集(1)消去蕴涵符号：例如：(2)减少否定符号的辖域：每个否定符号“¬”最多只用到一个谓词符号上，即利用等价关系把“¬”移到紧靠谓词的位置上。上式经等价变换后在进行消解过程之前,首先需要将谓词演算公式化为一个子句集。其变换过程由下列几个步骤组成：2023/7/23《人工智能》21(3)对变量标准化：使不同量词约束的变元有不同的名字，通过变量更名来完成。例如，上式经变换后(4)消去存在量词：分两种情况

a）存在量词不出现在全称量词的辖域内，则只要用一个新的个体常量替换受该量词约束的变元。b）存在量词位于一个或者多个全称量词的辖域内，此时要用Skolem函数f(x1,x2,…,xn)替换受该存在量词约束的变元。上式中存在量词(y)及(z)都位于(x)的辖域内，所以需要用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和g(x)，则替换后得到3.1.1化为子句集（2）

2023/7/23《人工智能》22(5)化为前束形：把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。

3.1.1化为子句集（3）

(6)化为合取范式(7)消去全称量词

：到了这一步，所有余下的量词均被全称量词量化了。同时全称量词的次序也不重要了。因此，我们可以消去全称量词。

2023/7/23《人工智能》23(8)获取子句集：3.1.1化为子句集（4）

(9)更换变量名称：使一个变量符号不出现在一个以上的子句中。上式在更改变量名后，可以得到子句集：2023/7/23《人工智能》24

子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。谓词公式F的不可满足性：对于任意论域中的任意一个解释，F都不能取得真值T，即F是永假的。定理

设有谓词公式F，其子句集为S，则F不可满足的充要条件是S不可满足。2023/7/23《人工智能》25定义：设L1为任一原子公式，L2为另一原子公式，且具有相同的谓词名，但一般具有不同的变量。已知两子句L1∨α和¬L2∨β，如果L1和L2具有最一般合一σ，那么通过消解可以从这两个子句推导出一个新子句ασ∨βσ。这个新子句叫做消解式（归结式）。3.1.2消解推理规则

2023/7/23《人工智能》26C1=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)2023/7/23《人工智能》27推论1设C1与C2是子句集S中的两个子句，C12是它们的消解式。若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性，即

S1的不可满足性＝>S的不可满足性推论2

设C1与C2是子句集S中的两个子句，C12是它们的消解式。若把C12加入S中得到新子句集S2，则S与S2在不可满足的意义上是等价的，即S2的不可满足性<＝>S的不可满足性定理

若C12是子句C1与C2的消解式，则C12是C1与C2逻辑结论。2023/7/23《人工智能》28

3.1.3消解反演求解过程

1基本思想：

如欲证明Q为P1,P2,…,Pn的逻辑结论，即证明

(P1∧P2∧…∧Pn)→

Q永真，即证明(P1∧P2∧…∧Pn)∧¬Q是不可满足的，即证明其子句集S是不可满足的。为此，检查子句集S中是否包含空子句。若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结能推出空子句，就说明子句集S是不可满足的，原定理得证。消解反演是完备的，即如果子句集不可满足，则一定可以得到空子句。2023/7/23《人工智能》292消解反演：设F为已知前提的公式集，Q为目标公式(结论)，用归结反演证明Q为真的步骤是：否定Q，得到¬Q；F={P1,P2,…,Pn}

把¬Q并入到公式集F中，得到{F,¬Q};{P1,P2,…,Pn,¬Q}

把公式集{F,¬Q}化为子句集S；(P1∧P2∧…∧Pn)∧¬Q

应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。2023/7/23《人工智能》30例:已知求证：G是F的逻辑结论。证明：首先把F和¬G化为子句集：然后进行归结：(6)¬A(x,y)∨¬B(y) 由(1)与(3)归结，{f(x)/z}(7)¬B(b) 由(4)与(6)归结，{a/x,b/y}(8)NIL 由(5)与(7)归结所以G是F的逻辑结论。上述归结过程如右图归结树所示。¬A(x,y)∨¬B(y)∨C(f(x))¬A(x,y)∨¬B(y)¬B(b)NIL¬C(z)A(a,b)B(b)2023/7/23《人工智能》313消解的一般过程：设子句集S={C1,C2,…Cn}，则消解的一般过程是：S内任意子句两两逐一进行归结，得到一组归结式，称为第一级归结式，记为S1。把S与S1内的任意子句两两逐一进行归结，得到一组归结式，称为第二级归结式，记为S2。S和S1内的子句与S2内的任意子句两两逐一进行归结，得到一组归结式，称为第三级归结式，记为S3。如此继续，直到出现了空子句或者不能再继续归结为止。

2023/7/23《人工智能》32

目的：为了提高消解推理的效率，删除某些无用的子句来缩小归结的范围。下述删除策略是完备的（即如果子句集S不可满足，则采用该策略一定可以推出空子句）。纯文字删除法如果某文字L在子句集中不存在可与之互补的文字¬L，则称该文字为纯文字。包含纯文字的子句可以删除。重言式删除法如果一个子句中同时包含互补文字对，则该字句称为重言式。重言式是永远为真的子句，可以删除。包孕删除法设有子句C1和C2，如果存在一个代换σ，使得：

C1σC2，则称C1包孕于C2，可删除C2。4删除策略2023/7/23《人工智能》33

目的：通过对参加归结的子句进行限制，尽可能减小归结的盲目性，使其尽快地归结出空子句。支持集策略限制：每一次归结时，亲本子句中至少有一个是由目标公式的否定所得到的子句，或者是它们的后裔。支持集策略是完备的（即如果子句集S不可满足，采用该策略一定可以推出空子句）。线性输入策略限制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。线性输入策略是不完备的。祖先过滤策略限制：参加归结的子句满足：(1)C1和C2中至少有一个是初始子句集中的子句；或(2)C1和C2中一个是另外一个的祖先子句。祖先过滤策略是完备的。5限制策略2023/7/23《人工智能》343.2

规则演绎系统

对于许多公式来说，子句形是一种低效率的表达式，因为一些重要信息可能在求取子句形过程中丢失。本节将研究采用易于叙述的if-then(如果-那么)规则来求解问题。

在所有基于规则系统中，每个if可能与某断言集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rulebaseddeductionsystem)。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。基于规则的演绎系统和产生式系统，均有正向推理和逆向推理两种推理方式。2023/7/23《人工智能》35

3.3产生式系统

一个产生式系统一般由三部分组成：规则库、综合数据库、控制系统。综合数据库产生式规则库控制系统2023/7/23《人工智能》36规则库

用于描述相应领域内知识的产生式的集合。一个规则库的例子:R1：动物有毛→哺乳类R2：动物产奶→哺乳类R3：哺乳类∧吃肉→食肉类R4：哺乳类∧吃草→有蹄类R5：食肉类∧黄褐色∧有斑点→金钱豹R6：食肉类∧黄褐色∧黑条纹→虎R7：有蹄类∧长脖→长颈鹿R8：有蹄类∧黑条纹→斑马2023/7/23《人工智能》37综合数据库又称为事实库、上下文、黑板等等。存放已知的事实和推导出的事实。2023/7/23《人工智能》38控制机制又称为推理机构，负责整个产生式系统的运行。控制机制完成的工作有：按照一定的策略，匹配规则的条件部分；当多于一条的规则匹配成功时（称为冲突），选择其中一条规则加以执行(冲突消解)；将匹配规则的结论部分放入综合数据库；计算结论的不确定性；决定系统何时终止运行；2023/7/23《人工智能》39一个动物识别的例子已知事实：一动物{有毛，吃草，黑条纹}R1：动物有毛→哺乳类

R2：动物产奶→哺乳类R3：哺乳类∧吃肉→食肉类R4：哺乳类∧吃草→有蹄类

R5：食肉类∧黄褐色∧有斑点→猎狗R6：食肉类∧黄褐色∧黑条纹→虎R7：有蹄类∧长脖→长颈鹿R8：有蹄类∧黑条纹→斑马2023/7/23《人工智能》40产生式系统求解问题的一般步骤初始化事实库；若规则库中存在尚未使用过的规则，且可匹配成功，则转第3步。否则转第5步；执行当前选中的规则，并把结论送入事实库；检查事实库中是否已经包含了解。若有则终止推理。若无则转第2步；要求用户增添事实。若有则转第2步。若无则终止推理。学科前沿讲座人工智能——皇帝的新脑还是人类的终结

一、关于人工智能

一、关于人工智能从数值计算文字、图像等多媒体信息处理初步实现了Leibniz提出的“将人的思维机器化”的思想让机器拥有人的心智——成为计算机专家梦寐以求的理想！1956年，M.L.Minsky，C.Shanon，J.McCarthy(人工智能之父)等在美国达德茅斯大学召开第一届人工智能学术会议。 会上首次使用“人工智能”这一术语。 标志着人工智能学科的诞生。一、关于人工智能1950年，W.格雷.瓦尔特，可以自己充电的“乌龟”1960年，K.M.柯尔，模拟了一个精神病疗法专家电脑下棋方面，97年的“深蓝”(DeepBlue)，03年的“小深”(DeepJunior)一、关于人工智能医生：我可以为你效劳吗病人：我不知道医生：请告诉我一些情形病人：不医生：请你说得仔细些病人：今天我厌烦得很医生：你知道这是什么原因病人：是的我老了医生：请继续讲病人：仿佛任何事情都激不起我的兴致医生：请更多地告诉我你的这种感觉病人：我也有些知道为何我会这样感觉医生：是吗病人：我似乎在想有一个家医生：什么东西使你有这样的想法病人：它是一种挑战医生：为什么那对你是重要的二、电脑能否实现人的智能？机器体力电脑计算速度和准确性人脑思维是否电脑能代替人脑实现智能？一旦能够实现，这种被认为是特权的智能行为将受到挑战。