循环术语集是描述逻辑长期以来的研究难点，它的最基本的问题即语义及推理问题没有得到合理的解决。分析了描述逻辑循环术语集的研究现状和存在的问题，基于图的互模拟的方法，给出了描述逻辑FL0循环术语集的可满足性条件。结果证明循环术语集的可满足性的推理是多项式复杂的。
2012,48(14) Computer Engineering and Applications计算机工程与应用 A={1,2,3,4,5},B={1,3} V1> (1,3);(2,4);(4,1);(5,3);(4,5)} 画出这个T的语法描述图G和语义描述图G,3描述逻辑系统FL的TBox的语义构造 如图1和图2。 令T是FL的标准的TBox的术语集,给定初始赋 值J,Δ是给定的论域。取T中任意一个定义式 N=VRD1口vR2D2∏…「VRkD 假定T基于初始解释J的解释/给当前所有的被 定义概念N都是空集。任取x∈A,问:如果现在将 图1语义描述图G了 x放到N中,是含可将其扩充为基于J的、T的一个模 型呢?怎样的x才能在基于J的且为T的一个模型 的解释下使得x∈N2下面就给出讨论。 定义6固定初始解释J,称关系x∈-N与T是 协调,若T存在基于J的模型/使得xgN。 在上下文清楚的情况下,关系x∈-N是协调 图2语义描述图( 的。易得下面的定理。 注图G中省略了顶点2、4、5到其余顶点的有 定理2关系x∈-N是协调,当且仅当,T存在基 向赋杖的边。 于J的模型使得x∈AM。 为了给出主要结果的证明先介绍王驹的描述 下面给出语义模型的构造定理来回答上面的问题。 逻辑系统ⅵ(仅含逻辑联结词并凵和存在彐)的相 定理3描述逻辑系统FL。的 TBoX T存在基于J 关内容。 的模型/使得x∈△W,当且仅当,在语法描述图Gr 定义4v的 TBOX T的语法描述图Gn。描述和基于初始解释J的语义描述图G,分别存在以下的 图Gr设置如下: 两条互模拟的无穷路径: (1)G7=<V,F>。 (2)V= NUN是顶点集。 VI (3)E是有向边的集合:①N→N∈E,如果 证明不失一般性,考虑T中任意一个定义式 N是被定义符号且彐RN在它的定义式的右边出 N=VR1D1VR2D2…「VRk2Dk 现;②N→B,∈E,如果M是被定义符号且 设T存在基于J的模型Ⅰ使得x∈AWM。将 N=VR1D1∏∨R2D2「…nR,DA放到更人的描述逻 彐RB,在它的定义式的右边出现;③N B,∈F,辑系统AICN考虑,由曹发生等人的命题1(假设 如果N是被定义符号且VsB在它的定义式的右边CD是7中的概念的合式公式,R为 base symbol则: 出现;④B—>B:∈E,如果B是基木符号 (1)-A=A。 定义5ⅵL的 TBOX T的基于初始解释/的语义 (2)-(C凵D)≡-C∏-D,-C∏D)=-CL-D。 描述图G。描述图G设置如下: (3)一VRC≡王R.-C.RC=VR.-C。 (1)G,=<V,E>。 则式子(1)可化为 (2)=Δ(初始解释J的论域)是结点集 M≡丑R1-D1丑R2,D2…凵Rk.=Dk (2) (3)E是有向边的集合:①x→y∈F,如果 再用符合N取代N,用符合D取代D,式 子(2)可化为 (x,y)∈R1;2x-→y∈E,如果x∈B。 N=R1D1山丑R2,D2凵…山丑RDk 定理1描述逻辑系统ⅵ中x∈N与T协调,当 于是式(3)便成为描述逻辑系统ⅵL中定义式。 且仅当,在语法描述图G和基于初始解释/的语义且N的语法描述图Gn与语义描述图G,和N在描 描述图G分别存在以下的两条互模把的无穷路径:述逻辑系统FL的TBox的语法描述图Gn与语义描 N →>D 述图G,分别对应相同。由定理1有x∈(N)即 汪天友,曹发生:描述逻辑FL循环术语集的可满足性 2012,48(14) x∈ΔN′,当且仅当,在语法描述图σr和基于初始解得到描述逻辑系统FL循环术语集的可满足性条 释/的语义描述图G分别存在以下的两条互模拟的件。这是描述逻辑系统FL循环术语集的另一方面 无穷路径 的结果,更甚者是想通过对这些基本描述逻辑系统 →D 的研究工作给出更大的描述逻辑系统的研究 用互模拟构造ⅵ和FL循环术语集的模型的方 yI 式都与初始解释J有关。怎样给岀初始解释J/才能使 证毕 得描述逻辑系统的循环术语集有模型?这是相当有意 回到例1,在语法描述图Gn和语义描述图G中义的。虽然定理1和定理3都间接给出了初始解释J 存在互模拟的无穷路: 应怎样解释基本符号集和基本 Roles集, TBOX T才有 2 模型,但不明朗。 4-)4)..4—1 上述两个方面都是进一步的研究工作。 B 参考文献: 在语法描述图Gn和语义描述图G,中存在互模王驹蒋运,申宇明描述逻辑v循环术语集的可满足 拟的无穷路 性及推理机制叮中国科学:F辑,2009,39(2):205-211 [2 Giacomo G D, Lenzerini MA uniform framework for con- cept definitions in description logics[J] Journal of Artifi- →> cial Intelligence Research, 1997, 6(1):87-110 由定理3得1,2,4,5∈△N,于是N={3}。易[3] Buchheit m, Donini f m,Nutw. et al.a refined archi- 基于初始解释.J解释/是为 TBOX T的语义模型。 tecture for terminological systems:tπ sinology= schema 虽然非循环的描述逻辑系统的初始解释.可以 views [J]. Artificial Intelligence, 1998, 99(2): 209-260 中随意解释基本符号集和基本Ros集BoxT都有模曹发生余泉王驹等循环 NALCN-Tbox具有模型的条件 型。但对于含循环的描述逻辑系统的初始解释丿并 计算机学报,2008,31(1):16-23 非如此。如果给定如下的初始解释J/: [S]蒋运承,王驹,邓培民,等描述逻辑FLˉ循环术语集的语义 及推理计算机学报,2008,31(2):185-195 A={1,2,3,4,S},B={1,2} [6 Baader F, Calvancsc D, McGuinncss D, ct al. Thc descrip- R′={(1,2);(2,3);(1,4);(3,4)} tion logic handbook: theory, implementation and applica- 那么基于厂的模型只能使得N=⑦。 tions M Cambridge: Cambridge University Press, 2003 由定理2、3立即可得: 7 Baader F Using automata theory for characterizing the 定理4关系x∈M是协调,当且仅当,在语法 semantics of terminological cycles[].Annals of Mathe 描述图Gr和基于初始解释J的语义描述图G,分别 matics and Artificial Intelligence, 1996, 18(2/4): 175-219 存在以下的两条互模拟的无穷路径: [8 Nebel BTerminological cycles semantics and computa- 由 Henzinger等人的结果可知,给定两个有向 tional properties[C]//Sowa J F, ed. Proceedings of the 图G1和G2,找到由G到G2的最大模拟是多项式时 Principles of Semantic Networks. San francisco: morgan 问的。由定理3立即可得: Kaufmann Publishers 1991: 331-362 推论Ⅰ给定初始解释J,描述逻辑系统FL。的 [9]张维,侯金宏,曹发生,等描述逻辑系统FLEN中概念的最 TBoX 7是否可满足是多项式复杂的。 小公共包含算法研究[计算机研究与发展,2010,47(6) 1053-1059 [10HenzingerMR,HenzingerTa,KopkePw.computing 4结束语 simulations on finite and infinite graphs[C]/Proceedings 对描述逻辑系统FL。的TBox的语义构造与 of the 36th Annual symposium on Foundations of Com Baader对描述逻辑系统FL的研究方式和得到的结 uter Science. New York IEEE Computer Society Press 果完全不一样。本文基于王驹的描述逻辑系统ⅵ 1995:453-462.