第四章人工智能逻辑第一节引言一、逻辑是重要的形式工具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.推理规则分离规则:AB,AB第四章人工智能逻辑第二节模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)d.语义解释1)Leibnitz的“可能世界”语义解释(1)可能世界:除了现实世界,还有许多可能世界,一命题的真或假取决于在哪个可能世界中对它进行考察。(2),模态算子解释A就是在所有可能世界中A真A就是存在可能世界使A在其中为真第四章人工智能逻辑第二节模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)d.语义解释2)改进的Kripke语义结构解释M=U,R,I,其中U为一非空集合,称为宇宙,其成员称为可能世界,可能世界用w1,w2,w,w’等表示;R是U上的一个二元关系,称为可能世界间的可到达关系(注意:R未必为偏序关系);I为U{P1,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为真)kwkwkwkw'第四章人工智能逻辑第二节模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK)d.语义解释2)改进的Kripke语义结构解释|=A当且仅当存在w’,wRw’,且|=A(若在w的某些可到达世界中A真,则在可能世界w中A为真)注:一般使用改进的Kripke结构作为模态逻辑的语义解释结构。kwkw'第四章人工智能逻辑第二节模态逻辑及其应用三、基本模态逻辑系统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=U,R,I,并要求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