張 勇，陳麗萍

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

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

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

1 ALC+語(yǔ)法及語(yǔ)義

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

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

定義2 TBox中任一個(gè)術(shù)語(yǔ)定義式，若術(shù)語(yǔ)定義左側(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)，則稱(chēng)該TBox為循環(huán)TBox.

定義4 ?β NB，J是對(duì) β的解釋?zhuān)Q(chēng)為基解釋?zhuān)洖?βJ，βJ?ΔJ.?A NT，I是對(duì)A的解釋記為AI，AI?ΔI，若 ΔI=ΔJ，則稱(chēng) I是 J的一個(gè)擴(kuò)展.

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

定義5 A≡T(A)是TBox中一個(gè)術(shù)語(yǔ)定義式，J是TBox基解釋?zhuān)琂所有擴(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的一個(gè)固定點(diǎn).

1.2 ALC+語(yǔ)義 ALC+解釋I=(ΔI，.I)，解釋域ΔI由非空集合組成，解釋函數(shù).I將概念映射成ΔI的子集，將關(guān)系映射成ΔI×ΔI的子集，并且滿足下列語(yǔ)義(tr(R)表示R的傳遞閉包)

2 ALC+的固定點(diǎn)語(yǔ)義的充分非必要條件

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

證明 1)充分性

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

ExtJ上的偏序關(guān)系≤定義為:i≤j當(dāng)且僅當(dāng) Ai?Aj，其中 i，jExtJ，A NT，

1)對(duì)于 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是原子概念，且每一個(gè)術(shù)語(yǔ)定義式右邊所有名稱(chēng)符號(hào)前不含否定構(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固定點(diǎn)定理［15］有充分性成立.

2)非必要性

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

由1)和2)命題得證.

證畢.

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

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

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

while(NiNT)

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

else Ndeep(Ni)=0;

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

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

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

可以歸納證明，循環(huán)ALC+-TBox，每一個(gè)術(shù)語(yǔ)定義式中名稱(chēng)符號(hào)的否定深度非奇都等價(jià)于，所有名稱(chēng)符號(hào)前不含否定構(gòu)子的術(shù)語(yǔ)定義式，由命題1可知，推論1成立.

3 ALC+固定點(diǎn)模型需滿足的條件

定義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為其固定點(diǎn)模型，則需滿足

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為其固定點(diǎn)模型，則需滿足

1)N(RI)∩AI≠?;

2)BI?P(RI).

命題4 循環(huán)ALC+-TBox定義式右邊使用值限定構(gòu)子?R+.A，如B≡?R+.A(A，B均為原子概念且可以為同一概念)，若I為其固定點(diǎn)模型，則需滿足

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為其固定點(diǎn)模型，則需滿足

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

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

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

或者對(duì)于 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)≠?，對(duì)于 ＜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)用

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

TBox中有術(shù)語(yǔ)定義式:A=﹁B∩?R.C，B=﹁A∩?R.C，J是TBox基解釋?zhuān)琂所有擴(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=kg0eqsu，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 的固定點(diǎn).

若根據(jù)命題3，由于AI1={a}，P(RI1)={b，c}，顯然AI1?P(RI1)不滿足，即命題3第2個(gè)條件不成立，所以得出I2不是TJ的固定點(diǎn);由于AI2={a，b}，P(RI2)={d，c}，顯然AI2?P(RI2)不滿足，即命題3第2個(gè)條件不成立，所以得出I2不是TJ的固定點(diǎn).

5 結(jié)束語(yǔ)

本文主要討論了術(shù)語(yǔ)定義中使用存在性限定和值限定算子，對(duì)于其他算子由于篇幅的原因未能分析.對(duì)于各種描述邏輯TBox中否定構(gòu)子的出現(xiàn)都可能會(huì)影響其是否具有模型，但否定存在有時(shí)也是必須的，而且其位置可以是任意的，下一步工作將對(duì)這一問(wè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).描述邏輯的動(dòng)態(tài)時(shí)序擴(kuò)展［J］.計(jì)算機(jī)應(yīng)用研究.2012，29(2):536-541.

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

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

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

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

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