第二章人工智能逻辑描述逻辑ppt课件.ppt

1、2022-3-27史忠植 高级人工智能1第二章 人工智能逻辑2.1 逻辑-重要的形式工具 2.2 非单调逻辑 2.3 默认逻辑 2.4 限定逻辑 2.5 自认知逻辑 2.6 真值维护系统2.7 情景演算的逻辑基础 2.8 动态描述逻辑描 述 逻 辑 Description Logics2022-3-27史忠植 高级人工智能3主要内容 什么是描述逻辑？什么是描述逻辑？ 为什么用描述逻辑？为什么用描述逻辑？ 描述逻辑的研究进展描述逻辑的研究进展 描述逻辑的体系结构描述逻辑的体系结构 描述逻辑的构造算子描述逻辑的构造算子 描述逻辑的推理问题描述逻辑的推理问题 我们的工作我们的工作2022-3-27史

2、忠植 高级人工智能41 什么是描述逻辑(DL)？一种基于对象的知识表示的形式化，一种基于对象的知识表示的形式化，也叫概念表示语言或术语逻辑。也叫概念表示语言或术语逻辑。建立在概念和关系(Role)之上 概念解释为对象的集合关系解释为对象之间的二元关系源于语义网络和KL-ONE是一阶逻辑FOL的一个可判定的子集具有合适定义的语义(基于逻辑)2022-3-27史忠植 高级人工智能5特点特点是以往表示工具的逻辑重构和统一形式化 框架系统 (Frame-based systems) 语义网络 (Semantic Networks) 面向对象表示 (OO representation) 语义数据模型 (

3、Semantic data models) 类型系统 (Type systems) 特征逻辑 (Feature Logics) 具有很强的表达能力 是可判定的，总能保证推理算法终止2022-3-27史忠植 高级人工智能6描述逻辑的应用描述逻辑的应用 概念建模 查询优化和视图维护 自然语言语义 智能信息集成 信息存取和智能接口 工程的形式化规范 术语学和本体论 规划 2022-3-27史忠植 高级人工智能72 2 为什么用描述逻辑？为什么用描述逻辑？若直接使用一阶逻辑，而不附加任何约束，则： 知识的结构将被破坏，这样就不能用来驱动推理 对获得可判定性和有效的推理问题来说，其表达能力太高，（也许是

4、太抽象了） 对兴趣表达，但仍然可判定的理论，其推理能力太低。DLDL的重要特征是：的重要特征是： 很强的表达能力； 可判定性，它能保证推理算法总能停止，并返回正确的结果。 2022-3-27史忠植 高级人工智能8在众多知识表示的形式化方法中，描述逻辑在十多年来受到人们的特别关注，主要原因在于以下三点 : 它们有清晰的模型-理论机制; 它们很适合于通过概念分类学来表示应用领域； 它们提供了很用的推理服务。 它们可以被认为是从基于框架的表示形式化向着精确的语义特征方向发展。此外，描述逻辑将分类学中表示和推理（专业推理）与在分类学中项的事实或实例的表示和推理（断言推理）区别开来。 2022-3-27

5、史忠植 高级人工智能93 描述逻辑的研究进展描述逻辑的研究进展 描述逻辑的基础研究描述逻辑的基础研究研究描述逻辑的构造算子、表示和推理的基本问题，如可满足性、包含检测、一致性、可判定性等。一般都在最基本的ALC的基础上在扩展一些构造算子，如数量约束、逆关系、特征函数、关系的复合等。TBox和Abox上的推理问题、包含检测算法等。Schmidt-Schaub 和 Smolka首先建立了基于描述逻辑ALC的Tableau算法，该算法能在多项式时间内判断描述逻辑ALC概念的可满足性问题。2022-3-27史忠植 高级人工智能10 描述逻辑的扩展研究描述逻辑的扩展研究A.Artale和E.Franco

6、ni (1998)提出了一个知识表示系统，用时间约束的方法将状态、动作和规划的表示统一起来。为了能让描述逻辑处理模态词，F.Baader将模态操作引入描述逻辑，证明了该描述逻辑公式的可满足性问题是可判定的。 Wolter等对具有模态算子的描述逻辑进行了深入系统的调查分析，并证明在恒定的领域假设下多种认知和时序描述逻辑是可判定的。 另外如时序扩展(Artale, Wolter)、模糊扩展(Straccia)等。2022-3-27史忠植 高级人工智能11 描述逻辑的应用研究描述逻辑的应用研究描述逻辑在许多领域中被作为知识表示的工具，如信息系统（Catarci,1993）数据库（Borgida,19

7、95; Bergamaschi 1992; Sheth, 1993）软件工程(Devambu, 1991)网络智能访问（Levy， 1996； Blanco，1994）规划（Seida, 1992）等 Horrocks对表达能力较强的描述逻辑进行了研究，并建立了一些逻辑框架和系统，如FaCT，SHIQ等。他和Dieter Fensel等人将描述逻辑、语义网和DAML结合起来，提出了DAML+OIL，其中以描述逻辑作为核心的表示和推理基础。并在XML及其RDF上面进行了扩展，用描述逻辑来研究语义网络和本体论。2022-3-27史忠植 高级人工智能124 描述逻辑的体系结构描述逻辑的体系结构一个描

8、述逻辑系统包含四个基本组成部分：1）表示概念和关系（Role）的构造集2）Tbox关于概念术语的断言3）Abox关于个体的断言4）Tbox和Abox上的推理机制。 2022-3-27史忠植 高级人工智能13 概念概念 解释为一个领域的子集 例子：所有在校学习的人员的集合构成“学生”概念又如：孩子，已婚的，哺乳动物等概念x | Student(x) ，x | Married(x) 关系关系(Roles) 属性(二元谓词，关系)例子：朋友，爱人， | Friend(x,y) ， | Loves(x,y) 1 1）DLDL的基本元素的基本元素概念和关系概念和关系2022-3-27史忠植 高级人工智能

9、14知识库TBox(模式)Man Human MaleHappy-father Human Has-child.Female Abox(数据)John: Happy-father : Has-child推理系统接口2022-3-27史忠植 高级人工智能152 2）TBoxTBox语言语言是描述领域结构的公理的集合定义定义: 引入概念的名称 A C, A CFather Man has-child.HumanHuman Animal Biped包含包含：声明包含关系的公理C D ( C D C D ，D C) has-degree.Masters has-degree.Bachelors一个解释

10、I满足： C D iff CI = DIC D iff CI DI一个解释I满足TBox T iff 它满足T中的每个公理(IT)2022-3-27史忠植 高级人工智能16 概念概念 表示实体(一元谓词，类)例子：学生，已婚的x | Student(x) ，x | Married(x) Bird Animal, Man Human 关系关系(Roles) 属性(二元谓词，关系)例子：朋友，爱人 | Friend(x,y) ， | Loves(x,y) TBox实例实例2022-3-27史忠植 高级人工智能17 概念断言概念断言 表示一个对象是否属于某个概念a:C例如：Tom是个学生，表示为To

11、m : Student或者 Student(Tom)John : Man has-child.Female 关系断言关系断言 表示两个对象是否满足一定的关系:R例如：John有个孩子叫Mary : has-child3 3）ABoxABox语言（断言部分）语言（断言部分）是描述具体情形的公理的集合是描述具体情形的公理的集合2022-3-27史忠植 高级人工智能18一个解释I满足： a : C iff aI CI :R iff RI一个解释I满足ABox A iff 它满足A中的每个公理记为： I A一个解释I满足知识库 = iff 它满足T和A 记为： I 2022-3-27史忠植 高级人工智

12、能194 4）语法和语义）语法和语义构造算子构造算子语法语法语义语义例子例子原子概念AAI IHuman原子关系RRI I Ihas-child对对概念概念C,D和关系和关系(role)R合取C DCI DIHuman Male析取C DCI DIDoctor Lawyer非 CI C Male存在量词 R.Cx| y. RIy CI has-child.Male全称量词 R.Cx| y. RI y CI has-child.Doctor2022-3-27史忠植 高级人工智能20一般地，描述逻辑依据提供的构造算子，在简单的概念和关系上构造出复杂的概念和关系。通常DL至少包含以下算子： 合取(

13、)，吸取( )，非( ) 量词约束：存在量词( )，全称量词()最基本的DL称之为ALC例如，ALC中概念Happy-father定义为：Man has-child.Male has-child.Female has-child.(Doctor Lawyer)5 DL DL中的构造算子中的构造算子2022-3-27史忠植 高级人工智能21构造算子构造算子语法语法语义语义例子例子数量约束n R . Cx| | y| RI ,y CI | n3 has-child .Male n R . Cx| | y| RI ,y CI | n 3 has-child .Male逆R -| RI has-chi

14、ld-传递闭包R*(RI )*has-child*DLDL中的其它算子中的其它算子topTIMale MaleBottomMan Man另外，有两个类似于FOL中的全集(true)和空集(false)的算子2022-3-27史忠植 高级人工智能22在在DLDL中添加算子中添加算子一般地，在描述逻辑中添加不同的算子，则得到不同表达能力的描述逻辑，其复杂性问题也不尽相同。例如，在ALC的基础上添加逆( - )算子，则构成ALCI若再加上数量约束算子(n , n )，则构成ALCIQ。若在描述逻辑中添加时序算子，则构成为时序描述逻辑(Temporal Description Logic)，例如，可以

15、添加：Until算子 U： C U DSince算子 S： C S D还可以加入其它算子，如模态算子 ， ， 等。2022-3-27史忠植 高级人工智能236 描述逻辑中的推理1) 一致性（协调性consistency）2) 可满足性(satisfiability)3) 包含检测（subsumption）4) 实例检测 (instance checking)5) Tableaux算法6）可判定性7）计算复杂性2022-3-27史忠植 高级人工智能241)1)一致性检测一致性检测( (ConsistencyConsistency) )知识库知识库是协调的吗？是协调的吗？即检测是否有的模型 (解释

16、) I ？ C关于关于Tbox T是协调的吗？是协调的吗？即检测是否有T的模型 I 使得 C ？2022-3-27史忠植 高级人工智能252) 2) 概念可满足性概念可满足性( (Satisfiablity) ) 对一个概念C，如果存在一个解释I使得CI是非空的，则称概念C是可满足的，否则是不可满足的。 检验一个概念的可满足性，实际上就是看是否有解释使得这个概念成立。例如：概念Male Female，即需要检测是否有性别既是男的又是女的这样的人。若确实是没有这种两性人，则我们断言，这个概念是不可满足的。又如概念： student worker，它是可满足的。即代表那些在职学生的集合。定理：定理

17、：概念C是可满足的，当且仅当C不包含于。 2022-3-27史忠植 高级人工智能26在知识库中检测在知识库中检测：C D？即检测 CI DI 是否在所有的解释中成立？3) 3) 概念包含概念包含( (Subsumption) )例如：例如：bird animalcomputer equipment在在Tbox中检测中检测：C D？即检测 CI DI 是否在Tbox T的所有解释中成立？2022-3-27史忠植 高级人工智能27C D iff C D是不可满足的。C T D iff C D关于T是不可满足的。C 关于T是一致的 iff C T A A包含与可满足性的关系包含与可满足性的关系 DD

18、CC D 2022-3-27史忠植 高级人工智能284 4）实例检测）实例检测(Instance checking)(Instance checking)概念的实例：概念的实例：Student (John)，或者表示为 John:Student关系的实例：关系的实例：Father(John, Mary)实例检索：实例检索：检索属于某个概念的所有实例的集合2022-3-27史忠植 高级人工智能295 5）可满足性检测算法）可满足性检测算法TableauxTableaux算法算法1) 规则规则: :S x:C1, x:C2S，若x:C1 C2在S中，且x:C1和x:C2不在S中同时出现。2) 规则

19、规则: :S x:D S，若x:C1 C2在S中，x:C1和x:C2都不在S中，且D= C1或者D= C2。3) 规则规则: :S xP1y,xPky, y:C S，若x:R.C在S中，R= P1 Pk，没有z使得xRz在S中成立，且z:C在S中，y为一个新变量。4) 规则规则: :S y:C S，若x:R.C在S中，xRy在S中成立，且y:C不在S中。 2022-3-27史忠植 高级人工智能30例子：检测概念的可满足性：(has-child.Male) (has-child.Male)，其检测过程为：(has-child.Male) (has-child.Male)(x)(has-child

20、.Male)(x)规则(has-child.Male)(x)规则has-child (x, y)规则Male (y)规则Male (y)规则矛盾所以这个概念是不可满足的。2022-3-27史忠植 高级人工智能316 6）可判定性）可判定性描述逻辑中的可满足性问题是可判定的。描述逻辑中的可满足性问题是可判定的。其它推理问题基本上可以归结为可满足性问题。其它推理问题基本上可以归结为可满足性问题。7 7）计算复杂性）计算复杂性描述逻辑中的推理问题其计算复杂性一般是描述逻辑中的推理问题其计算复杂性一般是多项式时间的。但通常由于构造的不同，其复杂多项式时间的。但通常由于构造的不同，其复杂性也有一定的差异

21、。性也有一定的差异。2022-3-27史忠植 高级人工智能32我们的工作我们的工作带缺省的描述逻辑带缺省的描述逻辑定义定义 一个缺省规则是形如 这样的表达式， 其中C、D、E为概念名，x是一个变元。C(x)称为前提条件，D(x)称为检验条件(缺省)，E(x)称为缺省的结论。定义定义1.2 一个知识库是一个三元组，其中T为Tbox，A为Abox，D为缺省规则集。)()(: )(xExDxC)()(),(: )(xFlyxOstrichxPenguinxBird2022-3-27史忠植 高级人工智能33面向主体的动态描述逻辑面向主体的动态描述逻辑 描述逻辑最开始只是用来表示静态知识的。为了考虑在时

22、间上的变化，或者在一定动作下的变化，以及保持其语言的相对简单性，很自然地我们需要通过相应的模态算子来扩展它，以保留其命题模态状态。提出面向主体的动态描述逻辑，用来描述主体中的动态知识以及推理。描述逻辑动态逻辑主体主体面向主体的动态描述逻辑2022-3-27史忠植 高级人工智能34描述逻辑与语义Web有何区别与联系？思思 考考描述逻辑与Prolog有何区别与联系？描述逻辑可以在哪些方面进行扩展与完善？2022-3-27史忠植 高级人工智能35参考文献参考文献http:/dl.kr.org/http:/www.cs.man.ac.uk/horrocks/Slides/index.htmlhttp:/www.cs.man.ac.uk/franconi/dl/course/史忠植史忠植 董明楷董明楷 蒋运承蒋运承 张海俊张海俊. 语义语义Web 的逻辑基础的逻辑基础. 中国科学中国科学 E 辑辑 信息科学信息科学 2004, 34(10): 1123-1138 精品课件精品课件！精品课件精品课件！谢谢！