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

《離散數(shù)學(xué)第四章二元關(guān)系.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第四章二元關(guān)系.ppt（100頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,第四章 二元關(guān)系,離散數(shù)學(xué) 陳志奎主編 人民郵電出版社,,,,,,,,,,,,,,,,,,,,,前言,在日常生活中，我們都十分熟悉關(guān)系這個(gè)詞的含義，例如夫妻關(guān)系，同事關(guān)系，上下級(jí)關(guān)系，位置關(guān)系等。在數(shù)學(xué)中，關(guān)系可表達(dá)集合中元素間的聯(lián)系。在計(jì)算機(jī)科學(xué)中，關(guān)系的概念也具有重要意義。例如，數(shù)字計(jì)算機(jī)的邏輯設(shè)計(jì)和時(shí)序設(shè)計(jì)中，都應(yīng)用了等價(jià)關(guān)系和相容關(guān)系的概念。在編譯程序設(shè)計(jì)、訊息檢索、數(shù)據(jù)結(jié)構(gòu)等領(lǐng)域中，關(guān)系的概念都是不可缺少的，常常使用復(fù)合數(shù)據(jù)結(jié)構(gòu)，諸如陣列、表格或者樹(shù)去表達(dá)數(shù)據(jù)集合。而這些數(shù)據(jù)集合的元素間往往存在著某種關(guān)系。在算法分析和程序結(jié)構(gòu)中，關(guān)系的概念起著重要作用。與關(guān)系相聯(lián)系著的，是對(duì)客體進(jìn)

2、行比較，這些被比較的客體當(dāng)然是有關(guān)系的。根據(jù)比較結(jié)果的不同，計(jì)算機(jī)將去執(zhí)行不同的任務(wù)。,2020/8/28,2,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,多重序元與笛卡爾乘積,,主要內(nèi)容,PART 01,關(guān)系的基本概念,PART 02,關(guān)系的運(yùn)算,PART 03,關(guān)系的性質(zhì),PART 04,關(guān)系的表示,PART 05,關(guān)系的閉包運(yùn)算,PART 06,特殊關(guān)系,PART 07,關(guān)系型數(shù)據(jù)庫(kù),PART 08,2020/8/28,3,,,,,,,,,,,,,,,,,,,,,4.1 多重序元與笛卡爾乘積,定義4.1 由兩個(gè)元素 x 和 y 按一定順序排列成的二元組叫作序偶或有序?qū)?/p>

3、，記作，其中 x 是序偶的第一元素， y 是序偶的第二元素。 與集合不同，序偶是元素順序相關(guān)的概念，即 ，而兩個(gè)序偶相等的充要條件是兩個(gè)序偶的第一元素相等且第二元素相等，即 例如集合 1 , 2 和 2 , 1 表示同一個(gè)集合，而 和 則表示平面上不同的點(diǎn)，即不同的序偶。,4,序偶,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.1 多重序元與笛卡爾乘積,例4.1 已知 ，求 x 和 y 。 解：由序偶相等的充要條件可得 解得 x = 3 , y = -2 。 應(yīng)該指出的是，序偶 兩個(gè)元素不一定來(lái)自同一個(gè)集合，他們可以代表不同類(lèi)型的事務(wù)。例如，a

4、 代表操作碼，b 代表地址碼，則序偶 就代表一條單址指令。,5,序偶,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.1 多重序元與笛卡爾乘積,把序偶的概念加以推廣，可以定義 n 重序元。例如，三重序元是一個(gè)序偶，它的第一元素是一個(gè)序偶，一般記作, z ，為方便起見(jiàn)把它簡(jiǎn)記為 。 依此類(lèi)推， 重序元是一個(gè)序偶，它的第一元素是 (n-1)重序元，并可記作 。給定兩個(gè) n 重序元 和 ，于是可有 因此可把 n 重序元改寫(xiě)成 ，其中第 i 個(gè)元素通常稱(chēng)作 n 重序元的第 i 個(gè)坐標(biāo)。,6,序偶,,,,,,,,,2020/8/28

5、,,,,,,,,,,,,,,,,,,,,,4.1 多重序元與笛卡爾乘積,定義4.2 設(shè) A 和 B 是任意兩個(gè)集合。若序偶的第一元素是 A 的一個(gè)元素，第二元素是 B 的一個(gè)元素，則所有這樣的序偶集合，稱(chēng)為 A 和 B 的笛卡兒乘積，記作 A x B ，即,7,笛卡爾乘積,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.1 多重序元與笛卡爾乘積,由排列組合的知識(shí)不難證明，如果 ， ，則 。 笛卡兒乘積運(yùn)算具有以下性質(zhì)。 1對(duì)任意集合 A ，根據(jù)定義有 一般來(lái)說(shuō)，笛卡兒乘積運(yùn)算不滿足交換律，即 （當(dāng) 時(shí)）,

6、8,笛卡爾乘積,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.1 多重序元與笛卡爾乘積,笛卡兒乘積運(yùn)算具有以下性質(zhì)。 3笛卡兒乘積運(yùn)算不滿足結(jié)合律，即,9,笛卡爾乘積,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.1 多重序元與笛卡爾乘積,笛卡兒乘積運(yùn)算具有以下性質(zhì)。 4笛卡兒乘積運(yùn)算對(duì)并和交運(yùn)算滿足分配率，即 （1） （2） （3） （4） 5 .,10,笛卡爾乘積,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.1 多重序元與笛卡爾乘

7、積,設(shè) 是加標(biāo)集合，與 A 對(duì)應(yīng)的指標(biāo)集合是集合 的笛卡兒乘積可以表示成 例如： 對(duì)于n個(gè)集合的笛卡爾乘積來(lái)說(shuō)，同理可有,11,笛卡爾乘積,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,多重序元與笛卡爾乘積,,主要內(nèi)容,PART 01,關(guān)系的基本概念,PART 02,關(guān)系的運(yùn)算,PART 03,關(guān)系的性質(zhì),PART 04,關(guān)系的表示,PART 05,關(guān)系的閉包運(yùn)算,PART 06,特殊關(guān)系,PART 07,關(guān)系型數(shù)據(jù)庫(kù),PART 08,2020/8/28,12,,,,,,,,,,,,,,,

8、,,,,,,4.2 關(guān)系的基本概念,定義4.3 設(shè) 且 為 n 個(gè)任意集合，若集合 ，則稱(chēng) R 為 間的 n 元關(guān)系；當(dāng) n = 2 ，則稱(chēng) R 為 到 的二元關(guān)系，簡(jiǎn)稱(chēng)關(guān)系；若 ，則稱(chēng) R 為空關(guān)系；若 ，則稱(chēng) R 為全關(guān)系；若 ，則稱(chēng) R 為 A上的 n 元關(guān)系。 例4.4 設(shè)集合 ，試給出集合 A 上的小于或等于關(guān)系，大于或等于關(guān)系。 解：令集合 A 上的小于或等于關(guān)系為 ，大于或等于關(guān)系為 ，根據(jù)定義4.1應(yīng)有：,13,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,

9、,,,,,,,,,,,,,,,4.2 關(guān)系的基本概念,例4.5 令 根據(jù)上面的定義可知， 是 上的一元關(guān)系， 是 上的二元關(guān)系， 是 上的三元關(guān)系。 若序偶 屬于 ，則記作 或 ，否則記作 或 。,14,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.2 關(guān)系的基本概念,定義4.4 設(shè) 為 間的 n 元關(guān)系， 為 間的 n 元關(guān)系，如果 （1）n = m ； （2）若 ，則 ； （3）把 和 作為集合看， 則稱(chēng) n 元關(guān)

10、系 和 m 元關(guān)系 相等，記作 。,15,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.2 關(guān)系的基本概念,定義4.5 對(duì)任意集合 A ，定義 A 上的全域關(guān)系 和 A 上的等價(jià)關(guān)系 為：,16,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.2 關(guān)系的基本概念,例4.7 設(shè) ，求以下關(guān)系 （1） （2） （3） （4） 解： （

11、1） （2） （3） （4）,17,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,多重序元與笛卡爾乘積,,主要內(nèi)容,PART 01,關(guān)系的基本概念,PART 02,關(guān)系的運(yùn)算,PART 03,關(guān)系的性質(zhì),PART 04,關(guān)系的表示,PART 05,關(guān)系的閉包運(yùn)算,PART 06,特殊關(guān)系,PART 07,關(guān)系型數(shù)據(jù)庫(kù),PART 08,2020/8/28,18,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,關(guān)系作為

12、序偶的集合，集合的運(yùn)算并、交、相對(duì)補(bǔ)、絕對(duì)補(bǔ)和對(duì)稱(chēng)差都可以作為關(guān)系的運(yùn)算。除此之外，關(guān)系特有的基本運(yùn)算還有以下七種。,19,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,定義4.6 設(shè) R 是二元關(guān)系 （1）R 中所有序偶的第一元素構(gòu)成的集合稱(chēng)為 R 的定義域，記作 ，其形式化表示為 （2）R 中所有序偶的第二元素構(gòu)成的集合稱(chēng)為 的值域，記作 ，其形式化表示為 （3）R 的定義域和值域的并集稱(chēng)為R的域，記作 ，其形式化表

13、示為,20,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,例4.8 ，則,21,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,定義4.7 設(shè) R 是二元關(guān)系，將 R 中每個(gè)序偶的第一元素同第二元素交換后所得到的關(guān)系稱(chēng)為

14、 R 的逆關(guān)系，簡(jiǎn)稱(chēng) R 的逆，記作 ，其形式化表示為 定義4.8 設(shè) F，G 為二元關(guān)系，G 對(duì) F 的右合成記作 ，其形式化定義為,22,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,例4.9 設(shè) ， ，則 類(lèi)似的也可以定義關(guān)系的左合成，即,23,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

15、,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,定義4.9 設(shè) R 是二元關(guān)系，A 是集合 （1）R 在 A上的限制記作 ，其形式化定義為 （2）R 在 A下的像記作 ，其形式化定義為 不難看出 是 R 的子關(guān)系，而 是 的子集。,24,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,例4.10 設(shè)

16、 ，則 為了使關(guān)系運(yùn)算表達(dá)式更為簡(jiǎn)潔，我們對(duì)關(guān)系運(yùn)算的優(yōu)先級(jí)作了進(jìn)一步規(guī)定：首先，關(guān)系運(yùn)算中的逆運(yùn)算優(yōu)先于其他運(yùn)算，而所有關(guān)系特有的運(yùn)算都優(yōu)先于其從集合繼承而得的運(yùn)算，最后，對(duì)于沒(méi)有規(guī)定優(yōu)先權(quán)的運(yùn)算以括號(hào)決定運(yùn)算順序。,25,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,定理4.1 設(shè) F 是任意關(guān)系，則 （1） （2） , 定理4.2 設(shè) F，G，H 是任意關(guān)系

17、，則 （1） （2）,26,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,定理4.3 設(shè) F，G 為任意關(guān)系，則 （1） （2） 定理4.4 設(shè) R為 A上的關(guān)系，則,27,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,202

18、0/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,定理4.5 設(shè) F，G ，H 為任意關(guān)系，則 （1） （2） （3） （4）,28,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,定理4.6 設(shè) F 為關(guān)系，A，B 為集合，則,29,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

19、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,上述的對(duì)關(guān)系的合成運(yùn)算可以推廣到一般情況。如果 是從 到 的關(guān)系， 是從 到 的關(guān)系，， 是從 到 的關(guān)系，則無(wú)括號(hào)表達(dá)式 表達(dá)了從 到 的關(guān)系。特別，當(dāng) 和 時(shí)，也就是說(shuō)當(dāng)集合 A上的所有 都是同樣的關(guān)系時(shí)，A 上的合成關(guān)系 可表達(dá)成 ，并稱(chēng)作關(guān)系R的冪。,30,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

20、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,,31,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關(guān)系的運(yùn)算,,32,,,

21、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,多重序元與笛卡爾乘積,,主要內(nèi)容,PART 01,關(guān)系的基本概念,PART 02,關(guān)系的運(yùn)算,PART 03,關(guān)系的性質(zhì),PART 04,關(guān)系的表示,PART 05,關(guān)系的閉包運(yùn)算,PART 06,特殊關(guān)系,PART 07,關(guān)系型數(shù)據(jù)庫(kù),PART 08,2020/8/28,33,,

22、,,,,,,,,,,,,,,,,,,,4.4 關(guān)系的性質(zhì),定義4.11 設(shè) R 為集合 A上的二元關(guān)系 （1）若對(duì)每個(gè) ，皆有 ，則稱(chēng) R 為自反的。其形式化表示為 R是自反的 （2）若對(duì)每個(gè) ，皆有 ，則稱(chēng) R 為反自反的。其形式化表示為 R是反自反的 （3）對(duì)任意的 ，若 ，則 ，就稱(chēng) R 為對(duì)稱(chēng)的。其形式化表示為 R是對(duì)稱(chēng)的 （4）對(duì)任意的 ，若 ，且 ，則x=y，就稱(chēng) R 為反對(duì)稱(chēng)的。其形式化表示為 R是反對(duì)稱(chēng)的,34,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

23、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.4 關(guān)系的性質(zhì),定義4.11 設(shè) R 為集合 A上的二元關(guān)系 （5）對(duì)任意的 ，若 且 ，則 就稱(chēng) R 為可傳遞的。其形式化表示為 R是可傳遞的 （6）存在 ，并且 而 ，則稱(chēng) R 為不可傳遞的。其形式化表示為 R是不可傳遞的,35,,,,,,,,,,,,,,,,,,,,,,,,,,,

24、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.4 關(guān)系的性質(zhì),例4.11 考慮自然數(shù)集合 上的普通相等關(guān)系“”，大于關(guān)系“”和大于等于關(guān)系“”，則顯然有 （1）“”關(guān)系是自反的、對(duì)稱(chēng)的、反對(duì)稱(chēng)的、可傳遞的。 （2）“”關(guān)系是反自反的、反對(duì)稱(chēng)的、可傳遞的。 （3）“”關(guān)系是自反的、反對(duì)稱(chēng)的、可傳遞的。 例4.12 空集 R上的二元空關(guān)系顯然是自反的、對(duì)稱(chēng)的、

25、反對(duì)稱(chēng)的、反自反的、可傳遞的。,36,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.4 關(guān)系的性質(zhì),定理4.10 設(shè) R為 A 的二元關(guān)系，則 （1）R 在 A上自反當(dāng)且僅當(dāng) （2）R 在 A 上反自反當(dāng)且僅當(dāng) （3）R 在 A 上對(duì)稱(chēng)當(dāng)且僅當(dāng) （4）R 在 A 上反對(duì)稱(chēng)當(dāng)且僅當(dāng) （5）R 在 A 上可傳

26、遞當(dāng)且僅當(dāng),37,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,多重序元與笛卡爾乘積,,主要內(nèi)容,PART 01,關(guān)系的基本概念,PART 02,關(guān)系的運(yùn)算,PART 03,關(guān)系的性質(zhì),PART 04,關(guān)系的表示,PART 05,關(guān)系的閉包運(yùn)算,PART 06,特殊關(guān)系,PA

27、RT 07,關(guān)系型數(shù)據(jù)庫(kù),PART 08,2020/8/28,38,,,,,,,,,,,,,,,,,,,,,4.5 關(guān)系的表示,定義4.12 設(shè) A 和 B為任意的非空有限集，R 為任意一個(gè)從A 到 B 的二元關(guān)系。以 中的每個(gè)元素為結(jié)點(diǎn)。對(duì)每個(gè) 皆畫(huà)一條從 x 到 y 的有向邊，這樣得到的一個(gè)圖稱(chēng)為關(guān)系 的關(guān)系圖。 例4.14 設(shè) ， ，從 A 到 B 的二元關(guān)系 R 為 ， 于是有,39,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

28、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關(guān)系圖,,,,,,,R的關(guān)系圖,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關(guān)系的表示,可以看出關(guān)系圖明確地反映了關(guān)系的某些性質(zhì)。如果關(guān)系 是自反的，則每個(gè)結(jié)點(diǎn)上都有一條從自身出發(fā)又指向自身的環(huán)邊；如果關(guān)系是反自反的，則任何結(jié)點(diǎn)上部沒(méi)有帶環(huán)的邊；如果一個(gè)關(guān)系 既不是自反的，也不是反自反的，則在某些結(jié)點(diǎn)上有帶環(huán)的邊，而在某些結(jié)點(diǎn)上沒(méi)有帶環(huán)的邊。 如果關(guān)系是對(duì)稱(chēng)的，則從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)間必定有往返兩條弧線。如果關(guān)系是反對(duì)稱(chēng)的，則在兩個(gè)結(jié)點(diǎn)間只會(huì)

29、存在單向弧線。,40,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關(guān)系圖,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關(guān)系的表示,圖4.2給出了具有各種性質(zhì)的關(guān)系的關(guān)系圖。當(dāng)集合中元素的數(shù)目較大時(shí)，關(guān)系的圖解表示就不是很方便了，由于計(jì)算機(jī)上表達(dá)矩陣并不困難，所以我們?cè)噲D尋求關(guān)系的矩陣表示。,41,,,,,,,,,,,,,

30、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關(guān)系圖,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關(guān)系的表示,定義4.13 給定兩個(gè)有限集合 和 ， R 是從 X 到 Y 的二元關(guān)系。如果有 則稱(chēng) 是 R 的關(guān)系矩陣，記作,42,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

31、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關(guān)系圖,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關(guān)系的表示,,43,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

32、,,,,關(guān)系圖,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關(guān)系的表示,,44,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關(guān)系圖,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關(guān)系的表示,,45,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

33、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關(guān)系圖,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關(guān)系的表示,,46,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

34、,,,,,,,,,,,,,,,,,,,,,關(guān)系圖,2020/8/28,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,多重序元與笛卡爾乘積,,主要內(nèi)容,PART 01,關(guān)系的基本概念,PART 02,關(guān)系的運(yùn)算,PART 03,關(guān)系的性質(zhì),PART 04,關(guān)系的表示,PART 05,關(guān)系的閉包運(yùn)算,PART 06,特殊關(guān)系,PART 07,關(guān)系型數(shù)據(jù)庫(kù),PART 08,2020/8/28,47,,,,,,,,,,,,,,,,,,,,,4.6 關(guān)系的閉包運(yùn)算,前面我們已經(jīng)介紹了如何使用關(guān)系的合成運(yùn)算去構(gòu)成新的關(guān)系，下面我們討論如何由給定的關(guān)系 R 構(gòu)成一個(gè)新的關(guān)系 并且 和

35、 應(yīng)具有某些性質(zhì)。 把確保這些性質(zhì)的那些序偶補(bǔ)充到 R 中去就可構(gòu)成 。給定一個(gè)二元關(guān)系 ，它規(guī)定了局部的性質(zhì)，希望求得的是具有全面性質(zhì)的另一個(gè)二元關(guān)系 。例如，由 R 構(gòu)成一個(gè)可傳遞關(guān)系 。 在日常家族關(guān)系中也有類(lèi)似的情形。如果 R是個(gè)父子關(guān)系，則 可能是個(gè)祖先關(guān)系；如果 R 是個(gè)子父關(guān)系，則 可能是個(gè)后代關(guān)系。,48,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

36、,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.6 關(guān)系的閉包運(yùn)算,定義4.14 給定集合 A，R 是 A上的二元關(guān)系。如果有另一個(gè)關(guān)系 滿足 （1） 是自反的（對(duì)稱(chēng)的、可傳遞的）。 （2） 。 （3）對(duì)于任何自反的(對(duì)稱(chēng)的、可傳遞的)關(guān)系 ，如果有 ，則 ，則稱(chēng)關(guān)系 為 的自反的（對(duì)稱(chēng)的，可傳遞的）閉包。并用 表示 的自反閉包，用 表示 的對(duì)稱(chēng)閉包，用 表示 的可傳遞閉包。,49,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

37、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.6 關(guān)系的閉包運(yùn)算,定理4.11 給定集合 X ，R 是 X上的關(guān)系。于是可有 （1） R是自反的當(dāng)且僅當(dāng) （2） R是對(duì)稱(chēng)的當(dāng)且僅當(dāng) （3） R是可傳遞的當(dāng)且僅當(dāng) 定理4.12 設(shè) R 是 上的二元關(guān)系，則有 （1） （2） （3）,50,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

38、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.6 關(guān)系的閉包運(yùn)算,不難看出，整數(shù)集合中，小于關(guān)系“ ”的自反閉包是“ ”，對(duì)稱(chēng)閉包是不等關(guān)系“ ”；恒等關(guān)系 的自反閉包是 ；對(duì)稱(chēng)閉包是 ；不等關(guān)系“ ”的自反閉包是全域關(guān)系，對(duì)稱(chēng)閉包是不等關(guān)系“ ”；空關(guān)系的自反閉包是恒等關(guān)系 ，對(duì)稱(chēng)閉包是空關(guān)系。,

39、51,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.6 關(guān)系的閉包運(yùn)算,例4.20 給定集合 ， 和 是 A 上的關(guān)系，試求出 和 ，并畫(huà)出相應(yīng)的關(guān)系圖來(lái)。 解： 關(guān)系 R，S 及其傳遞

40、閉包 ， 的關(guān)系圖如圖4.6所示。,52,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.6 關(guān)系的閉包運(yùn)算,定理4.13 設(shè) X 是含有 n個(gè)元素的集合，R 是 X上的二元關(guān)系。于是可有 例4.21 設(shè)集合

41、 ，R 是X中的二元關(guān)系，R 的關(guān)系圖如圖4.7所示，試畫(huà)出 R 的可傳遞閉包 的關(guān)系圖。 解：R 的可傳遞閉包 的關(guān)系圖如圖4.8所示。,53,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,圖4.7 R的關(guān)系圖,圖4.8 t(R) 的關(guān)系圖,20

42、20/8/28,,,,,,,,,,,,,,,,,,,,,4.6 關(guān)系的閉包運(yùn)算,定理4.15 設(shè) A 是集合，R 是集合 A上的二元關(guān)系。于是可有 （1） （2） （3）,54,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,

43、,,,,,,,,,,,,,,,,,,,,,多重序元與笛卡爾乘積,,主要內(nèi)容,PART 01,關(guān)系的基本概念,PART 02,關(guān)系的運(yùn)算,PART 03,關(guān)系的性質(zhì),PART 04,關(guān)系的表示,PART 05,關(guān)系的閉包運(yùn)算,PART 06,特殊關(guān)系,PART 07,關(guān)系型數(shù)據(jù)庫(kù),PART 08,2020/8/28,55,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定義4.15 給定非空集合S，及非空集合 ，如果有 （1） （2） 則稱(chēng)集合A 是集合 S 的覆蓋。 例如，設(shè)集合 ，并且給定S 的各子集的集合 和 ；顯然集合 A 和

44、集合 B 都是集合 S 的覆蓋。即覆蓋不唯一。,56,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,集合的覆蓋,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定義4.16 給定非空集合 S，及非空集 ，如果有

45、 （1） （2） 或 （3） 則稱(chēng)集合A 是集合 的一個(gè)劃分。劃分中的元素 稱(chēng)為劃分的類(lèi)。如果劃分是個(gè)有限集合，則劃分的秩是劃分的類(lèi)的數(shù)目。若劃分是個(gè)無(wú)限集合，則劃分的秩是無(wú)限的。劃分是覆蓋的特定情況，即 A中元素互不相交的特定情況。,57,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

46、,,,,,,,,,,,,,,,,,,,集合的劃分,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,例如 設(shè) ，試考察 S 的各子集的下列集合。 顯然集合 A和 B是S 的覆蓋，當(dāng)然 C，D ，E 也都是 S的覆蓋；同時(shí) C，D ，E 也還是 S 的劃分，并且C 的秩是2，D 的秩是1，E 的秩是3；而F 既不是覆蓋也不是劃分；集合S 的最大劃分是以S 的單個(gè)元素為類(lèi)的劃分，如上面的 E；S 的最小劃分是以S 為類(lèi)的劃分，如上面的 D。,58,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

47、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,集合的劃分和覆蓋,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定義4.17 設(shè) A和 是非空集合S 的兩種劃分，并可表示成 如果 的每一個(gè)類(lèi) ，都是A 的某一個(gè)類(lèi) 的子集，則稱(chēng)劃分 是劃分 A 的加細(xì)，并說(shuō)成是 加

48、細(xì)了A 。如果 是A 的加細(xì)和 ，則稱(chēng) 是A 的真加細(xì)。 劃分全集 E的過(guò)程，可看成是在表達(dá)全集 E的文氏圖上劃出分界線的過(guò)程。設(shè) A，B ，C 是全集E 的三個(gè)子集。由 A，B 和 C生成的E 的劃分的類(lèi)，稱(chēng)為極小項(xiàng)或完全交集。對(duì)于三個(gè)子集 A，B 和C 來(lái)說(shuō)，共有 個(gè)極小項(xiàng)，分別用 來(lái)表示。,59,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

49、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,集合的劃分和覆蓋,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,由圖4.可知 并且 是互不相交的， 一般情況，如果 是全集E 的 n個(gè)子集，則由這n 個(gè)子集能夠生成 個(gè)極小項(xiàng)，分別用 來(lái)表示它們。這些極小項(xiàng)互不相交，并且并起來(lái)等于全集E。,60,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

50、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,集合的劃分和覆蓋,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定義4.18 設(shè) X是任意集合, R是集合X 中的二元關(guān)系。如果 R是自反的、對(duì)稱(chēng)的和可傳遞的，也就是說(shuō),如果有 （1） （2） （3） 則稱(chēng) R 是等價(jià)關(guān)系。 如果 R 是集合 A上的等價(jià)關(guān)系，

51、則 R的定義域 是集合 A 自身，所以稱(chēng) R 是定義于集合A 上的關(guān)系。實(shí)數(shù)集合中數(shù)的等于關(guān)系，全集的各子集間的相等關(guān)系，命題集合中等價(jià)命題間的恒等關(guān)系等，都是等價(jià)關(guān)系。,61,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價(jià)關(guān)系,,,,,,,,,,,,,,,

52、,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,例4.22 給定集合 ，R 是 A上的二元關(guān)系，并且 R 給定成 ， 試證明 R 是一個(gè)等價(jià)關(guān)系，并畫(huà)出 R 的關(guān)系圖和寫(xiě)出 R 的關(guān)系矩陣。 解：R 的關(guān)系矩陣如下： 在圖4.10中給出了 R 的關(guān)系圖。由 R 的關(guān)系矩陣和關(guān)系圖可以看出，R 是等價(jià)關(guān)系。,62,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

53、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價(jià)關(guān)系,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,R的關(guān)系圖,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,設(shè) 是正整數(shù)集合，m 是正整數(shù)。對(duì)于 來(lái)說(shuō) ，可將 R 定義成 這里，“ ”等價(jià)于命題“當(dāng)用 m去除x 和y 時(shí)，它們都有同樣的余數(shù)”。故關(guān)系 R 也稱(chēng)為模 m 同余關(guān)系。,63,,,

54、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價(jià)關(guān)系,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定義4.19 設(shè) m是個(gè)正整數(shù)和 。如果對(duì)

55、于某一個(gè)整數(shù) n，有 ,則稱(chēng) x 模等價(jià)于 y，并記作 整數(shù)m 稱(chēng)為等價(jià)的模數(shù)。 顯然，這里是用“ ”表示模 m 等價(jià)關(guān)系 R 。 定理4.17 任何集合 中的模 m 相等關(guān)系 是一個(gè)等價(jià)關(guān)系。,64,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

56、,,,,,,,,,,,,,,,,,,,等價(jià)關(guān)系,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定義4.20 設(shè) R 是集合 A 上的等價(jià)關(guān)系：對(duì)于任何 來(lái)說(shuō)，可把集合 規(guī)定成 并稱(chēng)它是由 x關(guān)于 R 的等價(jià)類(lèi)。 為了簡(jiǎn)單起見(jiàn)，有時(shí)也把 就寫(xiě)成 或 。不難看出，集合 應(yīng)是由集合 A中與 x 有等價(jià)關(guān)系 R的那些元素所組成的。,65,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

57、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價(jià)類(lèi),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,例4.23 設(shè) ，R 是 A上的等價(jià)關(guān)系，并把 R給定成 試畫(huà)出等價(jià)關(guān)系圖，求出 A中各元素關(guān)于 R的等價(jià)類(lèi)。 解：等

58、價(jià)關(guān)系如圖4.11所示。由等價(jià)關(guān)系圖不難看出 圖4.11 等價(jià)關(guān)系圖,66,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價(jià)類(lèi),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2

59、020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定理4.18 設(shè) A是一個(gè)集合，R 是 A上的等價(jià)關(guān)系。如果 ，則 定理4.19 設(shè) R是集合 A上的等價(jià)關(guān)系。于是可有 （1）對(duì)于所有的 ，或者 或者 。 （2）,67,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

60、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價(jià)類(lèi),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定理4.20 設(shè) R是非空集合 A上的等價(jià)關(guān)系。R 的等價(jià)類(lèi)的集合 是A 的一個(gè)劃分。根據(jù)定理4.18和定理4.19就能夠證明此定理。此定理說(shuō)明非空集合的劃分和集合中的等價(jià)關(guān)系之間，存在一種自然對(duì)應(yīng)關(guān)系。 定義4.21 設(shè)R 是非空集合 A上的等價(jià)關(guān)系。以 R的所有等價(jià)類(lèi)作為元素的集合 稱(chēng)為S 關(guān)于R

61、的商集，記作 ，也可寫(xiě)成,68,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,商集,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,

62、,,,,,,,,,,,4.7 特殊關(guān)系,下面來(lái)考察集合 A中的兩個(gè)特殊等價(jià)關(guān)系：全域關(guān)系 和恒等關(guān)系 。顯然這兩種關(guān)系都是 A上的等價(jià)關(guān)系。由全域關(guān)系所生成的商集 僅包含一個(gè)元素 A，而由恒等關(guān)系所生成的商集 中的每個(gè)元素都是由 A中的單個(gè)元素所組成的。 所對(duì)應(yīng)的劃分是A 的最小劃分， 所對(duì)應(yīng)的劃分是 A的最大劃分。這兩種劃分被稱(chēng)為 A上的平凡劃分。,69,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

63、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,例4.24 令R 是整數(shù)集合 Z中的“模3同余”關(guān)系，R 可給定成 試求 Z 的元素所生成的 R 等價(jià)類(lèi)。 解：等價(jià)類(lèi)是,70,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

64、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價(jià)類(lèi),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定理4.21 設(shè)C 是非空集合A 的一個(gè)劃分，則由這個(gè)劃分所確定的下述關(guān)

65、系R ： 必定是個(gè)等價(jià)關(guān)系，并稱(chēng) R為由劃分 C導(dǎo)出的 A上的等價(jià)關(guān)系。,71,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價(jià)類(lèi),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

66、,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,,72,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價(jià)類(lèi),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關(guān)系,定義4.22 給定集合 A中的二元關(guān)系 R，如果R是自反的、對(duì)稱(chēng)的，則稱(chēng) 是相容關(guān)系。也就是說(shuō)，可以把 規(guī)定成： （1） （2） 顯然，所有的等價(jià)關(guān)系都是相容關(guān)系，但相容關(guān)系并不一定是等價(jià)關(guān)系。下面舉例說(shuō)明相容關(guān)系。 設(shè)集合 ，A 中的關(guān)系 不難看出 R是