文档库

最新最全的文档下载
当前位置:文档库 > 描述逻辑ABOX和TBOX

描述逻辑ABOX和TBOX

主要内容
什么是描述逻辑? ◆ 为什么用描述逻辑? ◆ 描述逻辑的研究进展 ◆ 描述逻辑的体系结构 ◆ 描述逻辑的构造算子 ◆ 描述逻辑的推理问题


1 什么是描述逻辑(DL)?
一种基于对象的知识表示的形式化, 也叫概念表示语言或术语逻辑。 建立在概念和关系(Role)之上 -概念解释为对象的集合 -关系解释为对象之间的二元关系 源于语义网络和KL-ONE 是一阶逻辑FOL的一个可判定的子集 具有合适定义的语义(基于逻辑)

特点
◆是以往表示工具的逻辑重构和统一形式化 - 框架系统 (Frame-based systems) - 语义网络 (Semantic Networks) - 面向对象表示 (OO representation) - 语义数据模型 (Semantic data models) - 类型系统 (Type systems) - 特征逻辑 (Feature Logics) ◆ 具有很强的表达能力 ◆ 是可判定的,总能保证推理算法终止

描述逻辑的应用
◆ 概念建模 ◆ 查询优化和视图维护 ◆ 自然语言语义 ◆ 智能信息集成 ◆ 信息存取和智能接口 ◆ 工程的形式化规范 ◆ 术语学和本体论 ◆ 规划 ◆…

2 为什么用描述逻辑?
若直接使用一阶逻辑,而不附加任何约束,则: ◆ 知识的结构将被破坏,这样就不能用来驱动推理 ◆ 对获得可判定性和有效的推理问题来说,其表达 能力太高,(也许是太抽象了) ◆ 对兴趣表达,但仍然可判定的理论,其推理能力 太低。 DL的重要特征是: ◆ 很强的表达能力; ◆ 可判定性,它能保证推理算法总能停止,并返回 正确的结果。

在众多知识表示的形式化方法中,描述逻辑在十多 年来受到人们的特别关注,主要原因在于以下三点 : ◆ 它们有清晰的模型-理论机制; ◆ 它们很适合于通过概念分类学来表示应用领域; ◆ 它们提供了很用的推理服务。 它们可以被认为是从基于框架的表示形式化向着 精确的语义特征方向发展。此外,描述逻辑将分类 学中表示和推理(专业推理)与在分类学中项的事 实或实例的表示和推理(断言推理)区别开来。

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

◆ 描述逻辑的扩展研究
A.Artale和E.Franconi (1998)提出了一个知识表示系统, 用时间约束的方法将状态、动作和规划的表示统一起来。 为了能让描述逻辑处理模

态词,F.Baader将模态操作 引入描述逻辑,证明了该描述逻辑公式的可满足性问题 是可判定的。 Wolter等对具有模态算子的描述逻辑进行了深入系统 的调查分析,并证明在恒定的领域假设下多种认知和时序 描述逻辑是可判定的。 另外如时序扩展(Artale, Wolter)、模糊扩展(Straccia)等。

◆ 描述逻辑的应用研究
描述逻辑在许多领域中被作为知识表示的工具,如 信息系统(Catarci,1993) 数据库(Borgida,1995; Bergamaschi 1992; Sheth, 1993) 软件工程(Devambu, 1991) 网络智能访问(Levy, 1996; Blanco,1994) 规划(Seida, 1992)等 Horrocks对表达能力较强的描述逻辑进行了研究, 并建立了一些逻辑框架和系统,如FaCT,SHIQ等。他 和Dieter Fensel等人将描述逻辑、语义网和DAML结合 起来,提出了DAML+OIL,其中以描述逻辑作为核心的 表示和推理基础。并在XML及其RDF上面进行了扩展, 用描述逻辑来研究语义网络和本体论。

4 描述逻辑的体系结构
一个描述逻辑系统包含四个基本组成部分: 1)表示概念和关系(Role)的构造集 2)Tbox——关于概念术语的断言 3)Abox——关于个体的断言 4)Tbox和Abox上的推理机制。

1)DL的基本元素——概念和关系
◆ 概念 ——解释为一个领域的子集

例子:所有在校学习的人员的集合构成“学生”概念 又如:孩子,已婚的,哺乳动物等概念 {x | Student(x) } ,{x | Married(x) }
◆ 关系(Roles) ——属性(二元谓词,关系)

例子:朋友,爱人, { | Friend(x,y) } ,{ | Loves(x,y) }

知 识 库

TBox(模式)
Man Human Male Happy-father Human Has-child.Female …

Abox(数据)
John: Happy-father : Has-child

推理系统 接口

2)TBox语言
是描述领域结构的公理的集合 定义: 引入概念的名称 A C, A C Father Man has-child.Human Human Animal Biped 包含:声明包含关系的公理 C D ( C D C D ,D C) has-degree.Masters has-degree.Bachelors 一个解释I满足: C D iff CI = DI C D iff CI DI 一个解释I满足TBox T iff 它满足T中的每个公理(IT)

TBox实例
◆ 概念 ——表示实体(一元谓词,类)

例子:学生,已婚的 {x | Student(x) } ,{x | Married(x) } Bird Animal, Man Human
◆ 关系(Roles) ——属性(二元谓词,关系)

例子:朋友,爱人 { | Friend(x,y) } ,{ | Loves(x,y) }

3)ABox语言(断言部分)
是描述具体情形的公理的集合
◆ 概念断言 ——表示一个对象是否属于某个概念

a:C 例如:Tom是个学生,表示为 Tom : Student 或者 Student(Tom) John : Man has-child.Female
◆ 关系断言 ——表示两个对象是否满足一定的关系

:R 例如:John有个孩子叫Mary : has-child

一个解释I满足: a : C iff aI ∈ CI :R iff ∈ RI 一个解释I满足ABox A

iff 它满足A中的每个公理 记为: I A 一个解释I满足知识库 ∑=< T, A > iff 它满足T和A 记为: I ∑

4)语法和语义
构造算子 原子概念 原子关系 语法 A R 语义 A I △I RI △I × △I


例子 Human has-child

对概念C,D和关系(role)R 合取 析取 非 存在量词 全称量词 C D C D C R.C R.C

CI∩ DI CI D I △I \C {x| y.∈ RI∧y ∈ CI} {x| y.∈ RI y ∈ CI}

Human Male Doctor Lawyer Male has-child.Male has-child.Doctor

5 DL中的构造算子
一般地,描述逻辑依据提供的构造算子,在简单的 概念和关系上构造出复杂的概念和关系。 通常DL至少包含以下算子: ◆ 合取( ),吸取( ),非( ) ◆ 量词约束:存在量词( ),全称量词() 最基本的DL称之为ALC 例如,ALC中概念Happy-father定义为: Man has-child.Male has-child.Female has-child.(Doctor Lawyer)

DL中的其它算子
构造算子 语法 ≥n R . C 数量约束 语义 {x| | {y|∈ RI ,y ∈ CI} | ≥n} 例子 ≥3 has-child .Male

≤ n R . C {x| | {y|∈ RI ,y ∈ CI} | ≤ n} ≤ 3 has-child .Male RR* {|∈ RI } (RI )* has-childhas-child*

逆 传递闭包

另外,有两个类似于FOL中的全集(true)和空集(false)的算子
top Bottom T ⊥ △I Male Male Man Man

在DL中添加算子
一般地,在描述逻辑中添加不同的算子,则得到不同 表达能力的描述逻辑,其复杂性问题也不尽相同。 例如,在ALC的基础上添加逆( - )算子,则构成ALCI 若再加上数量约束算子(≥n , ≤ n ),则构成ALCIQ。 若在描述逻辑中添加时序算子,则构成为时序描述 逻辑(Temporal Description Logic),例如,可以添加: Until算子 U: C U D Since算子 S: C S D 还可以加入其它算子,如模态算子□ ,◇ ,○ 等。

6 描述逻辑中的推理
1) 一致性(协调性consistency) 2) 可满足性(satisfiability) 3) 包含检测(subsumption) 4) 实例检测 (instance checking) 5) Tableaux算法 6)可判定性 7)计算复杂性

1)一致性检测(Consistency)
◆ C关于Tbox T是协调的吗?

即检测是否有T的模型 I 使得 C ≠ ?

◆知识库是协调的吗?

即检测是否有的模型 (解释) I ?

2) 概念可满足性(Satisfiablity)
对一个概念C,如果存在一个解释I使得CI是非空 的,则称概念C是可满足的,否则是不可满足的。 检验一个概念的可满足性,实际上就是看是否 有解释使得这个概念成立。例如:概念Male Female,即需要检测是否有性别既是男的又是女的 这样的人。若确实是没有这种两性人,则我们断言, 这个概念是不可满足的。 又如概念: student worker,它是可满足的。 即代表那些在职学生的集合。 定理:概念C是可满足的,当且仅当C不包含于⊥。

3) 概念包含(Subsumption)
◆在知识库中检测:

C D?

即检测 CI DI 是否在所有的解释中成立?
◆在Tbox中检测:

C D? 即检测 CI DI 是否在Tbox T的所有解释中 成立? 例如: bird animal computer equipment

包含与可满足性的关系
C D iff C D是不可满足的。 C T D iff C D关于T是可满足的。 C 关于T是一致的 iff C T A A D
D C

C D =

4)实例检测(Instance checking)
概念的实例:
Student (John),或者表示为 John:Student

关系的实例:
Father(John, Mary)

实例检索:检索属于某个概念的所有实例的集合

5)可满足性检测算法——Tableaux算法
1) 规则: S→ { x:C1, x:C2}S,若x:C1 C2在S中,且x:C1和x:C2不在S 中同时出现。 2) 规则: S→ {x:D}S,若x:C1C2 在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 中。

例子:检测概念的可满足性: (has-child.Male) (has-child.Male), 其检测过程为: ((has-child.Male) (has-child.Male))(x) (has-child.Male)(x) 规则 (has-child.Male)(x) 规则 has-child (x, y) 规则 Male (y) 规则 Male (y) 规则 ⊥ 矛盾 所以这个概念是不可满足的。

6)可判定性
描述逻辑中的可满足性问题是可判定的。 其它推理问题基本上可以归结为可满足性问题。

7)计算复杂性
描述逻辑中的推理问题其计算复杂性一般是 多项式时间的。但通常由于构造的不同,其复杂 性也有一定的差异。

思 考
描述逻辑与语义网络有何区别与联系? 描述逻辑与Prolog有何区别与联系? 描述逻辑可以在哪些方面进行扩展与完善? 您对数理逻辑、人工智能、知识表示与推理 是如何看待的?

参考文献
http://www.wendangku.net/doc/8c0bb4ec998fcc22bcd10d2a.html/ http://www.wendangku.net/doc/8c0bb4ec998fcc22bcd10d2a.html/~horrocks/Slides/index.html http://www.wendangku.net/doc/8c0bb4ec998fcc22bcd10d2a.html/~franconi/dl/course/

谢谢!
内容来自:文档资料库