《數(shù)學(xué)集合論》ppt課件

1、1 集合論集合論(Set Theory)是現(xiàn)代數(shù)學(xué)的基礎(chǔ)它的起源可是現(xiàn)代數(shù)學(xué)的基礎(chǔ)它的起源可追溯到追溯到16世紀(jì)末，但集合論實(shí)際發(fā)展是由世紀(jì)末，但集合論實(shí)際發(fā)展是由 19世紀(jì)世紀(jì) 70年代德國數(shù)學(xué)家康托爾年代德國數(shù)學(xué)家康托爾(G . Cantor) 在無窮序列和分在無窮序列和分析的有關(guān)課題的理論研究中創(chuàng)立的析的有關(guān)課題的理論研究中創(chuàng)立的. 集合論在計(jì)算機(jī)科學(xué)、人工智能領(lǐng)域、邏輯學(xué)及語言集合論在計(jì)算機(jī)科學(xué)、人工智能領(lǐng)域、邏輯學(xué)及語言學(xué)等方面都有著重要的應(yīng)用對于從事計(jì)算機(jī)科學(xué)的學(xué)等方面都有著重要的應(yīng)用對于從事計(jì)算機(jī)科學(xué)的工作者來說，集合論是不可缺少的理論知識，熟悉和工作者來說，集合論是不可缺少的理

2、論知識，熟悉和掌握它是十分必要的掌握它是十分必要的第第3章章 集合、關(guān)系與映射集合、關(guān)系與映射23.1 集合的基本概念集合的基本概念一、集合的概念一、集合的概念 把具有相同性質(zhì)的所有對象匯集在一起就稱為一個(gè)把具有相同性質(zhì)的所有對象匯集在一起就稱為一個(gè)集合集合. 把組成集合的對象稱為把組成集合的對象稱為元素元素。例如：例如：方程方程x210的實(shí)數(shù)解集合；的實(shí)數(shù)解集合；26個(gè)英文字母的集合；個(gè)英文字母的集合；坐標(biāo)平面上所有點(diǎn)的集合；坐標(biāo)平面上所有點(diǎn)的集合；3二、集合的表示二、集合的表示 一般用帶下角標(biāo)或不帶下角標(biāo)的大寫字母表示集合，如一般用帶下角標(biāo)或不帶下角標(biāo)的大寫字母表示集合，如 A, B, P

3、1, P2, Q1, Q2等等;一般用帶標(biāo)號或不帶標(biāo)號的小寫字母表示集合，如一般用帶標(biāo)號或不帶標(biāo)號的小寫字母表示集合，如 a, b, c, a1, a2,等等;3.1 集合的基本概念集合的基本概念4三、說明集合的方法三、說明集合的方法（1）列舉法）列舉法：如：如A=1,2,3,4，B0,2,4,6,8,10,（2）描述法）描述法：如：如A=x|P(x),P(x)是元素是元素x所具有的性質(zhì)。所具有的性質(zhì)。例：例：A=x|x2-5x+6=0（3）特定的字符集：）特定的字符集：在集合中常約定：在集合中常約定： N表示自然數(shù)集合；表示自然數(shù)集合；I(或或Z)表示整數(shù)集合；表示整數(shù)集合； Q表示有理數(shù)集

4、合；表示有理數(shù)集合；R表示實(shí)數(shù)集合；表示實(shí)數(shù)集合； E表示偶數(shù)集合；表示偶數(shù)集合； O表示奇數(shù)集合；表示奇數(shù)集合； P表示素?cái)?shù)集合；表示素?cái)?shù)集合； F表示分?jǐn)?shù)集合；表示分?jǐn)?shù)集合； C表示復(fù)數(shù)集合；表示復(fù)數(shù)集合； R表示正實(shí)數(shù)集合表示正實(shí)數(shù)集合； R*表示非零實(shí)數(shù)，即表示非零實(shí)數(shù)，即R*=x|xRx0; （4）圖示法）圖示法：用封閉曲線表示集合，封閉曲線內(nèi)的點(diǎn)：用封閉曲線表示集合，封閉曲線內(nèi)的點(diǎn) 表示集合中的元素表示集合中的元素3.1 集合的基本概念集合的基本概念5注意：注意：(1)集合的元素是確定的，即對集合集合的元素是確定的，即對集合A，任一元素，任一元素a或?qū)儆诖思匣驅(qū)儆诖思?aA)或

5、不屬于此集合或不屬于此集合(a A) ，兩者必居其一。兩者必居其一。(2)集合中的每個(gè)元素均不相同。集合中的每個(gè)元素均不相同。 即集合即集合 1,2,2,3,4,4 = 1,2,3,4 (3) 集合中的元素是無序的。集合中的元素是無序的。 例：例：4,3=3,43.1 集合的基本概念集合的基本概念6包含關(guān)系：包含關(guān)系：若集合若集合B中的每個(gè)元素都是中的每個(gè)元素都是A中的元素，稱中的元素，稱B包含于包含于A或或A包含包含B，稱集合，稱集合B是集合是集合A的一個(gè)的一個(gè)子集子集記為記為B A : ( x)(xBxA) 如果如果B不被不被A包含，則記作包含，則記作B A。 例如：例如：N Z Q R

6、C，但，但Z N。 3.1 集合的基本概念集合的基本概念四、集合間的關(guān)系：相等關(guān)系和包含關(guān)系四、集合間的關(guān)系：相等關(guān)系和包含關(guān)系 結(jié)論：結(jié)論：對任何集合對任何集合A都有都有A AA。 例如：例如： Aa，a和和a的關(guān)系為的關(guān)系為 a A ，又有，又有 aA 7若若B是是A的子集且在的子集且在A中存在不屬于中存在不屬于B的元素，則稱的元素，則稱集合集合B是集合是集合A的一個(gè)的一個(gè)真子集真子集，記為，記為B A : B A( x)(xAx B ，稱，稱A真包含于真包含于B。3.1 集合的基本概念集合的基本概念例如：例如：N Z Q R C8相等關(guān)系：相等關(guān)系：若集合若集合A的任一元素都是集合的任一

7、元素都是集合B中的元素并且集合中的元素并且集合B中的元素也是集合中的元素也是集合A中元素，則稱這兩個(gè)集合中元素，則稱這兩個(gè)集合相等相等，記為記為AB :( x)(aA aB) 或或 AB : (A B)(B A)否則稱這兩個(gè)集合否則稱這兩個(gè)集合不相等不相等，記為，記為A B 3.1 集合的基本概念集合的基本概念9五、子集具有的性質(zhì)：五、子集具有的性質(zhì)： A A 自反性自反性 A BB AAB 反對稱性反對稱性 A BB CA C 傳遞性傳遞性證明證明: 這里僅給出的證明這里僅給出的證明, 余下類似可證余下類似可證 A BB A ( x)(x Ax B)( x)(x Bx A)( x)(x Ax

8、 B)(x Bx A)( x)(x Ax B) AB 3.1 集合的基本概念集合的基本概念10不包含任何元素的集合稱為不包含任何元素的集合稱為空集空集。記為。記為例如：例如：A=x|x2-1, xR對任何集合對任何集合A， A全集全集U：所有集合都是所有集合都是U的子集。的子集。3.1 集合的基本概念集合的基本概念11六、集合的運(yùn)算六、集合的運(yùn)算交運(yùn)算：交運(yùn)算： AB := x|x Ax B 3.1 集合的基本概念集合的基本概念12并運(yùn)算：并運(yùn)算： AB: x|x Ax B 3.1 集合的基本概念集合的基本概念13兩個(gè)集合的并和交運(yùn)算可以推廣成兩個(gè)集合的并和交運(yùn)算可以推廣成n個(gè)集合的并和交：個(gè)

9、集合的并和交：A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn六、集合的運(yùn)算六、集合的運(yùn)算3.1 集合的基本概念集合的基本概念并和交運(yùn)算還可以推廣到無窮多個(gè)集合的情況：并和交運(yùn)算還可以推廣到無窮多個(gè)集合的情況：A1A2A1A2 14差運(yùn)算：差運(yùn)算： BA : x|x Bx A3.1 集合的基本概念集合的基本概念15全集全集U：所有集合都是所有集合都是U的子集。的子集。補(bǔ)集：補(bǔ)集：全集全集U與集合與集合A的差集稱為的差集稱為A的補(bǔ)集，的補(bǔ)集， 記為記為 UA=x|x A A AUA3.1 集合的基本概念集合的基本概念16對稱差運(yùn)算：對稱差運(yùn)算： AB:= x|x (AB)x

10、(BA) A B3.1 集合的基本概念集合的基本概念顯然：顯然： A A A B B A ABA A UAB17圖形表示集合間的關(guān)系文氏圖圖形表示集合間的關(guān)系文氏圖(Venn Digram表示表示)UA, B3.1 集合的基本概念集合的基本概念 AB181. 交換律交換律 ABBA ； ABBA2. 結(jié)合律結(jié)合律 A(BC)=(AB)C A(BC)=(AB)C3. 分配律分配律 A(BC)=(AB) (AC) A(BC)=(AB)(AC)4. 吸收律吸收律 A(AB)=A ； A(AB)=A5. De Mergam律律 6. 冪等律冪等律 AAA ; AAA7. 補(bǔ)余律補(bǔ)余律 8. 零律零律

11、A AUU9. 壹律壹律 AUA AA10. 互補(bǔ)律互補(bǔ)律 11. 重非律重非律 集合運(yùn)算的算律：設(shè)集合運(yùn)算的算律：設(shè)A,B,C是任意三個(gè)集合。是任意三個(gè)集合。BABA;BABA UAA;AA U;UAA 19定理：設(shè)定理：設(shè)A, B, C, D是任意三個(gè)集合。是任意三個(gè)集合。（1） 若若A B，則，則ABA ；ABB； (BA)AB（2） AB A, B; A, B AB（3） 若若A B且且C D；則；則AC BD ； AC BD （4） 若若AB ；則稱；則稱A，B不相交；若還有不相交；若還有ABU， 則稱則稱A，B為互補(bǔ)。為互補(bǔ)。 （5）若）若A B，則，則 （6） A(BC)(AB)

12、(AC) ； A(B C) (AB) (AC) (7) A (BC)(A B) (A C) 但但 A (BC) (AB) (AC) UAB,BA,AB冪集：冪集：由集合由集合A的所有子集組成的集合稱為的所有子集組成的集合稱為A的冪集。的冪集。 記為記為P(A)或或2A 即即P(A):B|B A例如：例如：Aa P(A)=,a A=a,b P(A)=,a,b,a,b A=,a P(A)=,a,a設(shè)設(shè)Aa1,a2,an,則則A的子集的子集B的的二進(jìn)制編碼二進(jìn)制編碼為：為：若若ai B，則，則ai記為記為1，否則記為，否則記為0，i1,2,n.按此規(guī)定得到的一個(gè)二進(jìn)制數(shù)稱為集合按此規(guī)定得到的一個(gè)二進(jìn)

13、制數(shù)稱為集合B的編碼。的編碼。設(shè)設(shè)|A|=n,則則P(A)= 2n21集合的應(yīng)用求若干有限集合并的元素個(gè)數(shù)。集合的應(yīng)用求若干有限集合并的元素個(gè)數(shù)。定理：定理：設(shè)設(shè)A1，A2是兩個(gè)有限集合，是兩個(gè)有限集合， 記記|A1|, |A2|為它們所含的元素個(gè)數(shù)，為它們所含的元素個(gè)數(shù)， 則則|A1A2|= |A1|+|A2| A1A2|in1i1nnkji1kjinji1jin1iin1iiA) 1(.AAAAAAA 推廣：推廣：例例1：假設(shè)某班有假設(shè)某班有50名學(xué)生，其中英語成績?yōu)閮?yōu)的名學(xué)生，其中英語成績?yōu)閮?yōu)的25名，名，數(shù)學(xué)成績?yōu)閮?yōu)的數(shù)學(xué)成績?yōu)閮?yōu)的20名，又有名，又有15名學(xué)生數(shù)學(xué)和英語成績均名學(xué)生數(shù)

14、學(xué)和英語成績均為優(yōu)。問這兩門課都不是優(yōu)的學(xué)生有幾名？為優(yōu)。問這兩門課都不是優(yōu)的學(xué)生有幾名？解：解：英語成績?yōu)閮?yōu)的學(xué)生組成的集合是英語成績?yōu)閮?yōu)的學(xué)生組成的集合是A；|A|=25 數(shù)學(xué)成績?yōu)閮?yōu)的學(xué)生組成的集合是數(shù)學(xué)成績?yōu)閮?yōu)的學(xué)生組成的集合是B；|B|=20 因此這兩門可成績均為優(yōu)的學(xué)生組成的集合是因此這兩門可成績均為優(yōu)的學(xué)生組成的集合是AB； | AB |=15 所以所以 | AB |=|A| +|B| AB |=25201530， 這說明兩門課中至少有一門課為優(yōu)的學(xué)生是這說明兩門課中至少有一門課為優(yōu)的學(xué)生是30名，名， 所以這兩門課都不是優(yōu)的學(xué)生有所以這兩門課都不是優(yōu)的學(xué)生有503020名名例例

15、2 2：求出在求出在1 1和和9090之間之間( (包括包括90)90)能被能被2 2，3 3，5 5 任一任一 數(shù)整除的整數(shù)個(gè)數(shù)。數(shù)整除的整數(shù)個(gè)數(shù)。解：設(shè)解：設(shè)A1，A2，A3分別為表示分別為表示1和和90之間能被之間能被2，3，5 任一數(shù)整除的整數(shù)集合。任一數(shù)整除的整數(shù)集合。 6636915183045|AAA|AA|AA|AA|A|A|A|AAA|353290|AAA|65390|AA|95290|AA|153290|AA|18590|A|30390|A|45290|A|321313221321321321323121321可可得得 所以所以 在在1和和90之間之間(包括包括90)能被能

16、被2，3，5 任一數(shù)整除任一數(shù)整除的整數(shù)個(gè)數(shù)為的整數(shù)個(gè)數(shù)為66。243.2 關(guān)關(guān) 系系定義定義1 1（笛卡爾積或直乘積）（笛卡爾積或直乘積） 設(shè)設(shè)A，B是任意兩個(gè)集合，是任意兩個(gè)集合， AB|xA, yB 稱為集合稱為集合A和和B的笛卡爾積或直乘積。的笛卡爾積或直乘積。 稱為有序?qū)蛐蚺紝?，稱為有序?qū)蛐蚺紝?，x稱為序偶對的第一稱為序偶對的第一 個(gè)元素，個(gè)元素，y稱為序偶對的第二個(gè)元素。稱為序偶對的第二個(gè)元素。 = iff a=x且且b=y25例：例：A=a,b，B=1,2,3，C=x則則 AB, BA, , , , 結(jié)論：設(shè)結(jié)論：設(shè) |A|=n, |B|=m, 則則 | AB |=nm3.2

17、 關(guān)關(guān) 系系 (AB)C,x,x,x, ,x,x,x結(jié)論：結(jié)論： (AB)C A(BC)A(BC)a,a,a, b,b,b,26笛卡兒積運(yùn)算的性質(zhì)笛卡兒積運(yùn)算的性質(zhì): 1. 若若A，B中有一個(gè)空集中有一個(gè)空集,則它們的笛卡兒積是空集則它們的笛卡兒積是空集, 即即 AA A 2. 當(dāng)當(dāng)AB且且A,B都不是空集時(shí)都不是空集時(shí),有有 ABBA。 所以所以,笛卡兒積運(yùn)算不滿足交換律笛卡兒積運(yùn)算不滿足交換律。 3. 當(dāng)當(dāng)A,B,C都不是空集時(shí)都不是空集時(shí),有有 (AB)CA(BC). 所以所以,笛卡兒積運(yùn)算不滿足結(jié)合律笛卡兒積運(yùn)算不滿足結(jié)合律。27定理定理1(笛卡兒積笛卡兒積運(yùn)算運(yùn)算對對或或運(yùn)算運(yùn)算滿足

18、分配律滿足分配律,即即) 設(shè)設(shè)A, B, C是任意三個(gè)集合；則是任意三個(gè)集合；則 A(BC) = (AB)(AC) /對對具有左分配律具有左分配律 A(BC) = (AB)(AC) /對對具有左分配律具有左分配律 (AB)C= (AB)(AC) /對對具有右分配律具有右分配律 (AB)C= (AB)(AC) /對對具有右分配律具有右分配律3.2 關(guān)關(guān) 系系28證明：證明： A(BC)=(AB)(AC) /對對具有左分配律具有左分配律令令x, y為分別屬于集合為分別屬于集合A和集合和集合BC的任意元素的任意元素, 則則 A(BC)x Ay (BC) x A(y By C)(x Ay B)(x A

19、y C) AB AC (AB)(AC) 所以：所以： A(BC)=(AB)(AC)3.2 關(guān)關(guān) 系系29定理定理2：設(shè)設(shè)A, B, C，D是任意四個(gè)集合；則是任意四個(gè)集合；則 若若A B且且C D，則，則AC BD規(guī)定：規(guī)定： AAA A,記為記為AnAn-1A例：例：A1,2 A3=A2A= 1,22 1,2 = ,1, ,2, ,1,2, ,1, ,2, ,1, ,2 3.2 關(guān)關(guān) 系系30定義定義2（二元關(guān)系）（二元關(guān)系） 設(shè)設(shè)A, B是任意兩個(gè)集合，則是任意兩個(gè)集合，則AB的任一子集稱為從的任一子集稱為從A到到B的的 二元關(guān)系二元關(guān)系(簡稱關(guān)系簡稱關(guān)系)，記為，記為R，顯然，顯然R A

20、B， 若若R，則稱，則稱x和和y有關(guān)系有關(guān)系R，記為，記為xRy; 否則否則 R，則稱，則稱x, y沒有關(guān)系，記為沒有關(guān)系，記為xRy 若若AB，則稱關(guān)系，則稱關(guān)系R是集合是集合A上的一個(gè)二元關(guān)系，即上的一個(gè)二元關(guān)系，即R A2； R| xA, 稱稱R為為A上的恒等關(guān)系，記為上的恒等關(guān)系，記為IA； 若若R，則稱，則稱R為空關(guān)系，記為為空關(guān)系，記為A； 若若RAAA2，則稱，則稱R為全域關(guān)系，記為為全域關(guān)系，記為UA； 設(shè)設(shè)|A|=n, 則則A2的序偶對一共有的序偶對一共有n2個(gè)，個(gè)，A上的二元關(guān)系一共有上的二元關(guān)系一共有 2n23.2 關(guān)關(guān) 系系31例例1：A=a,b, B=1,2,3則則R

21、1,是一個(gè)從是一個(gè)從A到到B的的(二元二元)關(guān)系。關(guān)系。同理同理 R2, 也是一個(gè)從也是一個(gè)從A到到B的的(二元二元)關(guān)系。關(guān)系。例例2：A=a, b, c,則則 IA,是一個(gè)是一個(gè)A上的恒等關(guān)系。上的恒等關(guān)系。UA ,是一個(gè)是一個(gè)A上的全域關(guān)系。上的全域關(guān)系。3.2 關(guān)關(guān) 系系32定理：定理：若若R1和和R2是是A上的關(guān)系，則上的關(guān)系，則 R1R2， R1R2， R1R2也是也是A上的關(guān)系。上的關(guān)系。1A1RUR 3.2 關(guān)關(guān) 系系證明：因?yàn)樽C明：因?yàn)镽1和和R2是是A上的關(guān)系，則上的關(guān)系，則R1 A2， R2 A2 所以所以R1R2 A2； R1R2 A2； R1R2 A2； 故故 ，R1

22、R2， R1R2， R1R2， 也是也是A上的關(guān)系。上的關(guān)系。21A1ARUR 1R33定義定義3 設(shè)設(shè)R是從集合是從集合A到到B的一個(gè)關(guān)系，稱的一個(gè)關(guān)系，稱 domRx|( y)( R) 為為R的的定義域定義域。 romRy|( x)( R) 為為R的的值域值域。3.2 關(guān)關(guān) 系系例：例：R,的的 domR=a,b romR=1,2,334關(guān)系的表示關(guān)系的表示矩陣法矩陣法圖形法圖形法3.2 關(guān)關(guān) 系系35矩陣法：矩陣法：設(shè)兩個(gè)有限集合設(shè)兩個(gè)有限集合 A=x1, x2, , xm, B=y1, y2, , yn, R AB. 則對應(yīng)于二元關(guān)系則對應(yīng)于二元關(guān)系R有一個(gè)有一個(gè)關(guān)系矩陣關(guān)系矩陣: M

23、R=(rij)mn, 其中其中 R 否則否則這里這里i1, 2, , m， j=1, 2, , n.01ijr3.2 關(guān)關(guān) 系系36 例如例如, Ax1,x2,x3, B=y1, y2, R=, 則則: 23101001RM矩陣法矩陣法:37 例如：例如：Ax1,x2,x3,x4, A上的一個(gè)關(guān)系上的一個(gè)關(guān)系R為為 R=, 矩陣法矩陣法:0010000011000011RM38圖形表示：圖形表示：設(shè)設(shè)R AB。用小圓圈分別表示集合用小圓圈分別表示集合A、B中的元素，中的元素，若若R，則由，則由x向向y引一條有向邊引一條有向邊(或稱為弧或稱為弧)。關(guān)系的表示：矩陣法和圖形法關(guān)系的表示：矩陣法和圖

24、形法例例1: Ax1,x2,x3, B=y1, y2, R=,x3x2x1y1y239 例例2: A1,2,3,4, A上的一個(gè)關(guān)系上的一個(gè)關(guān)系R為為 R=, ,關(guān)系的表示：矩陣法和圖形法關(guān)系的表示：矩陣法和圖形法設(shè)設(shè)R A2。用小圓圈表示集合。用小圓圈表示集合A中的元素，中的元素，若若R，則由，則由x向向y引一條有向邊引一條有向邊(或稱為弧或稱為弧)。40關(guān)系的性質(zhì)關(guān)系的性質(zhì)、合成和逆合成和逆定義定義(關(guān)系的性質(zhì)關(guān)系的性質(zhì))：設(shè)：設(shè)R是是A上的一個(gè)二元關(guān)系。上的一個(gè)二元關(guān)系。 R在在A中中自反自反:=( x)(x AxRx) R在在A中中非自反非自反: =( x)(x A(xRx) R在在A

25、中中對稱對稱:= ( x)( y) (x,y AxRyyRx) R在在A中中反對稱反對稱: =( x)( y)(x,y AxRyxy(yRx) R在在A中中傳遞傳遞: =( x)( y)( z)(x,y,z AxRyyRzxRy)41而而實(shí)數(shù)集合上的實(shí)數(shù)集合上的小于小于關(guān)系和集合上的關(guān)系和集合上的真包含真包含關(guān)系關(guān)系都是反自反關(guān)系。都是反自反關(guān)系。 例如例如:A上的全域關(guān)系上的全域關(guān)系UA，恒等關(guān)系，恒等關(guān)系IA 實(shí)數(shù)集合上的實(shí)數(shù)集合上的小于等于小于等于關(guān)系關(guān)系 正整數(shù)集合上的正整數(shù)集合上的整除整除關(guān)系關(guān)系 包含包含關(guān)系關(guān)系R 是給定集合族是給定集合族A上的上的自反、反自反關(guān)系舉例自反、反自反

26、關(guān)系舉例都是自反關(guān)系。都是自反關(guān)系。例例: 設(shè)設(shè)A=1,2,3，R1，R2，R3是是A上的關(guān)系，其中上的關(guān)系，其中R1,R2 R3, 說明說明R1，R2和和R3是否為是否為A上的自反關(guān)系和反自反關(guān)系上的自反關(guān)系和反自反關(guān)系解解: R1是自反的是自反的,R2是反自反的是反自反的,R3既不是自反的也不是既不是自反的也不是 反自反的。反自反的。結(jié)論：不自反的關(guān)系未必反自反；結(jié)論：不自反的關(guān)系未必反自反； 不反自反的關(guān)系未必自反不反自反的關(guān)系未必自反；43例如例如: A上的全域關(guān)系上的全域關(guān)系UA，恒等關(guān)系，恒等關(guān)系IA和空關(guān)系和空關(guān)系都是都是A上的對稱關(guān)系。上的對稱關(guān)系。恒等關(guān)系恒等關(guān)系IA和空關(guān)系

27、也是和空關(guān)系也是A上的反對稱關(guān)系。上的反對稱關(guān)系。但全域關(guān)系但全域關(guān)系UA一般不是一般不是A上的反對稱關(guān)系，除非上的反對稱關(guān)系，除非A為單元集或空集。為單元集或空集。 對稱、反對稱關(guān)系舉例對稱、反對稱關(guān)系舉例A44 設(shè)設(shè)A1,2,3，R1，R2，R3和和R4都是都是A上的關(guān)系，其中上的關(guān)系，其中 R1, R2, R3, R4,說明說明R1，R2，R3和和R4是否為是否為A上對稱和反對稱的關(guān)系。上對稱和反對稱的關(guān)系。 解解: R1既是對稱也是反對稱的。既是對稱也是反對稱的。 R2是對稱的但不是反對稱的。是對稱的但不是反對稱的。 R3是反對稱的但不是對稱的。是反對稱的但不是對稱的。 R4既不是對稱

28、的也不是反對稱的。既不是對稱的也不是反對稱的。 結(jié)論：結(jié)論：不對稱的關(guān)系未必反對稱；不對稱的關(guān)系未必反對稱；不反對稱的關(guān)系未必對稱；不反對稱的關(guān)系未必對稱；二元關(guān)系既可對稱也可反對稱；二元關(guān)系既可對稱也可反對稱；對稱、反對稱關(guān)系舉例對稱、反對稱關(guān)系舉例45反對稱的另一種定義：反對稱的另一種定義：R在在A中中反對稱反對稱: = ( x)( y)(xRyxy (yRx) /x,y A= ( x)( y)( (xRy)x=y (yRx) = ( x)( y)( (xRyyRx )x=y) = ( x)( y)(xRyyRxx=y)關(guān)系的性質(zhì)關(guān)系的性質(zhì)R4, 不是反對稱的不是反對稱的46例如例如: A

29、上的全域關(guān)系上的全域關(guān)系UA,恒等關(guān)系恒等關(guān)系IA和空關(guān)系和空關(guān)系 都是都是A上的上的傳遞關(guān)系傳遞關(guān)系。小于等于關(guān)系，整除關(guān)系和包含關(guān)系小于等于關(guān)系，整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的也是相應(yīng)集合上的傳遞關(guān)系傳遞關(guān)系。小于關(guān)系和真包含關(guān)系是相應(yīng)集合上的小于關(guān)系和真包含關(guān)系是相應(yīng)集合上的傳遞關(guān)系。傳遞關(guān)系。傳遞關(guān)系舉例傳遞關(guān)系舉例A47設(shè)設(shè)A1,2,3，R1，R2，R3是是A上的關(guān)系，其中上的關(guān)系，其中R1,R2,R3說明說明R1，R2和和R3是否為是否為A上的傳遞關(guān)系。上的傳遞關(guān)系。解解: R1和和R3是是A上的傳遞關(guān)系，上的傳遞關(guān)系，R2不是不是A上的傳遞關(guān)系。上的傳遞關(guān)系。 傳遞關(guān)系舉例傳

30、遞關(guān)系舉例48利用關(guān)系的表示來判斷關(guān)系的性質(zhì)利用關(guān)系的表示來判斷關(guān)系的性質(zhì)49關(guān)系的運(yùn)算：逆和合成關(guān)系的運(yùn)算：逆和合成定義定義(逆運(yùn)算逆運(yùn)算) 設(shè)設(shè)R是從集合是從集合A到集合到集合B的二元關(guān)系的二元關(guān)系 R-1:= | xA, yB且且xRy 稱為關(guān)系稱為關(guān)系R的逆關(guān)系。的逆關(guān)系。 顯然顯然R-1是從集合是從集合B到集合到集合A的二元關(guān)系的二元關(guān)系.例：例：A1,2,3, B=a,b R=,從集合從集合A到集合到集合B的二元關(guān)系的二元關(guān)系則：則： R-1,從集合從集合B到集合到集合A 的二元關(guān)系的二元關(guān)系50定理：設(shè)定理：設(shè)R和和S是從集合是從集合A到集合到集合B的關(guān)系。的關(guān)系。 R-1是一個(gè)

31、關(guān)系是一個(gè)關(guān)系 xR-1y iff yRx (R-1)-1=R (RS)-1=R-1S-1 (RS)-1=R-1S-1 (R S)-1 =R-1 S-1證明證明 ：令：令x, y分別為集合分別為集合A和集合和集合B中的任何元素，則中的任何元素，則 若若 x(RS)-1y y(RS)x yRx ySx xR-1y xS-1y x(R-1S-1)y 根據(jù)定義知根據(jù)定義知, (RS)-1=R-1S-1關(guān)系的運(yùn)算：逆和合成關(guān)系的運(yùn)算：逆和合成51令令x, y分別為集合分別為集合A和集合和集合B中的任何元素，中的任何元素，則若則若x(R S)-1yy(R S)x yRx (ySx) xR-1y (xS-

32、1y) x(R-1- S-1)y 由定義知由定義知, (R S)-1=R-1- S-1.關(guān)系的運(yùn)算：逆和合成關(guān)系的運(yùn)算：逆和合成52定義定義 (合成運(yùn)算合成運(yùn)算)設(shè)設(shè)R是從集合是從集合A到集合到集合B的二元關(guān)系，的二元關(guān)系， S是從集合是從集合B到集到集合合C的二元關(guān)系，則稱的二元關(guān)系，則稱 R o S:=| (xAzC( y)(yB) xRyySz 為關(guān)系為關(guān)系R和關(guān)系和關(guān)系S的從的從A到到C二元關(guān)系。二元關(guān)系。例：例：令令R=, , S=, 則則 R o S =,. S o R=. R o S S o R關(guān)系的運(yùn)算：逆和合成關(guān)系的運(yùn)算：逆和合成53結(jié)論：結(jié)論： 關(guān)系合成運(yùn)算滿足結(jié)合律，不滿

33、足交換律關(guān)系合成運(yùn)算滿足結(jié)合律，不滿足交換律.特別特別, 當(dāng)當(dāng) R=S時(shí)時(shí), 記記 Rn=Rn-1 o R.關(guān)系的運(yùn)算：逆和合成關(guān)系的運(yùn)算：逆和合成定理定理3.2.1 設(shè)設(shè)R ，R1和和R2 是從是從A到到B的二元關(guān)系，的二元關(guān)系，(p84) S是從是從B到到C的二元關(guān)系，則有下列結(jié)論：的二元關(guān)系，則有下列結(jié)論： (1) (R o S)-1 = S-1 o R-1 (2) (R1 R2 ) -1= R1-1 R2 -1 ; /書上錯(cuò)書上錯(cuò) (R1 R2 ) -1= R1-1 R2 -1 (3) (AB) -1= BA (4) (R1R2 ) -1= R1-1 R2 -1 ; (5) R1 R2

34、 iff R1-1 R2-1 (6) (7) (R1R2) o S = (R1 o S) (R2 o S) 練習(xí)練習(xí) (R1R2) o S (R1 o S)(R2 o S)1111RABRRRRBAR，這里，這里，則，則若若 55利用兩個(gè)關(guān)系的關(guān)系矩陣求它們的合成關(guān)系利用兩個(gè)關(guān)系的關(guān)系矩陣求它們的合成關(guān)系.例：例：R,是從是從A=1,2,3到到B=a,b,c的關(guān)系的關(guān)系 S=,是從是從B=a,b,c到到C=x,y,z的關(guān)系的關(guān)系 求求 R o SR o S,56 關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算 現(xiàn)在來討論另一種重要關(guān)系現(xiàn)在來討論另一種重要關(guān)系閉包閉包. 所謂閉包是指，所謂閉包是指，對于給定的關(guān)系

35、對于給定的關(guān)系R和一種性質(zhì)和一種性質(zhì)P, 把包含把包含R并且滿足性質(zhì)并且滿足性質(zhì)P的最小關(guān)系稱為的最小關(guān)系稱為R對于對于P的閉包的閉包, 記為記為P(R). 若若P是自反是自反的的, 則稱則稱R是是自反閉包自反閉包, 記為記為r(R), 若若P是對稱的，則稱是對稱的，則稱R是是對稱閉包對稱閉包, 記為記為s(R); 若若P是傳遞的是傳遞的, 則稱則稱R是是傳遞閉傳遞閉包包,記為記為t(R).57關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算定義定義3.2.1設(shè)設(shè)R和和R是集合是集合A上的一個(gè)二元關(guān)系，若滿足下列條件：上的一個(gè)二元關(guān)系，若滿足下列條件：(1) R是自反是自反(對稱對稱,傳遞傳遞)關(guān)系；關(guān)系；(2)

36、 R R ；(3) 若若R也是也是A上的自反上的自反(對稱對稱,傳遞傳遞) 關(guān)系且關(guān)系且R R ， 則則R R , 稱稱R是是R的自反的自反(對稱對稱,傳遞傳遞) 閉包關(guān)系，閉包關(guān)系， 記為為記為為r(R)(s(R)和和t(R).結(jié)論：結(jié)論： R是包含是包含R的最小的自反的最小的自反(對稱對稱,傳遞傳遞) 關(guān)系。關(guān)系。58定理定理1 設(shè)設(shè)R是集合是集合A上的一個(gè)二元關(guān)系，則上的一個(gè)二元關(guān)系，則 R是自反的是自反的 iff r(R) = R R是對稱的是對稱的 iff s(R) = R R是傳遞的是傳遞的 iff t(R) = R關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算59證明：證明： 只證明只證明設(shè)設(shè)R為

37、自反為自反. 由于由于R R, 取取R 為為R,以及任何包含以及任何包含R的自反關(guān)系的自反關(guān)系 R , 有有RR R, 可見可見R滿足自反滿足自反閉包定義閉包定義, 即即r(R) = R. 下面再給出關(guān)于閉包的三個(gè)構(gòu)造性定理下面再給出關(guān)于閉包的三個(gè)構(gòu)造性定理. 關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算定理定理3.2.2 設(shè)設(shè)R是集合是集合A上的任一二元關(guān)系，則上的任一二元關(guān)系，則 r(R) = R IA s(R) = RR-1 t(R) = Ri1i 關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算61證明證明 只證明和只證明和令令R R IA, 顯然顯然R R . 則則R 在在A中自反中自反. 又因又因?yàn)閷τ谌我獍瑸閷τ?/p>

38、任意包含R的自反關(guān)系的自反關(guān)系R, 顯然有顯然有IA R, 因此有因此有R IA R, 即即R R. 由自反閉包定義知由自反閉包定義知, r(R) =R , 即即r(R) =R IA.首先證明首先證明 Ri t(R). 用歸納法證明如下用歸納法證明如下: 當(dāng)當(dāng)i1時(shí)，根據(jù)傳遞閉包定義時(shí)，根據(jù)傳遞閉包定義, R t(R); 假設(shè)當(dāng)假設(shè)當(dāng)i1時(shí)時(shí)Ri t(R), 欲欲證證Ri+1 t(R)。 x,y,zA, 若若 Ri+1,因?yàn)橐驗(yàn)镽i+1 Ri o R 所以所以 y A,使得使得 Ri且且 R 由假設(shè)知由假設(shè)知 , t(R), 則則 t(R) 因此因此, Ri+1 t(R). 于是于是, Ri

39、t(R).1i1i 次證次證 t(R) Ri, 由于包含由于包含 R的傳遞關(guān)系都包含的傳遞關(guān)系都包含t(R)，且且R Ri, 因此只需證明因此只需證明Ri是傳遞即可是傳遞即可. x, y, z A, 則則 設(shè)設(shè) Ri, Ri, 則必則必 s,t N+ 使得使得 Rs， Rt 因此因此, Rs+t ,故故 Ri 所以所以 Ri是傳遞的是傳遞的. 綜上可知綜上可知, t(R) = Ri.1i1i1i1i1i1i1i64推論推論 t(R) Ri，其中其中kn例例. 設(shè)設(shè)R=, 試求試求r(R), s(R)和和t(R).解解: r(R)=R IA =, s(R)=RR-1 =,1i 關(guān)系的閉包運(yùn)算關(guān)系

40、的閉包運(yùn)算65下面求下面求t(R), 因因A只含有只含有3個(gè)元素個(gè)元素 ，所以，所以k3. R= ,R2=R o R=,R3=R2 o R= ,于是于是 t(R)=RR2R3 =, , , 關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算例：設(shè)例：設(shè)Aa,b,c,d, R, 則則 r(R),s(R),t(R) 為為解解: (1) r(R)=R IA =, =,., (2) s(R)=RR-1 =, =, (3) t(R)=RR2R3 =, , =, 67關(guān)系矩陣為關(guān)系矩陣為:證明證明 只給出的證明只給出的證明 因?yàn)橐驗(yàn)閞(R)=R IA, 已知已知R為對稱為對稱, 而而IA顯然也是對稱的顯然也是對稱的, 因此因此

41、r(R)是對稱的是對稱的. t(R)=RR2R3, 用歸納法證明用歸納法證明t(R)對稱對稱. 當(dāng)當(dāng) i1時(shí)，時(shí)， R是對稱的。是對稱的。定理定理 R為自反為自反s(R)和和t(R)為自反為自反 R為對稱為對稱r(R)和和t(R)為對稱為對稱 R為傳遞為傳遞r(R)為傳遞為傳遞假設(shè)對于假設(shè)對于i1時(shí)時(shí), Ri是對稱是對稱, 欲證欲證Ri+1是對稱是對稱. 令令 x, y A, 則則: xRi+1y x(Ri o R)y ( z)(xRizzRy) ( z)(zRixyRz) ( z)(yRzzRix) y(R o Ri)x yRi+1x 故故Ri+1是對稱的是對稱的, 于是于是t(R)是對稱的

42、是對稱的.70證明證明 sr(R)=s(R IA )= (R IA ) (R IA )-1 = (R IA ) (R-1(IA )-1) = RR-1 IA = s(R) IA =rs(R) (其中其中 IA = (IA )-1)閉包運(yùn)算律：閉包運(yùn)算律： rs(R)=sr(R) (自反對稱閉包自反對稱閉包等于等于對稱自反閉包對稱自反閉包) rt(R)=tr(R) (自反傳遞閉包自反傳遞閉包等于等于傳遞自反閉包傳遞自反閉包) st(R) ts(R) (對稱傳遞閉包對稱傳遞閉包包含于包含于傳遞對稱閉包傳遞對稱閉包)71若若R S, 則顯然有則顯然有s(R) s(S), t(R) t(S). 根據(jù)對

43、稱閉根據(jù)對稱閉包的定義包的定義, R s(R), 于是于是 t(R) ts(R) st(R) sts(R) 由于由于s(R)對稱，則對稱，則ts(R)亦對稱亦對稱, sts(R)=ts(R). 所以所以, 可得可得, st(R) ts(R) 72 注意：注意： ts(R) 不一定包含于不一定包含于st(R)例如：若例如：若R, 則則 s(R)=, ; t(R)= ts(R)=, st(R)=,73Warshall算法：求傳遞閉包的新方法算法：求傳遞閉包的新方法設(shè)設(shè)R是具有是具有n個(gè)元素的集合個(gè)元素的集合A上的任一二元關(guān)系，上的任一二元關(guān)系，由由MR 求求Mt(R)如下：如下：(1) MR M；

44、1i(2) 對于對于j1,n, 若有若有wji=1,則則wjkwjkwik (k=1,n)(3) i+(4) 若若in，則轉(zhuǎn)，則轉(zhuǎn)(2), 否則結(jié)束，此時(shí)否則結(jié)束，此時(shí)M即為即為R的傳遞閉包的傳遞閉包 矩陣矩陣Mt(R) 。例例: 設(shè)設(shè)Aa, b, c, d, R, 問問t(R)？練習(xí)：練習(xí)：p92(11)75 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分定義（定義（ 等價(jià)關(guān)系特殊的關(guān)系）等價(jià)關(guān)系特殊的關(guān)系）設(shè)設(shè)R是非空集合是非空集合A上的一個(gè)二元關(guān)系，上的一個(gè)二元關(guān)系，若關(guān)系若關(guān)系R自反、對稱和傳遞，則稱自反、對稱和傳遞，則稱R為為A上的等價(jià)關(guān)系上的等價(jià)關(guān)系例如：例如：實(shí)數(shù)中的實(shí)數(shù)中的等于關(guān)系等于關(guān)系；直線

45、間的；直線間的平行關(guān)系平行關(guān)系；在一群人的集合上在一群人的集合上年齡相等的關(guān)系年齡相等的關(guān)系是等價(jià)關(guān)系；是等價(jià)關(guān)系； 而而朋友關(guān)系朋友關(guān)系不一定是等價(jià)關(guān)系不一定是等價(jià)關(guān)系,因?yàn)樗赡懿皇莻鬟f的因?yàn)樗赡懿皇莻鬟f的. 例：例：設(shè)設(shè)A=1,2,8，如下定義，如下定義A上的關(guān)系上的關(guān)系R：R=|x，yAxy(mod 3) /模模3同余關(guān)系同余關(guān)系其中其中xy(mod 3)稱作稱作x與與y模模3相等相等(即即x除以除以3的余數(shù)與的余數(shù)與y除除以以3的余數(shù)相等的余數(shù)相等), 則則R為為A上的等價(jià)關(guān)系上的等價(jià)關(guān)系，因?yàn)?，因?yàn)?xA，有，有xx(mod 3) x, yA，若，若xy(mod 3)，則有，則有

46、yx(mod 3) x, y, zA，若，若xy(mod 3)，yz(mod 3)，則有則有xz(mod 3)一般，若一般，若R|x,yZxy(mod k)，kN+則則R是等價(jià)關(guān)系是等價(jià)關(guān)系。定義定義: 設(shè)設(shè)R是非空集合是非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系,對對 xA,令令xR=y| yAxRy 則稱則稱xR為為x關(guān)于關(guān)于R的等價(jià)類的等價(jià)類,簡稱為簡稱為x等價(jià)類等價(jià)類.在上例中有在上例中有 0R =3R =-3R =,-6,-3,0,3,6,; 1R =4R =-2R =,-5,-2,1,4,7,; 2R =5R =-1R =,-4,-1,2,5,8,; 集合集合A=1,2,8上等價(jià)關(guān)系的關(guān)系

47、圖上等價(jià)關(guān)系的關(guān)系圖79商集：商集：設(shè)設(shè)R為非空集合為非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 稱稱 xRxA 為為A關(guān)于關(guān)于R的的商集商集,記作記作A/R 即即 A/R xRxA如上例如上例 A/R= 0R,1R,2R = ,6,-3,0,3,6,; ,5,-2,1,4,7,; ,-4,-1,2,5,8,; 80定理定理(等價(jià)類的性質(zhì)等價(jià)類的性質(zhì)) 設(shè)設(shè)R是非空集合是非空集合A上的等價(jià)關(guān)系，則上的等價(jià)關(guān)系，則（1） xA，xR是是A的非空子集。的非空子集。（2） x,yA，如果，如果xRy，則，則xR=yR。（3） x,yA，如果，如果 (xRy)，則，則xRyR=.（4）x|xA=A證明：證明

48、：(1) xA，xR是是A的非空子集。的非空子集。 由等價(jià)類的定義可知由等價(jià)類的定義可知, xR=y| yAxRy A。 又由于等價(jià)關(guān)系的自反性有又由于等價(jià)關(guān)系的自反性有xxR，即，即xR非空。非空。 (2) x,yA，如果，如果xRy，則，則xR=yR。 任取任取zA ，若有，若有zxR = R = R 因此有因此有RR =R = R 從而證明了從而證明了zyR. 則則 xR yR。 同理可證同理可證 yR xR，從而得到了，從而得到了xR=yR。 （3） x,yA，如果，如果 (xRy) ，則，則xRyR=. 假設(shè)假設(shè)xRyR ，則存在則存在zxRyR，從而有，從而有zxRzyR，即，即R

49、R成立。根據(jù)成立。根據(jù)R的對稱性和傳遞性必有的對稱性和傳遞性必有R，與，與 (xRy) 矛盾，矛盾，即假設(shè)錯(cuò)誤，原命題成立。即假設(shè)錯(cuò)誤，原命題成立。 （4）xR|xA=A 先證先證xR|xA A 任取任取y，yxR|xA = x(xAyxR) = yA (因?yàn)橐驗(yàn)閤 A) 從而有從而有xR|xA A 再證再證A xR|xA 任取任取x，xA, xxRxA =xxR|xA 從而有從而有A xR|xA成立。成立。 綜上所述得綜上所述得xR|xA=A。84定義定義3.2.2 設(shè)設(shè)A是非空集合是非空集合,如果存在一個(gè)如果存在一個(gè)A的子集族的子集族 S=A1,A2,Am滿足以下條件滿足以下條件:(1)

50、Ai(i=1,2,m)非空非空；(2) S中任意兩個(gè)不同元素交集為空；中任意兩個(gè)不同元素交集為空；(3) S中中所有元素的并集等于所有元素的并集等于A；則稱則稱S為為A的一個(gè)劃分的一個(gè)劃分，且稱，且稱S中的元素中的元素Ai為為劃分塊劃分塊.劃分劃分85例例. 考慮集合考慮集合Aa, b, c, d的下列子集族的下列子集族(1) a,b,c,d 又稱最大劃分又稱最大劃分(塊最多塊最多)(7) ,a,b,c,d(6) a,b,c,a,d (5) a,b,c(4) a,b,c,d(3) a,b,c,d(2) a,b,c,d 又稱最小劃分又稱最小劃分(塊最少塊最少)86交叉劃分交叉劃分設(shè)設(shè)S1和和S2

51、是集合是集合A的兩個(gè)劃分，由的兩個(gè)劃分，由S1和和S2元素間元素間所有非空交集作為元素的集合稱為所有非空交集作為元素的集合稱為S1和和S2的的交叉劃分交叉劃分。例例 S1 a,b,c,d ,S2a,c,b,d的的交叉劃分交叉劃分為為 a,b,c,d87加細(xì)劃分加細(xì)劃分設(shè)設(shè)S1和和S2分別是集合分別是集合A的兩個(gè)劃分的兩個(gè)劃分,若對于若對于S1中的任一元中的任一元素素S1i，在，在S2中都存在元素中都存在元素S2j,使得使得S1i S2j,則稱則稱S1是是S2的的加細(xì)劃分加細(xì)劃分。若還有。若還有S1S2,則稱則稱S1是是S2的的真加細(xì)劃分真加細(xì)劃分。例例 S1a,b,c,d是是S2 a,b,c,

52、d的的 加細(xì)劃分加細(xì)劃分且為且為真加細(xì)劃分真加細(xì)劃分。88定理：交叉劃分是原來集合的加細(xì)劃分。定理：交叉劃分是原來集合的加細(xì)劃分。因?yàn)橐驗(yàn)镾1iS2j S1i且且S1iS2j S2j89定理：等價(jià)關(guān)系與劃分的關(guān)系相互確定定理：等價(jià)關(guān)系與劃分的關(guān)系相互確定把等價(jià)類的性質(zhì)和劃分的定義相比較，易見把等價(jià)類的性質(zhì)和劃分的定義相比較，易見商集就是商集就是A的一個(gè)劃分的一個(gè)劃分，并且不同的商集將對應(yīng)于不同的劃分。反，并且不同的商集將對應(yīng)于不同的劃分。反之任給之任給A的一個(gè)劃分的一個(gè)劃分S，如下定義，如下定義A上的關(guān)系上的關(guān)系R：R=|x,yAx與與y在在S的同一劃分塊中的同一劃分塊中則不難證明則不難證明R

53、為為A上的等價(jià)關(guān)系，且該等價(jià)關(guān)系所確定上的等價(jià)關(guān)系，且該等價(jià)關(guān)系所確定的商集就是的商集就是S。由此可見，由此可見，A上的等價(jià)關(guān)系與上的等價(jià)關(guān)系與A的劃分是一一對應(yīng)的。的劃分是一一對應(yīng)的。 90例：設(shè)例：設(shè)Aa,b,c,d,e,R= , , ,則集合則集合A上等價(jià)關(guān)系上等價(jià)關(guān)系R的商集為的商集為A/R=a,b,c,d,e,即為集合即為集合A的一個(gè)劃分。的一個(gè)劃分。反之，由劃分反之，由劃分a,b,c,d,e確定的集合確定的集合A上的等上的等價(jià)關(guān)系為價(jià)關(guān)系為a,ba,b,c,dc,d,ee = , , ,等價(jià)關(guān)系與劃分的關(guān)系相互確定等價(jià)關(guān)系與劃分的關(guān)系相互確定91例例 設(shè)設(shè)Aa1,a2,a3, 求出

54、求出A上所有的等價(jià)關(guān)系上所有的等價(jià)關(guān)系解解:R=URR=,R=IRR=, R=,92 對于對于n元集合元集合A上的全部劃分個(gè)數(shù)可轉(zhuǎn)化為上的全部劃分個(gè)數(shù)可轉(zhuǎn)化為將將n個(gè)不同個(gè)不同球放入球放入r(rn)個(gè)相同的盒中，無空盒的不同放法數(shù)，個(gè)相同的盒中，無空盒的不同放法數(shù)，由由第二類第二類Stirling數(shù)求得，記為數(shù)求得，記為S(n,r)，此遞歸公式為：，此遞歸公式為： S(n,r)=rS(n-1,r)+S(n-1,r-1). 其中：其中： S(n,0)=0, S(n,1)=1, S(n,2)=2n-1-1, S(n,n-1)= , S(n,n)=1是遞歸計(jì)算的基礎(chǔ)。是遞歸計(jì)算的基礎(chǔ)。例如例如,求求

55、4元集元集A上全部等價(jià)關(guān)系數(shù)上全部等價(jià)關(guān)系數(shù),通過求通過求A的全部劃分?jǐn)?shù)而給出的全部劃分?jǐn)?shù)而給出解解:第二類第二類Stirling個(gè)數(shù)為個(gè)數(shù)為=S(4,1)+S(4,2)+S(4,3)+S(4,4) =1+(23-1)+6+1=15. 等價(jià)關(guān)系與劃分等價(jià)關(guān)系與劃分2nC練習(xí)：計(jì)算練習(xí)：計(jì)算5個(gè)元素個(gè)元素A上的全部等價(jià)關(guān)系數(shù)上的全部等價(jià)關(guān)系數(shù)93 定義定義(偏序關(guān)系與偏序集偏序關(guān)系與偏序集) 設(shè)設(shè)R是集合是集合A上的一個(gè)二元關(guān)上的一個(gè)二元關(guān)系系, 如果如果R具有具有自反性自反性, 反對稱性和傳遞性反對稱性和傳遞性, 那么稱那么稱R為為一個(gè)偏序關(guān)系一個(gè)偏序關(guān)系(或部分序或部分序, 或半序關(guān)系或半序

56、關(guān)系); 記為記為，并稱，并稱 為偏序集。為偏序集。偏序關(guān)系偏序關(guān)系94例如例如: 1.實(shí)數(shù)集合實(shí)數(shù)集合R上的小于等于關(guān)系是一個(gè)偏序關(guān)系，上的小于等于關(guān)系是一個(gè)偏序關(guān)系， 偏序集為偏序集為。2.正整數(shù)集正整數(shù)集I+關(guān)于整除關(guān)系關(guān)于整除關(guān)系D是一個(gè)偏序關(guān)系，是一個(gè)偏序關(guān)系， 偏序集為偏序集為。偏序關(guān)系偏序關(guān)系954.集合集合A=a,b,c,d,e上的關(guān)系上的關(guān)系R是一個(gè)偏序關(guān)系，偏序是一個(gè)偏序關(guān)系，偏序集集, 這里這里 R=, , , 。偏序關(guān)系偏序關(guān)系3. 集合的包含關(guān)系是一個(gè)偏序關(guān)系，集合全體集合的包含關(guān)系是一個(gè)偏序關(guān)系，集合全體S作成一作成一個(gè)偏序集個(gè)偏序集.96相容關(guān)系與覆蓋相容關(guān)系與覆

57、蓋定義（定義（ 相容關(guān)系特殊的關(guān)系）相容關(guān)系特殊的關(guān)系）設(shè)設(shè)R是非空集合是非空集合A上的一個(gè)二元關(guān)系，上的一個(gè)二元關(guān)系，若關(guān)系若關(guān)系R自反、對稱，則稱自反、對稱，則稱R為為A上的相容關(guān)系上的相容關(guān)系例如：例如：實(shí)數(shù)中的實(shí)數(shù)中的等于關(guān)系等于關(guān)系；直線間的；直線間的平行關(guān)系平行關(guān)系；在一群人的集合上在一群人的集合上年齡相等的關(guān)系年齡相等的關(guān)系是相容關(guān)系；是相容關(guān)系； 而而朋友關(guān)系也是朋友關(guān)系也是相容關(guān)系。相容關(guān)系。結(jié)論：等價(jià)關(guān)系是相容關(guān)系，反之不真。結(jié)論：等價(jià)關(guān)系是相容關(guān)系，反之不真。97定義定義(覆蓋覆蓋) 設(shè)設(shè)A是非空集合是非空集合,如果存在一個(gè)如果存在一個(gè)A的子集族的子集族 S=A1,A2,

58、Am滿足以下條件滿足以下條件:(1) Ai(i=1,2,m)非空非空；(2) S中中所有元素的并集等于所有元素的并集等于A；則稱則稱S為為A的一個(gè)覆蓋的一個(gè)覆蓋。結(jié)論：劃分是覆蓋，反之不真。結(jié)論：劃分是覆蓋，反之不真。相容關(guān)系與覆蓋相容關(guān)系與覆蓋98例例. 考慮集合考慮集合Aa, b, c, d的下列子集族的下列子集族(1) a,b,c,d(7) ,a,b,c,d(6) a,b,c,a,d (5) a,b,c(4) a,b,c,d(3) a,b,c,d(2) a,b,c,d99例：設(shè)集合例：設(shè)集合=a1,a2,a3,a4,a5,a6,a7R=, , , a1 a2 a3 a4 a5 a6 a7

59、 相容關(guān)系與覆蓋相容關(guān)系與覆蓋100相容關(guān)系與覆蓋相容關(guān)系與覆蓋定義（相容類）定義（相容類）設(shè)設(shè)R為為A上的相容關(guān)系若上的相容關(guān)系若C A，如果對于，如果對于C中任中任意兩個(gè)元素意兩個(gè)元素a，b，都有，都有aRb，則稱，則稱C是有相容關(guān)系是有相容關(guān)系R產(chǎn)生的相容類。產(chǎn)生的相容類。相容類為相容類為a1,a2,a3,a3,a4 a3,a5,a6,a5,a6,a7101相容關(guān)系與覆蓋相容關(guān)系與覆蓋定義（最大相容類）定義（最大相容類） 設(shè)設(shè)R為為A上的相容關(guān)系不能真包含在任何其它相上的相容關(guān)系不能真包含在任何其它相容類中的相容類，稱為最大相容類。容類中的相容類，稱為最大相容類。最大相容類為最大相容類為

60、a1,a2,a3,a3,a4,a5 a3,a5,a6,a7102相容關(guān)系與覆蓋相容關(guān)系與覆蓋定義（完全覆蓋）定義（完全覆蓋） 設(shè)設(shè)R為為A上的相容關(guān)系其所有最大相容類的集合上的相容關(guān)系其所有最大相容類的集合稱為集合稱為集合A的完全覆蓋。的完全覆蓋。完全覆蓋為完全覆蓋為a1,a2,a3,a3,a4,a5 a3,a5,a6,a7103相容關(guān)系與覆蓋相容關(guān)系與覆蓋定理（最大相容類）定理（最大相容類） 集合集合A上的相容關(guān)系上的相容關(guān)系R與完全覆蓋存在一一對應(yīng)與完全覆蓋存在一一對應(yīng)由完全覆蓋由完全覆蓋a1,a2,a3,a3,a4,a5,a3,a5,a6,a7可得可得 集合集合A上的相容關(guān)系上的相容關(guān)系