宋澤成，石瑞平

（1. 唐山師范學(xué)院 數(shù)學(xué)與信息科學(xué)系，河北 唐山 063000；2. 石家莊信息工程職業(yè)學(xué)院 基礎(chǔ)部，河北 石家莊 050000）

1 引言

設(shè)R是集合A上的二元關(guān)系，要判定R在A上是否是等價(jià)關(guān)系，一般來講，只能從定義出發(fā)，有時(shí)也可以從關(guān)系圖判定。當(dāng)R包含的序偶較多時(shí)，從定義出發(fā)比較難于判定且計(jì)算量很大。

給定集合A上的一個(gè)二元關(guān)系R，設(shè)MR為R的關(guān)系矩陣，MR=(mij)n×n，這里mij只取1或0，它是一個(gè)布爾矩陣。下面從 MR出發(fā)，給出等價(jià)關(guān)系的判定方法，并討論等價(jià)關(guān)系的性質(zhì)。因自反性和對稱性很容易直接判定，本文不再討論，可參閱文獻(xiàn)[1]、[2]。傳遞性一般無規(guī)律性可言，本文主要討論傳遞性的判定。

2 傳遞性的判定方法

定義 1 設(shè)R是非空集合A上的二元關(guān)系，對任意的a, b, c∈A，每當(dāng)(a, b)∈R，且(b, c)∈R時(shí)，就有(a, c)∈R，則稱二元關(guān)系R在A上是傳遞的，也稱R是A上的傳遞關(guān)系。

定義2 設(shè)A,B,C為三個(gè)非空集合，R1是A，B上的二元關(guān)系，R2是B，C上的二元關(guān)系，則集合

定義3 設(shè)R是非空集合A上的二元關(guān)系，R?R，記作 R2，稱為R的二次冪。

如果集合A上的二元關(guān)系R具有傳遞性，那么，每當(dāng)(a, b)∈R，且(b, c)∈R時(shí)，就應(yīng)有 ( a,c)∈ R,所以可得R2?R；若R2?R，則R是傳遞的。

設(shè)A為有限集，元數(shù)為n， R2的關(guān)系矩陣為 MR2，且

又設(shè)R的關(guān)系矩陣為MR

這里MR和 MR2都是布爾矩陣。

由R2?R可知，關(guān)系矩陣MR中某元素 αij=1，那么MR2中對應(yīng)關(guān)系元素αi′j可以為1或者0，若MR中某元素αij=0那么MR2中對應(yīng)元素′只能等于0，否則R就不能滿足傳遞性，因此 αi′j≤αij(i,j = 1 ,2 … ,n)，而

這里的“.”是布爾運(yùn)算，其中

由αi′j可以看出，當(dāng)至少存在一個(gè)R，使αik和αkj同時(shí)為1時(shí)，αik? αkj=1那么不論其它項(xiàng)是0還是1，此時(shí) αi′j=1否則 αi′j=0這樣求αij可以簡化計(jì)算，提高運(yùn)算速度。

由以上討論，我們可以按以下步驟來驗(yàn)證非空集合A上的二元關(guān)系R是否具有傳遞性：

（1）寫出R的關(guān)系矩陣：

（2）設(shè)復(fù)合關(guān)系 R2的關(guān)系矩陣 MR2=(′)n×n，逐一檢查MR中元素是否為零，從α11開始，若 α11=1則接下去檢查α12；若 α11=0，則求，看是否為零，否則 R 不具有傳遞性，若′ =0檢查下一個(gè)元素α12。若 α12=1接下去檢查α13；若α12=0，則求，看它是否為零，否則R不具有傳遞性。以此類推，直到αnn為止。

（3）若MR中所以零元素αij對應(yīng)的MR2中元素′也全為零，那么R是傳遞的。

上述方法對應(yīng)集合A的元數(shù)較大，且R中會(huì)有的序偶較多時(shí)，判定R是否具有傳遞性是相當(dāng)好的，這是因?yàn)镽中序偶較多，那么MR中“1”的個(gè)數(shù)也較多，相應(yīng)的“0”元素個(gè)數(shù)就較少。下面通過具體的例子說明如何應(yīng)用上述方法。例如，設(shè)集合：

二元關(guān)系

（1）寫出關(guān)系矩陣

（2）設(shè) R ? R= R的關(guān)系矩陣為 M2= (′ )，因

122R5×5為 α12=0，求′ 得：

（3）因?yàn)镸R中13個(gè)零對應(yīng)的 MR2中元素也全為零，故R是A上的傳遞關(guān)系。

當(dāng)然，對應(yīng)集合A上的一些特殊二元關(guān)系，比如“模2同余”；“模3同余”“模同余”關(guān)系，“整除”關(guān)系，“大于”關(guān)系等等，由于R的結(jié)構(gòu)比較特殊，可以從這些關(guān)系本身的定義出發(fā)，來驗(yàn)證它的傳遞性。

3 等價(jià)關(guān)系的判定方法

定理1 以C1，C2，…，Cr為等價(jià)類，構(gòu)造集合A上的一個(gè)二元等價(jià)關(guān)系 R，則等價(jià)關(guān)系R的關(guān)系矩陣 MR等價(jià)于PR，這里

此分塊矩陣[3]對角線上的子塊P11，P22，…，Prr都是元素均為1的方陣，其階數(shù)分別對應(yīng)C1，C2，…，Cr的基數(shù)，子塊個(gè)數(shù)r等于R的等價(jià)類的個(gè)數(shù)，其他子塊Pij（i≠j）均為零矩陣，即MR等價(jià)于一個(gè)分塊對角矩陣。

證明 不妨設(shè)

這時(shí)A上的關(guān)系R的關(guān)系矩陣為MR。由集的無序性，可對集A中的元素任意排號(hào)，A中任意兩個(gè)元素對調(diào)一次，相當(dāng)于MR中對應(yīng)的行和列同時(shí)對換一次，即對MR進(jìn)行一次行變換則必須馬上對它進(jìn)行一次相同的列變換。設(shè)等價(jià)類C1，C2，…，Cr包含的元素如下，

這里b1，b2，…，bn就是a1，a2，…，an的一個(gè)排列。我們對集A進(jìn)行有限次元素對調(diào)，目的就是對集A中的元素重新排號(hào)，使之元素順序?yàn)槿缦滦问剑?/p>

對新的元素順序，再來考察R的關(guān)系矩陣，由于C1，C2，…Cr為R的等價(jià)類，以C1為例，C1中任意兩個(gè)元素都有關(guān)系，C1與Ci（i=2、…r）中任意兩個(gè)元素都沒有關(guān)系，所以P11= [ 1]i1×i1，P11的階數(shù)就是 C1的基數(shù)，而 P12，P13，…，P1r均為零矩陣。同樣，對于C2，C3，…，Cr，僅有P22，…，Prr這些子塊是元素均為1的方陣，其階數(shù)對應(yīng)等價(jià)類的基數(shù)，而其他子塊均為零矩陣。那末此時(shí)的 A，R的關(guān)系矩陣就是 PR了。在對A中元素對調(diào)位置的同時(shí)，對應(yīng)著對MR施以前邊約定的初等變換，一旦A中元素排成了

MR就化成了PR，所以MR等價(jià)于PR。

由定理1的證明可得如下判定方法：給定A上的一個(gè)二元關(guān)系R，首先寫出R的關(guān)系矩陣MR，若MR經(jīng)過初等變換后能化成一個(gè)分塊對角陣PR，且PR具有下述形式：

這里子塊P1，P2，…，PS都是元素均為1的方陣，那末R一定是A上的一個(gè)等價(jià)關(guān)系。

4 等價(jià)關(guān)系的性質(zhì)

定理2 若R是A上的等價(jià)關(guān)系，其關(guān)系矩陣為MR，那末，秩(MR)就是R的商集Q的基數(shù)，即秩(MR)=。

證明：因?yàn)镽是A上的等價(jià)關(guān)系，關(guān)系矩陣MR，不妨設(shè)此等價(jià)關(guān)系確定了s個(gè)等價(jià)類，即=s。由引理可知，MR經(jīng)過有限次初等變換后可變成分塊對角陣B，并且B的形式如下：

這里 Bi=[1]ti×ti，i=1，2，…，s，且s就是R確定的等價(jià)類的個(gè)數(shù)。由于初等變換不改變矩陣的秩，所以

任取Bi（1≤i≤s），顯然，秩(Bi)=1，又因?yàn)閷i做初等行、列變換，不會(huì)影響其他子塊Bj（i≠j），因此，

所以，

5 結(jié)束語

研究了對集合A上的二元關(guān)系用關(guān)系矩陣來判定傳遞性和等價(jià)關(guān)系的問題，給出了對集合中元素較多時(shí)簡便實(shí)用的一種方法，并討論了等價(jià)關(guān)系的矩陣性質(zhì)，證明了關(guān)系矩陣的秩就是商集的基數(shù)。

[1]耿素云,屈婉玲.離散數(shù)學(xué)[M].北京:高等教育出版社,2004:1.

[2]左孝凌,李為鑒,劉永才.離散數(shù)學(xué)[M].上海:上?？茖W(xué)技術(shù)文獻(xiàn)出版社,1982:9.

[3]同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系.線性代數(shù)[M].北京:高等教育出版社,2003:1.