循環(huán)ALC+的固定點存在性研究

張 勇，陳麗萍

(巢湖學(xué)院計算機(jī)與信息工程學(xué)院，安徽巢湖238000)

描述邏輯［1］是一階謂詞邏輯的可判定子集，是語義Web本體語言O(shè)WL Lite和OWL DL的邏輯基礎(chǔ)［2-6］.含有循環(huán)定義的描述邏輯一直是研究的難點［7-9］，其中很多含有不同構(gòu)子及關(guān)系的語言不僅語義問題沒有得到很好解決，而且推理也存在困難.很多時候描述邏輯TBox中的循環(huán)［10-11］是有意義的，而且可以豐富和擴(kuò)充語言的表達(dá)力，降低知識庫的復(fù)雜度，特別是在具體的領(lǐng)域知識表示中.對于非循環(huán)TBox，每一個名稱符號都可用基本符號唯一表示，要給定TBox中所有基本符號解釋后，該TBox存在唯一模型［12］，對其語義通常稱為描述語義.而對于含有循環(huán)定義的TBox則使用固定點［13-14］來刻畫循環(huán)定義的語義，模型擴(kuò)展集合上的偏序關(guān)系可以誘導(dǎo)出完備格，但是并不是每一個TBox都存在固定點模型，即使存在也不一定存在最大固定點模型或最小固定點模型.構(gòu)子(也稱算子)是描述邏輯表達(dá)能力和計算復(fù)雜性的決定性因素，表達(dá)能力的增強(qiáng)同時意味著推理復(fù)雜性的增強(qiáng).ALC是最小的命題封閉的描述邏輯語言［15］，含有否定、交、并、值限定和存在性限定等構(gòu)子.在實際應(yīng)用中，傳遞關(guān)系經(jīng)常是存在的而且是有意義的，所以研究帶有傳遞關(guān)系的循環(huán)ALC其TBox固定點模型的存在性是有意義的.

目前國內(nèi)對于描述邏輯的研究主要集中在基礎(chǔ)研究、擴(kuò)展研究和應(yīng)用研究，基礎(chǔ)研究主要針對描述邏輯的構(gòu)造算子、表示和推理的基本問題，擴(kuò)展研究主要應(yīng)用在時序擴(kuò)展［16］和模糊擴(kuò)展［17］等方面，應(yīng)用研究主要將描述邏輯做為領(lǐng)域中知識表示的工具.對于含有循環(huán)定義的描述邏輯目前很多語義及推理問題還沒有解決，當(dāng)前的研究主要集中在一些基本的理論問題［18-19］.國內(nèi)也有學(xué)者研究了不帶有傳遞關(guān)系的循環(huán)描述邏輯模型的判定［20］.帶有傳遞關(guān)系的循環(huán)描述邏輯研究也集中在推理方面，也有研究在帶有傳遞關(guān)系的循環(huán)描述邏輯中引入其他構(gòu)子［21］，總體上對于固定點語義的研究主要針對ALC語言，沒有考慮傳遞關(guān)系，傳遞關(guān)系是一種特殊關(guān)系，可以很好增強(qiáng)語言的表達(dá)能力.為此，筆者研究了含有傳遞關(guān)系的ALC-TBox具有固定點語義的條件，由于否定構(gòu)子的存在，使得討論充要條件變得困難，提出了否定深度的算法，進(jìn)一步得出其固定點語義存在的充分非必要條件.

1 ALC+語法及語義

1.1 ALC+語法 描述邏輯中基本的描述是原子概念和原子關(guān)系，復(fù)雜的描述建立在基本的描述和算子之上.對于復(fù)雜描述主要由TBox和ABox組成，TBox又稱術(shù)語集，其術(shù)語定義是概念和關(guān)系之間的聯(lián)系，ABox是概念斷言的集合，其斷言是使得一個個體是TBox中一個給定概念描述的實例.

定義1 TBox中出現(xiàn)在術(shù)語定義左側(cè)的概念稱為名稱符號，所有名稱符號集合記為NT;TBox中僅僅出現(xiàn)在術(shù)語定義右側(cè)的概念稱為基本符號，所有基本符號集合記為NB.

定義2 TBox中任一個術(shù)語定義式，若術(shù)語定義左側(cè)的原子概念為A，A NT，定義函數(shù)f:NT→NT，f(A)表示該定義式右側(cè)的原子概念集合，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為循環(huán)TBox.

定義4 ?β NB，J是對 β的解釋，稱為基解釋，記為 βJ，βJ?ΔJ.?A NT，I是對A的解釋記為AI，AI?ΔI，若 ΔI=ΔJ，則稱 I是 J的一個擴(kuò)展.

J所有擴(kuò)展的集合記為ExtJ，ExtJ={Ii|Ii是J的擴(kuò)展}，如果一個TBox每一個基解釋僅有一個擴(kuò)展，則此擴(kuò)展是其一個模型，則稱該TBox是可定義的.

定義5 A≡T(A)是TBox中一個術(shù)語定義式，J是TBox基解釋，J所有擴(kuò)展的集合為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由非空集合組成，解釋函數(shù).I將概念映射成ΔI的子集，將關(guān)系映射成ΔI×ΔI的子集，并且滿足下列語義(tr(R)表示R的傳遞閉包)

2 ALC+的固定點語義的充分非必要條件

命題1 循環(huán)ALC+-TBox，每一個術(shù)語定義式右邊所有名稱符號前不含否定構(gòu)子是TBox擁有固定點語義的充分非必要條件.

證明 1)充分性

設(shè)J是TBox的基本解釋，ExtJ表示J的所有擴(kuò)展集合.TJ:ExtJ→ ExtJ表示I到TJ(I)的映射，其中I ExtJ以下證明中簡記ExtJ為E，Ii為i，則IiExtJ可表示為i E.

ExtJ上的偏序關(guān)系≤定義為:i≤j當(dāng)且僅當(dāng) 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，≤ ＞是格.由數(shù)學(xué)歸納法易證E的任一有限非空子集必有上確界和下確界.所以＜E，≤＞是完備格.

2)設(shè)A，B，C是原子概念，且每一個術(shù)語定義式右邊所有名稱符號前不含否定構(gòu)子，其中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，≤＞上的函數(shù)E→E單調(diào).

1)和2)根據(jù)Tarski固定點定理［15］有充分性成立.

2)非必要性

舉一反例:TBox僅含術(shù)語定義 A=?R.┐A，J是基解釋，I是 J的擴(kuò)展，ΔI={x，y}，RI={＜x，y＞}，AI={x}，顯然I是TBox一固定點模型.

由1)和2)命題得證.

證畢.

命題1考慮術(shù)語定義式右邊所有名稱符號前不含否定構(gòu)子的情形，對于含有否定構(gòu)子的情形，需考慮概念的否定深度.下面給出求TBox中每個概念的否定深度的算法:

輸入 TBox中所有術(shù)語定義式.

給術(shù)語定義式排序:使得前一個定義式右邊出現(xiàn)的某一名稱符號必出現(xiàn)在下一術(shù)語定義式的左邊，最后一個術(shù)語定義式右邊出現(xiàn)的名稱符號必出現(xiàn)在第一個術(shù)語定義式左邊;

while(NiNT)

if(Ni前有否定構(gòu)子)Ndeep(Ni)=1;

else Ndeep(Ni)=0;

遍歷排序后的TBox中每一個術(shù)語定義式A≡T(A)，出現(xiàn)在T(A)中的每一個名稱符號Ni，Ndeep(Ni)=Ndeep(Ni)+Ndeep(A);

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

推論1 循環(huán)ALC+-TBox，每一個術(shù)語定義式中名稱符號的否定深度非奇是TBox擁有固定點語義的充分非必要條件.

可以歸納證明，循環(huán)ALC+-TBox，每一個術(shù)語定義式中名稱符號的否定深度非奇都等價于，所有名稱符號前不含否定構(gòu)子的術(shù)語定義式，由命題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 循環(huán)ALC+-TBox定義式右邊使用值限定構(gòu)子?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 循環(huán)ALC+-TBox定義式右邊使用存在性限定構(gòu)子?R.A，如B≡?R.A(A，B均為原子概念且可以為同一概念)，若I為其固定點模型，則需滿足

1)N(RI)∩AI≠?;

2)BI?P(RI).

命題4 循環(huán)ALC+-TBox定義式右邊使用值限定構(gòu)子?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 循環(huán)ALC+-TBox定義式右邊使用存在性限定構(gòu)子?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 應(yīng)用

通過下面的例子來介紹以上命題的應(yīng)用，由于篇幅這里僅介紹命題3的一個應(yīng)用.

TBox中有術(shù)語定義式:A=﹁B∩?R.C，B=﹁A∩?R.C，J是TBox基解釋，J所有擴(kuò)展的集合為ExtJ，定義映射 TJ:ExtJ→ExtJ，現(xiàn)有 Δ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=j5i0abt0b，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 的固定點.

若根據(jù)命題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 結(jié)束語

本文主要討論了術(shù)語定義中使用存在性限定和值限定算子，對于其他算子由于篇幅的原因未能分析.對于各種描述邏輯TBox中否定構(gòu)子的出現(xiàn)都可能會影響其是否具有模型，但否定存在有時也是必須的，而且其位置可以是任意的，下一步工作將對這一問題作深入研究，從其他途徑尋找解決方案.

［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］孫永新，趙希順，符志強(qiáng).描述邏輯的動態(tài)時序擴(kuò)展［J］.計算機(jī)應(yīng)用研究.2012，29(2):536-541.

［17］蔣運承，史忠植，湯庸，等.面向語義Web表示的模糊描述邏輯［J］.軟件學(xué)報.2007，18(6):1 257-1 269.

［18］蔣運承，王駒，周生明，等.描述邏輯εL混合循環(huán)術(shù)語集的LCS和MSC推理［J］.軟件學(xué)報，2008，19(10):2 483-2 497.

［19］蔣運承，王駒，周生明，等.描述邏輯εL循環(huán)術(shù)語集的混合推理［J］.計算機(jī)研究與發(fā)展，2009，46(1):15-22.

［20］曹發(fā)生，余泉，王駒，等.循環(huán) ALCN-Tbox具有模型的條件［J］.計算機(jī)學(xué)報，2008，31(1):16-23.

［21］曹逸，徐德志，陳建二，等.一種帶傳遞關(guān)系的認(rèn)知描述邏輯研究［J］.計算機(jī)研究與發(fā)展，2009，46(3):452-458.