模糊描述逻辑系统L-ALCN中的形式概念格

摘要:该文首先简单介绍格值模糊描述逻辑系统L-ALCN的语法和语义,介绍形式概念分析(FCA)的基本理论。把形式概念分析引入到模糊描述逻辑中,在国际上也是刚刚起步,尚不成熟。该文定义了模糊形式背景、模糊形式概念格,并证明了此概念格为完备格。

关键词: 模糊描述逻辑L-ALCN ;形式概念分析;形势概念格;模糊描述背景;模糊概念格

中图分类号:TP18文献标识码:A文章编号:1009-3044(2009)25-7219-03

Formal Concept Lattice of Fuzzy Description LogicL-ALCN

LI Jia

(College of Mathematics Science, Guangxi Normal University, Guilin 541004, China)

Abstract: First, she gives a brief introduction of the syntax and the semantics of L-ALCN system and the basic knowledge of Formal Concept Analysis. The study of Applying Formal Concept Analysis to Description Logics, in the international community is still in its infancy, not yet ripe. She Presents the definition of fuzzy Description Logic concept and fuzzy formal concept lattice. The fuzzy formal concept lattice of L-ALCN which she given are completely.

Key wodrs: fuzzy description logic L-ALCN; formal concept analysis; formal concept lattice;fuzzy description concept; fuzzy concept lattice

描述逻辑[1]是基于对象的知识表示的形式化工具,也叫概念表示语言或术语逻辑,一般情况下是一阶谓词逻辑的一个可判定子集。自从描述逻辑的提出到现在,国内外许多学者对描述逻辑进行了深入研究。目前描述逻辑在语义Web[2-3]、本体[4]、数据库[5-6]和软件工程[7]等领域得到了很好的应用。由于传统的描述逻辑[1]只能对精确知识进行表示和推理,不能对不确定或不精确知识进行表示和推理,许多学者对传统的描述逻辑进行了模糊化扩充,主要结果有:U Straccia对描述逻辑ALC进行了模糊化推广,提出了模糊描述逻辑FALC[8];李言辉提出了一种支持数量约束的扩展模糊描述逻辑EFALCN[9];G Stoilos提出了模糊描述逻辑FSI和FSHIN[10];蒋运承提出了模糊描述逻辑FALNUI[11-12]和FSHOIQ[13];李淑英等提出了L-ALCN [14]。本文就是在李淑英的模糊描述逻辑L-ALCN系统上研究格值模糊描述逻辑L-ALCN中的概念格问题的。

形式概念分析[15]是20世纪80年代初由德国Wille教授提出的,是一种十分成熟的数学模型,特点是小而全,对信息处理算法十分清晰,不尽人意的是形式概念分析的表达能力比较贫乏,而且没有推理机制,相比较而言,描述逻辑却有丰富的表达力。把形式概念分析的方法引入到描述逻辑的框架中是很有意义的。本文作者阅读了近年来国际上诸多的文献,目前,国际领域上还没有考虑将FCA引入到模糊描述逻辑框架中。

形式概念分析和模糊描述逻辑研究的基础都是概念。但是概念的获取在这两个研究领域中有着显著的不同。在形式概念分析中,首先必须存在一个形式背景,概念是由形式背景中的对象的集合和这些对象所共有的属性集合所构成的二元组。而在模糊描述逻辑的语义中,概念是由特定的映射(解释)给出的,概念解释成从解释域到完备格的映射,通过不同个体的不同隶属度来表达不同的概念。我们试图在形式概念和模糊描述逻辑之间建立一定的联系。利用形式概念分析的算法清晰等优点来A补模糊描述逻辑在此方面的不足。从模型或者逻辑的观点来考虑,就是一个模糊描述背景,L是所有模糊描述公式的集合,我们称之为属性集合;πi为从解释域到备值集合T 的所有映射 。我们在模糊描述逻辑的公式与映射之间建立关系,进而建立一个闭包算子,并建立一个模糊描述逻辑的概念格,同时证明了此格为完备格。

1 模糊描述逻辑系统 L-ALCN的语法和语义[14]

模糊描述逻辑L-ALCN是由经典描述逻辑ALCN的真值空间扩充到完备格形成的。令L=〈T,〉是一个完备格,T是备值集合, 是偏序关系,与相关的算子有和,称为并与交。令t与f是T上的最大元与最小元,并假设存在T上的一个关于的反单调否定函数,满足a=a,a∈T。

L-ALCN的语法

定义1. 令C是概念名集合, R是关系名集合, L-ALCN的概念是由以下的语法规则形成的:

定义2. 一个L-断言φ是一个形如〈ac〉,〈ac〉,〈ac〉,〈ac〉或a≠b的表达式,其中a, b是ALCN断言, c ∈T。

定义3 . L-ALCN中的知识库∑=(T , A)由两部分组成, T Box和ABox。其中T Box是模糊术语公理的有限集合,模糊术语公理有概念包含AC与概念等价A=C两种情况。 如果T =,那么∑是一个纯断言知识库。

L-ALCN的语义

定义4. 对于完备格L=〈T , 〉,一个L-解释是二元组I=(ΔI,•I),其中ΔI为解释域, •I为解释函数,其映射方式为:

个体变元d映为dI∈ΔI;

概念C映为隶属函数CI:ΔI T;

角色R映为隶属函数RI: ΔI×ΔIT

对于d∈ΔI,•I必须满足以下的方程:

定义5. 一个解释I满足:

1) 断言(,a≠b)当且仅当CI(aI)c,RI(aI,bI)c, (aI≠bI)(、和的情况类似);

2) AC(A=C)当且仅当d∈ΔI,AI(d)CI(d) (AI(d))成立;

3) 知识库∑当且仅当I满足∑中的每一个元素,此时说I是∑的一个模型。

2 形式概念分析的基本理论

定义6. 一个形式背景(G, M, I), G的元素称为对象, M的元素称为属性, (g, m) ∈I表示对象g具有属性m。对于形式背景(G, M, I),在对象子集XG和属性子集YM 统一定义算子*如下:

定义7. 背景(G, M, I)上的一个形式概念是二元组(X, Y),其中XG , YM,而且满足X*=Y, Y*=X。我们称X是概念(X, Y)的外延, Y是概念(X, Y)的内涵。用μ(G, M, I )表示背景(G, M, I)上的所有概念的集合。

命题1. 如果(G, M, I)是一个形式背景, X, X1, X2是对象的子集, F, F1, F2是属性的子集,则有下面的一些性质 :

定义8. 若(X1, Y1), ( X2, Y2)是某个背景上的两个概念, 而且X1X2 (等价于Y2Y1), 则我们称(X1, Y1)是( X2, Y2)的子概念, ( X2, Y2)是(X1, Y1)的超概念, 并记作(X1, Y1) ≤( X2, Y2),关系≤称为是概念的“层次序”。 (G, M, I)上的所有概念用这种序组成的集合用μ(G, M, I )表示,称它为背景(G, M, I)上的概念格。

定理1. (概念格的基本定理)概念格μ(G, M, I )是一个完全格,其上确界和下确界分别是:

3 模糊描述逻辑系统L-ALCN中形式概念格

定义9.一个模糊描述背景K:,是由L和πi,以及L与πi之间的关系O组成。其中,L为L-ALCN 中所有概念描述的集合(又称为公式集或属性集);i=(Δi,•i,T)称为一个解释, Δi为解释域,是一个非空有限的集合; πi为解释函数; T 为一个解释值域,是一个备值集合;πi为在i解释下从Δi到T 的所有的映射的全体。对任意的P∈L,都有Pi:ΔiT。对于关系O,我们定义:若P∈L,f∈πi,如有对任意的a∈Δi,都有f(a)Pi(a)成立,则称(P,f)∈O,否则称(P,f)O。

若固定解释 时,若解释域Δi中有m个个体, T中有n个备值时,此时共有nm个映射,这样把公式集L分成了nm个等价类。我们有P1,P2∈L,P1~P2当且仅当,对任意a∈Δi.P1i(a)=p2i(a)。

定义10.在一个模糊描述背景K:中,XL,Fπi,我们统一定义算子•*

定义11. 一个模糊描述背景K:,二元组称为一个模糊描述概念,其中XL,Fπi,并且有X*=F,F*=X,称X为的模糊外延,F为的模糊内涵。

命题2. 在一个模糊描述背景K:中,X ,X1,X2是L的子集,F,F1,F2是πi的子集,则有下面的一些性质:

证明:1)若f∈X2*,即对任意的P∈X2,a∈Δi,都有f(a)Pi(a),又由于X1X2,所以对任意的P∈X1,都有P∈X2,即对任意的P∈X1,a∈Δi,都有f(a)Pi(a)成立,所以f∈X1*,从而X2*X1*

2)若对任意的P∈X, f∈X*,则对任意的a∈Δi,有f(a)Pi(a),即对任意的f∈X*,都有对任意的a∈Δi,使f(a)Pi(a)成立,所以P∈X**,所以 XX**。

3)由(2)'可知XX***,由(2)XX**,再由(1)可知,X***X*

所以,X=X***

4)

另外

(1)' ,(2)',(3)'同理可证。

定义12. 一个模糊描述背景K:,若(X1,F1),(X2,F2)是背景上的两个概念,并且X1X2(等价于Y2Y1),我们称(X1,F1)是(X2,F2)的子概念, (X2,F2)是(X1,F1)的超概念,并记作(X1,F1)≤(X2,F2),关系≤称为是概念的“层次序”。 K:上的所有概念用这种序组成的集合用μ(L,πi,O)表示,称为概念格。

命题3. 若T为一个索引集,而且对每一个t∈T,XtL,Ftπi,则

。

定理2.概念格μ(L,πi,O)是一个完备格,其上确界和下确界分别是:

,

证明:要证明μ(L,πi,O)是一个完备格,只须证明对μ(L,πi,O)中的任何子集都有上确界以及下确界,设{(Xt,Ft)|t∈T}是μ(L,πi,O)的一个子集,要证明就是它的下确界,即我们证明一定是概念,以及一定是这个集合的下确界。

首先,由于每个(Xt,Ft)是概念,所以Xt=(Ft)*,于是,又由以上的命题,,这样 ,这显然是(F*,F**)的形式,一定是一个形式概念。

其次,由于是每个Xt的子集,所以是每个(Xt,Ft)的子概念,所以是 的一个下界,又因为{(Xt,Ft)|t∈T}的任何一个下界(X,F)都是X是所有Xt的子集,于是必有,即必有,所以是{(Xt,Ft)|t∈T}的下确界。

同理可证一定是{(Xt,Ft)|t∈T}的上确界。

4 结束语

本文是在基于格值模糊描述逻辑L-ALCN下讨论的概念格,将形式概念分析应用到描述逻辑上目前比较新的课题,本文也是在这种思想的指导下完成的。但是只是建立了模糊描述背景下的模糊概念格远不能达到这种要求,仍需要进一步进行模糊描述背景下的蕴含式等理论的研究。

参考文献:

[1] Baader F,Nutt W.Basic Description Logics[M]//Baader F,Calvanese D,McGuinness D,et al.The Description Logic Handbook:Theory,Implementation and Applications.Cambridge:Cambridge University Press,2003:47-100.

[2] 史忠植,董明楷,蒋运承,等.语义Web的逻辑基础[J].中国科学,E辑:信息科学,2004,34(10):1123-1138.

[3] 蒋运承,汤庸,王驹,等.面向语义Web的描述逻辑[J].模式识别与人工智能,2007,20(1):48-54.

[4] Baader F,Horrocks I,Sattler U.Description Logics[M]//Staab S,R Studer,editors.Handbook on Ontologies:International Handbooks on Information Systems.Springer,2004:3-28.

[5] Borgida A,Lenzerini M,Rosati R.Description Logics for Data Bases[M]//Baader F,Calvanese D,McGuinness D,et al.The Description Logic Handbook:Theory,Implementation and Applications.Cambridge:Cambridge University Press,2003:472-494.

[6] 蒋运承,汤庸,王驹,等.基于描述逻辑的带属性依赖时序ER模型[J].计算机研究与发展,2007,44(10):1765-1773.

[7] Berardi D,Calvanese D,Giacomo G D.Reasoning on UML Class Diagrams[J].Artificial Intelligence,2005,168(1-2):70-118.

[8] Straccia U.Reasoning within Fuzzy Description Logics[J].Journal of Artificial Intelligence Research,2001(14):137-166.

[9] 李言辉,徐宝文,陆建江,等.支持数量约束的扩展模糊描述逻辑复杂性研究[J].软件学报,2006,17(5):968-975.

[10] Stoilos G,Stamou G,Pan J Z,et al.Reasoning with Very Expressive Fuzzy Description Logics[J].Journal of Artificial Intelligence Research,2007(30):273-320.

[11] 蒋运承,汤庸,王驹.基于描述逻辑的模糊ER模型[J].软件学报,2006,17(1):20-30.

[12] 蒋运承,汤庸,王驹,等.模糊描述逻辑FALNUI的tableaux推理[J].计算机研究与发展,2007,44(8):1309-1316.

[13] 蒋运承,史忠植,汤庸,等.面向语义Web语义表示的模糊描述逻辑[J].软件学报,2007,18(6):1257-1269.

[14] 李淑英,李梅,蒋运承,等,刘真环.模糊描述逻辑L-ALCN[J].计算机研究与发展,2008,45(4):619-625

[15] Wille R.Restructuring lattice theory:an approach based on hierarchies of concepts[M]//Rival Ied.Ordered Sets.Dordrecht:Reidel,1982:445-470.