循环ALC+的固定点存在性研究

张 勇，陈丽萍

(巢湖学院计算机与信息工程学院，安徽巢湖238000)

描述逻辑［1］是一阶谓词逻辑的可判定子集，是语义Web本体语言OWL Lite和OWL DL的逻辑基础［2-6］.含有循环定义的描述逻辑一直是研究的难点［7-9］，其中很多含有不同构子及关系的语言不仅语义问题没有得到很好解决，而且推理也存在困难.很多时候描述逻辑TBox中的循环［10-11］是有意义的，而且可以丰富和扩充语言的表达力，降低知识库的复杂度，特别是在具体的领域知识表示中.对于非循环TBox，每一个名称符号都可用基本符号唯一表示，要给定TBox中所有基本符号解释后，该TBox存在唯一模型［12］，对其语义通常称为描述语义.而对于含有循环定义的TBox则使用固定点［13-14］来刻画循环定义的语义，模型扩展集合上的偏序关系可以诱导出完备格，但是并不是每一个TBox都存在固定点模型，即使存在也不一定存在最大固定点模型或最小固定点模型.构子(也称算子)是描述逻辑表达能力和计算复杂性的决定性因素，表达能力的增强同时意味着推理复杂性的增强.ALC是最小的命题封闭的描述逻辑语言［15］，含有否定、交、并、值限定和存在性限定等构子.在实际应用中，传递关系经常是存在的而且是有意义的，所以研究带有传递关系的循环ALC其TBox固定点模型的存在性是有意义的.

目前国内对于描述逻辑的研究主要集中在基础研究、扩展研究和应用研究，基础研究主要针对描述逻辑的构造算子、表示和推理的基本问题，扩展研究主要应用在时序扩展［16］和模糊扩展［17］等方面，应用研究主要将描述逻辑做为领域中知识表示的工具.对于含有循环定义的描述逻辑目前很多语义及推理问题还没有解决，当前的研究主要集中在一些基本的理论问题［18-19］.国内也有学者研究了不带有传递关系的循环描述逻辑模型的判定［20］.带有传递关系的循环描述逻辑研究也集中在推理方面，也有研究在带有传递关系的循环描述逻辑中引入其他构子［21］，总体上对于固定点语义的研究主要针对ALC语言，没有考虑传递关系，传递关系是一种特殊关系，可以很好增强语言的表达能力.为此，笔者研究了含有传递关系的ALC-TBox具有固定点语义的条件，由于否定构子的存在，使得讨论充要条件变得困难，提出了否定深度的算法，进一步得出其固定点语义存在的充分非必要条件.

1 ALC+语法及语义

1.1 ALC+语法 描述逻辑中基本的描述是原子概念和原子关系，复杂的描述建立在基本的描述和算子之上.对于复杂描述主要由TBox和ABox组成，TBox又称术语集，其术语定义是概念和关系之间的联系，ABox是概念断言的集合，其断言是使得一个个体是TBox中一个给定概念描述的实例.

定义1 TBox中出现在术语定义左侧的概念称为名称符号，所有名称符号集合记为NT;TBox中仅仅出现在术语定义右侧的概念称为基本符号，所有基本符号集合记为NB.

定义2 TBox中任一个术语定义式，若术语定义左侧的原子概念为A，A NT，定义函数f:NT→NT，f(A)表示该定义式右侧的原子概念集合，f(A)⊆NT.若∀A，B，C NT，B f(A)，C f(B)，则 C f(A).

定义3 TBox中若存在定义式A≡T(A)，使得A f(A)，则称该TBox为循环TBox.

定义4 ∀β NB，J是对 β的解释，称为基解释，记为 βJ，βJ⊆ΔJ.∀A NT，I是对A的解释记为AI，AI⊆ΔI，若 ΔI=ΔJ，则称 I是 J的一个扩展.

J所有扩展的集合记为ExtJ，ExtJ={Ii|Ii是J的扩展}，如果一个TBox每一个基解释仅有一个扩展，则此扩展是其一个模型，则称该TBox是可定义的.

定义5 A≡T(A)是TBox中一个术语定义式，J是TBox基解释，J所有扩展的集合为ExtJ，定义映射TJ:ExtJ→ExtJ，显然若 IExtJ，TJ(I)ExtJ，TJ(I)由 ATJ(I)=T(A)I定义，如果 I=TJ(I)，即 ∀A NT，有AI=ATJ(I)，那么，I是TJ的一个固定点.

1.2 ALC+语义 ALC+解释I=(ΔI，.I)，解释域ΔI由非空集合组成，解释函数.I将概念映射成ΔI的子集，将关系映射成ΔI×ΔI的子集，并且满足下列语义(tr(R)表示R的传递闭包)

2 ALC+的固定点语义的充分非必要条件

命题1 循环ALC+-TBox，每一个术语定义式右边所有名称符号前不含否定构子是TBox拥有固定点语义的充分非必要条件.

证明 1)充分性

设J是TBox的基本解释，ExtJ表示J的所有扩展集合.TJ:ExtJ→ ExtJ表示I到TJ(I)的映射，其中I ExtJ以下证明中简记ExtJ为E，Ii为i，则IiExtJ可表示为i E.

ExtJ上的偏序关系≤定义为:i≤j当且仅当 Ai⊆Aj，其中 i，jExtJ，A NT，

1)对于 0，1 E，定义 0= ∪iEi则 A0= ∪iEAi，1= ∩iEi则 A1= ∩iEAi，∀i，j E，有 i≤0，j≤0，1≤i，1≤j，所以＜E，≤ ＞是格.由数学归纳法易证E的任一有限非空子集必有上确界和下确界.所以＜E，≤＞是完备格.

2)设A，B，C是原子概念，且每一个术语定义式右边所有名称符号前不含否定构子，其中B，C可以是A，∀ i，j E，i≤j

①若 A≡B∩C，则 Ti(A)=Bi∩Ci，Tj(A)=Bi∩Cj，由于 Bi⊆Bj，Ci⊆Cj，显然 Ti(A)⊆Tj(A);

②若 A≡B∪C，则 Ti(A)=Bi∪Ci，Tj(A)=Bi∪Cj，由于 Bi⊆Bj，Ci⊆Cj，显然 Ti(A)⊆Tj(A);

③若 A≡∀R.B，则 Ti(A)={x|∀ y Δi∧ ＜ x，y ＞ Ri→y Bi}，由于 Bi⊆Bj，则若 y Bi必有 y Bj，则∀x Ti(A)，有∀y Δj∧ ＜x，y＞ Rj→y Bj，所以 Ti(A)⊆Tj(A);

④若 A≡∃R.B，则 Ti(A)={x|∃y Δi∧ ＜ x，y ＞ Ri∧y Bi}，由于 Bi⊆Bj，则若 y Bi必有 y Bj，则∀x Ti(A)，有∃y Δj∧ ＜x，y＞ Rj∧y Bj，所以 Ti(A)⊆Tj(A);

⑤若A≡∀R+.B，R+是特殊的R，所以由③得Ti(A)⊆Tj(A);

⑥若A≡∃R+.B，R+是特殊的R，所以由④得Ti(A)⊆Tj(A).

可知完备格＜E，≤＞上的函数E→E单调.

1)和2)根据Tarski固定点定理［15］有充分性成立.

2)非必要性

举一反例:TBox仅含术语定义 A=∃R.┐A，J是基解释，I是 J的扩展，ΔI={x，y}，RI={＜x，y＞}，AI={x}，显然I是TBox一固定点模型.

由1)和2)命题得证.

证毕.

命题1考虑术语定义式右边所有名称符号前不含否定构子的情形，对于含有否定构子的情形，需考虑概念的否定深度.下面给出求TBox中每个概念的否定深度的算法:

输入 TBox中所有术语定义式.

给术语定义式排序:使得前一个定义式右边出现的某一名称符号必出现在下一术语定义式的左边，最后一个术语定义式右边出现的名称符号必出现在第一个术语定义式左边;

while(NiNT)

if(Ni前有否定构子)Ndeep(Ni)=1;

else Ndeep(Ni)=0;

遍历排序后的TBox中每一个术语定义式A≡T(A)，出现在T(A)中的每一个名称符号Ni，Ndeep(Ni)=Ndeep(Ni)+Ndeep(A);

输出 Ndeep(Ni);//概念Ni的否定深度

推论1 循环ALC+-TBox，每一个术语定义式中名称符号的否定深度非奇是TBox拥有固定点语义的充分非必要条件.

可以归纳证明，循环ALC+-TBox，每一个术语定义式中名称符号的否定深度非奇都等价于，所有名称符号前不含否定构子的术语定义式，由命题1可知，推论1成立.

3 ALC+固定点模型需满足的条件

定义6 P(RI)={x|x ΔI∧ ＜x，y＞ RI}.

定义7 N(RI)={y|y ΔI∧ ＜x，y＞ RI}.

由于篇幅仅给出命题2和命题5的证明，其他证明方法相同，在此略去.

命题2 循环ALC+-TBox定义式右边使用值限定构子∀R.A，如B≡∀R.A(A，B均为原子概念且可以为同一概念)，若I为其固定点模型，则需满足

1)N(RI)⊆AI;

2)BI⊆P(RI).

证明 ∀y N(RI)，X BI，则 ＜ x，y ＞ RI，所以 y AI，即 N(RI)⊆AI，BI={x|∀y ΔI∧ ＜ x，y ＞RI→y AI}⊆{x|∀y ΔI∧ ＜x，y ＞ RI}=P(RI)，即 BI⊆P(RI).

命题3 循环ALC+-TBox定义式右边使用存在性限定构子∃R.A，如B≡∃R.A(A，B均为原子概念且可以为同一概念)，若I为其固定点模型，则需满足

1)N(RI)∩AI≠Ø;

2)BI⊆P(RI).

命题4 循环ALC+-TBox定义式右边使用值限定构子∀R+.A，如B≡∀R+.A(A，B均为原子概念且可以为同一概念)，若I为其固定点模型，则需满足

1)若 ＜x，y＞ (R+)I，则 xP((R+)I)，yN((R+)I);

若 ＜x，y ＞ (R+)I，则不存在 z使得 ＜ x，z＞ (R+)I且 ＜z，y＞ (R+)I;

2)P((R+)I)∩N((R+)I)≠Ø.

命题5 循环ALC+-TBox定义式右边使用存在性限定构子∃R+.A，如B≡∃R+.A(A，B均为原子概念且可以为同一概念)，若I为其固定点模型，则需满足

1)BI⊆P((R+)I);

2)AI∩N((R+)I)≠Ø;

3)P((R+)I)∩N((R+)I)≠Ø;

或者对于 xP((R+)I)，yN((R+)I)，则不存在 z使得 ＜x，z＞ (R+)I且 ＜z，y＞ (R+)I.

证明 BI={x|∃y ΔI∧ ＜x，y＞ tr(R)I∧y AI}⊆{x|∃y ΔI∧ ＜x，y＞ tr(R)I}=P((R+)I)，若AI∩N((R+)I)=Ø，则不存在y使得 ＜x，y＞ tr(R)I且y AI，所以必有AI∩N((R+)I)≠Ø，对于 ＜x，y＞ (R+)I，x P((R+)I)，y N((R+)I)，若存在 z使得 ＜ x，z＞ (R+)I且 ＜ z，y＞ (R+)I，则 P((R+)I)∩N((R+)I)≠Ø.

证毕.

4 应用

通过下面的例子来介绍以上命题的应用，由于篇幅这里仅介绍命题3的一个应用.

TBox中有术语定义式:A=﹁B∩∀R.C，B=﹁A∩∃R.C，J是TBox基解释，J所有扩展的集合为ExtJ，定义映射 TJ:ExtJ→ExtJ，现有 ΔI={a，b，c，d}，I1，I2 ExtJ，TJ(I1)ExtJ，TJ(I2)ExtJ，AI1={a}，AI2={a，b}，CI1=CI2={a，b，c}，BI1={d}，BI2={c，d}，RI1={＜ c，b ＞ ，＜ b，a ＞ ，＜ c，a ＞}，RI2={＜ d，c＞，＜c，b＞，＜d，b＞}，则有

显然，AI1≠ATJ(I1)，AI2≠ATJ(I2)，BI1≠BTJ(I1)，BI2≠BTJ(I2)，由定义得出 I1，I2 不是 TJ 的固定点.

若根据命题3，由于AI1={a}，P(RI1)={b，c}，显然AI1⊆P(RI1)不满足，即命题3第2个条件不成立，所以得出I2不是TJ的固定点;由于AI2={a，b}，P(RI2)={d，c}，显然AI2⊆P(RI2)不满足，即命题3第2个条件不成立，所以得出I2不是TJ的固定点.

5 结束语

本文主要讨论了术语定义中使用存在性限定和值限定算子，对于其他算子由于篇幅的原因未能分析.对于各种描述逻辑TBox中否定构子的出现都可能会影响其是否具有模型，但否定存在有时也是必须的，而且其位置可以是任意的，下一步工作将对这一问题作深入研究，从其他途径寻找解决方案.

［1］Badder F，Calvanese D，McGuinnes D，et al.The Description logic Handbook:Theory，Implemntation and Applications［M］.London:Cambridge University Presss，2003.

［2］Berners L，Hendler J，Lassila O.The semantic web［J］.Scientific American，2001，184(5):34-43.

［3］Badder F，Horrocks I，Sattler U.Description logics as ontology languanges for the semantic web［M］.//Hutter D，StephanW.Festschrift in hononor of Jorg Sickmann，Lecture Notes in Artificial Intelligence.［S.l.］:Springer，2005:228-248

［4］Borgida A，Lenzerini M，Rosati R.Description Logics for Data Bases［M］.//Badder F，McGuinness D，Nardi d，et al.Cambridge:Cambridge University Press，2003.

［5］Fontaine，P Ringeissen C，Schmidt R A.Hybrid unification in the description logic(mathcal{EL})［J］.Frontiers of Combining Systems.Lecture Notes in Computer Science，2013(8152):295-310.

［6］Giacomo G D，Lenzerini M.A uniform framework for concept definitions in description logics［J］.Journal of Artificial Intelligence Research，1997，6(1):87-110.

［7］Buchheit M，Donini F M，Nutt W，et al.A refined architeture for terminological systems:Terminology=schema+views［J］.Arti-ficial Intelligence，1998，9(2):209-260.

［8］Badder F.Using automata theory for characterizing the semanticsof terminological cycles［J］.Annals of Mathematics and Artificial Intelligence，1996，18(2/4):175-219.

［9］Nebel B.Reasoning and revision in hybrid representation systems［J］.Lecture Notes in Computer Science，1990，422:125-156.

［10］Garcia-Colin N，Montejano A，Montejano L，et al.Transitive oriented 3 hypergraphs of cyclic orders［J］.Order，2013，30(3):869-875.

［11］Ahmed E B，Nabli A，Gargouri F.Mining cyclic association rules from multidimensional knowledge procecding of the Sixth International Conference on Digital Information Management(ICDIM)，Melbourne，September 26-28，2011［C］.［S.l.］:IEEE，2011.

［12］Schmidt-Schauβ M，Smolka G.Attributive concept descriptions with complements［J］.Artificial Intelligence，1991，48(1):1-26.

［13］Mao H.Complete atomistic lattices are classification lattices［J］.Algebra universalis，2012，68(3/4):293-294.

［14］Kukushkin N S.On the existence of optima in complete chains and lattices［J］.Journal of Optimization Theory and Applications，2012，154(3):759-767.

［15］Tarski A.A lattice-theoretical fixpoint theorem and its applications［J］.Journal of Mathematics，1955，5(2):285-309.

［16］孙永新，赵希顺，符志强.描述逻辑的动态时序扩展［J］.计算机应用研究.2012，29(2):536-541.

［17］蒋运承，史忠植，汤庸，等.面向语义Web表示的模糊描述逻辑［J］.软件学报.2007，18(6):1 257-1 269.

［18］蒋运承，王驹，周生明，等.描述逻辑εL混合循环术语集的LCS和MSC推理［J］.软件学报，2008，19(10):2 483-2 497.

［19］蒋运承，王驹，周生明，等.描述逻辑εL循环术语集的混合推理［J］.计算机研究与发展，2009，46(1):15-22.

［20］曹发生，余泉，王驹，等.循环 ALCN-Tbox具有模型的条件［J］.计算机学报，2008，31(1):16-23.

［21］曹逸，徐德志，陈建二，等.一种带传递关系的认知描述逻辑研究［J］.计算机研究与发展，2009，46(3):452-458.