描述逻辑推理（共3篇）
描述逻辑推理 篇1
描述逻辑在众多领域中被广泛使用, 因此对描述逻辑中概念的匹配推理进行研究也就越加重要。目前描述逻辑被作为知识表示的工具应用在众多领域, 像数据库软件工程、信息系统、规划及网络职能访问中等均有使用。描述逻辑有着清晰的理论机制, 对于这些应用领域有着重要的作用, 同时可以提供众多重要的推理服务, 而描述逻辑中概念的匹配推理是描述逻辑运用中的重要环节。
1 描述逻辑及逻辑推理的概念及应用
描述逻辑是把描述对象通过知识表示的一中形式化, 依据KL-ONE的主要思想, 是一阶谓词逻辑的一个可判定子集。描述逻辑有着极强的表达能力, 同时有着明显的可判断信号, 因此, 在推理验算中总是可以有效终止, 并返回到正确结果。目前网络知识在表达中主要接受并使用的语言工具就是描述逻辑, 主要是由于描述逻辑有以下几点优势:描述逻辑模型-理论语义清晰, 在处理概念分层是有着显著的作用, 同时描述逻辑可以提供有效准确的推理机制共使用。因此在人工智能及计算机科学中被作为重点进行研究, 通过研究者的深入研究, 描述逻辑在服务计算、概念建模、语义web、数据库及软件工程领域取得了巨大的成就。
2 描述逻辑中概念的匹配推理的发展与研究现状
描述逻辑最初是用在静态知识的描述中。这种运用的使用范围较为狭窄, 同时存在着一些缺陷, 对时间及动作表示较差, 为了使表示言语简单, 通常利用相对应模态算子来对其进行扩展。Schild和Schmiedel在对认知逻辑及时序描述逻辑进行构造研究时, 发现可判断性受到表达能力的限制。Laux和Baader进行了优化, 将描述逻辑中的ALC与多态K结合, 将模态算子运用到概念及公式中并进行了验证, 并证明了结果语言的可判定性。Wolter等研究学者深度调查研究模态算子的描述逻辑后, 同时对时序描述逻辑及认知时序逻辑在恒定领域假设条件下进行折中, 并将两种命题动态逻辑PDL及描述逻辑进行结合, 提出了动态描述逻辑。E.Franconi和A.Artale为了使动作和规划能在统一的框架下进行表示和推理, 一种新的知识表示系统, 将规划、动作及状态通过时间约束统一, 同时与描述逻辑进行整合, 使得描述逻辑得到了较大的发展。
描述逻辑推理的核心问题是可满足性问题, 逻辑中的很多问题都可以发展为可满足性问题。Smolka和Schmidt-Schaub为了对可满足性问题进行自动判断, 建立了Tableau算法, 目前已在多种描述逻辑中广泛应用。F.Baader将模态操作引入描述逻辑, 实现了描述逻辑处理模态词的功能。目前描述逻辑的主要工作聚集在多维描述及模态公理的问题上, A.Schmiedel第一个提出整合时间方法;Schild则提出了另外简单的时序扩张办法。
3 描述逻辑系统зLN概念推理验算
描述语言主要有一些符号构成, 如⊥, Τ, Π, ∃R.C, ≥n R, ≤n R.全部的描述逻辑都是可以用递归的方法。这些逻辑推算存在着一定的规则, 通过这些规则, 对概念之间实现等价交换。概念在推算中, 被当做一个, 并且形成了二元关系。
我们知道每一个概念都对应着一棵描述树, 而每一棵描述树也对应着e LN中的一个概念描述。概念描述树实际上就是的一棵语法树, 它代表了概念的语法结构。当两棵描述树之间存在同态映射的时
候, 他们对应的概念之间又会有什么关系呢?其实它们的关系是:如果概念描述树Gc和G。之间存在同态映射ϕ:Vc→v D, 则有CGD⊆CGC成立。反过来也是一样, 即如果C⊆D, 则在GD和GC之间存在同态
映射ϕ:VD→VC。于是有如下定理:
定理1在描述逻辑系统εLN中C⊆D当且仅当下面的条件有一个成立:
1) C三⊥:
2) D三T:
3) 存在一个由GD= (VD, ED, υ0, ℓD) 到Gc= (Vc, Ec, ωc, ) 的同态映射ϕ:VD→VC。
证明:必要性证明 (“⇐”) : (1) 和 (2) 是显然成立的, 下面我们证明 (3) , 即:当存在一个
由GD= (VD, ED, υ0, ℓD) 到GC= (VC, EC, ω0, ℓC) 的同态映射ϕ:VD→VC时, 我们递归的证明于GD的顶点个数❘VD❘:在❘VD❘=1、❘VD❘>1时通过对不同的模型及推理办法进行验证, 证明上述办法的准确性, 最终实现对必要性的证明。
对充分性证明时, (1) 、 (2) 的证明比较容易, 在对 (3) 进行证明时可以采用逆否证法进行研究, 若GD到GC的同态映射不存在, 则说明D不包含C, 因此在对描述树中顶点的个数|V|进行归纳证明时同样可以采用, 即在❘VD❘=1、❘VD❘>1的证明中发现D不包含C。在本次推理中在对C, D之间的包含关系进行计算时, 只要对同态映射是否存在进行论证与计算, 即可得出￡LN中概念之间的包含关系。具体算法如下: (1) 输入任意的зLN概念C、D。 (2) 在一定的规则下将C、D标准化。 (3) 当D三T或者C三⊥, 输出C⊆D, 当D三⊥或者C三T, 则输出D⊆C。否则写出D、D的概念描述树GD和GC。 (4) 在对GD和GC之间是否有同态映射存在的时候, 可以用C、D的包含关系进行论证。在存在GC到GD的映射情况下, 输出D⊆C;在存在GD到GC映射时, 输出C⊆D。除此外认定C、D不存在包含关系。
4 结束语
描述逻辑的概念匹配推理在不断的发展与研究中, 随着现代计算机技术的发展以及各应用领域的需要, 对描述逻辑进行不断的研究与深化有助于推动改系统的发展, 目前描述逻辑的概念匹配推理已经得到了较大的发展, 然而随着新的科学技术的发展及应用中新的问题的出现, 现有的描述逻辑的概念匹配推理已经不适应需要, 因此, 要对描述逻辑进行不断的深入研究, 从而促进相关技术的发展与推广。
摘要：描述逻辑除了知识表示外, 在众多领域均有使用。描述逻辑有着强大的表达能力, 是知识形式化表现的重要方式。今年来描述逻辑受到了人们的极大关注, 关于描述逻辑中概念的匹配推理的研究逐渐增多及深入。该文对描述逻辑中概念的匹配推理研究现状进行分析, 探讨现存的问题并提出一些解决办法。
关键词：描述逻辑,概念的匹配推理,研究现状,问题
参考文献
[1]王驹, 蒋运承, 申宇铭.描述逻辑系统VL循环术语集的可满足性及推理机制[J].中国科学F辑, 2009, 23 (2) :205-211.
[2]张维, 曹发生, 余泉.描述逻辑系统eLN中的概念包含推理算法研究[J].毕节学院学报, 2010, 8 (28) :9-13.
[3]Franz Baader.The instance problem and the most specific concept in the description logic ELw.r.t.ter-minological cycles with descrip tive semantics[C].In Proceedings of the 26th Annual German Conference on Artificial Intelligence, volume 282 1 of Lecture Notes inArtificial Intelligence, Hamburg, Germany:Springer-Verlag, 2003:64-78.
描述逻辑推理 篇2
语义Web解决的问题是机哭对Web上知识的`理解,使计算机能够理解web上的知识,便于计算机处理,而在语义web的层次结构中,Ontology屡占重要的地位.本文在描述逻辑的基础之上,引入模态逻辑和时态逻辑,用于表达语义web上的模态语义,从而实现丰富web上的语义信息.
作 者：贾延明 高峥 作者单位：贾延明(河南商丘科技职业学院)
高峥(河南新乡学院现代教育技术中心)
基于描述逻辑的动作理论研究 篇3
作为用于知识表示的形式化工具,描述逻辑已经被广泛应用于众多领域中,如知识表示、信息系统、软件工程、 自然语言处理等。在下一代Web技术的语义Web中,描述逻辑更是扮演着关键角色,成为W3C推荐的Web本体语言,是OWL的逻辑基础。描述逻辑的主要特点在于具有较强的描述能力,同时保证 了相关推 理问题的 可判定性,有较强的推理算法作支撑。
动作的刻画和推理是知识表示和推理中重要的研究课题,是当前研究热点语义Web服务和智能主体的理论基础。目前,比较成熟的动作理论是基于一阶谓词逻辑的动作理论。以情景演算[1]、流演算[2]和STRIPS系统[3]为代表,它们的共同特点是采用一阶谓词逻辑或高阶谓词逻辑中的公式来表达世界状态、动作的前提条件和动作执行后产生的影响,具有很强的表达能力,但是相关推理问题却是不可判定的,限制了动作的推理能力。而基于命题动态逻辑的动作理论[4]采用命题公式刻画世界状态和动作, 虽然具有 可判定的 推理,但是描述 能力却大 大降低。 Baader等[5]提出了一种基于描述逻辑的形式系统,使用描述逻辑中的TBox和ABox来描述领域知识和动作,但该形式系统中的复杂 动作仅由 原子动作 的有限序 列构成。 Wolter[6]将描述逻辑与命题动态逻辑结合,提出了命题动态逻辑PDLC。Y.Gu等[7]以描述逻辑为参照,改进了情景演算,并在此基础 上研究了 动作的相 关问题。史忠植等[8,9,10,11]提出了一种动态描述逻辑,将描述逻辑与动态逻辑相结合,给出了动态描述逻辑的Tableau算法。常亮等[12]提出了一种基于动态描述逻辑DDL的动作理论,系统研究了动态描述逻辑的动作表示和推理问题,在此基础上解决了由于动作执行导致的状态更新问题。
在上述研究的基础 上,本文系统 探讨基于 描述逻辑ALCO@的动作理论。以描述逻辑中的TBox作为刻画的知识背景,给出原子动作的语法和语义。以描述逻辑中的TBox和ABox为知识库,给出执行动作后所引起的ABox的更新算法。
1ALCO@语法和语义
描述逻辑ALCO@的基本符号有:1大写字母C,D等表示的概念;2由概念组成的集合NC;3小写字母a,b等表示个体;4由个体组成的集合NI;5用大写字母R1,R2表示描述逻辑中的二 元关系;6由二元关 系组成的 集合NR;7用希腊字母φ,ψ表示断言;8概念构造符 、 、 、 和。
定义1:ALCO@语法。令NC和NR是可数的不相交的原子概念集和原子关系集,ALCO@的概念描述递归定义如下:
(1)任意原子A∈NC是ALCO@的概念。
(2)令C和D是ALCO@的概念,R是ALCO@的原子关系,即R∈NR,则表达式C(补)、C∪D(并)、C∩D(交)、R.C(存在约束)和R.C(全称约束)是ALCO@概念。
以下引入描述逻辑中常用的两个特殊记号:⊥指代空集的底概念, 指代论域全集的顶概念。
定义2:ALCO@语义。ALCO@是一个以二元对I = (ΔI,·I),其中ΔI代表论域的非空集合,·I是解释函数, 它将每个A∈Nc映射为ΔI的子集,每个R∈NR映射为 ΔI(ΔI的子集,分别称为原 子概念A和原子关 系R的解释,记作AI和RI。
定义3:表达式C≡D称为概念等价。如果C是一个概念名,该表达式也称为概念定义式,其中C称为被定义的概念。
定义4:形如C(a),C(a),R(a,b)和R(a,b)的表达式称为断言,其中C∈NC,a,b∈NI,R∈NR。
描述逻辑中的ABox是由概念断言和关系断言组成的知识库,TBox是由概念 和概念定 义式组成 的集合, TBox为ABox的表达提供一个规范。
定义5:标准否定 范式。ALCO@的概念是 标准否定 范式,当且仅当概念表达式中所有的否定符号()只出现在原子概念的前 面。运用以下 规则可以 将任意ALCO@概念转化为相应的标准否定范式:
2DL-A的语法与语义
DL-A中的基本符号有:1用拉丁语 α、β等表示原子动作名;2动作构造符“u”、“,”、“*”和“;”分别表示选择、顺序迭代和并发。
定义6:原子动作 α=(pre,con-result,final),其中:α 表示原子动作名;pre= {φ1,φ2,...φn}是前提条件集,表示动作执行的前提条件;con-result= {φ1/ψ1,φ2/ψ2,...φn/ ψn}是条件结果集,表示当满足“/”前面的条件时,动作执行就会产生“/”之后的结果;final= {φ1,φ2,...φn}是直接结果集,表示由于动作的执行所产生的直接结果。
例:一个顾客jack在网上书店订购了一本关于Java的书。如果要取消这个订单,那么取消订单动作的前提条件是订单是存在的,另外如果顾客Jack已经过款了,那么在取消订单的同时还要所付款退还给顾客Jack。
该描述中涉及到的概念名称为:Customer,Book,角色名称为:hasOrder,hasPaid,取消订单 这个动作 可描述为cancelOrder;
则该例子所描述的知识库可表示为:
其中:
说明:1关系断言hasOrder(jack,java)表示顾客Jack订购了一本关于Java的书;2关系断言hasPaid(jack,java)表示顾客Jack为名为Java这本书付过款了;3关系断言hasRefund(jack,java)表示将买Java书的钱退 还给Jack;4动作描述cancelOrder(jack,java)表示Jack要取消Java这本书的订单。
定义7:三元组M=(Δ,W,I)是DL-A的模型,其中 Δ是所有个体对象组成的非空集合,即论域;W是所有状态的集合;I是对W中的每个状态w赋予一个解释函数I (w),对个体常元概念和关系进行解释。
对于DL-A中的某个状态w∈ W,该状态的解释函数I(w)=(Δ,·I(w)),由论域 Δ 和解释函数·I(w)构成,在该状态下,概念、关系和动作的语义解释如下:
上述定义中采用了恒定解释域假设,模型中的所有状态都采用同一个解释域。而且个体名都作为刚性命名符来处理,即个体名的解释不随状态的变化而变化。
在状态w下,概念断言是用来表示个体与概念之 间的关系,其语义解释如下:
在状态w下,关系断言是用来表示两个个体之间 所具有的某种关系或者是某个个体所具有的某种属性,表示的是二元关系,其语义解释如下:
对于原子动作α的语义解释如下:
αI= (pre,con-result,final)I= {(w,w′)|存在个体a,b∈NI使得:
(1)对于任意的断言φ∈pre,都有
(2)对于任意的简单概念名C∈NC都有:
(3)对于任意的简单关系名R∈NR,都有:
则RI(w′)= (RI(w)∪R+)R-};其中w,w′是W中的两个状态。
定义8:γ=α,β表示顺序动作,α,β是原子动作。
说明:只有顺序动作中的原子动作α和β依次全部完成,顺序动作γ才能完成。动作α执行完之后的状态是动作β执行时的状态。
定义9:动作 γ=α∪β表示选择动作 ,其中 α和β都是原子动作。
说明:选择动作中,只执行满足条件的一个原子动作, 即要么执行α要么执行β。
定义10:动作γ=α*表示循环动作,其中 α是原子动作。
说明:循环动作表示动作α执行零次或多次。
循环动作的语义:
定义11:动作γ=(α1;α2;...;αn)表示并发动作,其中 α1,α2,...,αn都是原子动作。
说明:并发动作γ表示动作中的原子动作同时执行, 当且仅当所有的原子动作全部同时执行时,该动作γ才能够完成,只要其中一个原子动作无法完成,则并发动作就无法完成。
3基于DL-A的行动推理
根据知识库构成,可将推理问题分为以下几类:关于状态的推理、关于动作的推理以及由动作执行所导致的状态更新问题。
关于动作的推理主要分为两部分:判断原子动作定义式的一致性;动作的可执行性问题、投影问题以及规划问题。
定义12:称原子动作α=(pre,con-result,final)相对于TBox T和ABox A是一致,当且仅当存在某个模型M=(Δ,W,I),使得,其中w,w′是W中的两个状态。
动作的可执行性问题是指判断动作 α在某个状态下是否可以执行。例如 α=(pre,con-result,final)是一个原子动作,A是一个ABox。如果preA,那么该原子动作时可以执行。对于复杂动作的可执行性问题,可以将复杂动作分解成若干个原子动作,然后判断原子动作是否可执行,据此推出该复杂动作是否可执行。
动作投影问题是指判断某个状态下执行动作α后能否使某个断言成立。例如 α=(pre,con-result,final)是一个原子动作,A是一个ABox,D是一个关系断言或者概念断言。假设动作α是可以执行的,且执行结果为集合M。如果D∈M,则执行原子动作α后可以使断言D成立。
动作规划问题是指可否找到一个动作序列,使得从初始状态下出发可依次执行该序列中的动作,从而达到目标状态(或者是给定一个动作序列、初始状态和目标状态,验证该动作序列能否从初始状态达到目标状态)。
文献[6]在动态描述逻辑的基础上给出了上述推理问题的形式化定义,并且将转换成动态描述逻辑中公式的可满足性问题来解决。
由动作执行所引起的ABox更新问题,是本文需要解决的问题之一。基于描述逻辑ALCO@的知识库ABox对具体的状态进行了描述;当动作执行导致状态改变时,需要相应地对ABox进行更新处理,使得更新后的ABox能够描述更新后的状态。ABox更新算法的过程如下:
定义13:Obj(M)表示集合M中个体名的集合,其中M是断言集合。
算法1:根据Tableau算法将原知识库S进行扩展
设原知识库 为ABox A,TBox T,扩展的知 识库为A′。
(1) A′= A。
(2)从A′中取出一个概念断言D(a),如果该概念断言是TBox T中所定义的概念,则用概念定义符号“≡”右边的概念替换D,所得到的新的断言为C(a),执行A= A ∪{C(a)},A′= A′∪{C(a)}{D(a)}。
(3)从A′中取出一个概念断言D(a),如果该概念断言是非标准否定范式,则将该概念断言转化为标准否定范式,记为C(a),则执行A′= A′∪{C(a)}{D(a)},A∪{C (a)}。
(4)从A′中取出一个概念断言D(a)。1如果D是形如C E的概念,则执行A = A∪{C(a),E(a)},A′= A′∪{C(a),E(a)}{D(a)};2如果D是形如R.C的概念,则匹配A′中所有满足R(a.x)的关系断言,则执行A′ = A′∪{C(x)},A = A∪{C(x)}。
运行算法1后,可以在不影响原知识库的表达能力的基础上对原知识库进行最大限度扩展。将经过最大限度扩展的知识库称为完全知识库。
算法2:知识库S的更新算法如下:
将更新集U中的个体 集合表示 为Obj(U),知识库ABox A中个体集合表示为Obj(A);
(1)如果更新集U和知识库A都是完全的,则执行以下步骤;反之,将更新集 和知识库A按照算法1进行扩展,然后再执行以下步骤。
(2)从Obj(U)中取出一个元素a,如果aObj(A), 并且在更新集U中没有形如R(a,b)( R(a,b))或者R (b,a)( R(b,a))的关系断言,其中b∈Obj(A),则将更新集U中的所有关于个体a的断言C(a)加入到A中,即执行A=A∪{C(a)}。
(4)依次取出Obj(U)中的剩余元素,并且按照步骤 (3)执行。
算法3:动作执行引起的状态更新算法如下:
有ABox A和原子动作α=(pre,con-result,final)
令result=Φ
(1)首先将A和原子动作α中的所有断言按照算法1进行扩展,然后执行以下步骤:
(2)如果pre∈A,则表明原子动作 α是可以执行的,继续执行以下步骤;如果表明该原子动作是不可以执行的,算法终止;
(3)从con-result中取出一个元素φ/ψ,如果φ∈A,则result=result∪{ψ},con-result= con-result{φ/ψ};
(4)重复执行步骤(2),直到con-result集合中没有元素可取;
(5)final=final∪ result;
(6)将final集合作为更新集,将A作为原知识集,执行算法2;
(7)最后得到的知识库A就是执行动作 α之后的新的状态集合。
算法4:考察原子动作执行情况。在ABox执行任意一个动作α后,实际上发生的动作总可以由若干个原子动作组成的某个序列构成。因此,对应于任意一个动作 α, 可以通过多次应用算法3来构造出在ABox上执行动作α 后所得到新的ABox。
4结语
基于描述逻辑的动作理论系统DL-A具有如下特点:1使用描述逻辑ALCO@语言对世界的知识、状态、动作的前提条件、条件结果以及直接结果等进行了描述,其表达能力要比命题逻辑的动作理论更强;2它提供了具有可判定性的推理服务。后续研究重点探讨算法的可终止性、可靠性以及完备性。
摘要：情景演算对于动作理论的描述具有很强的表达能力,但是其推理算法具有不可判定性。在描述逻辑ALCO@的基础上,构建基于描述逻辑的动作理论系统DL-A。在该系统中,利用描述逻辑语言描述原子动作的表达式以及语义解释,并在此基础上利用各种构造符构造出顺序、选择、并发、迭代等复杂动作,同时赋予这些复杂动作的语法和语义。动作的实现会引起周围世界状态的改变,描述动作执行所引起的状态更新算法。基于描述逻辑ALCO@的动作理论不仅具有很强的表达能力,而且其算法具有可判定性,能够提供多种推理服务,可以应用于Web语义下的动作描述和推理。
关键词：描述逻辑,动作理论,状态更新,断言,动作推理,知识表示
参考文献
[1]REITER R.Knowledge in action:logical foundations for describing and implementing dynamical sysems[M].Cambridge,MA:MIT Press,2001.
[2]THIESCHER M.From situation calculus to fluent calculus:state update axioms as a solution to the inferential frame problem[J].Artificial intelligence,1999,111(1/2):277-299.
[3]FIKES R.STRIPS:a retospective[J].Artificial intelligence,1993,59(1-2):227-232.
[4]GIACOMO G,LENZERINI M.PDL-based framework for reasoning about actions[C].Proceeding of the 4th Congress of the Italian Association for Artifical Intelligence.LNAI 992.Berlin:Springer,1995:103-114.
[5]BAADER F,LUTZ C,MILICIC M,et al.Integrating description logics and action formalisms:first results[C].Proceeding of the12th National Conference on Artifical Intelligence.Menlo Park:AAAI Press,2005:572-577.
[6]WOLTER F,ZAKHARYASCHEV M.Temporalizing description logics[M].Frontiers of Combining Systems II,Studies Press/Wiley,2000:379-401.
[7]GU YI-LAN,SOUTCHANSKI M.Decidable reasoning in amodified situation calculus[C].Proceeding of the 20th International Joint Conferecne on Artifical Intelligence.Menlo Park:AAAI Press,2007:1891-1897.
[8]常亮,史忠植,邱莉榕,等.动态描述逻辑的Tableau判定算法[J].计算机学报,2008,6(31),896-909.
[9]史忠植,常亮.基于动态描述逻辑的语义Web服务推理[J].计算机学报,2008,31(9):1599-1611.
[10]SHI ZHONG-ZHI,DONG MING-KAI,JIANG YUN-CHENG,et al.A logical foundation for the semantic Web[J].Sciience in China,Ser.F,2005.48(2):161-178.
[11]CHANG LIANG,LIN FEN,SHI ZHONG-ZHI.A dynamic description logic for representation and reasoning about action[C].Proceedings of the 2nd International Conference on Knowledge science,Engineering and Management.Berlin:Springer,2007:115-127.