布爾矩陣的對偶塊關(guān)系矩陣及其行列空間格的容差關(guān)系

王思雨, 羅從文

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

0 引言

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

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

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

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

1 預(yù)備知識

具體可參見文獻[7].

由定義1容易得出以下性質(zhì).

性質(zhì)1設(shè)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設(shè)A=(aij)m×n∈βmn,定義集合

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

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

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

關(guān)于性質(zhì)1、性質(zhì)2、引理1的具體內(nèi)容,可參見文獻[7].

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

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

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

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

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

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

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

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

1)A≥B;

例1設(shè)

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

因為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 主要定理及結(jié)論

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

證明設(shè)aij=0,由引理1可知ρ(i)≤η(j).由已知θ是CR(A)上的一個容差關(guān)系,所以ρ(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的一個對偶塊關(guān)系矩陣.

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

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

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

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

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

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

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

則τ(B)滿足自反性.

設(shè)(R,W),(U,V)∈CR(A),假設(shè)(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)上的一個容差關(guān)系.

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

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

證明令:

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

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

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

根據(jù)引理2,不妨設(shè)

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

對所有的

即對所有的

bij=0.又

即證1θ=τβ(θ).

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

又因為

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

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

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

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

證明根據(jù)定理3,設(shè)

(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,根據(jù)引理1,有(R,W)∈CR(B),且

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

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

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

3 總結(jié)

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