離散數(shù)學第四章二元關系.ppt

《離散數(shù)學第四章二元關系.ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學第四章二元關系.ppt（100頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

13、示為,20,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關系的運算,例4.8 ，則,21,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關系的運算,定義4.7 設 R 是二元關系，將 R 中每個序偶的第一元素同第二元素交換后所得到的關系稱為

14、 R 的逆關系，簡稱 R 的逆，記作 ，其形式化表示為 定義4.8 設 F，G 為二元關系，G 對 F 的右合成記作 ，其形式化定義為,22,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關系的運算,例4.9 設 ， ，則 類似的也可以定義關系的左合成，即,23,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

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

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

17、，則 （1） （2）,26,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關系的運算,定理4.3 設 F，G 為任意關系，則 （1） （2） 定理4.4 設 R為 A上的關系，則,27,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,202

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

19、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關系的運算,上述的對關系的合成運算可以推廣到一般情況。如果 是從 到 的關系， 是從 到 的關系，， 是從 到 的關系，則無括號表達式 表達了從 到 的關系。特別，當 和 時，也就是說當集合 A上的所有 都是同樣的關系時，A 上的合成關系 可表達成 ，并稱作關系R的冪。,30,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

20、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關系的運算,,31,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.3 關系的運算,,32,,,

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

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

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

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

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

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

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

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

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

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

31、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關系圖,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關系的表示,,43,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

32、,,,,關系圖,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關系的表示,,44,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關系圖,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關系的表示,,45,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

33、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,關系圖,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.5 關系的表示,,46,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

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

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

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

37、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.6 關系的閉包運算,定理4.11 給定集合 X ，R 是 X上的關系。于是可有 （1） R是自反的當且僅當 （2） R是對稱的當且僅當 （3） R是可傳遞的當且僅當 定理4.12 設 R 是 上的二元關系，則有 （1） （2） （3）,50,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

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

39、51,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.6 關系的閉包運算,例4.20 給定集合 ， 和 是 A 上的關系，試求出 和 ，并畫出相應的關系圖來。 解： 關系 R，S 及其傳遞

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

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

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

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

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

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

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

47、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,集合的劃分和覆蓋,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關系,定義4.17 設 A和 是非空集合S 的兩種劃分，并可表示成 如果 的每一個類 ，都是A 的某一個類 的子集，則稱劃分 是劃分 A 的加細，并說成是 加

48、細了A 。如果 是A 的加細和 ，則稱 是A 的真加細。 劃分全集 E的過程，可看成是在表達全集 E的文氏圖上劃出分界線的過程。設 A，B ，C 是全集E 的三個子集。由 A，B 和 C生成的E 的劃分的類，稱為極小項或完全交集。對于三個子集 A，B 和C 來說，共有 個極小項，分別用 來表示。,59,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

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

50、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,集合的劃分和覆蓋,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關系,定義4.18 設 X是任意集合, R是集合X 中的二元關系。如果 R是自反的、對稱的和可傳遞的，也就是說,如果有 （1） （2） （3） 則稱 R 是等價關系。 如果 R 是集合 A上的等價關系，

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

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

53、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價關系,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,R的關系圖,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關系,設 是正整數(shù)集合，m 是正整數(shù)。對于 來說 ，可將 R 定義成 這里，“ ”等價于命題“當用 m去除x 和y 時，它們都有同樣的余數(shù)”。故關系 R 也稱為模 m 同余關系。,63,,,

54、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價關系,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關系,定義4.19 設 m是個正整數(shù)和 。如果對

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

56、,,,,,,,,,,,,,,,,,,,等價關系,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關系,定義4.20 設 R 是集合 A 上的等價關系：對于任何 來說，可把集合 規(guī)定成 并稱它是由 x關于 R 的等價類。 為了簡單起見，有時也把 就寫成 或 。不難看出，集合 應是由集合 A中與 x 有等價關系 R的那些元素所組成的。,65,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

57、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價類,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關系,例4.23 設 ，R 是 A上的等價關系，并把 R給定成 試畫出等價關系圖，求出 A中各元素關于 R的等價類。 解：等

58、價關系如圖4.11所示。由等價關系圖不難看出 圖4.11 等價關系圖,66,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價類,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2

59、020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關系,定理4.18 設 A是一個集合，R 是 A上的等價關系。如果 ，則 定理4.19 設 R是集合 A上的等價關系。于是可有 （1）對于所有的 ，或者 或者 。 （2）,67,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

60、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價類,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關系,定理4.20 設 R是非空集合 A上的等價關系。R 的等價類的集合 是A 的一個劃分。根據(jù)定理4.18和定理4.19就能夠證明此定理。此定理說明非空集合的劃分和集合中的等價關系之間，存在一種自然對應關系。 定義4.21 設R 是非空集合 A上的等價關系。以 R的所有等價類作為元素的集合 稱為S 關于R

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

62、,,,,,,,,,,,4.7 特殊關系,下面來考察集合 A中的兩個特殊等價關系：全域關系 和恒等關系 。顯然這兩種關系都是 A上的等價關系。由全域關系所生成的商集 僅包含一個元素 A，而由恒等關系所生成的商集 中的每個元素都是由 A中的單個元素所組成的。 所對應的劃分是A 的最小劃分， 所對應的劃分是 A的最大劃分。這兩種劃分被稱為 A上的平凡劃分。,69,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

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

64、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價類,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2020/8/28,,,,,,,,,,,,,,,,,,,,,4.7 特殊關系,定理4.21 設C 是非空集合A 的一個劃分，則由這個劃分所確定的下述關

65、系R ： 必定是個等價關系，并稱 R為由劃分 C導出的 A上的等價關系。,71,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價類,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

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