Domain理論及Rough集理論若干相關(guān)問題研究.pdf

1、隨著計(jì)算機(jī)科學(xué)的飛速發(fā)展，有關(guān)計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)研究越來越受到人們的關(guān)注和重視，已成為數(shù)學(xué)和計(jì)算機(jī)科學(xué)研究者共同感興趣的領(lǐng)域。產(chǎn)生于上個(gè)世紀(jì)70年代初的Domain理論和80年代初的Rough集理論正是這樣兩個(gè)重要交叉領(lǐng)域．它們獨(dú)立發(fā)展，但從共同的數(shù)學(xué)基礎(chǔ)來看，二者均基于數(shù)學(xué)中三大基本結(jié)構(gòu)之一的序結(jié)構(gòu)理論，同時(shí)與拓?fù)?、代?shù)、范疇、邏輯等學(xué)科有著密切的聯(lián)系。 它們的提出都有較強(qiáng)的計(jì)算機(jī)背景，但同時(shí)也是數(shù)學(xué)發(fā)展的需要．其中，Dom

2、ain理論建立的初衷是為高級程序設(shè)計(jì)語言的指稱語義學(xué)提供數(shù)學(xué)基礎(chǔ)，序和拓?fù)涞南嗷ソY(jié)合、相互作用是其基本特征，正因如此，Domain理論成為計(jì)算機(jī)科學(xué)家和數(shù)學(xué)家共同關(guān)心的領(lǐng)域．事實(shí)上，除了在計(jì)算機(jī)科學(xué)方面作為形式語義學(xué)的數(shù)學(xué)基礎(chǔ)或數(shù)學(xué)框架、賦予或解釋語句語義，以及應(yīng)用于人工智能(AI)中知識表示及推理(KRR)、數(shù)據(jù)分析等方面之外，在若干數(shù)學(xué)分支如動力系統(tǒng)、分形、拓?fù)涞确矫?，Domain也是一種重要的數(shù)學(xué)結(jié)構(gòu)；例如，Domain環(huán)境便從序

3、與拓?fù)浣蝗诘慕嵌葹槟承┩負(fù)淇臻g提供了一種計(jì)算模型．另一方面，Rough集理論創(chuàng)立的目的是為處理含糊不清(vague)的概念或數(shù)據(jù)提供一個(gè)有力的數(shù)學(xué)工具，但其理論基礎(chǔ)，依然建立在數(shù)學(xué)中的經(jīng)典分支如集合論、拓?fù)?、邏輯、代?shù)、序結(jié)構(gòu)理論之上．經(jīng)過二十多年的發(fā)展，Rough集方法已被廣泛應(yīng)用于AI和認(rèn)知科學(xué)中，尤其是在數(shù)據(jù)分析、知識表示、知識發(fā)現(xiàn)、機(jī)器學(xué)習(xí)、決策分析、專家系統(tǒng)、模式識別等領(lǐng)域。 作為兩個(gè)數(shù)學(xué)分支， Domain理論與Ro

4、ugh集理論有著各自不同的研究對象和特點(diǎn)，但它們的研究都是在序結(jié)構(gòu)的框架下進(jìn)行的，在某些方面相互滲透和相互影響．本文的主旨也就是對Domain理論與Rough集理論在這些方面的共同數(shù)學(xué)基礎(chǔ)特別是序結(jié)構(gòu)方面進(jìn)行討論．文中我們運(yùn)用拓?fù)?、序結(jié)構(gòu)、代數(shù)、范疇及邏輯的理論和方法，在Domain方面，研究了兩類最受關(guān)注的拓?fù)?Hausdorff拓?fù)?、Scott拓?fù)?的對偶拓?fù)?、有限偏序集的Cartesian積、積的收縮、相關(guān)范疇和Domain方程等

5、問題，在Rough集方面，研究了近似算子的刻畫及相關(guān)范疇問題，最后建立了Domain理論與Rough集理論之間深入的內(nèi)在聯(lián)系．具體而言，我們作了如下工作：首先，我們對Domain理論中與此相關(guān)的3個(gè)公開問題進(jìn)行討論。 第一個(gè)公開問題事實(shí)上由Mislove和Lawson在拓?fù)鋵W(xué)名著《Open Prob— lems in Topology》中提出的兩個(gè)關(guān)于對偶拓?fù)涞墓_問題組成：哪些拓?fù)渌鼈兺瑫r(shí)也是對偶拓?fù)?如果對一個(gè)拓?fù)溥B續(xù)取對偶

6、，作用有限次后所產(chǎn)生的拓?fù)渲杏谢閷ε嫉膯?對該問題，我們討論了兩類經(jīng)典的拓?fù)浼碒ausdorff拓?fù)渑cScott拓?fù)涞南嚓P(guān)問題。對任意Ha，usdorff空間(X，T)，有T<'d>=T<'ddd>，對T反復(fù)取對偶，連同T本身至多產(chǎn)生3個(gè)不同的拓?fù)洌篢、T<'d>和T<'dd>，由此，我們對所有Hausdorff空間做了一個(gè)分類，即三個(gè)嚴(yán)格遞增的類，然后刻畫了滿足T=T<'dd>的Hausdorff空間。事實(shí)上，滿足T=T<'dd>

7、的Hausdorff空間(X，T)恰為Hausdorff k-空間．此外，我們研究了對偶拓?fù)渑c原拓?fù)渲g的關(guān)系，為解決公開問題提供了一些可行的思路．另一方面，對Scott拓?fù)?，我們的研究對象是定向完備偏序?dcpo)D，其上Scott拓?fù)溆洖棣?D)，我們給出了σ(D)<'d>=ω(D)的刻畫及其成立的一個(gè)較廣泛的充分條件，研究了σ(D)<'d>=ω(D)與Scott緊集、強(qiáng)緊集之間的關(guān)系．此外，我們證明了對任何dcpoD有σ(D)<

8、'dd> σ(D)，進(jìn)而對應(yīng)于Hausdorff拓?fù)淝樾谓o出了σ(D)=σ(D)<'dd>的一個(gè)內(nèi)在刻畫，并借助于若干具體的例子討論了σ(D)與σ(D)<'dd>之間的關(guān)系．這些結(jié)果對上述公開問題在．Hausdorff拓?fù)渑cScott拓?fù)溥@兩類最受關(guān)注的重要情形下作了部分回答． 第二、三個(gè)公開問題都相關(guān)于有限偏序集的Cartesian積．其中，第二個(gè)公開問題是Plotkin于1978年在文[90]中提出的如下猜想：對于三元真值d

9、cpo T及任一基數(shù)k>ω，函數(shù)空間[T<'k>→T<'k>]不是T<'k>的收縮．我們知道Scott曾于1976年證明了具有可數(shù)基的連續(xù)格恰為2<'ω>的一個(gè)收縮以及更一般地，任一連續(xù)格恰為2的某個(gè)積的收縮[97]；隨后，Plotkin于1978年證明了具有可數(shù)基的coherent domain(即兩兩相容的子集必有上確界的domain)恰為T<'ω>的收縮．然而，該結(jié)果若要推廣至不可數(shù)情形，則有難以逾越的障礙，這正是Plotkin提

10、出上述猜想的原因．文中我們構(gòu)造性地證明了該猜想．這個(gè)結(jié)果不僅給出了T<'k>這個(gè)基本生成結(jié)構(gòu)在拓?fù)渑c序結(jié)構(gòu)理論方面的一個(gè)重要性質(zhì)，而且，在計(jì)算機(jī)科學(xué)中的形式語義學(xué)方面，它指出了這樣一個(gè)事實(shí)：對k>ω，T<'k>不能作為任何程序設(shè)計(jì)語言的指稱語義模型；其意義在于：對于形式語義學(xué)中包涵較連續(xù)格更為廣泛的基本生成結(jié)構(gòu)T<'k>，澄清了由其生成的colaerent domain作為指稱語義模型在理論上的界限． 類似地，作為對形式語義學(xué)數(shù)

11、學(xué)模型的考慮，基于Scott的前述結(jié)論，Mis—love和Lawson在[55]中更進(jìn)一步提出如下公開問題即本文的第三個(gè)問題：更為一般的拓?fù)淇臻g在積和收縮的作用下產(chǎn)生的最小封閉類具有什么性質(zhì)?具體地，若選擇一族有限T<,0>空間作為生成空間，會產(chǎn)生什么樣的空間類?它是Cartesian Closed的嗎?事實(shí)上，有限T<,0>空間恰為賦Scott拓?fù)涞挠邢奁蚣虼?，該公開問題中的有限T<,0>空間可直接換為有限偏序集．對該問題，我們

12、具體討論了生成的空間含T的任何一族有限偏序集(具有最小元)F，F(xiàn)在積和收縮的作用下產(chǎn)生的最小封閉類不是Cartesian Closed的，從而說明了： 在由任何一族非平凡有限偏序集作為生成空間在積和收縮的作用下產(chǎn)生的最小封閉類中，(1)連續(xù)格范疇是其最小的關(guān)于任意積和收縮封閉的Cartesian Closed滿子范疇，(2)若生成空間中每一個(gè)對象均為有限L—domain，則連續(xù)格范疇是其唯一的關(guān)于任意積和收縮封閉的Cartesi

13、an Closed滿子范疇。 綜上，我們澄清了Domain理論中關(guān)于對偶拓?fù)?、有限偏序集所生成的空間及相關(guān)范疇的一些疑問。 本文另一工作是研究Rough集理論中與序結(jié)構(gòu)相關(guān)的2個(gè)問題．正如前面所提到的， Rough集理論與Domain理論一樣具有知識表示及推理、數(shù)據(jù)分析等功能，而其中所用到的核心概念是近似算子(approxinlation operator)。首先，我們從整體角度刻畫該理論中的近似算子，然后，進(jìn)一步從范疇

14、角度考慮所有近似空間。 對一個(gè)近似空間(U,R)，由于上、下近似算子從整體看是對偶的，所以我們主要討論了上近似算子在R為各種可能關(guān)系情形下的刻畫．這些刻畫表明了Rough集理論與序結(jié)構(gòu)理論之間的密切聯(lián)系，同時(shí)我們得到了該算子的一些重要而新穎的性質(zhì)．另一方面，基于前述刻畫及應(yīng)用之需，我們建立了近似空間與完備原子布爾格、素代數(shù)格之間的聯(lián)系，從不同知識間關(guān)系的角度，定義了近似空間范疇AS<,E>用范疇的語言(構(gòu)造)解釋了對信息系統(tǒng)的不

15、同處理。比如，pullback可用來解釋兩個(gè)或兩個(gè)以上源信息系統(tǒng)的融合；pushout可用來解釋兩個(gè)或兩個(gè)以上源信息系統(tǒng)的共有的背景知識．在Rough集理論中引入范疇打破了原有的對知識處理的單一的方式，從范疇層次對已有的相關(guān)或不相關(guān)的知識進(jìn)行處理。以上對近似算子的刻畫以及引入范疇理論為Rough集的研究提供了一個(gè)新的途徑。 最后，我們從Domain理論與Rough集理論共有的知識表示及推理功能的角度，借助于形式概念分析的方法，在

16、概念格這個(gè)共同的基點(diǎn)上，通過模態(tài)算子◇和□構(gòu)成的Galois聯(lián)絡(luò)以及引入逼近結(jié)構(gòu)，在兩個(gè)理論之間建立了深入的內(nèi)在聯(lián)系。具體而言，我們通過Galois聯(lián)絡(luò)討論了Rough集理論中已有的兩種概念格結(jié)構(gòu)，并將其推廣至無窮情形，得出在Rough集框架下的完備格的概念格表示，由此說明了：Rough集框架下的概念格與標(biāo)準(zhǔn)的概念格具有同等的表達(dá)力．然后，從邏輯的角度，我們討論了Rough概念格與信息系統(tǒng)(由Scott定義)之間的聯(lián)系，證明了對任何形式

17、上下文(U，V,|=)，當(dāng)屬性集V有限時(shí)，其面向?qū)ο蟮腞ough概念恰和相應(yīng)導(dǎo)出信息系統(tǒng)的狀態(tài)一致。一般地，對無限情形，我們在Rough概念格中引入逼近結(jié)構(gòu)，定義了Rough可逼近概念，得到任何形式上下文的Rough可逼近概念和相應(yīng)導(dǎo)出信息系統(tǒng)的狀態(tài)一致，然后構(gòu)造了Rough集框架下的Domain結(jié)構(gòu)，并給出完備代數(shù)格的Rough可逼近概念格表示。以上結(jié)果不僅建立了Domain理論和Rough集理論之間深人的內(nèi)在聯(lián)系，而且也表明了Dom