反擬陣、凸幾何與伽羅瓦連接的關(guān)系及其應(yīng)用

王 剛，毛 華，武 秀

(1. 河北大學(xué) 生命科學(xué)學(xué)院 河北 保定 071002； 2. 河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河北 保定 071002)

0 引言

19世紀(jì)初凸幾何成為數(shù)學(xué)的一個(gè)獨(dú)立分支[1-2]。 伽羅瓦連接根基于伽羅瓦格理論[3]，而伽羅瓦格理論是形式概念分析(formal concept analysis，F(xiàn)CA)[4]的核心，每一對(duì)伽羅瓦連接與伽羅瓦格之間存在一一對(duì)應(yīng)。 一些研究人員已將凸幾何的方法應(yīng)用于FCA研究中[5]。 由于反擬陣與凸幾何之間有一一對(duì)應(yīng)關(guān)系[2]，使得研究凸幾何與伽羅瓦連接之間的關(guān)系，與研究反擬陣與伽羅瓦連接之間的關(guān)系具有一致性。 尋找更為有效的方法來(lái)構(gòu)造一個(gè)形式背景的伽羅瓦格，是FCA研究所面臨的問(wèn)題之一。 研究反擬陣或凸幾何與伽羅瓦連接的關(guān)系，是解決上述FCA問(wèn)題的基礎(chǔ)，也可將反擬陣和凸幾何加入到FCA研究中以得到新的結(jié)果， 這也是本文的主要研究目的。

雖然目前已經(jīng)有較多的生物分類方法，但將信息提取方法融入生物分類學(xué)[6]研究中是亟須解決的問(wèn)題之一。 本文將探索解決該問(wèn)題所需的基本理論，主要包括以下3項(xiàng)工作:(Ⅰ) 對(duì)于一個(gè)凸幾何(G,τ)，是否存在一個(gè)伽羅瓦連接(K,L)滿足LK=τ？若為是，這樣的(K,L)在映射相等的觀點(diǎn)下是否唯一?若不唯一，在何種思想下可以唯一？(Ⅱ) 對(duì)于一個(gè)伽羅瓦連接(K,L)，是否有一個(gè)凸幾何(G,τ)滿足τ=LK？若為否，則何時(shí)可為是?(Ⅲ) 對(duì)一個(gè)伽羅瓦連接(K,L)，給出一方法構(gòu)造反擬陣，且利用此方法判定(G,LK)的凸幾何性質(zhì)。此外，本文利用上述方法對(duì)一個(gè)生物信息系統(tǒng)實(shí)例進(jìn)行了分類。

1 一些定義和引理

本節(jié)將給出后續(xù)工作所需的一些基本定義和性質(zhì)，其他內(nèi)容如格論可參考文獻(xiàn)[7]，F(xiàn)CA可參考文獻(xiàn)[4]。 本文所有考慮均為有限的，2A代表集合A的所有子集族。

定義1[2，4](1) 若集合G上的一個(gè)函數(shù)τ: 2G→ 2G滿足：對(duì)于任意的A，B?G，有以下條件成立，①A?τ(A); ②A?B?τ(A)?τ(B); ③τ(τ(A))=τ(A)。則稱τ為閉包算子，稱固定點(diǎn)A=τ(A)為閉的。

(AE) 若閉包算子τ滿足條件反交換性：對(duì)任意的X?G,y,z∈G且y≠z, 有y,z?τ(X)且z∈τ(X∪y) ?y?τ(X∪z)，則稱(G,τ)為凸幾何。

(2) 令F?2G，若F滿足條件 (a1)：對(duì)于每個(gè)非空集合X∈F，一定存在一個(gè)x∈X滿足Xx∈F；以及(a2)：X,Y∈F?X∪Y∈F。 則稱(G,F)為集合G上的一個(gè)反擬陣。

(3) 稱格L為半模的，如果對(duì)于?x,y∈L都有：若y覆蓋x∧y，則必有x∨y覆蓋x。

注1閉包算子有多種定義方式，本文采用文獻(xiàn)[2]中相關(guān)定義。

引理1[2](1) 令N為集合G滿足如下性質(zhì)的子集族：①G∈N；②X,Y∈N?X∩Y∈N。 那么N產(chǎn)生如下算子：τ(A)=∩{X：A?X且X∈N}，τ(A)是N中包含有A的唯一的最小集，而τ是一個(gè)閉包算子。 反之，每一個(gè)閉包算子τ定義一個(gè)集族N，其中的元為τ的閉集，該集族滿足性質(zhì)①和②。

(2) 設(shè)F?2G且N={GX:X∈F}，τ是由N產(chǎn)生的閉包算子，則(G,F)為反擬陣?(G,τ)為凸幾何。

(3) 令F?2G滿足條件(a1)，則(G,F)為反擬陣當(dāng)且僅當(dāng)(F, ?)為半模格。

注2若集合系統(tǒng)(G,N)滿足引理1(1)中的①和②，且相應(yīng)的閉包算子滿足(AE)，則反擬陣和凸幾何之間存在一一對(duì)應(yīng)F?N={GX:X∈F}。 在此對(duì)偶概念下，凸幾何與反擬陣這兩個(gè)概念是完全等價(jià)的。

定義2[3]令G和M為兩個(gè)集合，Φ為G和M之間的二元關(guān)系，即Φ?G×M。 對(duì)于G的任意子集X，令K(X)={y∈M：對(duì)于所有x∈X，有(x,y)∈Φ}；對(duì)于M的任何子集Y，令L(Y)={x∈G: 對(duì)于所有y∈Y，有(x,y)∈Φ}。 則這一對(duì)映射(K,L)是G與M之間的一個(gè)伽羅瓦連接。

注3(1) 在文獻(xiàn)[4]中稱定義2中(G,M,Φ)為一個(gè)形式背景。對(duì)于(A,B)?(G,M)，若A=L(B)且B=K(A)，則稱(A,B)為一概念，A為概念(A,B)的外延，B為概念(A,B)的內(nèi)涵。 全體概念關(guān)于概念之間的泛化和例化關(guān)系構(gòu)成一個(gè)格，此格稱為(G,M,Φ)的伽羅瓦格，記為Gal(G,M,Φ)。

(2) 由定義2知，伽羅瓦連接(K,L)是由形式背景(G,M,Φ)產(chǎn)生的，而形式背景(G,M,Φ)是由(K,L)產(chǎn)生的。

引理2[3]令G和M為兩個(gè)集合，(K,L)為G和M之間的伽羅瓦連接。 那么映射LK是G上的一個(gè)閉包算子，KL是M上的一個(gè)閉包算子。

注4文獻(xiàn)[5]中定理5指出：對(duì)于一個(gè)伽羅瓦連接(f,g)，若想討論gf和fg的性質(zhì)，則僅需考慮gf和fg中的一個(gè)即可。 因此引理 2對(duì)于工作(Ⅰ)和(Ⅱ)是有意義的。

說(shuō)明1(1) 令(G,M,Φ)為一個(gè)形式背景，從文獻(xiàn)[4]發(fā)現(xiàn)有一個(gè)形式背景(G1,M1,Φ1)滿足L1K1(?)=?，其中G1=G{g: 對(duì)于任何的m∈M，有(g,m)∈Φ}，M1=M{m: 對(duì)于任何的g∈G，有(g,m)∈Φ}，并且對(duì)于任意的x∈G1和y∈M1，有(x,y)∈Φ1? (x,y)∈Φ。 此外(K1,L1)是由(G1,M1,Φ1)產(chǎn)生的。

(2) 由于Gal(G1,M1,Φ1)≌Gal(G,M,Φ)，故對(duì)于(G,M,Φ)的討論僅需研究(G1,M1,Φ1)[4]。

(3) 從文獻(xiàn)[4]以及上述內(nèi)容可知，即使有LK(?)=?的限制，也不會(huì)影響對(duì)伽羅瓦連接的討論。 同時(shí)，即使τ(?)=?，也不會(huì)影響對(duì)凸幾何的研究，故本文所有結(jié)果對(duì)凸幾何亦成立。

2 工作(Ⅰ)～(Ⅲ)

本節(jié)將給出伽羅瓦連接和凸幾何之間的關(guān)系，并且完成工作(Ⅰ)～(Ⅲ)。

首先，完成工作(Ⅰ)。

定理1設(shè)(G，τ)為一個(gè)凸幾何，

(1) 定義一個(gè)二元關(guān)系R?G×2G為(x,Y)∈R?Y=τ(Y)且x∈Y。 令(K，L)是由(G, 2G,R)產(chǎn)生的伽羅瓦連接，則LK=τ成立。

(2) 定義R2?G×M為(x,Y)∈R2?x∈Y, 且M={X?G:τ(X)=X}。 令(K2,L2)是由(G,M,R2)產(chǎn)生的伽羅瓦連接，則L2K2=τ成立。

證明先證明(1)。 由R的定義以及注3(1)可保證(G, 2G,R)為一個(gè)形式背景。 設(shè)X?G且N為τ的所有閉集構(gòu)成的集族，從定義2導(dǎo)出K(X)={Y∈2G: ?x∈X，(x,Y)∈R}={Y∈N：?x∈X，x∈Y}。 因此，對(duì)于?Y∈K(X)和?x∈X，必有(x,Y)∈R，也就是x∈Y。 這就導(dǎo)出X?Y，根據(jù)定義1(1)中的①和②可得X?τ(X)?τ(Y)=Y，故τ(X)∈K(X)。一方面，由定義2可知LK(X)={a∈G: ?Y∈K(X), (a,Y)∈R}。 運(yùn)用τ(X)∈K(X)導(dǎo)出對(duì)任意的a∈LK(X)，必有(a,τ(X))∈R，即a∈τ(X)，故得LK(X)?τ(X)。 另一方面，對(duì)任意的Y∈K(X)，τ(X)?Y表明對(duì)任意的z∈τ(X)，必有z∈Y成立，即(z，Y)∈R。 進(jìn)一步地，z∈LK(X)成立，亦即τ(X)?LK(X)。 總之有LK=τ成立。

再證明(2)。 利用(1)的證明并結(jié)合R2的定義，則可得L2K2=τ成立。

定理1解決了對(duì)一個(gè)凸幾何(G,τ)，存在一個(gè)伽羅瓦連接(K,L)滿足LK=τ的問(wèn)題，同時(shí)發(fā)現(xiàn)(K,L)在通常映射相等的觀點(diǎn)下不唯一。 依據(jù)數(shù)學(xué)理論觀點(diǎn)，同構(gòu)意義下的數(shù)學(xué)結(jié)構(gòu)視為同一個(gè)結(jié)構(gòu)。 因此，考慮在何種同構(gòu)思想下，這樣的(K,L)能夠唯一。 為此，給出定義3。

定義3設(shè)(Oj,Pj,Rj)為一個(gè)形式背景，并且對(duì)應(yīng)的伽羅瓦連接為(Kj,Lj)(j=1, 2)。 若存在一個(gè)雙射π：O1→O2滿足條件：對(duì)于任意的X?O1，X=L1K1(X) ?πX=L2K2(πX)，則

(1) (K1,L1)是伽羅瓦同構(gòu)于(K2,L2);

(2) 稱π為一個(gè)(K1,L1)和(K2,L2)之間的伽羅瓦同構(gòu)映射。

注5將定義3與文獻(xiàn)[4]中定義86進(jìn)行比較得出：伽羅瓦同構(gòu)是比兩個(gè)形式背景之間的同構(gòu)定義要弱的一種映射形式，即定義3在適用范圍方面要比兩個(gè)形式背景之間的同構(gòu)更為廣泛。

定理2設(shè)(G,τ)為一個(gè)凸幾何， 則在伽羅瓦同構(gòu)意義下，存在且僅存在唯一一個(gè)伽羅瓦連接(K,L)滿足LK=τ。

證明由定理1和定義3可得定理2。

說(shuō)明2對(duì)于凸幾何(G,τ), 定理1以構(gòu)造方式發(fā)現(xiàn)一個(gè)伽羅瓦連接(K,L)使其滿足LK=τ。 定理 2 保證了在伽羅瓦同構(gòu)意義下(K,L)的唯一性。

其次，完成工作(Ⅱ)。

令(K,L)為集合G和M之間的一個(gè)伽羅瓦連接，以及有G上的一個(gè)伽羅瓦連接τ，是否有LK=τ?例1給出一個(gè)否定的回答。

例1設(shè)k為一個(gè)正整數(shù)并且I={X?G: |X|≤k}，由文獻(xiàn)[8]第10頁(yè)知(G,I)為擬陣。 根據(jù)文獻(xiàn)[8]第8頁(yè)定理4知：(G,I)的閉包算子σ滿足定義1(1)的條件，并且當(dāng)|X|≤k-1時(shí)，有σ(X)=X；當(dāng)|X|≥k時(shí)，有σ(X)=G。

設(shè)X?G且|X|=k-1,選取y,z∈GX且y≠z,則有σ(X)=X, 以及X∪y，X∪z?G和|X∪y|=|X∪z|=k。 因此σ(X∪y)=σ(X∪z)=G，從而z∈G=σ(X∪y)和y∈σ(X∪z)。 故σ不滿足條件(AE)，即(G,σ)不是凸幾何。 定義R?G×2G為(x，Y)∈R?Y=σ(Y)且x∈Y， 可以證明，由(G, 2G,R)產(chǎn)生的伽羅瓦連接(K,L)滿足LK=σ。 對(duì)任意凸幾何(G,τ)，因τ不一定為σ，故不一定有LK=τ。

下面給出LK=σ成立的證明。

從LK?σ和σ?LK兩個(gè)方面加以證明。令X?G， 一方面，因?yàn)镵(X)={Y∈2G: ?x∈X，(x，Y)∈R}={Y: ?x∈X，x∈Y=σ(Y)}，可導(dǎo)出X?Y=σ(Y)，故X?σ(X)?σ(Y)=σ(σ(Y))=Y成立，因此σ(X)∈K(X)。 由于LK(X)={a∈G: ?Y∈K(X)，(a，Y)∈R}，并且結(jié)合σ(X)∈K(X)導(dǎo)出，對(duì)于任意的a∈LK(X) 必有(a，σ(X))∈R，即a∈σ(X),從而LK(X)?σ(X)成立。 另一方面，對(duì)任意的Y∈K(X)，σ(X)?Y表明對(duì)于任意的b∈σ(X)，必有b∈Y成立，即(b,Y)∈R。 因此，b∈LK(X)是正確的,從而σ(X)?LK(X)成立。

定理3將給出在什么條件下，一個(gè)伽羅瓦連接(K,L)和凸幾何(G,τ)滿足LK=τ。

定理3令(K,L)為G和M之間的一個(gè)伽羅瓦連接,

(1)LK滿足條件(AE)當(dāng)且僅當(dāng)存在一個(gè)凸幾何(G,τ)滿足LK=τ。

(2) 設(shè)F={GY:Y=LK(Y)},F滿足定義1(2)中的(a1)，并且(F, ?)是一個(gè)半模格當(dāng)且僅當(dāng)(G,LK)是一個(gè)凸幾何。

證明由引理2和定義1易得(1)。由引理1易證明(2)。

再者，完成工作(Ⅲ)。

定理3可以發(fā)現(xiàn)在什么條件下一個(gè)伽羅瓦連接(K,L)對(duì)應(yīng)一個(gè)凸幾何，但可惜不是用構(gòu)造性方法。 下文將用構(gòu)造性方法確定(G,LK)的凸幾何性質(zhì)。 由引理 1及注2知：(G,LK)的凸幾何性質(zhì)是由(G, {Y?G:Y=LK(Y)})在反擬陣方面的性質(zhì)所決定的。 故給出判定一個(gè)伽羅瓦連接產(chǎn)生凸幾何性質(zhì)的方法，其思路如下：令 (K,L)為集合G和M之間的一個(gè)伽羅瓦連接，以及F={GY:Y=LK(Y)}。 設(shè)(G,M,R)為由(K,L)產(chǎn)生的形式背景，從文獻(xiàn)[4]可得如下陳述:

(1) 在伽羅瓦連接集合與形式背景集合之間存在一一對(duì)應(yīng)關(guān)系; 在形式背景集合與伽羅瓦格集合之間存在一一映射。

(2) 設(shè)B(G)={A?G: 存在B?M使得(A,B)∈Gal(G,M,R)}，則格(B(G), ?)同構(gòu)于Gal(G,M,R)。

(3) 設(shè)B(LK)={Y:Y=LK(Y)}，則B(G)=B(LK)。

(4) 有許多構(gòu)造B(G) 或(B(G), ?) 的方法。

陳述(1)～(4)意味著F={GY:Y∈B(LK)}可選任意構(gòu)造B(G)的方法[4]，用于尋找出F，進(jìn)一步地，找到(F, ?)。 同時(shí)，在FCA中一些構(gòu)造B(G)的算法可以用于構(gòu)造(B(G), ?)的Hasse圖。 如果使用這些算法，由于(F, ?)是(B(G), ?)的對(duì)偶，則可以構(gòu)造出(F, ?)的Hasse圖。 從(F, ?)的Hasse圖中可以很容易地確定(F, ?)的半模性，進(jìn)而可以判定(F, ?)是否為一個(gè)反擬陣。 文獻(xiàn)[9]給出一些判定一個(gè)結(jié)構(gòu)為反擬陣的算法，也可以用這些算法判定(F, ?)的反擬陣性質(zhì)。 同時(shí)，(G,LK)的凸幾何性質(zhì)也可以利用引理1加以判斷。

3 應(yīng)用舉例

本節(jié)用一個(gè)實(shí)例說(shuō)明上述一些結(jié)論的具體應(yīng)用。

例2給定原始生物信息系統(tǒng)(O1,P1,R1)，其中O1={紡織娘1，紡織娘2，紡織娘3},P1={體長(zhǎng)，翅長(zhǎng)，翅寬，前胸背板長(zhǎng)，前胸背板高}, 生物信息背景R1如表1所示。 根據(jù)文獻(xiàn)[10]的操作過(guò)程，可以將表1轉(zhuǎn)化為如表2所示的二元化生物信息背景。表2中的1表示該行的生物個(gè)體擁有對(duì)應(yīng)該列的生物特征，0表示該行的生物個(gè)體不擁有對(duì)應(yīng)該列的生物特征。

表1 生物信息背景Table 1 Biological information context cm

表2 二元化生物信息背景Table 2 Binary biological information context

若令紡織娘1為a, 紡織娘2為b, 紡織娘3為c, 體長(zhǎng)為e1，翅長(zhǎng)為e2，翅寬為e3，前胸背板長(zhǎng)為e4，前胸背板高為e5, 則可以得到與表2對(duì)應(yīng)的形式背景(O2,P2,R2)的數(shù)學(xué)表示，如表3所示。利用文獻(xiàn)[4]中的方法，可以生成與表3對(duì)應(yīng)的伽羅瓦格，如圖1所示。 為簡(jiǎn)潔起見(jiàn)，將{X}簡(jiǎn)記為X，其中{X}?O2或者{X}?P2。

圖1 表3生成的伽羅瓦格Figure 1 Galois lattice produced by Table 3

表3 二元化生物信息背景的數(shù)學(xué)表示Table 3 Mathematical representation of binary biological information context

如果令F={, {a,b}, {a,b,c}}, 利用定義1 (3)易知(F, ?)是一個(gè)半模格，再利用引理1知(O2,F)為一個(gè)反擬陣。 事實(shí)上，依據(jù)表1～3的關(guān)系以及生物形態(tài)學(xué)知識(shí)可知，(b,e1e2e3e4e5)表示紡織娘2擁有5個(gè)生物特征e1、e2、e3、e4、e5；(ab,e1e2e3e5)中的ab在(F, ?)中滿足{a,b}覆蓋，該特點(diǎn)表明{a,b}中的元，即紡織娘1具有紡織娘2的祖先特征，這幾個(gè)特征是e1、e2、e3和e5。 在(F, ?)中{a,b,c}覆蓋{a,b}表明{a,b,c}{a,b}中的元，即紡織娘3具有紡織娘1和紡織娘2的祖先特征，這些特征是e2和e3。 原始生物信息背景的生物特征分析樹(shù)狀結(jié)構(gòu)如圖2所示。 此處，N={{a,b,c}X:X∈F}={{a,c}, {c},?}，產(chǎn)生的閉包算子τ為τ(A)=∩{Y:A?Y且Y∈N}，滿足τ(?)=τ({a,b})=τ({b,c})=τ()=τ({a,b,c})=?,τ({a})=τ({a,c})={a,c},τ({c})={c}。 由上面討論和引理1(2)可以得到({a,b,c},τ)是一個(gè)凸幾何。

圖2 原始生物信息背景的生物特征分析樹(shù)狀結(jié)構(gòu)Figure 2 Tree structure of biological characteristic analysis for raw biological information context

注6例2表明，在一個(gè)生物信息系統(tǒng)組成的形式背景(G,M,Φ)中，G是生物個(gè)體集合，M是生物特征集合，Φ?G×M。 若令F?2G, 在(F, ?)中，對(duì)于任意的x,y∈F, 當(dāng)x覆蓋x∧y, 則表明生物集合x(chóng)x∧y中的生物個(gè)體擁有生物群體x∧y的祖先特征。 如果(F, ?)為一個(gè)半模格，那么x∨yy中的生物個(gè)體都擁有生物群體y的祖先特征。 這一推測(cè)對(duì)于生物的系統(tǒng)發(fā)育問(wèn)題會(huì)有所幫助，也顯示出考慮半模格的優(yōu)勢(shì)所在。

即使(F, ?)不為半模格，也可以借用半模格的性質(zhì)進(jìn)行討論。 對(duì)于任意的x,y∈F, 下文將根據(jù)x,y之間的關(guān)系，分成狀態(tài)1～3研究擁有x與y的祖先特征問(wèn)題。

狀態(tài)1設(shè)x,y在(F, ?)中可比較，不妨設(shè)在(F, ?)中x

狀態(tài)2設(shè)x,y在(F, ?)中不可比較，分以下3種情況進(jìn)行討論。

情況1 在(F, ?)中x,y無(wú)公共上界。

該情況表明在(F, ?)中x,y無(wú)共同的祖先特征。

情況2 在(F, ?)中x,y有唯一的公共上界x∨y。

① 設(shè)從y到x∨y的極大鏈為{y,yi1,…,yi(mi-1),x∨y}(i=1,2,…,ny)。

情況3 在(F, ?)中x,y有不唯一的公共上界(xy)1,…,(xy)t(t>1)。

對(duì)于每一個(gè)(xy)i, 重復(fù)情況2，可以得到相應(yīng)的Ai和Bi(i=1,2，…,t)。 利用凸幾何的閉包算子和伽羅瓦連接的產(chǎn)生過(guò)程，這時(shí)如果在(F, ?)中存在包含有A1∪…∪At的最小元C，則C中的元擁有x和y的祖先特征B1∩…∩Bt。 如果這樣的C不存在，則也說(shuō)明Ai擁有x和y的祖先特征。

對(duì)上述情況分析如下：① 對(duì)于情況2和情況3中存在C，這時(shí)關(guān)于x和y與x∨y或C產(chǎn)生的生物特征分析的樹(shù)狀結(jié)構(gòu)圖是有根樹(shù)；對(duì)于情況3中不存在C，這時(shí)關(guān)于x和y以及(xy)1,…,(xy)t產(chǎn)生的生物特征分析的樹(shù)狀結(jié)構(gòu)圖是無(wú)根樹(shù)。 對(duì)于情況1，此時(shí)與x和y有關(guān)的生物特征分析的樹(shù)狀結(jié)構(gòu)圖是無(wú)根樹(shù)。 ② 三種情況的討論完全是依據(jù)偏序集理論和格論，以及伽羅瓦連接的思想進(jìn)行的，并無(wú)任何其他推測(cè)，所以可以保證結(jié)果在數(shù)學(xué)理論方面的正確性。 由于遍歷了所有可能的結(jié)果，因此從生物分類角度而言也是可行和可信的。

狀態(tài)3設(shè)x,y在(F, ?)中不可比較， 對(duì)于狀態(tài)2的情況1，由于結(jié)論簡(jiǎn)單，這里不再討論。 對(duì)于狀態(tài)2的其他兩種情況，給出一種不同于狀態(tài)2的求法，分以下兩部分進(jìn)行討論。

第1部分：對(duì)于狀態(tài)2中的情況2，分兩種子情況加以討論。

子情況1 (F，?)中兩個(gè)元x,y的關(guān)系見(jiàn)圖3， 其中的實(shí)線表示覆蓋關(guān)系，虛線表示兩個(gè)元之間有鏈關(guān)系。 求取x∨y與x和y的祖先特征關(guān)系的思路如下。

圖3 (F,?)中兩個(gè)元x, y的關(guān)系Figure 3 Relationship between two elements x and y in (F,?)

第1步 將x1視為一個(gè)外群個(gè)體集合，將x1與yj(j=1,…,m-1,m)之間分別做假設(shè)的連線，此處做實(shí)線，并且x∨y=ym。

第2步 ({x∧y,x1,y,y1}, ?)構(gòu)成一個(gè)半模格，利用半模性推測(cè)出y1(x1∪y)具有的x1和y的哪些祖先特征，事實(shí)上，若用z′表示生物個(gè)體z的生物特征集合，則這些特征是x′1∩y′, 將所得y1與x1和y的那些祖先特征與y′1求交集，替換掉y1原先具有的生物特征。

第3步 令y=y1,y1=y2, 重復(fù)第1、2步。 由于采用的生物樣本的有限性，導(dǎo)致了所考慮的生物個(gè)體集合的有限性。 也就是經(jīng)過(guò)m次重復(fù), 一定可以推測(cè)出x∨yym-1具有的x1和ym-1的可能祖先特征。

第4步 令x1=x2, 重復(fù)第1～3步，由于x∨y的有限性，可知x1,…,xn-1的有限性，如此經(jīng)過(guò)n次重復(fù)，可以得到x∨yym-1具有的x和ym-1的可能祖先特征。

第5步 由于考慮{x∧y,xi,yj,y}的可能祖先特征關(guān)系時(shí)，得到的是yjy具有xi(i=1,…,n-1,n;j=1,…,m-1,m)和y的可能的祖先特征，其中x=xn，x∨y=ym。 將所有這些祖先特征集合求交集，推測(cè)出x∨y(x∪y)具有的x和y的一些祖先特征，此處是利用伽羅瓦連接與凸幾何運(yùn)算的定義推測(cè)的。

對(duì)子情況1分析如下：① 在第1步中做假設(shè)的連線是可行的，因?yàn)樵谙到y(tǒng)發(fā)育分析時(shí)，有時(shí)是允許假設(shè)一個(gè)外群，例如做系統(tǒng)發(fā)育分析時(shí)常用的Hennig方法[11]。 ② 從對(duì)應(yīng)的思路過(guò)程可以看出，x∧y在求得最后結(jié)果的過(guò)程中幾乎沒(méi)有作用。 如果x∧y不存在時(shí)，可以假設(shè)一個(gè)下界，不妨設(shè)?∈F，這是由于?′=M，所以在上述過(guò)程中，所有結(jié)果均不受影響。

子情況2 若x和y之間有唯一上界x∨y，但是從y到x∨y，以及從x到x∨y的極大鏈不一定是唯一的，則對(duì)于每對(duì)從y到x∨y的極大鏈和從?到x的極大鏈，重復(fù)子情況1，類似狀態(tài)2中情況2的④，可以得到所需的祖先特征關(guān)系。

第2部分：對(duì)于狀態(tài)2中的情況3進(jìn)行討論。

對(duì)于每個(gè)x和y的上界，重復(fù)第1部分，其他類似狀態(tài)2中情況3的討論。

需要說(shuō)明的是：① 狀態(tài)2和狀態(tài)3只是理論上的方法和想法，還需具體的算法實(shí)現(xiàn)以及生物分類實(shí)踐的檢驗(yàn)，并與已有方法進(jìn)行比對(duì)，這些研究將在后續(xù)工作中進(jìn)行。② 雖然Gal(G,M,Φ)的外延全體(GalG(G,M,Φ), ?)不一定是半模的，但是在某些情況下，比如例2的情況，或者只考慮(GalG(G,M,Φ), ?)部分時(shí)，有可能是半模的，這樣利用反擬陣的性質(zhì)[2]可以很快地解決所要討論的問(wèn)題。 另外，如果需要考慮N={GX:x∈GalG(G,M,Φ)}的情況，則可以利用凸幾何的性質(zhì)[1]迅速地發(fā)現(xiàn)所需答案。 再有，上面的討論是GalG(G,M,Φ)，事實(shí)上，由伽羅瓦連接與反擬陣和凸幾何的關(guān)系可知，不一定用(G,M,Φ)的伽羅瓦格，可更為一般化地用伽羅瓦連接討論一個(gè)生物信息組成的形式背景中生物個(gè)體集合之間的關(guān)系。

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

本文借助反擬陣討論凸幾何與伽羅瓦連接之間的關(guān)系，利用凸幾何與反擬陣之間的對(duì)應(yīng)關(guān)系，以及FCA中伽羅瓦連接與伽羅瓦格的聯(lián)系、伽羅瓦格與反擬陣的半模性的聯(lián)系，得到判定一個(gè)伽羅瓦連接產(chǎn)生的幾何是否為凸幾何的方法，該方法為用反擬陣和凸幾何方法研究FCA提供了思路。 未來(lái)將嘗試進(jìn)一步地發(fā)展和實(shí)現(xiàn)這些想法和思路。