人工智能逻辑二部分

第二章人工智能逻辑

第二部分史忠植中国科学院计算技术研究所高级人工智能9/12/20231史忠植高级人工智能描述逻辑

DescriptionLogics9/12/20232史忠植高级人工智能主要内容◆

什么是描述逻辑？◆为什么用描述逻辑？◆描述逻辑的研究进展◆描述逻辑的体系结构◆描述逻辑的构造算子◆描述逻辑的推理问题◆我们的工作9/12/20233史忠植高级人工智能1什么是描述逻辑(DL)？ 一种基于对象的知识表示的形式化，也叫概念表示语言或术语逻辑。建立在概念和关系(Role)之上

－概念解释为对象的集合 －关系解释为对象之间的二元关系源于语义网络和KL-ONE是一阶逻辑FOL的一个可判定的子集具有合适定义的语义(基于逻辑)9/12/20234史忠植高级人工智能特点◆是以往表示工具的逻辑重构和统一形式化 －

框架系统(Frame-basedsystems) －

语义网络(SemanticNetworks) －

面向对象表示(OOrepresentation) －

语义数据模型(Semanticdatamodels) －

类型系统(Typesystems) －

特征逻辑(FeatureLogics)◆

具有很强的表达能力◆是可判定的，总能保证推理算法终止9/12/20235史忠植高级人工智能描述逻辑的应用

◆概念建模◆查询优化和视图维护◆自然语言语义◆智能信息集成◆信息存取和智能接口◆工程的形式化规范◆术语学和本体论◆规划◆…9/12/20236史忠植高级人工智能2为什么用描述逻辑？若直接使用一阶逻辑，而不附加任何约束，则：◆知识的结构将被破坏，这样就不能用来驱动推理◆对获得可判定性和有效的推理问题来说，其表达能力太高，（也许是太抽象了）◆对兴趣表达，但仍然可判定的理论，其推理能力太低。DL的重要特征是：◆很强的表达能力；◆可判定性，它能保证推理算法总能停止，并返回正确的结果。9/12/20237史忠植高级人工智能在众多知识表示的形式化方法中，描述逻辑在十多年来受到人们的特别关注，主要原因在于以下三点:◆它们有清晰的模型-理论机制;◆它们很适合于通过概念分类学来表示应用领域；◆它们提供了很用的推理服务。它们可以被认为是从基于框架的表示形式化向着精确的语义特征方向发展。此外，描述逻辑将分类学中表示和推理（专业推理）与在分类学中项的事实或实例的表示和推理（断言推理）区别开来。9/12/20238史忠植高级人工智能3描述逻辑的研究进展◆描述逻辑的基础研究 研究描述逻辑的构造算子、表示和推理的基本问题，如可满足性、包含检测、一致性、可判定性等。 一般都在最基本的ALC的基础上在扩展一些构造算子，如数量约束、逆关系、特征函数、关系的复合等。 TBox和Abox上的推理问题、包含检测算法等。

Schmidt-Schaub和Smolka首先建立了基于描述逻辑ALC的Tableau算法，该算法能在多项式时间内判断描述逻辑ALC概念的可满足性问题。9/12/20239史忠植高级人工智能◆描述逻辑的扩展研究

A.Artale和E.Franconi(1998)提出了一个知识表示系统，用时间约束的方法将状态、动作和规划的表示统一起来。 为了能让描述逻辑处理模态词，F.Baader将模态操作引入描述逻辑，证明了该描述逻辑公式的可满足性问题是可判定的。

Wolter等对具有模态算子的描述逻辑进行了深入系统的调查分析，并证明在恒定的领域假设下多种认知和时序描述逻辑是可判定的。

另外如时序扩展(Artale,Wolter)、模糊扩展(Straccia)等。9/12/202310史忠植高级人工智能◆描述逻辑的应用研究描述逻辑在许多领域中被作为知识表示的工具，如 信息系统（Catarci,1993） 数据库（Borgida,1995;Bergamaschi1992;Sheth,1993） 软件工程(Devambu,1991) 网络智能访问（Levy，1996；Blanco，1994） 规划（Seida,1992）等 Horrocks对表达能力较强的描述逻辑进行了研究，并建立了一些逻辑框架和系统，如FaCT，SHIQ等。他和DieterFensel等人将描述逻辑、语义网和DAML结合起来，提出了DAML+OIL，其中以描述逻辑作为核心的表示和推理基础。并在XML及其RDF上面进行了扩展，用描述逻辑来研究语义网络和本体论。9/12/202311史忠植高级人工智能4描述逻辑的体系结构一个描述逻辑系统包含四个基本组成部分：1）表示概念和关系（Role）的构造集2）Tbox——关于概念术语的断言3）Abox——关于个体的断言4）Tbox和Abox上的推理机制。

9/12/202312史忠植高级人工智能◆概念——解释为一个领域的子集

例子：所有在校学习的人员的集合构成“学生”概念 又如：孩子，已婚的，哺乳动物等概念{x|Student(x)}，{x|Married(x)}◆

关系(Roles)——属性(二元谓词，关系)例子：朋友，爱人，{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}1）DL的基本元素——概念和关系9/12/202313史忠植高级人工智能知识库TBox(模式)Man≐Human⊓MaleHappy-father≐Human⊓

∃Has-child.Female⊓

…Abox(数据)John:Happy-father<John,Mary>:Has-child推理系统接口9/12/202314史忠植高级人工智能2）TBox语言 是描述领域结构的公理的集合定义:引入概念的名称A≐

C,A

⊑

CFather≐

Man⊓

∃

has-child.HumanHuman⊑

Animal⊓

Biped包含：声明包含关系的公理C

⊑

D

(C≐

D

C

⊑

D，D

⊑

C)∃

has-degree.Masters⊑

∃

has-degree.Bachelors一个解释I满足：C≐

D

iffCI

=DI C⊑

D

iffCI

⊆

DI一个解释I满足TBoxT

iff它满足T中的每个公理(I⊨T)9/12/202315史忠植高级人工智能◆概念——表示实体(一元谓词，类)例子：学生，已婚的{x|Student(x)}，{x|Married(x)} Bird

⊑

Animal,Man⊑Human◆

关系(Roles)——属性(二元谓词，关系)例子：朋友，爱人{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}TBox实例9/12/202316史忠植高级人工智能◆概念断言——表示一个对象是否属于某个概念 a:C例如：Tom是个学生，表示为

Tom

:Student 或者 Student(Tom)

John

:Man⊓

∃

has-child.Female◆

关系断言——表示两个对象是否满足一定的关系 <a,b>:R例如：John有个孩子叫Mary

<John,

Mary>

:has-child3）ABox语言（断言部分） 是描述具体情形的公理的集合9/12/202317史忠植高级人工智能一个解释I满足：a:

C

iffaI

∈

CI<a,b>:R

iff<aI,bI>

∈RI一个解释I满足ABoxA

iff它满足A中的每个公理记为：I⊨A一个解释I满足知识库

=<T,A

>

iff它满足T和A记为：I⊨

9/12/202318史忠植高级人工智能4）语法和语义构造算子语法语义例子原子概念AAI⊆△IHuman原子关系RRI⊆△I

△Ihas-child对概念C,D和关系(role)R合取C⊓DCI∩DIHuman⊓Male析取C⊔DCI⋃

DIDoctor⊔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.Doctor9/12/202319史忠植高级人工智能一般地，描述逻辑依据提供的构造算子，在简单的概念和关系上构造出复杂的概念和关系。通常DL至少包含以下算子： ◆合取(⊓)，吸取(⊔)，非(¬) ◆量词约束：存在量词(∃)，全称量词(∀)最基本的DL称之为ALC例如，ALC中概念Happy-father定义为： Man⊓

∃

has-child.Male

⊓

∃

has-child.Female

⊓

∀has-child.(Doctor⊔

Lawyer)5DL中的构造算子9/12/202320史忠植高级人工智能构造算子语法语义例子数量约束≥nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≥n}≥3

has-child.Male≤nR.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中的其它算子topT△IMale⊔

¬MaleBottom

Man⊓

¬Man另外，有两个类似于FOL中的全集(true)和空集(false)的算子9/12/202321史忠植高级人工智能在DL中添加算子一般地，在描述逻辑中添加不同的算子，则得到不同表达能力的描述逻辑，其复杂性问题也不尽相同。例如，在ALC的基础上添加逆(-)算子，则构成ALCI若再加上数量约束算子(≥n,≤n)，则构成ALCIQ。若在描述逻辑中添加时序算子，则构成为时序描述逻辑(TemporalDescriptionLogic)，例如，可以添加： Until算子U：C

U

D Since算子S：CSD还可以加入其它算子，如模态算子□，

，○等。9/12/202322史忠植高级人工智能6描述逻辑中的推理1)

一致性（协调性consistency）2)可满足性(satisfiability)3)包含检测（subsumption）4)实例检测(instancechecking)5)Tableaux算法6）可判定性7）计算复杂性9/12/202323史忠植高级人工智能1)一致性检测(Consistency)◆知识库<T,A>是协调的吗？ 即检测是否有<T,A>的模型(解释)I？◆C关于TboxT是协调的吗？

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

≠

？9/12/202324史忠植高级人工智能2)概念可满足性(Satisfiablity)

对一个概念C，如果存在一个解释I使得CI是非空的，则称概念C是可满足的，否则是不可满足的。

检验一个概念的可满足性，实际上就是看是否有解释使得这个概念成立。例如：概念Male⊓

Female，即需要检测是否有性别既是男的又是女的这样的人。若确实是没有这种两性人，则我们断言，这个概念是不可满足的。又如概念：student⊓worker，它是可满足的。即代表那些在职学生的集合。定理：概念C是可满足的，当且仅当C不包含于

。

9/12/202325史忠植高级人工智能◆在知识库中检测： C⊑

D？ 即检测CI

⊆

DI是否在所有的解释中成立？3)概念包含(Subsumption)例如： bird⊑animal computer⊑equipment◆在Tbox中检测： C⊑

D？ 即检测CI

⊆

DI是否在TboxT的所有解释中成立？9/12/202326史忠植高级人工智能C⊑

Diff

C⊓

¬D是不可满足的。C⊑T

Diff

C⊓

¬D关于T是不可满足的。C关于T是一致的iffC⊑T

A⊓

¬A包含与可满足性的关系¬DDCC⊓

¬D＝

9/12/202327史忠植高级人工智能4）实例检测(Instancechecking)概念的实例： Student(John)，或者表示为John:Student关系的实例： Father(John,Mary) 实例检索：检索属于某个概念的所有实例的集合9/12/202328史忠植高级人工智能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中。

9/12/202329史忠植高级人工智能例子：检测概念的可满足性：(∀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) ∀规则

矛盾所以这个概念是不可满足的。9/12/202330史忠植高级人工智能6）可判定性描述逻辑中的可满足性问题是可判定的。其它推理问题基本上可以归结为可满足性问题。7）计算复杂性描述逻辑中的推理问题其计算复杂性一般是多项式时间的。但通常由于构造的不同，其复杂性也有一定的差异。9/12/202331史忠植高级人工智能SemanticWebArchitecture9/12/202332史忠植高级人工智能我们的工作◆带缺省的描述逻辑定义

一个缺省规则是形如这样的表达式，其中C、D、E为概念名，x是一个变元。C(x)称为前提条件，D(x)称为检验条件(缺省)，E(x)称为缺省的结论。定义1.2一个知识库是一个三元组<T,A,D>，其中T为Tbox，A为Abox，D为缺省规则集。9/12/202333史忠植高级人工智能◆动态描述逻辑描述逻辑最开始只是用来表示静态知识的。为了考虑在时间上的变化，或者在一定动作下的变化，以及保持其语言的相对简单性，很自然地我们需要通过相应的模态算子来扩展它，以保留其命题模态状态。提出动态描述逻辑，用来描述主体中的动态知识以及推理。描述逻辑动态逻辑＋主体面向主体的动态描述逻辑9/12/202334史忠植高级人工智能以客观世界的形式化建模为研究内容，提出一种统一的形式化框架，同时从静态和动态两个方面来刻画世界的模型。为动态领域的建模提供一种有效的形式化理论工具；将世界中的概念、关系和个体，公理、事实和动作有机地整合在一起，形成统一的关联和运作机制，使动作与公理和事实相互作用，统一表示并进行推理；对概念、公式和动作都给出了统一的、合适的语法和语义；主体与本体的结合

动态描述逻辑DDL9/12/202335史忠植高级人工智能动态描述逻辑DDLDDL：语义环境中对服务过程方面的建模和推理服务改变环境的状态：前提条件和执行结果，Action服务描述：基于WorldModel，e.g.,描述服务的前提和结果的词汇来自World