第四章-人工智能逻辑ppt课件

.,第四章人工智能逻辑,第一节引言一、逻辑是重要的形式工具1、Aristotle从数学的研究中分离出逻辑学，认为形式逻辑是一切推理活动的最基本出发点。2、Baccon归纳逻辑3、Leibnitz将数学的方法引入逻辑领域，提出数理逻辑，将形式逻辑符号化，从而能对人的思维进行运算和推理。,.,第四章人工智能逻辑,第一节引言一、逻辑是重要的形式工具3、Leibnitz注：现代数理逻辑主要研究内容为：逻辑运算、证明论、公理集合论、递归论、模型论。4、形式化实质上就是一个算法，即一个机械地实现的过程，用于将概念、断言、事实、规则、推演乃至整个被描述系统表述得很严密、精确而无需任何专门的知识，即可被毫无歧义地感知。,.,第四章人工智能逻辑,第一节引言二、逻辑学与人工智能1、研究目标a)逻辑学研究人的思维规律和法则。注：逻辑是思维的规范，推理是思维的法则b)人工智能模拟、扩展和延伸人的智能，即模拟人的思维过程，研究人的思维规律和推理方法，并让计算机学会思维。,.,第四章人工智能逻辑,第一节引言二、逻辑学与人工智能2、研究方法由于人类智能行为在很大程度上是通过语言和文字表达出来的，所以，人工智能模拟人类思维是以模拟人类的自然语言作为出发点。逻辑学研究人的思维是从研究人的自然语言入手。方法相近。3、逻辑可作为重现智能的手段,.,第四章人工智能逻辑,第一节引言三、人工智能中的逻辑学注：逻辑和推理是人工智能的基本框架。1、主要内容a)逻辑作为程序设计语言，即逻辑程序设计b)逻辑作为知识表示和推理的工具，即知识表示与推理,.,第四章人工智能逻辑,第一节引言三、人工智能中的逻辑学2、逻辑程序设计将函数和关系等概念形式化，然后利用标准逻辑的推理方法进行求解，得到与有关计算机程序一样的效果，这就是逻辑程序设计。Prolog是将逻辑方法(自动推理)应用于计算机程序设计语言的一个例子，其理论基础是一阶逻辑。更确切地，是Horn子句逻辑。注：Horn子句是指仅由句节(原子或负原子)通过或符号连接而成的句子中最多有一个正原子。,.,第四章人工智能逻辑,第一节引言三、人工智能中的逻辑学3、关于知识的表示与推理可使用逻辑进行知识的表示与推理。多数基于逻辑的智能系统是使用一阶逻辑或一阶逻辑的扩充形式。注：1)智能行为的基础是知识，尤其是常识性知识。人类的智能行为对于知识的依赖主要表现在对于知识的利用。,.,第四章人工智能逻辑,第一节引言三、人工智能中的逻辑学3、关于知识的表示与推理注：2)一阶逻辑的优点是它具有相当强的表达能力，同时可很好地表达不确定性知识。此外，一阶逻辑还有一完备的公理系统。完备的公理体系为设计有关推理的策略和算法提供了一个参考标准。这就是经典逻辑(传统的形式逻辑及谓词逻辑),.,第四章人工智能逻辑,第一节引言三、人工智能中的逻辑学3、关于知识的表示与推理注：3)虽然，有人坚信，一阶逻辑对于知识表示是足够的，但从实际应用角度看，为方便、清楚和简洁起见，知识表示不一定非得从一阶逻辑出发不可。事实上，人们从实际应用出发已经发明和创建了许多适合于不同目的的逻辑系统。这就是非经典逻辑。,.,第四章人工智能逻辑,第一节引言三、人工智能中的逻辑学4、常使用的非经典逻辑a)模态逻辑用于刻划各种认知概念，如相信、知道、愿望、意图、目标、承诺等。b)时序逻辑用于刻划时间因素,.,第四章人工智能逻辑,第一节引言三、人工智能中的逻辑学4、常使用的非经典逻辑c)模糊逻辑用于描述不确定和不精确的概念。注：模糊逻辑是直接建立在自然语言上的逻辑系统，与其它逻辑系统相比，考虑了更多的自然语言的成分。Fuzzylogic=computingwithwordsd)动作逻辑,.,第四章人工智能逻辑,第一节引言四、一阶逻辑的扩充1、语构扩充a)二阶谓词逻辑演算系统引入二阶量词、谓词变元和函数变元b)模态逻辑系统引入模态词2、语义扩充多值逻辑和模糊逻辑,.,第四章人工智能逻辑,第一节引言四、一阶逻辑的扩充3、非经典逻辑与经典逻辑之间的主要区别a)是演绎还是归纳？注：归纳逻辑在人工智能中也很重要，虽然形式化程度不高。b)二值还是多值？注：多值逻辑的理论基础尚显薄弱。c)是否遵循形式逻辑和传统数理逻辑(经典逻辑)的运算法则？,.,第四章人工智能逻辑,第一节引言四、一阶逻辑的扩充3、非经典逻辑与经典逻辑之间的主要区别d)是否引入额外的逻辑算子？e)单调还是非单调的？注：传统逻辑是单调的。,.,第四章人工智能逻辑,第二节模态逻辑及其应用一、基本思想在普通逻辑中引入模态词。二、模态词自然语言中用于表示事物的“势态”、人的“情态”以及过程的“变迁”(历史的或未来的)词称为模态词。如：“必须”、“可能”，“应该”、“允许”、“知道”、“许可”，“一贯”、“偶然”等。,.,第四章人工智能逻辑,第二节模态逻辑及其应用二、模态词注：1)模态词与真值联结词不同，因为由真值联结词联结而成的复合命题，其真值完全由组成它的各成分命题所确定，而由模态词连接而成的复合命题就无这种性质。,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统基本模态逻辑系统是在普通逻辑系统(一般为一阶谓词逻辑)中引入“可能”和“必然”两个模态词。1、模态逻辑正规系统(NSK)a.语言部分1)字母表为集合P1,P2,(必然),(可能),(,)2)项集为空集,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)a.语言部分3)公式定义(1)Pi是公式；(2)若A,B是公式，则AB,A,A,A均是公式；(3)除此以外，无别的公式注：AB=(AB)AB=ABAB=(AB)(BA),定义,定义,定义,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)b.公理模式A1AAAAA2(AB)(AB)(公理K)A3全体重言式A4A(当A是公理时)c.推理规则分离规则：,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)d.语义解释1)Leibnitz的“可能世界”语义解释(1)可能世界：除了现实世界，还有许多可能世界，一命题的真或假取决于在哪个可能世界中对它进行考察。(2),模态算子解释A就是在所有可能世界中A真A就是存在可能世界使A在其中为真,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)d.语义解释2)改进的Kripke语义结构解释M=,其中U为一非空集合，称为宇宙，其成员称为可能世界，可能世界用w1,w2,w,w等表示；R是U上的一个二元关系，称为可能世界间的可到达关系(注意：R未必为偏序关系)；I为UP1,P2,到0,1的映射，即对每一个可能世界w,对每一个原子命题赋值；,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)d.语义解释2)改进的Kripke语义结构解释I(wi,Pj)=1表示在可能世界wi中给Pj赋值真；I(wk,Pl)=0表示在可能世界wk中给Pl赋值假。|=A当且仅当|A|=A当且仅当对所有w,若wRw，则|=A(若在w的一切可到达世界中A真，则在可能世界w中A为真),.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)d.语义解释2)改进的Kripke语义结构解释|=A当且仅当存在w,wRw，且|=A(若在w的某些可到达世界中A真，则在可能世界w中A为真)注：一般使用改进的Kripke结构作为模态逻辑的语义解释结构。,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统2、T系统a.公理模式T1(AA)AT2A(AB)T3ABBAT4(AB)(CA)(CB)T5AA(公理T)T6(AB)(AB)(公理K),.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统2、T系统b.推理规则R1(代入规则)：若p是A中变量，A为合式公式，且能用上述公理系统证明(写作|A)，B为任一合式公式，用B代入A中的p后使A成为A，则也有|A。R2(分离规则)：由|AB及|A，有|B成立。R3(必然规则)：从|A可得|A,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统2、T系统b.推理规则注：1)在T系统中规定,为基本逻辑算子，其它逻辑算子可用这三个算子定义：A=AAB=ABAB=(AB)AB=(AB)(BA)AB(A严格蕴含B)=(AB)A=B(A严格等价B)=(AB)(BA),定义,定义,定义,定义,定义,定义,定义,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统2、T系统b.推理规则注：2)T系统引入严格蕴含和严格等价的目的是避免悖论。3)必然规则不能理解为AA，因为必然规则的含义是，若A是定理，则A也是定理，而AA则表示，若A为真，则A也为真，通常A为真不等于A是定理。,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统2、T系统b.推理规则注：4)T系统包含NSK系统。5)T系统基本是最弱的命题模态逻辑系统，而NSK是最基本的命题模态逻辑系统。,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统2、T系统c.语义解释使用改进的Kripke语义结构，即K=，并要求R是连续的(也称为序列的)且自反的。这是因为有：若R是自反的，则AA和AA皆为真，即公理T成立。证明：R是自反的，若wRw可知，A能推出|=wA,因此A为真，同样可证|=wA.,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统2、T系统c.语义解释注：1)R称为连续的(序列的)，当且仅当对U中的每个w，存在U中的，使wR2)R称为自反的，当且仅当对U中的每个w,有wRw成立3)R是自反的，则R一定是连续的(序列的),.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统2、T系统d.重要性质(1)AA(2)A(BA)(A(BA)(3)A(AB)(A(AB)注：性质(2)和(3)表明，若A必然成立，则任何命题均严格推出(严格蕴含)A；若A必然假，则A能严格蕴含任何命题B，这就是所谓的严格蕴含悖论，与实质蕴含悖论相对应。,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统3、S4系统对于T系统，增加公理模式：AA(公理4)，就成为S4系统。S4的语义解释仍使用改进的Kripke语义结构解释，并要求可能世界之间的可到达关系R是传递的，即满足传递性。这是因为：若R是传递的，则AA(公理4)成立。证明：设当前世界为，A表示凡满足R的均使A为真，若使R成立，则由传递性知R成立，这表明A成立。,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统3、S4系统注：1)称R是传递的，当且仅当对U中任意的,从R和R可推出R2)这里当然要求R是连续(序列)和自反的3)S4系统具有如下性质：(1)AA(2)AA(3)AA(4)AA(5)AA,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统4、S5系统对于T系统，增加公理模式：AA(公理5)，就成为S5系统。S4的语义解释仍使用改进的Kripke语义结构解释，并要求可能世界之间的可到达关系R是欧几里德和自反的。这是因为：若R是欧几里德且自反的，则AA(公理5)成立。,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统4、S5系统注：1)称R是欧几里德的，当且仅当对U中任意的,，由R和R可推出R2)当R是欧几里德且自反时，AA成立证明：设当前世界为，A表示存在，使R，且|=A，由R和R有R，即R是自反的，说明有|=A成立。现设是任意一个使R成立的可能世界，再次引用欧几里德性质，可有R成立，此表明|=A成立，从而|=A成立。证毕#,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统4、S5系统注：3)若关系R是自反和欧几里德的，则R是对称的。证明：对于任意的,U,令R,R则有R(欧几里德性质)；由R和R可知有R(欧几里德性质)；因此，R是对称的。,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统4、S5系统注：4)若关系R是欧几里德和对称的，则R是传递的。证明：对于任意的,U,令R,R则有R(欧几里德性质)；由R可有R(R是对称的)；由R和R可知有(欧几里德性质)；由R,R可证R；因此，R是传递的。,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统4、S5系统注：5)当关系R是自反且欧几里德的时候，R是一等价关系。这表示，可将可能世界集分为一组互不相关的等价类，若将每个等价类看成一个可能世界，则得到一个缩小了的模型，称为商模型。6)S4是S5的子系统，即公理4是公理5的推论。证明见P429,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统4、S5系统注：7)T系统、S4系统和S5系统均是一致的(A和A不同时属于同一系统)8)S5系统具有性质：(1)PP(2)PP(3)AA,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统5、一阶模态谓词演算系统a.公理系1)一阶谓词演算系统的公理及推理规则2)模态逻辑正规系统的公理及推理规则3)关于模态词与量词关系的公理及推理规则b.语义结构仍使用Kripke语义解释结构：，其中D是个体域，且约定为各可能世界所公用的个体域，I为一解释集合Iw|wU,.,第四章人工智能逻辑,第二节模态逻辑及其应用三、基本模态逻辑系统5、一阶模态谓词演算系统b.语义结构Iw为可能世界w中对常元、函词、谓词等的解释，对变元的指派。其真值规定如下：公式A在结构K的可能世界w中对解释Iw及其指派s为真，即|=AS，规定为：|=Bs当且仅当对所有w,若wRw，则|=Bs;|=Bs当且仅当存在w,若wRw，则|=Bs;|=vA当且仅当对每一个dD,有|=As(v/d);|=vA当且仅当存在dD,有|=As(v/d);,.,第四章人工智能逻辑,第二节模态逻辑及其应用四、模态逻辑的几种解释1、真理论模态逻辑(必然逻辑)真理论模态逻辑又称为关于“必然”的模态逻辑。其模态词是“必然”和“可能”。S4和S5可解释为真理论模态逻辑系统。2、认识论模态逻辑(知道逻辑)认识论模态逻辑又称为关于“知道”的模态逻辑。和分别解释为“知道”和“认可”。S4可解释为认识论模态逻辑系统。,.,第四章人工智能逻辑,第二节模态逻辑及其应用四、模态逻辑的几种解释3、道义论模态逻辑道义论模态逻辑又称为关于“应该”的模态逻辑。其模态词是“应该”和“允许”。A解释为“A是应该真的”，A解释为“A是允许真的”。S5可解释为道义论模态逻辑系统。注：道义论模态逻辑会与“行为”有关。4、时序逻辑时序逻辑讨论事件在时间上的将来永久性和可能性。具体地说，将A解释为“A将永远真”，A解释为“A将会真”。,.,第四章人工智能逻辑,第二节模态逻辑及其应用四、模态逻辑的几种解释4、时序逻辑为了表示事件在时间上的过去一贯性和可能性，在时序逻辑中还可引入另一组模态词：“一贯地”、“曾经有()”。S4可解释为时序逻辑。注：时序逻辑对程序规范、程序验证以及程序语义、形式化等应用具有重要意义。5、经验论模态逻辑经验论模态逻辑又称为关于经验的模态逻辑。其模态词有：“一贯地(A)”、“偶然的(A)”、“经验地(A:根据经验A真)”、“有先例地(A:A真有先例)”。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑1、一般知道逻辑a)模态词使用“知道”和“认可”(不排除)。b)知道的含义1)某人确切地知道某事，即只要他知道一件事，则这件事必然是真的2)某人认为某事是真的，这是他的主观认识，与该事是否真不一定一致，严格地说，这应该属于信念的范围。c)认识主体我,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑1、一般知道逻辑d)凡人知道逻辑引入模态算子K(表示知道)和Z(不排除)。ZAKA1)公理ZAKAKAZA(并非不能排除A不成立，即可排除A不成立，即知道A)KAZA(知道A，则会不排除A成立)KAKKAZAZZAZAKZAZAZKA,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑1、一般知道逻辑d)凡人知道逻辑1)公理注：(1)ZAKA不能作为公理，这是因为：ZAKA等价于ZAZA等价于(ZAZA)等价于“不排除A成立也不排除A成立是假的”，这不符合常识(可能对A的真假一无所知)。(2)凡人知道逻辑中的“知道”本质上是一种信念。(3)弱S4系统可解释为凡人知道逻辑。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑1、一般知道逻辑e)圣人知道逻辑在凡人知道逻辑中，加上公理KAA(若我知道某件事，则这件事一定为真)。注：(1)圣人知道逻辑和凡人知道逻辑的区别反映了知道逻辑和信念逻辑的本质不同。(2)圣人虽然不犯错误，但推理能力可能是有限的，即公理K：(K(AB)(KAKB)不一定能成立，如对数学定理证明。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑1、一般知道逻辑e)超人知道逻辑在圣人知道逻辑中，加上公理K：(K(AB)(KAKB)。这样，再加上普通命题逻辑的推理规则(由AB及BC得AC)，就可推出所有被已知知识蕴含的知识。注：超人知道逻辑只是具有超人的推理能力，但不能洞察一切客观上为真的命题。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑1、一般知道逻辑f)上帝知道逻辑在超人知道逻辑中，加上公理：如果A可证，则KA也可证，即(|A)(|KA)(必然规则)注：必然规则写成AKA是不合适的，因为A为假而KA为真时，此规则也成立，表示上帝会将假命题视作真命题。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑1、一般知道逻辑g)KS4系统1)公理AZAZ(AB)ZAZBZZAZA2)推理规则由|AB推出|ZAZB由|A推出|KA,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑1、一般知道逻辑g)KS4系统注：KS4接近上帝知道逻辑，但不能作为真正的上帝知道逻辑，这是因为，由公理AZA可得AZA，表示即使A非事实(命题为假)，不排除A(命题ZA为真)也符合此公理，而上帝不会犯这样的错误。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑a)认识主体一群有着不同知识的个体，简称群体。b)群体知道逻辑K(m)(有m个个体)1)公理J1：普通命题演算的所有重言式J2：KiAKi(AB)KiB(i=1,m)(公理K)2)推理规则Q1：若A可证，且AB可证，则B可证Q2：若A可证，则KiA可证(i=1,m),.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑b)群体知道逻辑K(m)(有m个个体)3)语义基本思想是用可能世界集表达，每一个个体ai被赋予一个可能世界集Wi,Wi中的每个可能世界w均是ai心目中可能的现实世界。个体ai知道某个事实p的含义是：p在Wi的每个对ai来说是可到达的可能世界(简称可到达世界)中为真。反之，若p至少在Wi的一个可到达世界中为假，则称ai不知道p，若p在Wi的所有可到达世界中均为假，则称ai知道非p。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑b)群体知道逻辑K(m)(有m个个体)3)语义具体地，是使用Kripke群体模型M=(W,R1,R2,Rm,V)，若Ri，则表示从可能世界的一个个体ai的观点看来，是一个可到达的现实世界。称是可从到达的，若存在可能世界序列1,2,n,使得=1,iRii+1成立,n=,1in-1,其中对每个i,存在一个j,使得Ri=Rj。|=A当且仅当A在中为真。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑c)群体的最小知识闭包Lm()(是命题集)1)Lm()2)若ALm()，则ALm()3)若A，BLm()，则ABLm()4)若ALm()，则KiALm()，i=1,m,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑d)一致性1)命题A称为是一致的，若A不是K(m)可证的2)一组命题A1,A2,An称为是一致的，当且仅当A1A2.An是一致的。3)命题的一个无限集称为是一致的，当且仅当它的每个有限子集均是一致的。4)命题集S称为最大一致的，若S是一致的，且对所有的ALm()-S，AS均不是一致的。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑d)一致性注：(1)每个一致的命题可以扩充成为最大一致的命题集。(2)若S是一个最大一致的命题集，则对所有的命题A、B有：或者AS，或者AS；ABS，当且仅当AS且BS；若AS且(AB)S，则BS;若A恒真，则AS。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑e)健康性和完备性1)健康性若任何在一群体知道逻辑的公理系统中可证的命题在每个可能世界中皆成立，则称该群体知道逻辑的公理系统是健康的。2)完备性若每个在所有可能世界中成立的命题均是在系统中可证的，则称该系统是完备的。注：K(m)是一个健康且完备的系统。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑f)K(m)扩充1)增加公理J3：KiAA(知识公理)(若有人知道A为真，则A为真，即群体中任何人均无错误的知识)J4：KiAKiKiA(正内省公理)(每个人均知道他知道什么)J5：KiAKiKiA(负内省公理)(每个人均知道他不知道什么)注:若将Ki比作,J3可作为公理T,J4可作为公理S4,J5可作为公理S5,从而解释为知道是有意义的。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑f)K(m)扩充2)引进新算子算子JJAK1AK2A.KmA(J表示人所共知的知识)算子CCAJAJJAJJJA(C表示无限层内省(自己知道自己知道)和无限层外察(每个人知道别人知道)的知识，即，C是常识模态词),.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑f)K(m)扩充2)引进新算子注：(1)显然，算子C表达的内容比算子J表达的要多得多，但日常生活中又好像若每个人均知道某件事，则每个人均知道别人也知道这件事，很难区分J和C，但可举一反例，如秘密组织。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑f)K(m)扩充2)引进新算子注：(2)算子C和J的语义可表达如下：|=JA成立，当且仅当对所有使得Ri成立的(其中1im,任意)，皆有|=A成立。|=CA成立，当且仅当对所有从可到达的世界有，|=A成立。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑f)K(m)扩充3)关于J和C的公理(常识型附加公理)J6：JpK1pK2p.KmpJ7：CppJ8：CpCJpJ9：CpC(pq)CqJ10：(pJq)(pCq),.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑f)K(m)扩充3)关于J和C的公理(常识型附加公理)注：(1)J7表明，凡常识都是事实(2)J7和J8合在一起给出Cp的递归定义；(3)J9表示常识推理在逻辑上是全知的；(4)J10表明，必然成为J型常识的事实也必然成为C型常识。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑f)K(m)扩充4)关于C的推理规则(常识型附加规则)Q3：若p是可证的，则Cp也是可证的。注：对于上述知道逻辑。每个人只能利用自己的知识来进行推理，但实际上，每个人都不会拥有全部知识，需要合作。这种由不完全知识组成的相对完全的知识称为潜在的知识，可用算子I表示潜在的知识。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑f)K(m)扩充5)算子I的语义刻划设M=(W,R1,R2,Rm,V)是一个Kripke群体模型，则|=IA成立，当且仅当对所有的公共世界，皆有|=A成立(其中，A是一个命题)。注：在这里，称为是(相对于的)一个公共世界，当且仅当对所有i(1im),Ri皆成立。即，在所有个体都认为是可能的现实世界的地方，并且只有在这种地方，成立的命题才是潜在的知识。,.,第四章人工智能逻辑,第二节模态逻辑及其应用五、知道逻辑2、群体知道逻辑f)K(m)扩充6)关于I的公理和规则(集成型知识公理和规则)(1)公理J11：KipIpi=1,m(2)规则Q4：IpI(pq)Iq,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑1、信念含义解释a)表示尚未被完全证实的知道。注：在这种含义下，只有已经被证实(变为知道)的信念和尚未被证实的信念之分，而不存在可能被否证的信念。b)表示不一定正确的知道。注：在这种含义下，信念既可被证实，也可被否证。,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑1、信念含义解释c)表示对已有证据积累的一种函数，体现对某个命题的相信程度。注：此时，从数学上说，信念就是一种概率(或其它表示不精确程度的数学量)，它在证据积累过程中可以变化，常用于专家系统的不精确推理。,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑2、模态算子B(相信)W(可以接受)WA=BAK(知道)Z(不排除)ZA=KA,定义,定义,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑3、凡人信念逻辑公理：KABABAWAWAZABABBAWAWWABABKA(理智人公理)ZABA(鲁莽人信念公理,不排除A就去相信A)ZAWA(谨慎人信念公理,不排除A就可接受A),.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑4、超人信念逻辑B(AC)(BABC)5、上帝信念逻辑BAKA(凡相信者必真),.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑6、Pap信念逻辑系统a)公理(1)BiABi(AC)BiC(每个人都是超人)(2)BiABiA(每个人都不会发生逻辑上的矛盾)(3)Bi(AC)BiA(4)Bi(AC)BiC,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑6、Pap信念逻辑系统b)推理规则(1)若对所有个体i,均有BiABiC成立,则亦有AC成立(所有人都相信的命题就是真命题，每个人都有一票否决权)。(2)不存在这样的个体I,使得对任何命题A，只要BiA成立，就有A成立(排除了上帝的存在，(BiAA),.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑7、KL逻辑a)算子m个知道算子：K1,K2,Kmm个信念算子：B1,B2,BmJ,C,L,QJAK1AK2A.KmACAJAJJAJJJALAB1AB2A.BmAQALALLALLLA,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑7、KL逻辑b)公理(1)命题演算的全部公理(2)由|A和|(AB)可得|B(3)Ki(AB)(KiAKiB)(超人知道公理，逻辑全知)(4)KiAA(圣人知道逻辑)(5)KiAKiKiA(6)C(AB)(CACB)(公共常识全知)(7)CAKiA,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑7、KL逻辑b)公理(8)CAKiCA(对于常识，每个人均知道)(9)C(AJA)(ACA)(10)由|A，可得|CA(11)Bi(AB)(BiABiB)(超人信念公理，逻辑全信)(12)Bifalse(相信的命题至少不能证明其错)(13)Q(AB)(QAQB)(公共常识全信)(14)QALA(常识信念也是每个人的信念),.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑7、KL逻辑b)公理(15)QALQA(对常识型信念，每个人均相信)(16)Q(ALA)(LAQA)(17)KiABiA(知道A者一定相信A)(18)BiAKiBiA(相信A者一定知道自己相信A)(19)CAQA(常识一定是常识型信念),.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑7、KL逻辑c)语义模型M=(W,R1,R2,Rm,R1,R2,Rm,V)，其中：1)每个Ri均是W上的等价关系2)各个Ri具有如下性质：(1)Ri是序列的(连续的)(2)由Ri可推出Ri(3)对于任意的,若Ri及Ri均成立，则Ri也成立。,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑7、KL逻辑d)性质Bi(BiAA)(每个人相信，只要他相信A，则A就一定是真命题)(主观主义者的信念逻辑),.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信a)概念由KA和K(AB)可知有KB成立，再加上普通命题逻辑的推理规则(由AB及BC得AC)，就可推出所有被已有知识蕴含的知识。这就是逻辑全知。由BA和B(AC)可知有BC成立，再加上普通命题逻辑的推理规则(由AB及BC得AC)，就可推出所有被已有信念蕴含的信念。这就是逻辑全信。注：建立信念逻辑系统是要尽力避免逻辑全知(信),.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信b)摆脱逻辑全知的方法途经1)将显式信念和隐式信念区分开来显式信念是与推理者相关的信念，而隐式信念虽然可能被推理者所持有，但却和推理者目前考虑的问题无关。注：为了区分显式信念和隐式信念，我们可引入情景概念显式信念在其中成立的环境。在一个情景中，一个命题可真可假，或既真又假，或不知真假。若一个情景中不包含矛盾，且每个命题在其中的真假值已知，则称之为完善的情景，即可能世界。,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信b)摆脱逻辑全知的方法途经2)逻辑方式避免在系统中出现逻辑闭包(即通过无穷推理求出全体可能信念的集合)。避免逻辑闭包的方法可有语义和语法方法。(1)语义方法通常设计某些不可能世界或非标准世界，使一些本来为真的命题在其中不为真，或本来不为真的命题到其中成为真的了。,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信b)摆脱逻辑全知的方法途经2)逻辑方式(2)语法方法通常是先给出推理者的一个初始信念集，然后给出一组不完备的推理规则，使推理者只能得到范围有限的结论，如，Konolige的演绎信念系统。注：这种方法的缺点是初始信念集的选择往往是人为的、不自然的，若用来描述计算机或机器人这类人工制造的信念推理系统也许还可以，而要描述人的信念活动就很困难了。,.,第四章人工智能逻辑,第二节模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信b)摆脱逻辑全知的方法途经3)心理学方式把某些心理学概念引进逻辑中，如，“意识到”。人必须先意识到某个事物或概念的存在，然后才能产生对那个事物或概念的信念，从而把信念和意识区分开来。由此，意识逻辑就成了信念逻辑之上的一层元逻辑，它控制着信念逻辑的推理。,.,第四章人工智能逻辑,第二节模态逻辑及其应用七、时序逻辑1、基本时序逻辑a)在模态逻辑中，将模型M=(W,R,V)中的R解释为时间先后关系，且R是一个自反且传递的关系。b)“”解释为永远算子，“”解释为将会算子。可有AA(若永远,则现在.)注：1)时序逻辑不具备性质：pp，即，S5不能作为时序逻辑。这是因为，时序逻辑不具备欧几里德性质：若R且R,则可推出R。原因是时间关系不可逆转。如：死亡是出生的将来世界,上学也是出生的将来世界,则上学是死亡的将来世界，显然，这是谬误。,.,第四章人工智能逻辑,第二节模态逻辑及其应用七、时序逻辑1、基本时序逻辑注：2)时序逻辑在分析和证明一个计算机程序的语义时非常有用，如，部分正确性、完全正确性、两事件间的联系。,.,第四章人工智能逻辑,第二节模态逻辑及其应用七、时序逻辑2、扩充时序逻辑a)引入新的时序算子：“下个状态”算子(表示当前状态的下一个状态)和“直到”算子(pq表示q总有一天要成立，并且在q成立之前，p一直成立)。b)引入新的时序算子：A(对从当前状态出发的所有路径)、E(存在从当前状态出发的某条路径)、F(在指定路径上的将来某个状态)、G(在指定路径上的将来所有状态)、N(在指定路径上的下一个状态)、U(在指定路径上直到某命题成立为止)、P(表示对某个过去世界)和H(表示对所有的过去世界)。,.,第四章人工智能逻辑,第二节模态逻辑及其应用七、时序逻辑2、扩充时序逻辑注：1)时序逻辑可分为线性时序逻辑和分枝时序逻辑。两种时序逻辑的公式是一样的，关键在于语义有所区别：线性时序逻辑以路径作为命题的论断对象，而分枝时序逻辑以状态作为命题的论断对象，这两种语义的不同表现在下列事实上：在线性时序逻辑中有：pp(p称为有时p)但在分枝时序逻辑中无：pp2)扩充时序逻辑既包含线性时序逻辑，也包含分枝时序逻辑。,.,第四章人工智能逻辑,第二节模态逻辑及其应用七、时序逻辑2、扩充时序逻辑注：3)可有如下公理和规则：(1)AHFAAGPA(2)若A是公理，则GA、HA是公理(3)若A可证，则GA可证(4)若A可证，则HA可证(5)若AB可证，则GAGB可证(6)若AB可证，则HAHB可证,.,第四章人工智能逻辑,第二节模态逻辑及其应用七、时序逻辑2、扩充时序逻辑注：3)可有如下公理和规则：(7)PGAA(若对某个过去时刻来说，将来恒有A成立，则现在A成立)(8)FHAA(若对某个将来时刻来说，过去恒有A成立，则现在A成立)4)XYZ-e是一个线性时序逻辑语言，Clarke的CTL则是一个分枝时序逻辑语言。,.,第四章人工智能逻辑,第二节模态逻辑及其应用八、基于区间的时间推理1、基本思想以时间区间作为表示时间的基本单位。,.,第四章人工智能逻辑,第二节模态逻辑及其应用八、基于区间的时间推理2、基本定义设A,B是时间区间，t(A)和t(B)分别表示A和B的左端，t(A)+和t(B)+分别表示A和B的右端，定义：a)A在B之前(以AA表示),具体特征为t(A)+t(B)；b)A等于B(以A=B或B=A表示),具体特征为t(A)=t(B)且t(A)+=t(B)+；c)A遇上B(以AmB或BmiA表示),具体特征为t(A)+=t(B)；d)A交叉B(以AoB或BoiA表示),具体特征为t(A)t(B)t(A)+t(B)+；,.,第四章人工智能逻辑,第二节模态逻辑及其应用八、基于区间的时间推理2、基本定义设A,B是时间区间，t(A)和t(B)分别表示A和B的左端，t(A)+和t(B)+分别表示A和B的右端，定义：e)A在B之中(以AdB或BdiA表示),具体特征为t(B)t(A)t(A)+=t(B)+；f)A开始B(以AbB或BbiA表示),具体特征为t(A)=t(B)t(A)+t(B)+；g)A结束B(以AeB或BeiA表示),具体特征为t(B)t(A)v(F)p,v(p)=succ(v(p)p,q,v(pq)=max(v(p),v(q)v(pq)=v(pq)v(pq)=v(pq)v(pq)=v(pq)v(qp),.,第四章人工智能逻辑,第四节多值逻辑与模糊逻辑三、三值逻辑4、Post的三值逻辑注：这里，排中律、矛盾律、恒等律和零幂律(pp,而是p=p)无一成立,DeMorgan定律只成立了一半。其原因是这些定律基本上均是以真假的正负两极为基础的，现在从两极转为三极，它们就失去了存在的基础。这里对两极对立的概念进一步模糊了，主要表现在非运算“”上，该运算不是以U为中心的对称，而是真假之间的定向循环运动，它使三个真值的作用和地位向平等的方向迈进了一步。,.,第四章人工智能逻辑,第四节多值逻辑与模糊逻辑四、多值逻辑模糊化1、将三值逻辑推广到任意的n值逻辑(n3)，甚至任意的无穷多值逻辑或不可数多值逻辑。构成模糊命题逻辑系统2、引进模糊度量和模糊谓词从模糊命题逻辑过渡到模糊谓词逻辑3、使模糊变量和模糊谓词取值真正模糊化,.,第四章人工智能逻辑,第四节多值逻辑与模糊逻辑五、模糊逻辑模糊：不精确Zadah-FuzzySet六、算子模糊逻辑把程度词看成作用于谓词符号的算子，把这种算子加入到模糊逻辑中，构成算子模糊逻辑。具体地，程度词表示成一个数值，如：0.9(乌鸦都是黑的)。一般形如P,表示命题P在程度上是可信的,.,第四章人工智能逻辑,第四节多值逻辑与模糊逻辑七、模糊逻辑及其推广应用1、模糊数学模糊图论、模糊微分方程2、用模糊度代替可信度(专家系统)3、模糊数据库4、模糊模式识别5、模糊推理6、模糊规划与模糊决策7、模糊聚类分析8、模糊控制(家电),.,第四章人工智能逻辑,第五节归纳逻辑一、归纳与演绎正如分析和综合一样，归纳与演绎必然相互关联，要注意二者的相互联系和相互补充。,.,第四章人工智能逻辑,第五节归纳逻辑二、经典归纳方法1、归纳归纳是科学方法的基础，它能使人们对个别事物的认识上升为对一般事物和客观规律的认识。2、枚举归纳法枚举局限：对客观事物和现象的简单罗列会导致草率的归纳和错误的结论。,.,第四章人工智能逻辑,第五节归纳逻辑二、经典归纳方法3、例证表和例证比较法(Baccon)注重将归纳和分析方法相结合。例证表主要有三种：a)存在表记录“当现象x出现时存在另一种现象y”(xRy)。b)缺乏表记录“当现象x出现时另一种现象y不存在”(xRy)。c)比较表记录“当现象x由于条件不同而发生变化时，现象y也随之发生变化”，意在找出x和y两种现象变化之间的依赖关系。,.,第四章人工智能逻辑,第五节归纳逻辑二、经典归纳方法4、Mill五法Mill提出通过分析事件发生的条件来确定因果关系,有五种方法。A)契合法(也称求同法)识别必要条件。给定两个互不相交的事件集合A和B，寻找这样的条件C，它在A中每一个事件发生前成立，但不一定在B中所有事件发生前成立。这样的条件C被定义为A中事件发生的必要条件。,.,第四章人工智能逻辑,第五节归纳逻辑二、经典归纳方法4、Mill五法A)契合法(也称求同法)注：1)找必要条件时往往要通过分析多个可能的条件，并排除不合适的候选者后才能得到。2)必要条件往往不是很简单地就能识别，有时需要对具体条件加以抽象，且这种抽象不宜过分，以能说明问题为准则。3)必要条件可能不止一个，是一复合条件组合。,.,第四章人工智能逻辑,第五节归纳逻辑二、经典归纳方法4、Mill五法B)差异法识别某个特定事件发生的原因。给定一个事件e和一个事件集合A，e发生前的条件有许多和A中所有事件发生前的条件一样。寻找这样的条件C，它在e发生前成立，但不在A中任何事件发生前成立。C被定义为特定事件e发生的一个条件。,.,第四章人工智能逻辑,第五节归纳逻辑二、经典归纳方法4、Mill五法B)差异法注：1)由于差异法是对特定事件发生原因的判定，所找到的原因很难说是充分条件或必要条件，笼统地说，说它是充分或必要条件均可，因为正是该特定事件且仅有该特定事件满足此条件。但实际上，它只是相对于集合eA是充要的，出了这个集合，它可以即不是必要的，也不是充分的。,.,第四章人工智能逻辑,第五节归纳逻辑二、经典归纳方法4、Mill五法B)差异法注：2)差异法要求e和A中事件之间除了一个条件不一样外，其它条件均一样。这个不一样的条件有时不易确定，有时还不唯一。若不唯一，则最好先构造一个和e同类的事件集合E，然后用契合法查找其中哪些条件是必要的。,.,第四章人工智能逻辑,第五节归纳逻辑二、经典归纳方法4、Mill五法C)契合求差法(求同求异并用法或同异法)识别某类事件发生的特殊原因。给定两个事件集合A和B，寻找这