2009-8-20 史忠植 高级人工智能 1
高级人工智能第二章 人工智能逻辑史忠植中国科学院计算技术 研 究所
2009-8-20 史忠植 高级人工智能 2
第二章 人工智能逻辑
2.1 逻辑 -----重要的形式工具
2.2 非单调逻辑
2.3 默认逻辑
2.4 限定逻辑
2.5 自认知逻辑
2.6 真值维护系统
2.7 情景演算的逻辑基础
2.8 动态描述逻辑描 述 逻 辑
Description Logics
2009-8-20 史忠植 高级人工智能 4
主要内容
◆ 什么是描述逻辑？
◆ 为什么用描述逻辑？
◆ 描述逻辑的研究进展
◆ 描述逻辑的体系结构
◆ 描述逻辑的构造算子
◆ 描述逻辑的推理问题
◆ 我们的工作
2009-8-20 史忠植 高级人工智能 5
1 什么是描述逻辑 (DL)？
一种基于对象的知识表示的形式化，
也叫概念表示语言或术语逻辑。
建立在概念和关系 (Role)之上
－ 概念解释为对象的集合
－ 关系解释为对象之间的二元关系源于语义网络和 KL-ONE
是一阶逻辑 FOL的一个可判定的子集具有合适定义的语义 (基于逻辑 )
2009-8-20 史忠植 高级人工智能 6
特点
◆ 是以往表示工具的逻辑重构和统一形式化
－ 框架系统 (Frame-based systems)
－ 语义网络 (Semantic Networks)
－ 面向对象表示 (OO representation)
－ 语义数据模型 (Semantic data models)
－ 类型系统 (Type systems)
－ 特征逻辑 (Feature Logics)
◆ 具有很强的表达能力
◆ 是可判定的,总能保证推理算法终止
2009-8-20 史忠植 高级人工智能 7
描述逻辑的应用
◆ 概念建模
◆ 查询优化和视图维护
◆ 自然语言语义
◆ 智能信息集成
◆ 信息存取和智能接口
◆ 工程的形式化规范
◆ 术语学和本体论
◆ 规划
◆ …
2009-8-20 史忠植 高级人工智能 8
2 为什么用描述逻辑？
若直接使用一阶逻辑，而不附加任何约束，则：
◆ 知识的结构将被破坏，这样就不能用来驱动推理
◆ 对获得可判定性和有效的推理问题来说，其表达能力太高，（也许是太抽象了）
◆ 对兴趣表达，但仍然可判定的理论，其推理能力太低。
DL的重要特征是：
◆ 很强的表达能力；
◆ 可判定性，它能保证推理算法总能停止，并返回正确的结果。
2009-8-20 史忠植 高级人工智能 9
在众多知识表示的形式化方法中，描述逻辑在十多年来受到人们的特别关注，主要原因在于以下三点,
◆ 它们有清晰的模型 -理论机制 ;
◆ 它们很适合于通过概念分类学来表示应用领域；
◆ 它们提供了很用的推理服务。
它们可以被认为是从基于框架的表示形式化向着精确的语义特征方向发展。此外，描述逻辑将分类学中表示和推理（专业推理）与在分类学中项的事实或实例的表示和推理（断言推理）区别开来。
2009-8-20 史忠植 高级人工智能 10
3 描述逻辑的研究进展
◆ 描述逻辑的基础研究研究描述逻辑的构造算子、表示和推理的基本问题，
如可满足性、包含检测、一致性、可判定性等。
一般都在最基本的 ALC的基础上在扩展一些构造算子，
如数量约束、逆关系、特征函数、关系的复合等。
TBox和 Abox上的推理问题、包含检测算法等。
Schmidt-Schaub 和 Smolka首先建立了基于描述逻辑
ALC的 Tableau算法，该算法能在多项式时间内判断描述逻辑 ALC概念的可满足性问题。
2009-8-20 史忠植 高级人工智能 11
◆ 描述逻辑的扩展研究
A.Artale和 E.Franconi (1998)提出了一个知识表示系统，
用时间约束的方法将状态、动作和规划的表示统一起来。
为了能让描述逻辑处理模态词,F.Baader将模态操作引入描述逻辑，证明了该描述逻辑公式的可满足性问题是可判定的。
Wolter等对具有模态算子的描述逻辑进行了深入系统的调查分析，并证明在恒定的领域假设下多种认知和时序描述逻辑是可判定的。
另外如时序扩展 (Artale,Wolter)、模糊扩展 (Straccia)等。
2009-8-20 史忠植 高级人工智能 12
◆ 描述逻辑的应用研究描述逻辑在许多领域中被作为知识表示的工具，如信息系统（ 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上面进行了扩展，
用描述逻辑来研究语义网络和本体论。
2009-8-20 史忠植 高级人工智能 13
4 描述逻辑的体系结构一个描述逻辑系统包含四个基本组成部分：
1） 表示概念和关系 （ Role） 的构造集
2） Tbox—— 关于概念术语 的断言
3） Abox—— 关于个体 的断言
4） Tbox和 Abox上的推理机制 。
2009-8-20 史忠植 高级人工智能 14
◆ 概念 —— 解释为一个领域的子集例子：所有在校学习的人员的集合构成“学生”概念又如：孩子，已婚的，哺乳动物等概念
{x | Student(x) },{x | Married(x) }
◆ 关系 (Roles) —— 属性 (二元谓词，关系 )
例子：朋友，爱人，
{<x,y> | Friend(x,y) },{<x,y> | Loves(x,y) }
1） DL的基本元素 —— 概念和关系
2009-8-20 史忠植 高级人工智能 15
知识库
TBox(模式 )
Man? Human? Male
Happy-father? Human Has-child.Female? …
Abox(数据 )
John,Happy-father
<John,Mary>,Has-child
推理系统接口
2009-8-20 史忠植 高级人工智能 16
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中的每个公理 (I?T)
2009-8-20 史忠植 高级人工智能 17
◆ 概念 —— 表示实体 (一元谓词，类 )
例子：学生，已婚的
{x | Student(x) },{x | Married(x) }
Bird? Animal,Man? Human
◆ 关系 (Roles) —— 属性 (二元谓词，关系 )
例子：朋友，爱人
{<x,y> | Friend(x,y) },{<x,y> | Loves(x,y) }
TBox实例
2009-8-20 史忠植 高级人工智能 18
◆ 概念断言 —— 表示一个对象是否属于某个概念
a:C
例如,Tom是个学生，表示为
Tom,Student 或者 Student(Tom)
John,Man has-child.Female
◆ 关系断言 —— 表示两个对象是否满足一定的关系
<a,b>:R
例如,John有个孩子叫 Mary
<John,Mary>,has-child
3） ABox语言（断言部分）
是描述具体情形的公理的集合
2009-8-20 史忠植 高级人工智能 19
一个解释 I满足,a,C iff aI ∈ CI
<a,b>:R iff <aI,bI > ∈ RI
一个解释 I满足 ABox A iff 它满足 A中的每个公理记为,I? A
一个解释 I满足知识库?=< T,A > iff 它满足 T和
A
记为,I
2009-8-20 史忠植 高级人工智能 20
4）语法和语义构造算子 语法 语义 例子原子概念 A AI? △ I Human
原子关系 R RI?△ I? △ I has-child
对概念 C,D和关系 (role)R
合取 C? D CI∩ DI Human? Male
析取 C? D CI? DI Doctor?Lawyer
非?C △ I \C?Male
存在量词?R.C {x|? y.<x,y>∈RI∧y ∈ CI}?has-child.Male
全称量词?R.C {x|? y.<x,y>∈RI?y ∈ CI}?has-child.Doctor
2009-8-20 史忠植 高级人工智能 21
一般地，描述逻辑依据提供的构造算子，在简单的概念和关系上构造出复杂的概念和关系。
通常 DL至少包含以下算子：
◆ 合取 (? )，吸取 (? )，非 (?)
◆ 量词约束：存在量词 (? )，全称量词 (?)
最基本的 DL称之为 ALC
例如,ALC中概念 Happy-father定义为：
Man has-child.Male
has-child.Female
has-child.(Doctor? Lawyer)
5 DL中的构造算子
2009-8-20 史忠植 高级人工智能 22
构造算子 语法 语义 例子数量约束
≥n R,C {x| | {y|<x,y>∈ RI,y ∈ CI} | ≥n} ≥3 has-child,Male
≤ n R,C {x| | {y|<x,y>∈ RI,y ∈ CI} | ≤ n} ≤ 3 has-child,Male
逆 R - {<y,x>|<x,y>∈RI } has-child-
传递闭包 R* (RI )* has-child*
DL中的其它算子
top T △ I MaleMale
Bottom ManMan
另外，有两个类似于 FOL中的全集 (true)和空集 (false)的算子
2009-8-20 史忠植 高级人工智能 23
在 DL中添加算子一般地，在描述逻辑中添加不同的算子，则得到不同表达能力的描述逻辑，其复杂性问题也不尽相同。
例如，在 ALC的基础上添加逆 ( - )算子，则构成 ALCI
若再加上数量约束算子 (≥n,≤ n )，则构成 ALCIQ。
若在描述逻辑中添加时序算子，则构成为时序描述逻辑 (Temporal Description Logic)，例如，可以添加：
Until算子 U,C U D
Since算子 S,C S D
还可以加入其它算子，如模态算子 □,◇,? 等。
2009-8-20 史忠植 高级人工智能 24
6 描述逻辑中的推理
1) 一致性 （ 协调性 consistency）
2) 可满足性 (satisfiability)
3) 包含检测 （ subsumption）
4) 实例检测 (instance checking)
5) Tableaux算法
6） 可判定性
7） 计算复杂性
2009-8-20 史忠植 高级人工智能 25
1)一致性检测 (Consistency)
◆ 知识库 <T,A>是协调的吗？
即检测是否有 <T,A>的模型 (解释 ) I？
◆ C关于 Tbox T是协调的吗？
即检测是否有 T的模型 I 使得 C ≠?？
2009-8-20 史忠植 高级人工智能 26
2) 概念可满足性 (Satisfiablity)
对一个概念 C，如果存在一个解释 I使得 CI是非空的，则称概念 C是可满足的，否则是不可满足的。
有解释使得这个概念成立。例如：概念 Male?
Female，即需要检测是否有性别既是男的又是女的这样的人。若确实是没有这种两性人，则我们断言，
这个概念是不可满足的。
student? worker，它是可满足的。
即代表那些在职学生的集合。
定理,概念 C是可满足的，当且仅当 C不包含于?。
2009-8-20 史忠植 高级人工智能 27
◆ 在知识库中检测,
C? D？
即检测 CI? DI 是否在所有的解释中成立？
3) 概念包含 (Subsumption)
例如：
bird? animal computer? equipment
◆ 在 Tbox中检测,
C? D？
即检测 CI? DI 是否在 Tbox T的所有解释中成立？
2009-8-20 史忠植 高级人工智能 28
C? D iff CD是不可满足的。
C?T D iff CD关于 T是可满足的。
C 关于 T是一致的 iff C?T AA
包含与可满足性的关系
D
D
C CD ＝?
2009-8-20 史忠植 高级人工智能 29
4）实例检测 (Instance checking)
概念的实例：
Student (John)，或者表示为 John:Student
关系的实例：
Father(John,Mary)
实例检索,检索属于某个概念的所有实例的集合
2009-8-20 史忠植 高级人工智能 30
5）可满足性检测算法 —— Tableaux算法
1)?规则,
S→? { x:C1,x:C2}?S,若 x:C1? C2在 S中,且 x:C1和 x:C2不在 S
中同时出现 。
2)?规则,
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
中 。
2009-8-20 史忠植 高级人工智能 31
例子：检测概念的可满足性：
(?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)?规则
矛盾所以这个概念是不可满足的。
2009-8-20 史忠植 高级人工智能 32
6）可判定性描述逻辑中的可满足性问题是可判定的。
其它推理问题基本上可以归结为可满足性问题。
7）计算复杂性描述逻辑中的推理问题其计算复杂性一般是多项式时间的。但通常由于构造的不同，其复杂性也有一定的差异。
2009-8-20 史忠植 高级人工智能 33
我们的工作
◆ 带缺省的描述逻辑定义 一个缺省规则是形如 这样的表达式，
其中 C,D,E为概念名,x是一个变元。 C(x)称为前提条件,D(x)称为检验条件 (缺省 ),E(x)称为缺省的结论。
定义 1.2 一个知识库是一个三元组 <T,A,D>，其中 T为 Tbox，
A为 Abox,D为缺省规则集。
)(
)(:)(
xE
xDxC
)(
)(),(:)(
xFl y
xO s t r i c hxPe n g u i nxB i r d
2009-8-20 史忠植 高级人工智能 34
◆ 面向主体的动态描述逻辑描述逻辑最开始只是用来表示静态知识的。
为了考虑在时间上的变化，或者在一定动作下的变化，以及保持其语言的相对简单性，很自然地我们需要通过相应的模态算子来扩展它，以保留其命题模态状态。
提出面向主体的动态描述逻辑，用来描述主体中的动态知识以及推理。
描述逻辑动态逻辑
＋ 主体面向主体的动态描述逻辑
2009-8-20 史忠植 高级人工智能 35
描述逻辑与语义网络有何区别与联系？
思 考描述逻辑与 Prolog有何区别与联系？
描述逻辑可以在哪些方面进行扩展与完善？
您对数理逻辑、人工智能、知识表示与推理是如何看待的？
2009-8-20 史忠植 高级人工智能 36
参考文献
http://dl.kr.org/
http://www.cs.man.ac.uk/~horrocks/Slides/index.html
http://www.cs.man.ac.uk/~franconi/dl/course/
谢谢！
高级人工智能第二章 人工智能逻辑史忠植中国科学院计算技术 研 究所
2009-8-20 史忠植 高级人工智能 2
第二章 人工智能逻辑
2.1 逻辑 -----重要的形式工具
2.2 非单调逻辑
2.3 默认逻辑
2.4 限定逻辑
2.5 自认知逻辑
2.6 真值维护系统
2.7 情景演算的逻辑基础
2.8 动态描述逻辑描 述 逻 辑
Description Logics
2009-8-20 史忠植 高级人工智能 4
主要内容
◆ 什么是描述逻辑？
◆ 为什么用描述逻辑？
◆ 描述逻辑的研究进展
◆ 描述逻辑的体系结构
◆ 描述逻辑的构造算子
◆ 描述逻辑的推理问题
◆ 我们的工作
2009-8-20 史忠植 高级人工智能 5
1 什么是描述逻辑 (DL)？
一种基于对象的知识表示的形式化，
也叫概念表示语言或术语逻辑。
建立在概念和关系 (Role)之上
－ 概念解释为对象的集合
－ 关系解释为对象之间的二元关系源于语义网络和 KL-ONE
是一阶逻辑 FOL的一个可判定的子集具有合适定义的语义 (基于逻辑 )
2009-8-20 史忠植 高级人工智能 6
特点
◆ 是以往表示工具的逻辑重构和统一形式化
－ 框架系统 (Frame-based systems)
－ 语义网络 (Semantic Networks)
－ 面向对象表示 (OO representation)
－ 语义数据模型 (Semantic data models)
－ 类型系统 (Type systems)
－ 特征逻辑 (Feature Logics)
◆ 具有很强的表达能力
◆ 是可判定的,总能保证推理算法终止
2009-8-20 史忠植 高级人工智能 7
描述逻辑的应用
◆ 概念建模
◆ 查询优化和视图维护
◆ 自然语言语义
◆ 智能信息集成
◆ 信息存取和智能接口
◆ 工程的形式化规范
◆ 术语学和本体论
◆ 规划
◆ …
2009-8-20 史忠植 高级人工智能 8
2 为什么用描述逻辑？
若直接使用一阶逻辑，而不附加任何约束，则：
◆ 知识的结构将被破坏，这样就不能用来驱动推理
◆ 对获得可判定性和有效的推理问题来说，其表达能力太高，（也许是太抽象了）
◆ 对兴趣表达，但仍然可判定的理论，其推理能力太低。
DL的重要特征是：
◆ 很强的表达能力；
◆ 可判定性，它能保证推理算法总能停止，并返回正确的结果。
2009-8-20 史忠植 高级人工智能 9
在众多知识表示的形式化方法中，描述逻辑在十多年来受到人们的特别关注，主要原因在于以下三点,
◆ 它们有清晰的模型 -理论机制 ;
◆ 它们很适合于通过概念分类学来表示应用领域；
◆ 它们提供了很用的推理服务。
它们可以被认为是从基于框架的表示形式化向着精确的语义特征方向发展。此外，描述逻辑将分类学中表示和推理（专业推理）与在分类学中项的事实或实例的表示和推理（断言推理）区别开来。
2009-8-20 史忠植 高级人工智能 10
3 描述逻辑的研究进展
◆ 描述逻辑的基础研究研究描述逻辑的构造算子、表示和推理的基本问题，
如可满足性、包含检测、一致性、可判定性等。
一般都在最基本的 ALC的基础上在扩展一些构造算子，
如数量约束、逆关系、特征函数、关系的复合等。
TBox和 Abox上的推理问题、包含检测算法等。
Schmidt-Schaub 和 Smolka首先建立了基于描述逻辑
ALC的 Tableau算法，该算法能在多项式时间内判断描述逻辑 ALC概念的可满足性问题。
2009-8-20 史忠植 高级人工智能 11
◆ 描述逻辑的扩展研究
A.Artale和 E.Franconi (1998)提出了一个知识表示系统，
用时间约束的方法将状态、动作和规划的表示统一起来。
为了能让描述逻辑处理模态词,F.Baader将模态操作引入描述逻辑，证明了该描述逻辑公式的可满足性问题是可判定的。
Wolter等对具有模态算子的描述逻辑进行了深入系统的调查分析，并证明在恒定的领域假设下多种认知和时序描述逻辑是可判定的。
另外如时序扩展 (Artale,Wolter)、模糊扩展 (Straccia)等。
2009-8-20 史忠植 高级人工智能 12
◆ 描述逻辑的应用研究描述逻辑在许多领域中被作为知识表示的工具，如信息系统（ 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上面进行了扩展，
用描述逻辑来研究语义网络和本体论。
2009-8-20 史忠植 高级人工智能 13
4 描述逻辑的体系结构一个描述逻辑系统包含四个基本组成部分：
1） 表示概念和关系 （ Role） 的构造集
2） Tbox—— 关于概念术语 的断言
3） Abox—— 关于个体 的断言
4） Tbox和 Abox上的推理机制 。
2009-8-20 史忠植 高级人工智能 14
◆ 概念 —— 解释为一个领域的子集例子：所有在校学习的人员的集合构成“学生”概念又如：孩子，已婚的，哺乳动物等概念
{x | Student(x) },{x | Married(x) }
◆ 关系 (Roles) —— 属性 (二元谓词，关系 )
例子：朋友，爱人，
{<x,y> | Friend(x,y) },{<x,y> | Loves(x,y) }
1） DL的基本元素 —— 概念和关系
2009-8-20 史忠植 高级人工智能 15
知识库
TBox(模式 )
Man? Human? Male
Happy-father? Human Has-child.Female? …
Abox(数据 )
John,Happy-father
<John,Mary>,Has-child
推理系统接口
2009-8-20 史忠植 高级人工智能 16
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中的每个公理 (I?T)
2009-8-20 史忠植 高级人工智能 17
◆ 概念 —— 表示实体 (一元谓词，类 )
例子：学生，已婚的
{x | Student(x) },{x | Married(x) }
Bird? Animal,Man? Human
◆ 关系 (Roles) —— 属性 (二元谓词，关系 )
例子：朋友，爱人
{<x,y> | Friend(x,y) },{<x,y> | Loves(x,y) }
TBox实例
2009-8-20 史忠植 高级人工智能 18
◆ 概念断言 —— 表示一个对象是否属于某个概念
a:C
例如,Tom是个学生，表示为
Tom,Student 或者 Student(Tom)
John,Man has-child.Female
◆ 关系断言 —— 表示两个对象是否满足一定的关系
<a,b>:R
例如,John有个孩子叫 Mary
<John,Mary>,has-child
3） ABox语言（断言部分）
是描述具体情形的公理的集合
2009-8-20 史忠植 高级人工智能 19
一个解释 I满足,a,C iff aI ∈ CI
<a,b>:R iff <aI,bI > ∈ RI
一个解释 I满足 ABox A iff 它满足 A中的每个公理记为,I? A
一个解释 I满足知识库?=< T,A > iff 它满足 T和
A
记为,I
2009-8-20 史忠植 高级人工智能 20
4）语法和语义构造算子 语法 语义 例子原子概念 A AI? △ I Human
原子关系 R RI?△ I? △ I has-child
对概念 C,D和关系 (role)R
合取 C? D CI∩ DI Human? Male
析取 C? D CI? DI Doctor?Lawyer
非?C △ I \C?Male
存在量词?R.C {x|? y.<x,y>∈RI∧y ∈ CI}?has-child.Male
全称量词?R.C {x|? y.<x,y>∈RI?y ∈ CI}?has-child.Doctor
2009-8-20 史忠植 高级人工智能 21
一般地，描述逻辑依据提供的构造算子，在简单的概念和关系上构造出复杂的概念和关系。
通常 DL至少包含以下算子：
◆ 合取 (? )，吸取 (? )，非 (?)
◆ 量词约束：存在量词 (? )，全称量词 (?)
最基本的 DL称之为 ALC
例如,ALC中概念 Happy-father定义为：
Man has-child.Male
has-child.Female
has-child.(Doctor? Lawyer)
5 DL中的构造算子
2009-8-20 史忠植 高级人工智能 22
构造算子 语法 语义 例子数量约束
≥n R,C {x| | {y|<x,y>∈ RI,y ∈ CI} | ≥n} ≥3 has-child,Male
≤ n R,C {x| | {y|<x,y>∈ RI,y ∈ CI} | ≤ n} ≤ 3 has-child,Male
逆 R - {<y,x>|<x,y>∈RI } has-child-
传递闭包 R* (RI )* has-child*
DL中的其它算子
top T △ I MaleMale
Bottom ManMan
另外，有两个类似于 FOL中的全集 (true)和空集 (false)的算子
2009-8-20 史忠植 高级人工智能 23
在 DL中添加算子一般地，在描述逻辑中添加不同的算子，则得到不同表达能力的描述逻辑，其复杂性问题也不尽相同。
例如，在 ALC的基础上添加逆 ( - )算子，则构成 ALCI
若再加上数量约束算子 (≥n,≤ n )，则构成 ALCIQ。
若在描述逻辑中添加时序算子，则构成为时序描述逻辑 (Temporal Description Logic)，例如，可以添加：
Until算子 U,C U D
Since算子 S,C S D
还可以加入其它算子，如模态算子 □,◇,? 等。
2009-8-20 史忠植 高级人工智能 24
6 描述逻辑中的推理
1) 一致性 （ 协调性 consistency）
2) 可满足性 (satisfiability)
3) 包含检测 （ subsumption）
4) 实例检测 (instance checking)
5) Tableaux算法
6） 可判定性
7） 计算复杂性
2009-8-20 史忠植 高级人工智能 25
1)一致性检测 (Consistency)
◆ 知识库 <T,A>是协调的吗？
即检测是否有 <T,A>的模型 (解释 ) I？
◆ C关于 Tbox T是协调的吗？
即检测是否有 T的模型 I 使得 C ≠?？
2009-8-20 史忠植 高级人工智能 26
2) 概念可满足性 (Satisfiablity)
对一个概念 C，如果存在一个解释 I使得 CI是非空的，则称概念 C是可满足的，否则是不可满足的。
有解释使得这个概念成立。例如：概念 Male?
Female，即需要检测是否有性别既是男的又是女的这样的人。若确实是没有这种两性人，则我们断言，
这个概念是不可满足的。
student? worker，它是可满足的。
即代表那些在职学生的集合。
定理,概念 C是可满足的，当且仅当 C不包含于?。
2009-8-20 史忠植 高级人工智能 27
◆ 在知识库中检测,
C? D？
即检测 CI? DI 是否在所有的解释中成立？
3) 概念包含 (Subsumption)
例如：
bird? animal computer? equipment
◆ 在 Tbox中检测,
C? D？
即检测 CI? DI 是否在 Tbox T的所有解释中成立？
2009-8-20 史忠植 高级人工智能 28
C? D iff CD是不可满足的。
C?T D iff CD关于 T是可满足的。
C 关于 T是一致的 iff C?T AA
包含与可满足性的关系
D
D
C CD ＝?
2009-8-20 史忠植 高级人工智能 29
4）实例检测 (Instance checking)
概念的实例：
Student (John)，或者表示为 John:Student
关系的实例：
Father(John,Mary)
实例检索,检索属于某个概念的所有实例的集合
2009-8-20 史忠植 高级人工智能 30
5）可满足性检测算法 —— Tableaux算法
1)?规则,
S→? { x:C1,x:C2}?S,若 x:C1? C2在 S中,且 x:C1和 x:C2不在 S
中同时出现 。
2)?规则,
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
中 。
2009-8-20 史忠植 高级人工智能 31
例子：检测概念的可满足性：
(?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)?规则
矛盾所以这个概念是不可满足的。
2009-8-20 史忠植 高级人工智能 32
6）可判定性描述逻辑中的可满足性问题是可判定的。
其它推理问题基本上可以归结为可满足性问题。
7）计算复杂性描述逻辑中的推理问题其计算复杂性一般是多项式时间的。但通常由于构造的不同，其复杂性也有一定的差异。
2009-8-20 史忠植 高级人工智能 33
我们的工作
◆ 带缺省的描述逻辑定义 一个缺省规则是形如 这样的表达式，
其中 C,D,E为概念名,x是一个变元。 C(x)称为前提条件,D(x)称为检验条件 (缺省 ),E(x)称为缺省的结论。
定义 1.2 一个知识库是一个三元组 <T,A,D>，其中 T为 Tbox，
A为 Abox,D为缺省规则集。
)(
)(:)(
xE
xDxC
)(
)(),(:)(
xFl y
xO s t r i c hxPe n g u i nxB i r d
2009-8-20 史忠植 高级人工智能 34
◆ 面向主体的动态描述逻辑描述逻辑最开始只是用来表示静态知识的。
为了考虑在时间上的变化，或者在一定动作下的变化，以及保持其语言的相对简单性，很自然地我们需要通过相应的模态算子来扩展它，以保留其命题模态状态。
提出面向主体的动态描述逻辑，用来描述主体中的动态知识以及推理。
描述逻辑动态逻辑
＋ 主体面向主体的动态描述逻辑
2009-8-20 史忠植 高级人工智能 35
描述逻辑与语义网络有何区别与联系？
思 考描述逻辑与 Prolog有何区别与联系？
描述逻辑可以在哪些方面进行扩展与完善？
您对数理逻辑、人工智能、知识表示与推理是如何看待的？
2009-8-20 史忠植 高级人工智能 36
参考文献
http://dl.kr.org/
http://www.cs.man.ac.uk/~horrocks/Slides/index.html
http://www.cs.man.ac.uk/~franconi/dl/course/
谢谢！
