知识基础工程与应用 5

第四章知识推理同济大学“智能制造工程专业联盟”教材编委会知识推理概述逻辑推理主要内容不确定性推理推理的工程应用知识推理概述知识推理概述知识推理-定义推理一般是指这样一个过程，通过对事物进行分解、分析，再进行综合，然后做出决策这个过程往往是从事实开始，运用已经掌握的知识，找出其中隐含的事实或总结出新的知识这个过程也是根据某种想法由已知的一个判定(判断)得出另外一个判断的过程知识推理方法分类推理前提推理方法推理结论推理过程单调性逻辑关系问题推理逻辑基础所用知识确定性解决确定性推理不确定性推理归纳推理演绎推理单调推理非单调推理类比推理推理控制策略及分类推理控制策略推理策略搜索策略推理效率问题推理路线问题推理方向控制策略冲突消解策略求解策略限制策略推理效果问题混合推理双向推理控制正向推理控制反向推理控制解决问题推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。可分为：

逻辑推理逻辑推理1.什么是命题

命题是一个有确定真或假的陈述句。命题只有两种取值，因此这样的命题逻辑也称为二值逻辑。2.简单命题和复合命题

简单命题是不包含任何的与、或、非一类联结词的命题，又称原子命题。如“1+1=2”这样的命题就是简单命题。这样的命题不可再分割，如再分割就不完整。

复合命题是把一个或几个简单命题用联结词（如与、或、非）联结所构成的新的命题，也称为分子命题。

由简单命题“太阳是东边升起的”和“1+1=2”经联结词“而且”联结而成，这两个简单命题均为真时，复合命题的取值才为真。命题逻辑3.命题联结词及真值表常用的逻辑联结词包括：¬、∧、∨、→、

通过联结词，可以根据原有的命题定义出新的命题。命题逻辑的许多问题都可看做是一个计算复合命题的真假值的问题，常用的一个方法是真值表方法。

由联结词构成新命题的真值表中，假如一个新命题包括两个变元P、Q，每个变元有真（T）、假（F）两种取值，从而P、Q共有四种可能的取值，在真值表中会有四行对应。对P，Q的每组真值组合（如P=T，Q=F）或说真值指派，都称作命题A的一个解释。

联结词∧（与）、∨（或）、¬（否）与计算机学科中的与门、或门和非门电路是相对应的，因而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。命题逻辑4谓词为了克服命题逻辑的局限性，通过引入了谓词和量词，对简单命题和命题间的相互关系做进一步的描述，形成了谓词逻辑。谓词逻辑又称为一阶逻辑。在谓词逻辑中，一般将简单命题分解为个体词和谓词两个部分。个体词（individual）是一个命题里表示思维对象的词，表示独立存在的具体或抽象的客体。具体的、确定的个体词称为个体常项，一般用a、b、c表示；抽象的、不确定的个体词称为个体变项，一般用x、y、z表示。谓词包含一元谓词和多元谓词。如果命题里只有一个个体词，这时表示该个体词性质或属性的词便称为一元（目）谓词，以P（x）、Q（x）、R（x）表示。如果在命题里的个体词多于一个，那么表示这几个个体词间的关系的词为多元（目）谓词。

一阶逻辑/谓词逻辑5量词用来表示个体数量的词是量词（quantification），给谓词加上量词称作谓词的量化，可看作是对个体词所加的限制、约束的词。定义4.1符号“∀”称作全称量词（universalquantification），读作“所有的x”、“任意x”或“一切x”，含义相当于自然语言中的“任意的”、“所有的”、“一切的”、“每一个”、“凡”等。（∀x）P（x）意指对论域D中的所有个体都具有性质P。命题（∀x）P（x）当且仅当对论域中的所有x来说P（x）均为真时方为真。定义4.2符号“∃”称作存在量词（existentialquantification），读作“存在x”，含义相当于自然语言中的“某个”、“存在”、“有的”、“至少有一个”、“有些”等。（∃x）P（x）意指对论域D中至少有一个个体具有性质P。命题（∃x）P（x）只要论域中的有一个x使P（x）为真，就为真。一阶逻辑/谓词逻辑6自然语句形式化将一个用自然语言描述的命题表示成谓词公式的形式，称为谓词逻辑中的自然语言形式化。基本方法如下：（1）首先要将问题分解成一些原子命题和逻辑联结符；（2）之后分解出各个基本命题的个体词、谓词和量词；（3）按照合式公式的表示规则翻译出自然语句。一阶逻辑/谓词逻辑7谓词公式及分类定义4.3谓词逻辑中的谓词公式递归地定义为：（1）命题常项、命题变项和原子谓词公式（不含联结词的谓词）是谓词公式；（2）如果A是谓词公式，则¬A也是谓词公式；（3）如果A和B是谓词公式，则由逻辑联结词联结A和B的符号串也是谓词公式，如（A∧B）、（A∨B）、（A→B）、（A↔B）等；（4）若A是谓词公式，且A中无∀x、∃x出现，则（∀x）A（x）、（∃x）A（x）也是谓词公式；（5）只有有限次地应用（1）～（4）构成的符号串才是谓词公式。谓词公式也称为合式公式，简称公式。一阶逻辑/谓词逻辑从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程称为自然演绎推理。基本的推理规则是P规则、T规则、假言推理、拒取式推理等。

假言推理

P,PQQ由PQ及P为真，可推出Q为真。

拒取式

Q,PQ

P由PQ及Q为假，可推出P为假。推出铜能导电如果x是金属，则x能导电；铜是金属；如果下雨，则地下湿；地下不湿；推出没有下雨例如：P规则：在推理的任何步骤上都可引入前提。T规则：推理时，如果前面步骤中有一个或多个公式永真蕴含公式S，则可把S引入推理过程中。自然演绎推理

这里应避免如下两类错误：一是肯定后件(Q)的错误；另一是否定前件(P)的错误；所谓肯定后件是指，当P

Q为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。例1:伽利略在证明哥白尼的日心说时，曾使用了如下推理：(1)

如果行星系统是以太阳为中心的，则金星会显示出位相的变化;(2)

金星显出位相变化;(3)

所以，行星系统是以太阳为中心的。这就是使用了肯定后件的推理，违反了经典逻辑的逻辑规则。

所谓否定前件是指，当P

Q为真时，希望通过否定前件P来推出后件Q为假，这也是不允许的。例2：下面的推理就使用了否定前件的推理，违反了逻辑规则：(1)

如果下雨，则地上是湿的;

(2)

没有下雨;

(3)

所以地上不湿。这显然是错误的。自然演绎推理用自然演绎推理求解问题

例：已知如下事实：(1)凡是容易的课程小王（Wang）都喜欢；(2)C班的课程都是容易的；(3)ds是C班的一门课程；求证：小王喜欢ds这门课。

证明：首先定义谓词：

EASY(x)：x是容易的；

LIKE(x,y)：x喜欢y;

C(x)：x是C班的一门课。自然演绎推理自然演绎推理优缺点

优点：表达定理证明过程自然，容易理解，而且其拥有丰富的推理规则，推理过程灵活，便于在其推理规则中嵌入领域启发性知识。缺点：容易产生组合爆炸，推理过程中得到的中间结论一般成指数形式递增。自然演绎推理自动定理证明是人工智能的一个重要研究领域，这不仅是由于许多数学问题需要通过定理证明得以解决，而且很多非数学问题(如医疗诊断、机器人行动规划）也都可归结为一个定理证明问题。定理证明的实质是对前提P和结论Q证明P

Q的永真性。但是要证明一个谓词公式的永真性是很困难的。通过研究发现应用反证法的思想可把关于永真性的证明转化为不可满足性的证明。欲证明P

Q永真，只要证明P∧

Q不满足就可以了。关于不可满足性的证明，海伯伦及鲁宾逊先后进行了卓有成效的研究，提出了相应的理论和方法。海伯伦提出的海伯伦域及海伯伦定理为自动定理的证明奠定了理论基础；鲁宾逊提出的归结原理对机械化推理有了重大的突破。无论是海伯伦还是鲁宾逊的理论，都是以子句集为背景开展研究的。归结原理

一般来说，一个子句集的基原子有无限多个，它在H域上的解释也有无限多个。

可以证明，对给定域D上的任一个解释，总能在H域上构造一个解释与它对应，如果D域上的解释能满足子句集S，则在H域上的相应解释也能满足S，由此可推出如下两个定理：

[定理1]

子句集S不可满足的充要条件是S对H域上的一切解释为假；

[定理2]

子句集不可满足的充要条件是存在一个有限的不可满足的基子句集S’。

该定理称为海伯伦定理。

海伯伦定理只从理论上给出了证明子句集不可满足性的可行性及方法，但要在计算机上实现其证明过程是很困难的。1965年鲁宾逊提出了归结原理，这才使机器定理证明变为现实。归结原理[定义1]

若P是原子谓词公式，则称P与

P为互补文字。1.命题逻辑中的归结原理[定义4.4]

设C1与C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么从C1与C2中分别消去L1和L2，并将两个子句中余下的部分析取，构成一个新子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。

例1：设C1=

P

Q

R,C2=

Q

S这里L1=Q,L2=

Q,通过归结可得：C12=

P

R

S例2：设C1=P,C2=

P通过归结可得：

C12=NIL归结原理例3：

设

C1=

P

Q,C2=

Q

R,C3=P首先对C1与C2进行归结，得到：

C12=

P

R然后再对C12与C3进行归结，得到：

C123=R归结可用一棵树直观的表示出来，如上例可用下图表示其归结过程：

P

Q

Q

R

P

RP

R归结原理[定理4.1]

归结式C12是其亲本子句C1与C2的逻辑结论。即如果C1与C2为真，则C12为真。这是归结原理中很重要的一个定理，由此可得到如下两个推论：

[推论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的不可满足性。这两个推论告诉我们：

为要证明子句集S的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入子句集S，或者用归结式替换它的亲本子句，然后对新子句集证明不可满足性就可以了。如果经过归结能得到空子句，根据空子句的不可满足性，立即可得到原子句集S是不可满足的结论。这就是用归结原理证明子句集不可满足的基本思想。归结原理2.谓词逻辑中的归结原理

在谓词逻辑中，由于子句中含有变元，所以不像命题逻辑那样可直接消去互补文字，而需要先用最一般合一对变元进行代换，然后才能进行归结。

例:设有如下两个子句：C1=P(x)

Q(x)C2=

P(a)

R(y)

由于P(x)与P(a)不同，所以C1与C2不能直接进行归结，但若用最一般合一

={a/x}对两个子句分别进行代换：

C1

=P(a)

Q(a)C2

=

P(a)

R(y)就可对他们进行归结，消去P(a)与P(a),得到如下的归结式：Q(a)

R(y)归结原理

下面给出谓词逻辑中关于归结的定义。[定义4.5]

设C1与C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字，若

是L1和

L2的最一般合一，则称：C12=(C1

－｛L1

｝)∪

(C2

－{L2

})为C1和C2的二元归结式，L1和L2称为归结式上的文字。[定义4.6]子句C1与C2的归结式是下列二元归结式之一：①C1与C2的二元归结式。②C1的因子C2σ1与C2的二元归结式。③C1与C2的因子C2σ2的二元归结式。④C1的因子C2σ1与C2的因子C2σ2的二元归结式。归结原理一组将问题和其解答联系起来的多重推理称为一条链（chain）。[定义1]

一条由问题开始搜索并得到其解答的链，称为正向链

案例：假设你正在开车，忽然看到一部闪着警灯的警车。使用正向链，你也许会推断警察想要你或其他人停下来。即，上述的事实（闪着警灯的警车）支持两个可能的结论（让你停下来或让其他人停下来）。若警车恰好在你身后停下来或警察朝你挥手，更进一步的推论是警察让你停下来的可能性大于让其他人停下来。[定义2]

一条由假设回溯到支持该假设的事实的链，称为反向链案例：以此为有效假设，可以使用反向链来推理这是为什么。一些可能的中间假设是：因为乱丢杂物、超速、设备故障和开着一部偷来的车。于是你就会思索是否有支持这些中间假设的证据，是因为你扔出窗外的垃圾吗?是在速度限制为60公里/小时的地方以100公里/小时的速度行驶吗?任意或所有的这些中间假设都是证明警察让你停车这一假设的可能理由。推理策略不确定性推理不确定性推理1）为什么要研究不确定性推理问题

•现实世界的问题求解大部分是不良结构；

•对不良结构的知识描述具有不确定性（或叫不精确性）：（1）问题证据（初始事实、中间结论）的不确定性；（2）

专门知识（规则）的不确定性。

2）

什么是不确定性推理不确定性推理就是从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却合理或者近乎合理的结论的思维过程。

不确定性推理概念体系3）不确定性推理中的基本问题它除了必须解决推理方向、推理方法、控制策略等基本问题外，一般还需要解决不确定性的表示和量度、不确定性匹配、不确定性的传递算法以及不确定性的合成等重要问题。

（1）知识的不完备和不精确在很多情况下，解决问题需要的知识往是不完备、不精确的。知识不完备是指在解决某一问题时，不具备解决该问题所需要的全部知识。例如，设备故障诊断，由于设备运行环境的复杂性，不可能具有设备故障的全部知识。知识不精确是指既不能完全确定知识为真，又不能完全确定知识为假。（2）知识描述模糊知识描述模糊是指知识的边界不明确。人们在描述时，多采用一些程度量词，例如“天空云量较多”、“设备剧烈振动”，这些概念都是比较模糊的，用这类概念所描述的知识也是模糊的。用一些模糊的量词描述一个数值范围，是常用的处理方法。但不可能全部的描述都能量化。（3）多种原因导致同一结论在现实世界中，由多种原因导出同一结论的情况有很多。例如，机器振动，可能是因为轴承磨损引起，也有可能是超载引起，或者是机箱变形引起。维修人员需要根据其它表征，做出猜测性的推断。（4）解题方案不唯一针对同一个问题，会存在多种解决方案。这些方案会因人、因事、因地而异，可能很难绝对地判断其优劣。对于这些情况，人们往往根据当时情景优先选择主观上认为相对较优的方案，这也是一种不确定性推理。不确定性的含义1.关于知识的不确定性

知识的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度。它也是以赋予规则在0和1之间的系数的方法来表示的。例如，有以下规则：“如果在‘响应特性’测试中，机床得分小于整体平均值，那么机床响应特性偏低，建议提高电机响应”（0.9）。以上规则表示，“如果在‘响应特性’测试中，机床得分小于整体平均值”这事实完全肯定的可信度为1.0，那么得出“机床响应特性偏低，建议提高电机响应”的结论的可信度为0.9。知识的不确定性是可以用一个数值来描述的，该数值表示相应知识的确定性程度，也称为知识的静态强度。知识的静态强度可以是该知识在应用中成功的概率，也可以是该知识的可信程度等。如果用概率来表示静态强度，则其取值范围为[0，1]，该值越接近于1，说明该知识越接近“真”。不确定性的来源2.关于证据的不确定性人对事物的观察，由于受到主观判断或者观察手段的影响，对所看到事实的描述经常带有具有某种不确定性。例如，对下雨程度的判断，对风力的判断等。这就是说，你的观察具有某种程度的不确定性。观察事物时带有的干扰或不精确都会导致证据的不确定性。参照知识静态强度的概念，证据的不确定性也可以用取值范围[-1,1]的一个数字来表示（称为证据的动态强度）。例如，上面机床响应特性的例子，如果规则的条件部分不完全确定，即可信度不为1.0时，比较简单的求得结论可信度的方法如下：取结论可信度为条件可信度（即证据动态强度）与知识静态强度的乘积。假设其条件可信度0.8，上述规则的系数为0.9，则结论的可信度为Cout=0.8×0.9=0.72。不确定性的来源

不确定性推理方法主要分为两类：基于概率论的不确定性推理方法和基于模糊理论的模糊推理方法基于概率论的不确定性推理方法包括可信度推理方法、主观贝叶斯方法和证据理论。

不确定性推理常用方法可信度方法是由E.H.Shortliffe等人在确定性理论的基础上，结合概率提出的一种不确定性推理方法。可信度是指人们根据以往经验对某个事物或现象为真的程度做出的一个判断，或者是人们对某个事物或现象为真的相信程度。可信度推理模型也称为C-F（CertaintyFactor）模型，是基于可信度表示的不确定性推理的基本方法。显然，可信度具有较大的主观性和经验性，其准确性是难以把握的。但是，对某一具体领域而言，由于该领域专家具有丰富的专业知识及实践经验，要给出该领域知识的可信度还是完全有可能的，因此可信度方法不失为一种实用的不确定性推理方法。可信度推理

1.知识不确定性的表示在C-F模型中，知识是用产生式规则表示的，其一般形式是：

ifEthenH(CF(H,E))

其中，

E：是知识的前提条件，它既可以是一个单个条件，也可以是用and及or连接起来的复合条件；

H：是结论，它可以是一个单一结论，也可以是多个结论。

CF(H,E)：是该条知识的可信度，称为可信度因子或规则强度，静态强度。

CH(H,E)在[-1，1]上取值，它指出当前提条件E所对应的证据为真时，它对结论为真的支持程度。例如：if头痛and流涕then感冒（0.7）表示当病人确有“头痛”及“流涕”症状时，则有7成的把握认为他患了感冒。可信度推理

2.证据不确定的表示在该模型中，证据的不确定性也用可信度因子表示。如：

CF(E)=0.6表示证据E的可信度为0.6。证据可信度值的来源分为两种情况：

•对于初始证据，其可信度的值由提供证据的用户给出；

•对于用先前推出的结论作为当前推理的证据，其可信度值在推出该结论时通过不确定性传递算法计算得到。

证据E的可信度CF(E)也是在[-1，1]之间取值。

可信度推理

3.组合证据不确定性的算法

•当组合证据是多个单一证据的合取时，即：

E=E1andE2and…andEn

若已知CF(E1)，CF(E2)，…，CF(En)，则CF(E)=min{CF(E1)，CF(E2)，…，CF(En)}

•当组合证据是多个单一证据的析取时，即：

E=E1orE2or…orEn

若已知CF(E1)，CF(E2)，…，CF(En)，则CF(E)=max{CF(E1)，CF(E2)，…，CF(En)}可信度推理4.不确定性的传递算法

C-F模型中的不确定性推理是从不确定的初始证据出发，通过运用相关的不确定性知识，最终推出结论并求出结论的可信度值。结论H的可信度由下式计算：

CF(H)=CF(H,E)max{0,CF(E)}

5.结论不确定性的合成算法

若由多条不同知识推出了相同的结论，但可信度不同，则可用合成算法求出综合可信度。设有如下知识：

ifE1thenH(CF(H,E1))ifE2thenH(CF(H,E2))

则结论H的综合可信度可分如下两步算出：可信度推理

•首先分别对每一条知识求出CF(H)：

CF1(H)=CF(H,E1)max{0,CF(E1)}CF2(H)=CF(H,E2)max{0,CF(E2)}•然后用下述公式求出E1与

E2对H的综合影响所形成的可信度：

CF1(H)+CF2(H)–CF1(H)

CF2(H)若CF1(H)0,CF2(H)0CF1(H)+CF2(H)+CF1(H)

CF2(H)

若CF1(H)0,CF2(H)0

CF1(H)+CF2(H)

若CF1(H)与CF2(H)异号

1–min{|CF1(H)|,|CF2(H)|

}

CF1，2(H)=可信度推理

主观贝叶斯推理

主观贝叶斯推理

主观贝叶斯推理3.不确定传递算法

主观贝叶斯方法推理的任务就是根据E的概率P（E）及LS，LN的值，把H的先验概率P（H）更新为后验概率P（H|E）或P（H|¬E）。（1）证据肯定存在时

主观贝叶斯推理为简介起见，引入几率（odds）函数O（x），它与概率P（x）的关系为

几率（odds）函数：概率：几率函数和概率函数有相同的单调性。

主观贝叶斯推理

主观贝叶斯推理

主观贝叶斯推理

主观贝叶斯推理证据理论（TheoryofEvidence）由德普斯特（A.P.Dempster）于20世纪60年代首先提出，并由沙佛（G.Shafer）在20世纪70年代中期进一步发展起来的一种处理不确定性的理论，所以，又称为D-S理论。

证据理论是用集合表示命题的。

在证据理论中，D是变量x所有可能取值的集合，D的任何一个子集A都对应一个关于x的命题，称该命题为“x的值是在A中”。

为了描述和处理不确定性，证据理论引入了概率分配函数、信任函数及似然函数等概念。证据理论

证据理论

证据理论

证据理论

证据理