王思雨, 羅從文

(三峽大學 理學院, 湖北 宜昌 443002)

0 引言

概念格作為形式概念分析的核心數據結構,能夠用來進行分類、聚類和提取規(guī)則. Ganter等[1]首先提出了塊關系和容差關系的概念,容差關系描述了概念格中概念的歸類和劃分關系,而塊關系反映了形式背景經過變換后形成的概念格中的外延與內涵仍然是原背景中的.已經證明了有一個塊關系就存在一個容差關系與之對應,即形式背景的塊關系構成的格同構于概念格的容差關系構成的格. 由容差關系可以誘導出商格,得到的商格同構于塊關系的概念格. Konecny等[2]將塊關系的概念推廣到模糊集上,得到塊L-關系和完全L-容差的概念,證明了塊L-關系的L-集合與完全L-容差的L-集合同構. 楊凱等[3]運用容差關系和塊關系一一對應的關系,從概念間虧值的角度出發(fā),通過虧值計算實現(xiàn)了由容差關系找出與之對應的塊關系,為虧值理論在形式概念與分析知識體系中的結合與應用提供了擴展和思路. 關于容差關系及其商格的更多結論具體可參見文獻[4-5].

僅由0和1這兩個元素組成的布爾矩陣有著極其簡單、清晰的形式. 在關系理論、邏輯學、模糊數學、圖論、格論、代數半群理論、組合論、計算機科學等領域有著密切的聯(lián)系和應用. 文獻[6-9]用矩陣的語言刻畫形式背景的概念格,構造了由一個布爾矩陣的特定行指標和列指標對所確定的指標格,得到了布爾矩陣指標格的一些基本性質,研究了有限格同構于布爾矩陣的指標格的充要條件. 以上定義的布爾矩陣的指標格同構于與之對應的形式背景的概念格. 郭玲等[10]將塊關系推廣到布爾矩陣上,給出布爾矩陣的塊關系矩陣的概念,運用布爾矩陣指標格的性質證明了布爾矩陣的塊關系矩陣構成的格同構于布爾矩陣指標格的容差關系構成的格. Luo等[6]從對偶的角度刻畫了布爾矩陣的指標格也叫作布爾矩陣的行列空間格,給出了布爾矩陣的行列空間格中元素交和并運算、有限格同構于行列空間格的充要條件、同余矩陣構成的格與由同余矩陣誘導的商格的關系. 布爾矩陣的行列空間格對偶同構于布爾矩陣的指標格. 關于格論和布爾矩陣的更多結論具體可參見文獻[11-12].

在以上結論的基礎上,本文主要研究布爾矩陣的對偶塊關系矩陣及其行列空間格的容差關系. 給定一個布爾矩陣的對偶塊關系矩陣,如何找到與之對應的布爾矩陣的行列空間格的容差關系;反之,給定布爾矩陣的行列空間格的容差關系,如何找到與之對應的布爾矩陣的對偶塊關系矩陣. 在第一部分,介紹了布爾矩陣的行列空間格的概念和基本性質,引入布爾矩陣的對偶塊關系矩陣的概念. 在第二部分,首先建立了布爾矩陣的對偶塊關系矩陣與其行列空間格的容差關系之間的聯(lián)系,進而證明了布爾矩陣的對偶塊關系矩陣形成的格同構于行列空間格的容差關系形成的格,最后得到了由容差關系誘導的商格同構于對偶塊關系矩陣的行列空間格.

定義為(aij∧bij)m×n,其中

1 預備知識

具體可參見文獻[7].

由定義1容易得出以下性質.

性質1設A=(aij)m×n∈βmn,對于集合

有:

1)R1?R2?R2′?R1′,

1′)W1?W2?W2′?W1′;

2)R″?R,

2′)W″?W;

3)R′=R?,

3′)W′=W?;

引理1設A=(aij)m×n∈βmn,定義集合

則CR(A)關于運算∧和∨構成一個格,其中∧和∨定義如下:

(R1,W1)∧(R2,W2)=(R1∪R2,(W1∩W2)′′), (R1,W1)∨(R2,W2)=((R1∩R2)′′,W1∪W2),

則稱CR(A)是A的行列空間格.

關于性質1、性質2、引理1的具體內容,可參見文獻[7].

定義2[1]設V是一個格,V上的一個容差關系θ指關系θ?V×V滿足自反性、對稱性且關于格V的交和并運算相容,即對a,b,c∈V,有

aθb?(a∧c)θ(b∧c),(a∨c)θ(b∨c),

容易證明格V上的所有容差關系的集合關于集合的包含關系形成一個格,記作Tol(V)[13].

引理2[1]若θ是格V上的一個容差關系,則有aθb,x,y∈[a∧b,a∨b]?xθy.

定義3[1]若θ是有限格V上的一個容差關系,對于任意a∈V,定義:

aθ:=∧{b∈V|aθb},aθ:=∨{b∈V|aθb},

則區(qū)間[a]θ=[aθ,(aθ)θ]叫作θ的一個塊.

定義4設A=(aij)m×n,B=(bij)m×n∈βmn,稱B是A的一個對偶塊關系矩陣指下列條件成立:

1)A≥B;

例1設

則A的行列空間格CR(A)如圖1所示.容易得出B是A的對偶塊關系矩陣.

因為A≥B且對每個

有:

B1*=B2*={67}∈R(A),B3*=B4*={?}∈R(A),B5*=B6*={12}∈R(A),B7*={1267}∈R(A).B*1=B*2={567}∈C(A),B*3=B*4=B*5={?}∈C(A),B*6=B*7={127}∈C(A).

即Bi*∈R(A),B*j∈C(A).

圖1 矩陣A的行列空間格CR(A)

2 主要定理及結論

定理1設A=(aij)m×n∈βmn,θ是CR(A)上的一個容差關系,定義矩陣B=(bij)∈βmn如下:bij=0?ρ(i)θ(ρ(i)∧η(j)),則B是A的對偶塊關系矩陣.

證明設aij=0,由引理1可知ρ(i)≤η(j).由已知θ是CR(A)上的一個容差關系,所以ρ(i)θρ(i),即ρ(i)θ(ρ(i)∧η(j)),因此bij=0,故A≥B.

要證明Bi*∈R(A),只需考慮這個元素

η(j0)≥∧{η(j)|ρ(i)θ(ρ(i)∧η(j))},

因此有

ρ(i)∧η(j0)≥ ∧{ρ(i)∧η(j)|ρ(i)θ(ρ(i)∧η(j))},

綜上所述B是A的一個對偶塊關系矩陣.

定理2設A=(aij)m×n∈βmn,B是A的一個對偶塊關系矩陣,對任意的(R,W),(U,V)∈CR(A),定義τ(B)如下:

(R,W)τ(B)(U,V)?B≤A(R,V)∩A(U,W),

則τ(B)是CR(A)上的一個容差關系.

證明設(R,W)∈CR(A),顯然有

RA?W?WA?R?A≤A(R,W).

由于B=(bij)m×n是對偶塊關系矩陣,則有B≤A≤A(R,W),從而有

B≤A(R,W)∩A(R,W)?(R,W)τ(B)(R,W),

則τ(B)滿足自反性.

設(R,W),(U,V)∈CR(A),假設(R,W)τ(B)(U,V),則

(R,W)τ(B)(U,V)?B≤A(R,V)∩A(U,W)?B≤A(U,W)∩A(R,V)?(U,V)τ(B)(R,W),

則τ(B)滿足對稱性.

下證τ(B)對交和并運算滿足相容性.

若T是一個指標集,且有元素滿足

(Rt,Wt)τ(B)(Ut,Vt),t∈T,

我們的論點如下:由于

(Rt,Wt)τ(B)(Ut,Vt)?B≤A(Rt,Vt)∩A(Ut,Wt),

則有B≤A(Rt,Vt),從而有

RtB?Vt=UtA?RtBA?VtA=Ut.

又由于

即

則τ(B)是CR(A)上的一個容差關系.

定理3設A=(aij)m×n∈βmn,則A的行列空間格CR(A)上的所有容差關系形成的格Tol(CR(A))同構于A的所有對偶塊關系矩陣形成的格BR(A),即映射:

其中β(θ)=(bij)∈βmn滿足:bij=0?ρ(i)θ(ρ(i)∧η(j)),是一個格同構映射.

證明令:

下證1θ=τβ(θ),1B=βτ(B).顯然β和τ都是保序映射.設θ是CR(A)上的一個容差關系,我們需要證明:

(R,W)θ(U,V)?(R,W)τ(β(θ))(U,V),

其中β(θ)=(bij)m×n∈βmn.

根據引理2,不妨設

(R,W)>(U,V)?R?U?V?W.

對所有的

即對所有的

bij=0.又

即證1θ=τβ(θ).

設矩陣B=(bij)m×n∈βmn是矩陣A的對偶塊關系矩陣,則

又因為

β(τ(B))中第i行,第j列元素為0.

因此B=β(τ(B)),即1B=βτ(B).

定理4設A=(aij)m×n∈βmn,若θ是CR(A)上的一個容差關系且B與θ對應的對偶塊關系矩陣,則有CR(A)/θ?CR(B),更準確地,有:

1)映射[(WA,W),(R,RA)]是θ的一個塊當且僅當(R,W)∈CR(B).

證明根據定理3,設

(WA,W),(R,RA)∈CR(A),

且(WA,W)≤(R,RA),則((WA,W),(R,RA))∈θ當且僅當B≤A(R,W),即RB?W,WB?R.對任意的(X,Y)∈CR(B),則有(X,Y)θ=(XBA,XB)且(X,Y)θ=(YB,YBA),因此((X,Y)θ)θ=(XBB,XBBA).

若令W=XB,R=XBB,根據引理1,有(R,W)∈CR(B),且

[(X,Y)]θ=[(X,Y)θ,((X,Y)θ)θ]=

[(XBa,XB),(XBB,XBBA)]=

[(WA,W),(R,RA)].

3 總結

根據布爾矩陣行列空間格的性質,文章首先給出了布爾矩陣的對偶塊關系矩陣的定義. 給定布爾矩陣的行列空間格的容差關系,由性質1、引理1可以得到與之對應的布爾矩陣的對偶塊關系矩陣;反之,給定布爾矩陣的對偶塊關系矩陣,由性質1、性質2可以得到與之對應的布爾矩陣的行列空間格的容差關系. 因此存在從布爾矩陣的行列空間格上的所有容差關系形成的格到布爾矩陣的對偶塊關系矩陣形成的格的映射,并推導出此映射是一個同構映射. 證明了由容差關系誘導的商格同構于對偶塊關系矩陣的行列空間格.