淺析集合論中的等價(jià)關(guān)系及其判斷方法

郭麗君

(蘭州博文科技學(xué)院電信工程學(xué)院，蘭州730101)

1 引 言

離散數(shù)學(xué)課程是計(jì)算機(jī)學(xué)科各專業(yè)核心課，在課程體系中占有重要地位，該課程由集合論、代數(shù)系統(tǒng)、圖論、數(shù)理邏輯四部分內(nèi)容組成，集合論是所有章節(jié)內(nèi)容的基礎(chǔ)，因此從集合論出發(fā)，通過集合的基本定義和運(yùn)算、有序組和笛卡爾乘積、關(guān)系的定義和性質(zhì)、次序關(guān)系、等價(jià)關(guān)系[1-2]，由淺入深，使得學(xué)生對(duì)集合有了更全面、更系統(tǒng)的認(rèn)識(shí)，其中等價(jià)關(guān)系更是將關(guān)系和集合更緊密的聯(lián)系起來，通過等價(jià)關(guān)系能更深刻的認(rèn)識(shí)一個(gè)集合.但通過等價(jià)關(guān)系的定義判斷一個(gè)關(guān)系是否是等價(jià)關(guān)系，在關(guān)系較為復(fù)雜的情況下，判斷不太準(zhǔn)確，通過寫出等價(jià)關(guān)系的關(guān)系矩陣[3-4]，用矩陣?yán)碚撊ヅ袛嗟葍r(jià)關(guān)系更為有效，同時(shí)為進(jìn)一步通過計(jì)算機(jī)編程手段判斷等價(jià)關(guān)系奠定了理論依據(jù)，這也是相關(guān)教科書上沒有提到的.

2 劃分與塊

1.1 基本概念

在集合論中，關(guān)系作為笛卡爾集合的子集，是集合論的一個(gè)重要組成部分，并不是每個(gè)集合都能稱為關(guān)系，只有元素形式為有序偶的集合才能稱為關(guān)系.

定義1設(shè)非空集合A與B，定義集合R={(ai,bi)|ai∈A,bi∈B}為集合A到B的一個(gè)關(guān)系.其中集合A稱為關(guān)系R的定義域，集合B稱為關(guān)系R的值域，一般情況下有R?A×B.定義在集合A與B上的若干個(gè)關(guān)系，按其性質(zhì)可歸類為次序關(guān)系、等價(jià)關(guān)系等，其中要掌握等價(jià)關(guān)系，劃分與塊的概念是一個(gè)非常重要的定義，掌握劃分的思想是進(jìn)一步理解塊、等價(jià)類等概念的基礎(chǔ).

定義2對(duì)非空集合E，有A1,A2,…,An都是集合E的子集，且滿足以下兩個(gè)條件：

實(shí)際上，關(guān)于劃分和塊的概念在生活中隨處可見，如集合E={計(jì)算機(jī)科學(xué)班全體學(xué)生}，可以按照{(diào)男生}和{女生}將集合E劃分成兩塊，但這只是最普通的一種劃分，如果按照學(xué)生的籍貫來劃分，又可將E劃分成{甘肅籍學(xué)生}{陜西籍學(xué)生}{吉林籍學(xué)生}等多塊，又或是以學(xué)生所在宿舍來劃分，以該班學(xué)生共40人為例，至少可以將集合E劃分成7塊，還可以根據(jù)對(duì)學(xué)生考察的不同目的進(jìn)行其他方式的劃分，但無論是怎樣的劃分，每種劃分方式下得到的塊都滿足兩兩互斥性，同時(shí)所有塊的并集正好覆蓋集合E.除以學(xué)生作為集合進(jìn)行劃分外，在實(shí)際生活中如超市的所有貨品、車站的候車區(qū)、小吃街的所有攤位組成的集合，都符合劃分和塊的概念，也就是說，劃分與塊的概念在生活中隨處可見，劃分將龐大的集合變得更確切、更具體，塊中的元素更明了、更清晰、更統(tǒng)一.而在集合X上建立一個(gè)等價(jià)關(guān)系R后，該等價(jià)關(guān)系R也能對(duì)集合X產(chǎn)生一個(gè)劃分.

1.2 等價(jià)類對(duì)集合的劃分

定義3等價(jià)關(guān)系是指一個(gè)定義在集合X上的關(guān)系R，如果能滿足自反性、對(duì)稱性和傳遞性，則關(guān)系R稱為等價(jià)關(guān)系.

在集合X上定義一個(gè)等價(jià)關(guān)系R，可進(jìn)一步對(duì)集合X進(jìn)行劃分，劃分得到的塊稱為等價(jià)類，具體定義如下：

定義4設(shè)R是集合X上的等價(jià)關(guān)系，對(duì)任一x∈X可以構(gòu)造一個(gè)X的子集[x]R，稱為x對(duì)于R的等價(jià)類,記為[x]R={y|y∈X,xRy}，也即[x]R={y|y∈X,(x,y)∈R}.

在實(shí)際生活中，存在很多等價(jià)關(guān)系，如老鄉(xiāng)關(guān)系、同學(xué)關(guān)系、同事關(guān)系等，在整數(shù)集合上，定義的一種同余關(guān)系也為等價(jià)關(guān)系，即R={(x,y)|x-y能被m整除,x,y,m∈,m≠0}.

下面通過分別驗(yàn)證該關(guān)系具有自反性、對(duì)稱性、傳遞性來說明關(guān)系R為等價(jià)關(guān)系.

證首先，對(duì)任意x∈，都有x-x=0能被m整除，即?(x,x)∈R，所以關(guān)系R滿足自反性.

其次，若有(x,y)∈R，也就是x-y能被m整除，那么y-x=-(x-y)也能被m整除，則有(y,x)∈R，所以關(guān)系R滿足對(duì)稱性.

最后，若有(x,y)∈R,(y,z)∈R，也就是x-y能被m整除且y-z能被m整除，那么x-z=(x-y)+(y-z)也能被m整除，則有(x,z)∈R，所以關(guān)系R滿足傳遞性.

綜上可知，關(guān)系R為等價(jià)關(guān)系.

當(dāng)(x,y)∈R,x≠y時(shí)，對(duì)整數(shù)x,y,m之間的關(guān)系進(jìn)一步分析，發(fā)現(xiàn)元素x,y同時(shí)除以m時(shí)，商不同但余數(shù)完全相同，因此將關(guān)系R比較形象的稱為以m為模的同余關(guān)系，記為x≡y(modm).

={x|x=2n,n∈}∪{x|x=2n+1,n∈}且{x|x=2n,n∈}∩{x|x=2n+1,n∈}=?，

對(duì)數(shù)字有了負(fù)數(shù)的定義后，整數(shù)集合又可以劃分為正整數(shù)集合、零和負(fù)整數(shù)集合，即

=+∪{0}∪-且+∩{0}=?,+∩-=?,-∩{0}=?.

通過對(duì)整數(shù)集合現(xiàn)有的認(rèn)識(shí)，以上是兩種最常見的劃分方式，看起來也是最容易理解和被接受的劃分，但存在的問題是，上述方法無論是將整數(shù)劃分成兩塊還是三塊，每個(gè)塊中整數(shù)的特點(diǎn)都不太明顯，因?yàn)檎麛?shù)中既有奇數(shù)又有偶數(shù)，既有正數(shù)又有負(fù)數(shù)，現(xiàn)有的常規(guī)的兩種劃分只是對(duì)整數(shù)集合最初步的理解和認(rèn)識(shí).

利用同余關(guān)系，可以按照模m的取值將整數(shù)集合進(jìn)行任意劃分，且劃分后的每一塊都保留整數(shù)的特點(diǎn)，即既有偶數(shù)又有奇數(shù)，既有正整數(shù)又有負(fù)整數(shù).如當(dāng)m=4時(shí)，

R={(x,y)|x-y能被4整除,x,y∈}，

R所構(gòu)成的等價(jià)類分別為[0]R={…,-8,-4,0,4,8,…},[1]R={…，-7,-3,1,5,9,…}，

[2]R={…,-6,-2,2,6,10,…}, [3]R={…,-5,-1,3,7,11,…}，

顯然四個(gè)塊滿足兩兩互斥性，同時(shí)四個(gè)類的并集正好覆蓋住集合，由此在集合上建立模為4的同余關(guān)系后，得到了整數(shù)集合的又一個(gè)劃分，將整數(shù)集合劃分成了4塊，以此類推，以模m的取值決定可以將整數(shù)集合進(jìn)行任意劃分，顯然對(duì)整數(shù)集合的這種劃分更科學(xué).

例1設(shè)在集合A={1,2,5,8,10,13,15,16}上建立以3為模的同余關(guān)系R，將集合A進(jìn)行劃分.

解關(guān)系R的等價(jià)類為[1]R={1,10,13,16},[2]R={2,5,8},[15]R={15}，因此集合A此時(shí)被劃分成了3塊，即A={[1]R,[2]R,[15]R}，記為A的商集A/R.

1.3 由集合的劃分產(chǎn)生等價(jià)關(guān)系

反過來，任給一個(gè)集合的劃分，也會(huì)產(chǎn)生一個(gè)等價(jià)關(guān)系，等價(jià)關(guān)系和劃分時(shí)刻都是同時(shí)存在，相互依存的.

例2設(shè)集合A={a,b,c,d,e,f}的一個(gè)劃分是A1={a,b,c},A2=j5i0abt0b,A3={e,f}，則由此劃分產(chǎn)生的等價(jià)關(guān)系為R={(a,a),(b,b),…,(f,f),(a,b),(b,a),(a,c),(c,a),(b,c),(c,b),(e,f),(f,e)}.

顯然構(gòu)造的關(guān)系R是一個(gè)等價(jià)關(guān)系，實(shí)際上R=(A1×A1)∪(A2×A2)∪(A3×A3)，對(duì)任一定義在集合A,B上的關(guān)系R，一般情況下，R?A×B，若有R=A×B，則此關(guān)系R稱為定義在集合A,B上的全關(guān)系，已知一個(gè)集合的劃分，對(duì)應(yīng)的等價(jià)關(guān)系實(shí)際上是各塊與自身全關(guān)系的一個(gè)并集，但等價(jià)關(guān)系不一定是全關(guān)系.

從疑點(diǎn)數(shù)據(jù)表中可知：在重度用電客戶簇中，有一個(gè)疑點(diǎn)用戶，在輕度用電客戶簇中有9個(gè)疑點(diǎn)用戶都可能存在偷電等情況的發(fā)生。經(jīng)過實(shí)際有關(guān)人員對(duì)這些用戶的調(diào)查，確實(shí)發(fā)現(xiàn)存在問題。實(shí)驗(yàn)結(jié)果表明該算法能夠?yàn)閮?nèi)部審計(jì)提供審計(jì)依據(jù)，提高了工作效率。

3 等價(jià)關(guān)系與全關(guān)系

一個(gè)關(guān)系R如果是自反的、對(duì)稱的、傳遞的，則該關(guān)系稱為等價(jià)關(guān)系，而全關(guān)系的性質(zhì)也要求關(guān)系滿足自反的、對(duì)稱的、傳遞的，那么等價(jià)關(guān)系一定是全關(guān)系嗎？實(shí)則不然.

實(shí)際上，全關(guān)系一定是等價(jià)關(guān)系，但等價(jià)關(guān)系不一定是全關(guān)系，而由等價(jià)關(guān)系所構(gòu)成的等價(jià)類形成的關(guān)系是全關(guān)系.

如果對(duì)等價(jià)關(guān)系按照等價(jià)類畫出關(guān)系圖的話，那等價(jià)關(guān)系和全關(guān)系之間的聯(lián)系更顯然，也更能體現(xiàn)出塊的價(jià)值和作用，如畫出例1的關(guān)系圖如下：

圖1 例1的關(guān)系圖

在例1中將集合A={1,2,5,8,10,13,15,16}通過以3為模的同余關(guān)系R劃分成了三塊，對(duì)應(yīng)的關(guān)系R顯然不是全關(guān)系，因?yàn)橹辽倏梢钥闯?1,2)?R，而按照等價(jià)類畫出關(guān)系R的關(guān)系圖，對(duì)應(yīng)的三個(gè)類的關(guān)系圖均是全關(guān)系，因此，全關(guān)系一定是等價(jià)關(guān)系，而等價(jià)關(guān)系不一定是全關(guān)系，但是按照類的劃分對(duì)應(yīng)的關(guān)系一定是全關(guān)系，也可以理解為在一個(gè)等價(jià)關(guān)系中包含著若干個(gè)全關(guān)系，有幾個(gè)等價(jià)類就有幾個(gè)全關(guān)系.

4 等價(jià)關(guān)系的判斷

全面理解了等價(jià)關(guān)系之后，對(duì)一個(gè)給定的關(guān)系還要學(xué)會(huì)判斷該關(guān)系是否是等價(jià)關(guān)系，如果通過定義觀察關(guān)系是否有自反性、對(duì)稱性、傳遞性的方法進(jìn)行判斷，對(duì)含有元素較少的關(guān)系可能比較有效，但對(duì)于較為復(fù)雜的關(guān)系來說用定義觀察的方法得到的結(jié)論就不太準(zhǔn)確了，通過引入關(guān)系矩陣和矩陣的布爾運(yùn)算可以解決這一問題，用關(guān)系矩陣判斷一個(gè)關(guān)系是否是等價(jià)關(guān)系也更具科學(xué)性，同時(shí)用矩陣?yán)碚撆袛嗟葍r(jià)關(guān)系也為進(jìn)一步利用計(jì)算機(jī)編程進(jìn)行等價(jià)關(guān)系的判斷奠定了理論基礎(chǔ).

定義5設(shè)定義在集合X={a1,a2,…,an}上的關(guān)系R，定義其關(guān)系矩陣為An=(aij)n，其中

由此得到與一個(gè)與關(guān)系R完全對(duì)應(yīng)的n階方陣，且該方陣為布爾方陣.

用矩陣An的特點(diǎn)來說明對(duì)應(yīng)的關(guān)系R是否是等價(jià)關(guān)系比較客觀，且容易判斷，有以下定理：

證首先，對(duì)應(yīng)的關(guān)系矩陣An滿足aii=1,i=1,2,…,n,即對(duì)角線上的元素均為1，則說明?ai∈X,都有(ai,ai)∈R，根據(jù)自反性的定義，關(guān)系R是自反的.

其次，如果關(guān)系矩陣An是一個(gè)對(duì)稱矩陣，則An滿足aij=aji,i,j=1,2,…,n,即說明?(ai,aj)∈R,則必有(aj,ai)∈R，根據(jù)對(duì)稱性的定義，關(guān)系R是對(duì)稱的.

綜上所述，關(guān)系R滿足自反性、對(duì)稱性、傳遞性，所以關(guān)系R是等價(jià)關(guān)系，定理得證.

例3判斷定義在集合X={a,b,c,d}上的關(guān)系R={(a,a),(b,b),(c,c),(d,d),(a,c),(c,a)}是否是等價(jià)關(guān)系.

證該關(guān)系R比較簡(jiǎn)單，用定義可以直接判斷出關(guān)系R是等價(jià)關(guān)系，我們用矩陣?yán)碚摷右则?yàn)證，關(guān)系R對(duì)應(yīng)的關(guān)系矩陣為

顯然關(guān)系矩陣A是對(duì)稱矩陣，對(duì)角線上元素均為1，且A(2)=A，因此關(guān)系R是等價(jià)關(guān)系.

5 結(jié) 論

在離散數(shù)學(xué)中關(guān)系是個(gè)非常重要的概念，是集合論中學(xué)習(xí)的重點(diǎn)也是難點(diǎn)，而關(guān)系性質(zhì)的判定如果只局限于概念判定法，勢(shì)必會(huì)影響后續(xù)學(xué)習(xí)，而且概念判定只適用于簡(jiǎn)單形式的關(guān)系，對(duì)復(fù)雜的關(guān)系利用概念判斷不一定有效，也顯得不那么科學(xué).等價(jià)關(guān)系的判定，特別是其中關(guān)系傳遞性質(zhì)的判定，對(duì)于學(xué)生來說，不是那么容易理解，在關(guān)系中元素眾多的情況下更是難以判斷，通過使用關(guān)系矩陣計(jì)算方法實(shí)現(xiàn)對(duì)等價(jià)關(guān)系的判定，既使得判定工作具有很好的可計(jì)算性，也具有更高的科學(xué)性，同時(shí)也為進(jìn)一步利用計(jì)算機(jī)編程輔助手段判斷關(guān)系的性質(zhì)，判斷關(guān)系是否為等價(jià)關(guān)系提供了可靠的理論依據(jù)，對(duì)于離散數(shù)學(xué)的教學(xué)也具有較好的參考價(jià)值.但必須要提的是，此處關(guān)系傳遞性的判斷是基于等價(jià)關(guān)系的前提下，也就是關(guān)系本身既有自反性也有對(duì)稱性，用定理中的矩陣?yán)碚撆袛鄠鬟f性是有效的，對(duì)其他關(guān)系傳遞性的判斷是否仍然有效還要進(jìn)一步探討.

致謝作者非常感謝相關(guān)文獻(xiàn)對(duì)本文的啟發(fā)以及審稿專家提出的寶貴意見.