離散數(shù)學(xué)第四章二元關(guān)系3rd zhou

1/36第四章二元關(guān)系2/452/45回顧關(guān)系的冪運(yùn)算關(guān)系的性質(zhì)3/453/45四、關(guān)系的閉包運(yùn)算閉包的定義：給定集合X，R是X中的二元關(guān)系。如果有另一個(gè)關(guān)系滿足（1）是自反的(對(duì)稱的、可傳遞的)；

（2）（3）對(duì)于任何自反的(對(duì)稱的、可傳遞的)關(guān)系，如果，則則稱關(guān)系為R的自反的(對(duì)稱的，可傳遞的)閉包。

并用r(R)表示的R自反閉包，用s(R)表示R的對(duì)稱閉包，用t(R)表示R的可傳遞閉包。4/454/45四、關(guān)系的閉包運(yùn)算定理：給定集合X，R是X中的關(guān)系。于是可有(a)當(dāng)且僅當(dāng)，R才是自反的。(b)當(dāng)且僅當(dāng)，R才是對(duì)稱的。(c)當(dāng)且僅當(dāng)，R才是傳遞的。證明：僅給出（a）的證明過(guò)程由閉包的定義可知，又由于R是包含了R的自反關(guān)系，根據(jù)自反閉包的定義有。因此有。反之，如果，則由自反閉包定義可知R是自反的。

5/455/45四、關(guān)系的閉包運(yùn)算定理：設(shè)R為A上的關(guān)系,則有(1)r(R)=R∪R0(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…說(shuō)明：對(duì)有窮集A(|A|=n)上的關(guān)系,(3)中的并最多不超過(guò)Rn證只證(1)和(3).(1)由IA=R0R∪R0知R∪R0是自反的,且滿足RR∪R0設(shè)R

是A上包含R的自反關(guān)系,則有RR

和IAR

.從而有R∪R0R.R∪R0滿足閉包定義,所以r(R)=R∪R0.6/456/45四、關(guān)系的閉包運(yùn)算(3)先證R∪R2∪…t(R)成立.用歸納法證明對(duì)任意正整數(shù)n有Rnt(R).n=1時(shí)有R1=Rt(R).假設(shè)Rnt(R)成立,那么對(duì)任意的<x,y>

<x,y>∈Rn+1=RnR

t(<x,t>∈Rn∧<t,y>∈R)

t(<x,t>∈t(R)∧<t,y>∈t(R))<x,y>∈t(R)這就證明了Rn+1t(R).由歸納法命題得證.再證t(R)R∪R2∪…成立,為此只須證明R∪R2∪…傳遞.任取<x,y>,<y,z>,則

<x,y>∈R∪R2∪…∧<y,z>∈R∪R2∪…

t(<x,y>∈Rt)∧s(<y,z>∈Rs)

ts(<x,z>∈RtRs)

ts(<x,z>∈Rt+s)

<x,z>∈R∪R2∪…從而證明了R∪R2∪…是傳遞的.7/457/45四、關(guān)系的閉包運(yùn)算在整數(shù)集合中，小于關(guān)系“<”的自反閉包是“≤”；恒等關(guān)系IX的自反閉包是IX。不等關(guān)系“≠”的自反閉包是全域關(guān)系；空關(guān)系的自反閉包是恒等關(guān)系。在整數(shù)集合中，小于關(guān)系“<”的對(duì)稱閉包是不等關(guān)系“≠”；小于或等于關(guān)系“≤”的對(duì)稱閉包是全域關(guān)系；恒等關(guān)系IX的對(duì)稱閉包是IX；不等關(guān)系“≠”的對(duì)稱閉包是不等關(guān)系“≠”。8/458/45四、關(guān)系的閉包運(yùn)算例：給定集合X={a,b,c}，R和S是X中的關(guān)系，給定試求出t(R),t(S)，并畫出關(guān)系圖解：R,t(R)St(S)9/459/45四、關(guān)系的閉包運(yùn)算定理：設(shè)X是集合，R是X中的二元關(guān)系，于是有（1）如果R是自反的，那么s(R),t(R)也是自反的；（2）如果R是對(duì)稱的，那么r(R),t(R)也是對(duì)稱的；（3）如果R是可傳遞的，那么r(R)也是可傳遞的。證明（1）：若R是自反的，則對(duì)于所有的

都有即s(R),t(R)是自反的10/45四、關(guān)系的閉包運(yùn)算11/45四、關(guān)系的閉包運(yùn)算證明（3）：

12/4512/45四、關(guān)系的閉包運(yùn)算定理：設(shè)X是集合，R是集合中的二元關(guān)系，于是有證明：13/4513/45四、關(guān)系的閉包運(yùn)算證明（b）：因?yàn)?，，而?duì)于所有的有，以及。根據(jù)這些關(guān)系式，可有于是14/4514/45四、關(guān)系的閉包運(yùn)算證明（c）：如果，則，根據(jù)對(duì)稱閉包的定義，有。首先構(gòu)成上式兩側(cè)的可傳遞閉包，再依次構(gòu)成兩側(cè)的對(duì)稱閉包,可以求得以及。而ts(R)是對(duì)稱的，所以，從而有。15/4515/45四、關(guān)系的閉包運(yùn)算注意：（1）通常用R+表示R的可傳遞閉包t(R)，并讀作“R加”。（2）通常用R*表示R的自反可傳遞閉包tr(R)，并讀作“R星”。16/4516/454.5特殊關(guān)系一、集合的劃分和覆蓋定義：給定非空集合S，設(shè)非空集合A={A1,A2,…,An}，如果有則稱集合A是集合S的覆蓋。注意：集合的覆蓋不唯一。例如：S={a,b,c}，A={{a,b},{b,c}}，B={{a},{b,c}}，A和B都是集合S的覆蓋。17/4517/45一、集合的劃分和覆蓋定義：給定非空集合S，設(shè)非空集合A={A1,A2,…,An}，如果有則稱集合A是集合S的一個(gè)劃分。劃分中的元素Ai稱為劃分的類。劃分的類的數(shù)目叫劃分的秩。劃分是覆蓋的特定情況，即中元素互不相交的特定情況。18/4518/45一、集合的劃分和覆蓋例：設(shè)S={1,2,3}，考慮下列集合S的覆蓋S的覆蓋S的覆蓋、劃分，秩為2S的覆蓋、劃分，秩為1，最小劃分S的覆蓋、劃分，秩為3，最大劃分19/4519/45一、集合的劃分和覆蓋定義：設(shè)A和A'是非空集合S的兩種劃分，并可以表示成如果A'的每一類A'j，都是A的某一類Ai的子集，那么稱劃分A'是劃分A的加細(xì)，并稱A'加細(xì)了A。如果A'是A的加細(xì)并且A'≠A，則稱A'是A的真加細(xì)。20/4520/45極小項(xiàng)、完全交集定義：劃分全集E的過(guò)程，可看成是在表達(dá)全集的文氏圖上劃出分界線的過(guò)程。設(shè)A，B，C是全集E的三個(gè)子集。由A，B和C生成的E的劃分的類，稱為極小項(xiàng)或完全交集。

n個(gè)子集生成2n個(gè)極小項(xiàng)，用表示。21/4521/45一、集合的劃分和覆蓋定理：由全集的n個(gè)子集A1,A2,…,An所生成的全部極小項(xiàng)集合，能夠構(gòu)成全集E的一個(gè)劃分。證明：證明這個(gè)定理，只需證明全集E中的每一個(gè)元素，都僅屬于一個(gè)完全交集就夠了。如果，則，或，或；…；或。由此可見(jiàn)，定有這里或是Ai或是～Ai

。試考察兩個(gè)不同的完全交集T。因?yàn)閮蓚€(gè)完全交集是不同的，就是說(shuō)存在這樣一個(gè)i，使得和，因此可有，即；因而任何一個(gè)都不能同時(shí)屬于兩個(gè)不同的完全交集。22/4522/45一、集合的劃分和覆蓋注意：不難看出，這里所說(shuō)的完全交集，與命題演算中的極小項(xiàng)相似。但是和極小項(xiàng)的集合不同，極大項(xiàng)的集合不能構(gòu)成全集的劃分。23/4523/45二、等價(jià)關(guān)系定義：設(shè)X是任意集合,R是集合中的二元關(guān)系。如果R是自反的、對(duì)稱的和可傳遞的，則稱R是等價(jià)關(guān)系。即滿足以下幾點(diǎn)：如果R是集合X中的等價(jià)關(guān)系，則R的域是集合X自身，所以，稱R是定義于集合X中的關(guān)系。例如

數(shù)的相等關(guān)系是任何數(shù)集上的等價(jià)關(guān)系。

又例如一群人的集合中姓氏相同的關(guān)系也是等價(jià)關(guān)系。但朋友關(guān)系不是等價(jià)關(guān)系，因?yàn)樗豢蓚鬟f。

24/4524/45二、等價(jià)關(guān)系例：給定集合X={1,2,…,7}，R是X中的二元關(guān)系，并且給定成試證明R是等價(jià)關(guān)系。解：R的關(guān)系矩陣如下：R的關(guān)系圖如下：25/4525/45二、等價(jià)關(guān)系注意：上例是模數(shù)系統(tǒng)中模等價(jià)關(guān)系的特定情況。

設(shè)Z+是正整數(shù)集合，m是個(gè)正整數(shù)。對(duì)于來(lái)說(shuō)，可將R定義成。這里，“x-y可被m整除”等價(jià)于命題“當(dāng)用m去除x和y時(shí)，它們都有同樣的余數(shù)”。故關(guān)系R也稱為模m同余關(guān)系。26/4526/45元素的等價(jià)

設(shè)R是集合A上的等價(jià)關(guān)系，若元素aRb，則稱a與b等價(jià)，或稱b與a等價(jià)。定義：設(shè)m是個(gè)正整數(shù)，。如果對(duì)于某一個(gè)整數(shù)n，有x-y=n?m,則稱x模m等價(jià)于y，并記作整數(shù)m稱為等價(jià)的模數(shù)。“”表示模m等價(jià)關(guān)系R。27/4527/45二、等價(jià)關(guān)系定理：任何集合中的模m相等關(guān)系，是一個(gè)等價(jià)關(guān)系。證明：設(shè)R是任何集合中的模m相等價(jià)關(guān)系。如果X=Ф，則R是個(gè)空關(guān)系，顯然有是自反的、對(duì)稱的和可傳遞的。如果X≠Ф

，則需考察下列三條：(1)對(duì)于任何來(lái)說(shuō)，因?yàn)閤-x=0?m，所以有。因此，模m相等關(guān)系是自反的。

(2)對(duì)于任何來(lái)說(shuō)，如果，則存在某一個(gè)，能使x-y=n?m。于是可有y-x=(-n)?m，因此有，即模m相等關(guān)系是對(duì)稱的。(3)設(shè)，和。于是存在，能使和。而，從而可有，即模m相等關(guān)系是可傳遞的。

28/4528/45等價(jià)類

定義

設(shè)是集合A上的等價(jià)關(guān)系，則A

中等價(jià)于元素的所有元素組成的集合稱為生成的等價(jià)類，用表示，即說(shuō)明：簡(jiǎn)單起見(jiàn)，有時(shí)候把[a]R簡(jiǎn)單寫作[a]或a/R。29/4529/45等價(jià)類例：設(shè)X={a,b,c,d}，R是X中的等價(jià)關(guān)系，并把R給定成

則：30/4530/45等價(jià)類的性質(zhì)設(shè)X是一集合，X是R中的等價(jià)關(guān)系2.對(duì)于所有的，或者，或者證明：當(dāng)X=Ф，上述結(jié)論肯定為真。當(dāng)X≠Ф時(shí)，分兩種情況討論(1)xRy(2)xR'y１.如果x∈X,則x∈[x]R。該性質(zhì)是明顯的，因?yàn)椋沂亲苑吹?，所以有xRx,于是x∈[x]R31/4531/45等價(jià)類的性質(zhì)(1)xRy故。類似地可以證明由上得若，則xRz

，

由R的對(duì)稱性有zRx，

又由R的傳遞性有zRy

，因此(2)xR'y假設(shè),因此有且，故于是由xRz,zRy，得xRy，與xR'y相矛盾32/4532/45等價(jià)類的性質(zhì)3.證明：假定，對(duì)于某個(gè)，有。由于，會(huì)有，因而。設(shè)，于是因而

證畢。33/4533/45等價(jià)類的性質(zhì)例

設(shè)A={a,b,c,d}，A上的關(guān)系R是A上的等價(jià)關(guān)系

同一個(gè)等價(jià)類中元素均相互等價(jià)。不同等價(jià)類中的元素互不等價(jià)。由A的各元素所生成的等價(jià)類必定覆蓋A，決定了集合A的一種劃分。34/4534/45二、等價(jià)關(guān)系定理：設(shè)R是非空集合X中的等價(jià)關(guān)系。R的等價(jià)類的集合，是X的一個(gè)劃分。定義：設(shè)R是非空集合X中的等價(jià)關(guān)系。R的各元素生成的等價(jià)類集合叫按R去劃分X的商集，記作X/R，也可以寫成X(modR)。由定義可知，按R對(duì)集合X的劃分X/R是一個(gè)集合，并且X/R的基數(shù)是X的不同的R等價(jià)類的數(shù)目，因此X/R的基數(shù)又稱為等價(jià)關(guān)系R的秩。35/4535/45特殊的等價(jià)關(guān)系全域關(guān)系：令等價(jià)關(guān)系R1=XX，這里X的每一個(gè)元素與X的所有元素都有R1的關(guān)系。按R1劃分X的商集乃是集合{X}。等價(jià)關(guān)系R1是全域關(guān)系。全域關(guān)系會(huì)造成集合X的最小劃分。恒等關(guān)系R：X的每一個(gè)元素僅關(guān)系到它自身，而不關(guān)系到其它元素。顯然，R是個(gè)恒等關(guān)系。按R劃分X的商集，僅由單元素集合組成。恒等關(guān)系R會(huì)造成集合X的最大劃分。這些劃分均稱作X的平凡劃分。36/4536/45等價(jià)關(guān)系與集合的劃分例：令R是整數(shù)集合I中的“模3同余”關(guān)系，R可給定成

求Z的元素所生成的R等價(jià)類。

解：等價(jià)類是可以看出，等價(jià)關(guān)系可以造成集合的一個(gè)劃分。

37/4537/45等價(jià)關(guān)系與集合的劃分定理：設(shè)C是非空集合X的一個(gè)劃分，則由這個(gè)劃分所確定的下述關(guān)系R必定是個(gè)等價(jià)關(guān)系，并稱R為由C劃分導(dǎo)出的X中的等價(jià)關(guān)系。證明：要證明R是個(gè)等價(jià)關(guān)系，就必須證明R是自反的、對(duì)稱的和可傳遞的。(a)由于C是X的劃分，C必定覆蓋X。對(duì)任意的