【教学课件】第四章人工智能逻辑.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)模糊逻辑 用于描述不确定和不精确的概念。注：模糊逻辑是直接建立在自然语言上的逻辑系统，与其它逻辑系统相比，考虑了更多的自然语言的成分。Fuzzy logic=computing with words d)动作逻辑,第四章 人工智能逻辑,第一节 引言四、一阶逻辑的扩充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=AB AB=(AB)(BA),定义,定义,定义,第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)b.公理模式 A1 AA AA A2(AB)(AB)(公理K)A3 全体重言式 A4 A(当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)A T2 A(AB)T3 ABBA T4(AB)(CA)(CB)T5 AA(公理T)T6(AB)(AB)(公理K),第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 b.推理规则 R1(代入规则)：若p是A中变量，A为合式公式，且能用上述公理系统证明(写作|A)，B为任一合式公式，用B代入A中的p后使A成为A，则也有|A。R2(分离规则)：由|A B及|A，有|B成立。R3(必然规则)：从|A可得|A,第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 b.推理规则 注：1)在T系统中规定,为基本逻辑算子，其它逻辑算子可用这三个算子定义：A=A AB=AB AB=(A B)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为真，同样可证|=w A.,第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 c.语义解释 注：1)R称为连续的(序列的)，当且仅当对U中的每个w，存在U中的，使wR 2)R称为自反的，当且仅当对U中的每个w,有wRw成立 3)R是自反的，则R一定是连续的(序列的),第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 d.重要性质(1)AA(2)A(B A)(A(BA)(3)A(AB)(A(AB)注：性质(2)和(3)表明，若A必然成立，则任何命题均严格推出(严格蕴含)A；若A必然假，则A能严格蕴含任何命题B，这就是所谓的严格蕴含悖论，与实质蕴含悖论相对应。,第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统3、S4系统 对于T系统，增加公理模式：A A(公理4)，就成为S4系统。S4的语义解释仍使用改进的Kripke语义结构解释，并要求可能世界之间的可到达关系R是传递的，即满足传递性。这是因为：若R是传递的，则A A(公理4)成立。证明：设当前世界为，A表示凡满足R的均使A为真，若 使R成立，则由传递性知R成立，这表明A成立。,第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统3、S4系统 注：1)称R是传递的，当且仅当对U中任意的,从R和R可推出R 2)这里当然要求R是连续(序列)和自反的 3)S4系统具有如下性质：(1)AA(2)AA(3)AA(4)AA(5)AA,第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统4、S5系统 对于T系统，增加公理模式：A A(公理5)，就成为S5系统。S4的语义解释仍使用改进的Kripke语义结构解释，并要求可能世界之间的可到达关系R是欧几里德和自反的。这是因为：若R是欧几里德且自反的，则AA(公理5)成立。,第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统4、S5系统 注：1)称R是欧几里德的，当且仅当对U中任意的,，由R和R可推出R 2)当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)P P(3)AA,第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统5、一阶模态谓词演算系统 a.公理系 1)一阶谓词演算系统的公理及推理规则 2)模态逻辑正规系统的公理及推理规则 3)关于模态词与量词关系的公理及推理规则 b.语义结构 仍使用Kripke语义解释结构：，其中D是个体域，且约定为各可能世界所公用的个体域，I为一解释集合Iw|w U,第四章 人工智能逻辑,第二节 模态逻辑及其应用三、基本模态逻辑系统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(不排除)。ZAKA 1)公理 ZAKA KAZA(并非不能排除A不成立，即可排除A不成立，即知道A)KAZA(知道A，则会不排除A成立)KAKKA ZA ZZA ZA KZA ZAZKA,第四章 人工智能逻辑,第二节 模态逻辑及其应用五、知道逻辑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)公理 AZA Z(AB)ZAZB ZZAZA 2)推理规则 由|AB推出|ZAZB 由|A推出|KA,第四章 人工智能逻辑,第二节 模态逻辑及其应用五、知道逻辑1、一般知道逻辑 g)KS4系统 注：KS4接近上帝知道逻辑，但不能作为真正的上帝知道逻辑，这是因为，由公理AZA可得 A ZA，表示即使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=,1i n-1,其中对每个i,存在一个j,使得Ri=Rj。|=A当且仅当A在中为真。,第四章 人工智能逻辑,第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 c)群体的最小知识闭包Lm()(是命题集)1)Lm()2)若ALm()，则ALm()3)若A，B Lm()，则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：KiAKiKi A(负内省公理)(每个人均知道他不知道什么)注:若将Ki比作,J3可作为公理T,J4可作为公理S4,J5可作为公理S5,从而解释为知道是有意义的。,第四章 人工智能逻辑,第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 f)K(m)扩充 2)引进新算子 算子J JAK1AK2A.KmA(J表示人所共知的知识)算子C CAJAJJAJJJA(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.Kmp J7：Cpp J8：CpCJp J9：CpC(pq)Cq J10：(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：KipIp i=1,m(2)规则 Q4：IpI(pq)Iq,第四章 人工智能逻辑,第二节 模态逻辑及其应用六、信念逻辑1、信念含义解释 a)表示尚未被完全证实的知道。注：在这种含义下，只有已经被证实(变为知道)的信念和尚未被证实的信念之分，而不存在可能被否证的信念。b)表示不一定正确的知道。注：在这种含义下，信念既可被证实，也可被否证。,第四章 人工智能逻辑,第二节 模态逻辑及其应用六、信念逻辑1、信念含义解释 c)表示对已有证据积累的一种函数，体现对某个命题的相信程度。注：此时，从数学上说，信念就是一种概率(或其它表示不精确程度的数学量)，它在证据积累过程中可以变化，常用于专家系统的不精确推理。,第四章 人工智能逻辑,第二节 模态逻辑及其应用六、信念逻辑2、模态算子 B(相信)W(可以接受)WA=BA K(知道)Z(不排除)ZA=KA,定义,定义,第四章 人工智能逻辑,第二节 模态逻辑及其应用六、信念逻辑3、凡人信念逻辑 公理：KABA BAWA WAZA BABBA WAWWA BABKA(理智人公理)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,Km m个信念算子：B1,B2,Bm J,C,L,Q JAK1AK2A.KmA CAJAJJAJJJA LAB1AB2A.BmA QALALLALLLA,第四章 人工智能逻辑,第二节 模态逻辑及其应用六、信念逻辑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,R m,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)但在分枝时序逻辑中无：pp 2)扩充时序逻辑既包含线性时序逻辑，也包含分枝时序逻辑。,第四章 人工智能逻辑,第二节 模态逻辑及其应用七、时序逻辑2、扩充时序逻辑 注：3)可有如下公理和规则：(1)AHFA AGPA(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(以A m B或B mi A表示),具体特征为 t(A)+=t(B)；d)A交叉B(以A o B或B oi A表示),具体特征为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之中(以A d B或B di A表示),具体特征为t(B)t(A)t(A)+=t(B)+；f)A开始B(以A b B或B bi A表示),具体特征为t(A)=t(B)t(A)+t(B)+；g)A结束B(以A e B或B ei A表示),具体特征为 t(B)t(A)t(A)+=t(B)；,第四章 人工智能逻辑,第二节 模态逻辑及其应用八、基于区间的时间推理2、基本定义 注：1)时间区间之间的关系，不是可以直接获得，往往需要通过知识(常识)才能提炼出来。2)关系可以组合形成新的关系。为了直观，常常把关系画成有向图的形式，对于时间区间之间未确定的关系可通过逐步建立时间区间网络并在网络上进行推理(传播时间约束关系)获得。,第四章 人工智能逻辑,第二节 模态逻辑及其应用八、基于区间的时间推理3、时间约束