Domain理論及Rough集理論若干相關問題研究.pdf

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

2、ain理論建立的初衷是為高級程序設計語言的指稱語義學提供數學基礎，序和拓撲的相互結合、相互作用是其基本特征，正因如此，Domain理論成為計算機科學家和數學家共同關心的領域．事實上，除了在計算機科學方面作為形式語義學的數學基礎或數學框架、賦予或解釋語句語義，以及應用于人工智能(AI)中知識表示及推理(KRR)、數據分析等方面之外，在若干數學分支如動力系統、分形、拓撲等方面，Domain也是一種重要的數學結構；例如，Domain環(huán)境便從序

3、與拓撲交融的角度為某些拓撲空間提供了一種計算模型．另一方面，Rough集理論創(chuàng)立的目的是為處理含糊不清(vague)的概念或數據提供一個有力的數學工具，但其理論基礎，依然建立在數學中的經典分支如集合論、拓撲、邏輯、代數、序結構理論之上．經過二十多年的發(fā)展，Rough集方法已被廣泛應用于AI和認知科學中，尤其是在數據分析、知識表示、知識發(fā)現、機器學習、決策分析、專家系統、模式識別等領域。 作為兩個數學分支， Domain理論與Ro

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

5、問題，在Rough集方面，研究了近似算子的刻畫及相關范疇問題，最后建立了Domain理論與Rough集理論之間深入的內在聯系．具體而言，我們作了如下工作：首先，我們對Domain理論中與此相關的3個公開問題進行討論。 第一個公開問題事實上由Mislove和Lawson在拓撲學名著《Open Prob— lems in Topology》中提出的兩個關于對偶拓撲的公開問題組成：哪些拓撲它們同時也是對偶拓撲?如果對一個拓撲連續(xù)取對偶

6、，作用有限次后所產生的拓撲之中有互為對偶的嗎?對該問題，我們討論了兩類經典的拓撲即Hausdorff拓撲與Scott拓撲的相關問題。對任意Ha，usdorff空間(X，T)，有T<'d>=T<'ddd>，對T反復取對偶，連同T本身至多產生3個不同的拓撲：T、T<'d>和T<'dd>，由此，我們對所有Hausdorff空間做了一個分類，即三個嚴格遞增的類，然后刻畫了滿足T=T<'dd>的Hausdorff空間。事實上，滿足T=T<'dd>

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

8、'dd> σ(D)，進而對應于Hausdorff拓撲情形給出了σ(D)=σ(D)<'dd>的一個內在刻畫，并借助于若干具體的例子討論了σ(D)與σ(D)<'dd>之間的關系．這些結果對上述公開問題在．Hausdorff拓撲與Scott拓撲這兩類最受關注的重要情形下作了部分回答． 第二、三個公開問題都相關于有限偏序集的Cartesian積．其中，第二個公開問題是Plotkin于1978年在文[90]中提出的如下猜想：對于三元真值d

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

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

11、學模型的考慮，基于Scott的前述結論，Mis—love和Lawson在[55]中更進一步提出如下公開問題即本文的第三個問題：更為一般的拓撲空間在積和收縮的作用下產生的最小封閉類具有什么性質?具體地，若選擇一族有限T<,0>空間作為生成空間，會產生什么樣的空間類?它是Cartesian Closed的嗎?事實上，有限T<,0>空間恰為賦Scott拓撲的有限偏序集，因此，該公開問題中的有限T<,0>空間可直接換為有限偏序集．對該問題，我們

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

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

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

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

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

17、上下文(U，V,|=)，當屬性集V有限時，其面向對象的Rough概念恰和相應導出信息系統的狀態(tài)一致。一般地，對無限情形，我們在Rough概念格中引入逼近結構，定義了Rough可逼近概念，得到任何形式上下文的Rough可逼近概念和相應導出信息系統的狀態(tài)一致，然后構造了Rough集框架下的Domain結構，并給出完備代數格的Rough可逼近概念格表示。以上結果不僅建立了Domain理論和Rough集理論之間深人的內在聯系，而且也表明了Dom