離散數(shù)學(xué)集合論部分

1、 對于從事計(jì)算機(jī)科學(xué)工作的人們來說，集對于從事計(jì)算機(jī)科學(xué)工作的人們來說，集 合論是必不可少的基礎(chǔ)知識。例如程序設(shè)計(jì)語合論是必不可少的基礎(chǔ)知識。例如程序設(shè)計(jì)語 言、數(shù)據(jù)結(jié)構(gòu)、形式語言等都離不開子集、冪言、數(shù)據(jù)結(jié)構(gòu)、形式語言等都離不開子集、冪 集、集合的分類等概念。集合成員表和范式在集、集合的分類等概念。集合成員表和范式在 邏輯設(shè)計(jì)、定理證明中也都有重要應(yīng)用。邏輯設(shè)計(jì)、定理證明中也都有重要應(yīng)用。 本部分從集合的直觀概念出發(fā)，介紹了集本部分從集合的直觀概念出發(fā)，介紹了集 合論中的一些合論中的一些基本概念基本概念和和基本理論基本理論。 集合論是研究集合的一般性質(zhì)的數(shù)學(xué)集合論是研究集合的一般性質(zhì)的數(shù)學(xué)

2、分支分支，它研究集合不依賴于組成它的事物，它研究集合不依賴于組成它的事物 的特性的性質(zhì)。集合論總結(jié)出由各種對象的特性的性質(zhì)。集合論總結(jié)出由各種對象 構(gòu)成的集合的共同性質(zhì)，并用統(tǒng)一的方法構(gòu)成的集合的共同性質(zhì)，并用統(tǒng)一的方法 來處理。來處理。 集合論的特點(diǎn)是研究對象的廣泛性，集合論的特點(diǎn)是研究對象的廣泛性， 集合是各種不同對象的抽象，這些對象可集合是各種不同對象的抽象，這些對象可 以是數(shù)或圖形，也可以使任意其它事務(wù)。以是數(shù)或圖形，也可以使任意其它事務(wù)。 1. 1. 二十六個英文字母可以看成是一個集合；二十六個英文字母可以看成是一個集合； 2. 2. 所有的自然數(shù)看成是一個集合；所有的自然數(shù)看成是一

3、個集合； 3. 3. 重慶郵電大學(xué)計(jì)算機(jī)學(xué)院重慶郵電大學(xué)計(jì)算機(jī)學(xué)院20102010級的本科學(xué)生可以看級的本科學(xué)生可以看 成是一個集合；成是一個集合； 4. 4. 這間教室中的所有座位可以看成是一個集合。這間教室中的所有座位可以看成是一個集合。 組成一個集合的那些對象或單元稱為這組成一個集合的那些對象或單元稱為這 個集合的元素。個集合的元素。通常，用小通常，用小寫的英文字母寫的英文字母a, b, c,表示表示集合中的元素。元素可以是單個集合中的元素。元素可以是單個 的數(shù)字也可以是字母，還可以是集合。的數(shù)字也可以是字母，還可以是集合。 如：如：A=a,c,b ; B=a,b,c 設(shè)設(shè)A是一個集合，

4、是一個集合，a是集合是集合A中的元素，中的元素，元素與元素與 集合的關(guān)系：集合的關(guān)系： 屬于屬于； 不屬于不屬于 若若a是集合是集合A中的元素記為中的元素記為a A，讀作，讀作a屬于屬于A； 若若a不是集合不是集合A中的元素，則記為中的元素，則記為a A，讀作，讀作a不不 屬于屬于A。 例如：例如：A是正偶數(shù)集合，則是正偶數(shù)集合，則2 A，4 A， 6 A；而；而 1 A，3 A，19 A。 特別注意：特別注意： 集合并不決定于它的元素展示方法。集合的元素集合并不決定于它的元素展示方法。集合的元素 被重復(fù)或重新排列，集合并不改變，即被重復(fù)或重新排列，集合并不改變，即a, a ,b, c, d,

5、 c= a, b, c, d。 集合的元素可以是具體事物，可以是抽象概念，集合的元素可以是具體事物，可以是抽象概念， 也可以是集體，如一本書，一支筆；集合也可以是集體，如一本書，一支筆；集合1,2,3可可 以是集合以是集合B=一本書，一支筆，一本書，一支筆，1,2,3 的元素。的元素。 特別地，以集合為元素的集合稱為集合族或集合特別地，以集合為元素的集合稱為集合族或集合 類如類如A=1,2,3, 8,9,6。 集合中元素之間可以有某種關(guān)聯(lián)，也可以彼此毫集合中元素之間可以有某種關(guān)聯(lián)，也可以彼此毫 無關(guān)系。無關(guān)系。 有限集有限集A 中所含元素的個數(shù)稱為集合的中所含元素的個數(shù)稱為集合的 元數(shù)。記作：

6、元數(shù)。記作：| A | 如：如： A =1,3,2,4,5,9 則則 | A |= 6； 設(shè)設(shè)A是所有英文字母組成的集合，則是所有英文字母組成的集合，則 A=26。 特別，特別， | |=0 列舉法列舉法(列元素法列元素法) ：將集合中的元素一一列舉，將集合中的元素一一列舉， 或列出足夠多的元素以反映集合中元素的特征，或列出足夠多的元素以反映集合中元素的特征， 例如：例如：V=a, b, c, d, e 或或 B=1,2,3, 4, 5,6,。 描述法描述法(謂詞表示法謂詞表示法) :將集合元素的條件或性將集合元素的條件或性 質(zhì)用文字或符號在花括號內(nèi)豎線后面表示出來。質(zhì)用文字或符號在花括號內(nèi)豎

7、線后面表示出來。 A=x|關(guān)于關(guān)于x的一個命題的一個命題P; 如：如：B=x|0 x10; B= x|x=a2,a是自然數(shù)是自然數(shù)。 E A a e 文氏圖文氏圖 用一個大的矩形表示全集，在矩形內(nèi)畫一些圓或用一個大的矩形表示全集，在矩形內(nèi)畫一些圓或 其它的幾何圖形，來表示集合，有時也用一些點(diǎn)來表其它的幾何圖形，來表示集合，有時也用一些點(diǎn)來表 示集合中的特定元素。示集合中的特定元素。 例如：例如：集合集合A=a,b,c,d,e ，用，用文氏圖文氏圖表示如下表示如下: d c b 幾類特殊集合幾類特殊集合: N=0,1,2,3,，即自然數(shù)集合。，即自然數(shù)集合。 Z=,-2,-1,0,1,2,3,，

8、即整數(shù)集合。，即整數(shù)集合。 Z+=1,2,3,，即正整數(shù)集合。，即正整數(shù)集合。 Q=有理數(shù)集合。有理數(shù)集合。 R=實(shí)數(shù)集合。實(shí)數(shù)集合。 C=復(fù)數(shù)集合。復(fù)數(shù)集合。 確定性；確定性； 互異性；互異性； 無序性；無序性； 多樣性；多樣性； 任何一個對象，或者是這個集合的元素，或任何一個對象，或者是這個集合的元素，或 者不是，二者必居其一；者不是，二者必居其一； 例如：例如：A=x| x是自然數(shù)，且是自然數(shù)，且x100； B=x| x+1=3； C=x| x是大學(xué)生是大學(xué)生。 集合中任何兩個元素都是不同的，即集集合中任何兩個元素都是不同的，即集 合中不允許出現(xiàn)重復(fù)的元素。合中不允許出現(xiàn)重復(fù)的元素。 例

9、如：例如： 集合集合A=a,b,c,c,b,dA=a,b,c,c,b,d，實(shí)際，實(shí)際 上，應(yīng)該是上，應(yīng)該是A=a,b,c,dA=a,b,c,d 。 再如再如 1,2,3,2,4= 1,2,3,41,2,3,2,4= 1,2,3,4。 集合與其中的元素的順序無關(guān)；集合與其中的元素的順序無關(guān)； 例如：例如： 集合集合a,b,c,d,e、d,c,e,a,b、 e,c,d,b,a， 都是表示同一個集合。都是表示同一個集合。 集合集合4,2,1,3 = 1,2,3,4。 集合中的元素可以是任意的對象，集合中的元素可以是任意的對象， 相互獨(dú)立，相互獨(dú)立， 不要求一定要具備明顯不要求一定要具備明顯 的共同特

10、征。的共同特征。 例如：例如： A=a,a,a,b,a, 1； A=1,a,*,-3,a,b,x| x是汽車是汽車,地球地球 注意注意: 對于任何集合對于任何集合A, 都有都有A A。 設(shè)設(shè)A，B是兩個集合，若是兩個集合，若B的元素都是的元素都是A的元的元 素，則稱素，則稱B是是A的的子集子集，也稱，也稱A包含包含B，或，或B被被A包包 含，記以含，記以B A ，或，或A B 。 若若B A ，且，且A B，則稱，則稱B是是A的的真子集真子集，也，也 稱稱A真包含真包含B ，或，或B真包含于真包含于A ，記以，記以A B，或，或B A 。 例例3.1 設(shè)設(shè)A=a, b,c, a, a, b 試

11、判斷下列表達(dá)試判斷下列表達(dá) 式正確與否。式正確與否。 （1）a A （2）a A （3）a A （4） A （5） A （6）b A （7）b A （8）b A （9）a,b A (10) a,b A (11) c A (12) c A (13) c A (14) a,b,c A 。 解解：( (4)4)，(7)(7)，(11)(11)，(13), (14) (13), (14) 錯誤。錯誤。 例例3.2 對于任意集合對于任意集合A, B和和C, 下述論斷是否正確下述論斷是否正確 （1）若）若A B, B C 則則A C （2）若）若A B, B C 則則A C （3）若）若A B, B C

12、則則A C 解解：（：（1） （2） （3） 對對(3)舉反例舉反例 A= , B= 1, C= 1。 例例3.3 設(shè)設(shè)A=1,2,3, 4,5, 6,7,8 下列選項(xiàng)正確的是（下列選項(xiàng)正確的是（ 3 ）；）； （1） 1 A （2）1,2,3 A （3）4,5 A （4） A 例例3.4 下列各選項(xiàng)錯誤的是（下列各選項(xiàng)錯誤的是（2）；）； （1） （2） （3） （4） 例例3.5 在在0 _ 之間填上正確的符號：（之間填上正確的符號：（4） （1） = （2） （3） （4） 當(dāng)兩個集合當(dāng)兩個集合A A和和B B的元素完全一樣，即的元素完全一樣，即A A，B B實(shí)實(shí) 際上是同一個集合時，則

13、稱集合際上是同一個集合時，則稱集合A A，B B相等，記為相等，記為 A=BA=B。 符號化表示為：符號化表示為： A=B A B B A 例：例：設(shè)設(shè)A=x|x是偶數(shù)，且是偶數(shù)，且0 x10， B=2,4,6,8， 則則 A=B。 注：注：說明兩個集合說明兩個集合A、B相等，需說明兩相等，需說明兩 個問題：個問題： 1、A是集合是集合B的子集（的子集（A B） （任意元素（任意元素aA，有，有aB） 2、B是集合是集合A的子集（的子集（A B） （任意元素（任意元素aB，有，有aA） 集合的包含關(guān)系也可表成集合的包含關(guān)系也可表成 A B( x)(x Ax B) 這表明，要證明這表明，要證明A

14、 B，只需對任意元素，只需對任意元素x， 有下式有下式 x Ax B成立即可。成立即可。 不含任何元素的集合叫做空集，記作不含任何元素的集合叫做空集，記作 。 空集的符號化表示為：空集的符號化表示為：=x | P(x)P(x) 。 其中其中P(x)為任何謂詞公式。為任何謂詞公式。 如：如：A=x|xR x2+1=0。 該方程無實(shí)數(shù)解。該方程無實(shí)數(shù)解。 注意：注意： 由定義可知，對任何集合由定義可知，對任何集合A，有，有A。這是因?yàn)槿?。這是因?yàn)槿?意元素意元素x，公式，公式xx A總是為真。總是為真。 注意：注意： 與與是不同的。是不同的。 是以是以為元素的集合，為元素的集合， 而而沒有任何元素

15、，能用沒有任何元素，能用 構(gòu)成集合的無限序列：構(gòu)成集合的無限序列： ， 該序列除第一項(xiàng)外，每項(xiàng)均以前一項(xiàng)為元素的集合。該序列除第一項(xiàng)外，每項(xiàng)均以前一項(xiàng)為元素的集合。 定理：定理：空集是一切集合的子集?？占且磺屑系淖蛹?證明：證明：對于任何集合對于任何集合A，由子集定義有，由子集定義有 , A x(x xA) 右邊的蘊(yùn)涵式中前件為右邊的蘊(yùn)涵式中前件為x為假，所以整個為假，所以整個 蘊(yùn)涵式對一切蘊(yùn)涵式對一切 x 為真，所以為真，所以 A為真為真 推論推論：空集是唯一的。：空集是唯一的。 證明證明: 如不唯一如不唯一, 設(shè)存在空集設(shè)存在空集1和和2, 由由空集是空集是 一切集合的子集一切集合的

16、子集得得1 2 和和2 1 。根據(jù)集合相等。根據(jù)集合相等 的定義得，的定義得， 1 = 2 如果一個集合包含了所要討論的每一個如果一個集合包含了所要討論的每一個 集合，則稱該集合為全集，記為集合，則稱該集合為全集，記為E 或或 U。 它可形式地表為它可形式地表為 E =x | P(x)P(x)。其中。其中 P(x)為任何謂詞公式。為任何謂詞公式。 注意符號注意符號 和和 意義的區(qū)別：意義的區(qū)別： 表示元素與集合之間的關(guān)系，而表示元素與集合之間的關(guān)系，而 則表則表 示集合與集合之間的關(guān)系。但由于集合的抽象示集合與集合之間的關(guān)系。但由于集合的抽象 性，集合中的元素可以是集合，故可以發(fā)生如：性，集合

17、中的元素可以是集合，故可以發(fā)生如： A B且且A B的情形的情形 例例 設(shè)設(shè)A=1,2,3, 1,2,3， 則則 1,2,3 A 且且 1,2,3 A 。 注意：注意： 對任意集合對任意集合A, 有有A A。 空集是任意集合的子集，且空集是唯一的。空集是任意集合的子集，且空集是唯一的。 對于任意兩個集合對于任意兩個集合A、B，A=B的充的充 要條件是要條件是A B且且 B A。（。（這個結(jié)論非常簡單，但它非常重要，很多證這個結(jié)論非常簡單，但它非常重要，很多證 明都是用這個方法或思路來證明。）明都是用這個方法或思路來證明。） 設(shè)設(shè)A 是集合，是集合，A的所有子集為元素做成的集的所有子集為元素做成

18、的集 合稱為合稱為A的的冪集冪集,記以記以P(A) 符號化表示為：符號化表示為： P(A)=x| x A。 例：例： A=a,b,c ，則，則 P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c。 例例3.6 設(shè)設(shè) A=a, a 下列選項(xiàng)錯誤的是下列選項(xiàng)錯誤的是 A. a P(A) B. a P (A) C. a P(A) D. a P (A) 例例3.7 冪集冪集P(P(P()為（為（C ） A. , B. , , C. , , , D. , , P(A)=P(A)=, a, a, a, a 例例3.8 判斷下面的關(guān)系是否正確判斷下面的關(guān)系是否正確, 并簡要說明理由。并簡要說明理由

19、。 a,b a,b,c, a,b,c a,b a,b,c, a,b,c a,b a,b, a,b a,b a,b,a,b 解答解答： 對選項(xiàng)對選項(xiàng), 因?yàn)橐驗(yàn)閍,b 中每個元素中每個元素(只有只有a和和b) 均在集合均在集合a,b,c, a,b,c 對選項(xiàng)對選項(xiàng), 因?yàn)橐驗(yàn)閍,b 中每個元素中每個元素(只有只有a和和b) 均在集合均在集合a,b, a,b 對選項(xiàng)對選項(xiàng) , 集合集合a,b,c, a,b,c中含有中含有4個元個元 素，分別為素，分別為a, b, c, a,b,c沒有沒有a,b，所以不正確。，所以不正確。 對選項(xiàng)對選項(xiàng), 集合集合a,b,a,b中含有中含有3個元素，個元素， 分別為

20、分別為a, b, a,b沒有沒有a,b，所以不正確。，所以不正確。 1.若若A為有窮集，為有窮集，|A|=n，則，則 |2A | = Cn0 + Cn1 + + Cnn =2n 。 2.x P(A)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x A。 3.設(shè)設(shè)A、B是兩個集合，是兩個集合，A B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) P(A) P(B)。 并并 A B = x | x A x B ； 交交 A B = x | x A x B ； 相對補(bǔ)相對補(bǔ) A B = x | x A x B ； 對稱差對稱差 A B = (A B) (B A) = (A B) (A B) ； 絕對補(bǔ)絕對補(bǔ) A = E A 。 A B A A B A A B

21、 A B A-B A B A A B B C A B (A B)-C 集合運(yùn)算對應(yīng)的文氏圖表示集合運(yùn)算對應(yīng)的文氏圖表示 并和交運(yùn)算可以推廣到有窮個集合上，即并和交運(yùn)算可以推廣到有窮個集合上，即 A1 A2 An= x | x A1 x A2 x An A1 A2 An= x | x A1 x A2 x An 某些重要結(jié)果：某些重要結(jié)果： A B A A B A B= A B= A B=A 集合的廣義交和廣義并集合的廣義交和廣義并 設(shè)設(shè)S為集合，為集合，S的元素的元素構(gòu)成的集合稱的元素的元素構(gòu)成的集合稱 為為S的的廣義并廣義并，記為，記為 S，其中，其中 S=xz(z S x z； 設(shè)設(shè)S非空集

22、合，非空集合，S的元素的公共元素構(gòu)成的的元素的公共元素構(gòu)成的 集合稱為集合稱為S的廣義交，記為的廣義交，記為 S，其中，其中 S=xz(z Sx z。 說明：說明： （1 1）規(guī)定）規(guī)定 = = ， 無意義。無意義。 （2 2）若）若 ，則由定義不難證明，則由定義不難證明 S=S= S=S= （3 3）并運(yùn)算和廣義并運(yùn)算的運(yùn)算符相同，但前者是二元運(yùn)算，）并運(yùn)算和廣義并運(yùn)算的運(yùn)算符相同，但前者是二元運(yùn)算， 后者是一元運(yùn)算，因此在運(yùn)算過程中不會對后者是一元運(yùn)算，因此在運(yùn)算過程中不會對 產(chǎn)生誤解。產(chǎn)生誤解。 123 , n SS SSS 123n SSSS 123n SSSS 例：例：設(shè)集合設(shè)集合A

23、=a,b,c,a,c,d,a,c,e，求，求 A， A，A，A，A，A。 解：解： A=a,b,c,d,e； A=a,c； A=a b c d e； A=a c； A=a c； A=a b c d e 。 優(yōu)先級優(yōu)先級 一般地, 一元運(yùn)算符(補(bǔ)集,冪集,廣義并,廣 義交)優(yōu)先于優(yōu)先于 二元運(yùn)算符(差集,并集,交集, 對稱差,笛卡兒積)； 二元運(yùn)算符優(yōu)先于優(yōu)先于 集合關(guān)系符(, , ) 。 此外,許多集合表達(dá)式里還使用到聯(lián)結(jié)詞,和 邏輯關(guān)系符以及括號,我們規(guī)定: (1) 集合運(yùn)算優(yōu)先于邏輯運(yùn)算； (2) 括號內(nèi)優(yōu)先于括號外； (3) 同一括號內(nèi),同一優(yōu)先級按從左至右運(yùn)算。 集合運(yùn)算律集合運(yùn)算律

24、冪等律冪等律：AAA； AAA 同一律同一律：AA； AE=A 零零 律：律：AE=E ； A 結(jié)合律：結(jié)合律：(AB)CA(BC)； (AB)CA(BC) 交換律交換律：ABBA； ABBA 分配律分配律：A（BC）（）（AB）(AC)； A(BC)=(AB)(AC) 排中律：排中律： 矛盾律：矛盾律： 吸收律吸收律：A（AB）A A(AB)A 摩根律：摩根律： 雙重否定律雙重否定律： AAE AA ABABABAB ()()()ABCABAC ()()()ABCABAC AA AB A , AB B ； A AB , B AB ； A-B A ，A-B=AB； AB=BA BAB=A A-

25、B= ； A B=B A； (A B) C=A ( B C) A =A； A A = ； A B=A CB=C。 集合集合等式的證明，可采用命題邏輯的等值式證明，等式的證明，可采用命題邏輯的等值式證明， 其基本思想是其基本思想是互為子集互為子集： 欲證欲證:A=B 即證即證: 即證即證:對任意的對任意的 x , ， 當(dāng)上述過程可逆時，可以合并為當(dāng)上述過程可逆時，可以合并為 對任意的對任意的x, ABBA xAxBxBxA xAxB 集合相等的證明方法集合相等的證明方法 例：例： 證明下列集合恒等式。證明下列集合恒等式。 （1 1）AA（BCBC）（）（ABAB）(AC)(AC) （2 2） （

26、3 3） 證明：證明：(1) (1) 對任意的對任意的x x A (BC) A(BC) A() (A)(A) ()() x xx xxBxC xxBxxC xABxAC xABAC ABAB ()()()ABCABAC (2) 對任意的對任意的x BA()xABxAxxxBxAB (3) 對任意的對任意的x () () () () () ()() ()() ()() xABC xAxBC xAxBC xAxBxC xAxBxC xAxBxAxC xABxAC xABAC 例例3.3.2 證明：（證明：（1） （2）A B=（AB）-（AB） ABAB AB()()()EABEAEB AB 證明

27、證明：(1) (2) AB=（A-B）（B-A） ()() ()()()() ()() ()() ABBA ABAABBBA ABAB ABAB 例例 證明證明(AB)- C =(A-C)(B-C). 證明證明: 對于對于 x x (AB)- C x (AB) x C ( x A xB ) x C ( x A x C) (xB x C) x ( A- C ) x ( B- C) x ( A-C) (B- C) (AB)- C =(A-C)(B-C) 例例 證明證明 證明：證明：(1)必要性必要性：對任意的：對任意的X, 因此，因此， 。 (2)充分性充分性：對任意的：對任意的x， 因此因此 ，

28、結(jié)論得證。，結(jié)論得證。 ( )( )ABP AP B ( )( )xP AxAxBxP B ( )( )P AP B ( ) ( ) xAxAxP AxP BxBxB AB 例例 求在求在1和和1000之間不能被之間不能被5或或6，也不能被，也不能被8整整 除的數(shù)的個數(shù)解：設(shè)除的數(shù)的個數(shù)解：設(shè)1到到1000之間的整數(shù)構(gòu)成全之間的整數(shù)構(gòu)成全 集集E，A，B，C分別表示其中可被分別表示其中可被5，6或或8整除整除 的數(shù)的集合。的數(shù)的集合。 解：解：在在ABC中的數(shù)一定可被中的數(shù)一定可被5,6和和8的最小的最小 公倍數(shù)公倍數(shù) 5,6,8 =120整除，即整除，即 ABC= 1000/ 5,6,8 =

29、8 同樣可得同樣可得 AB= 1000/ 5,6 =33； AC= 1000/ 5,8 =25； BC= 1000/ 6,8 =41； 然后計(jì)算然后計(jì)算 A= 1000/5 =200 ； B= 1000/6 =166 ； C= 1000/8 =125 從而得到從而得到 ABC=200+100+33+67=400 所以，所以，不能被不能被5或或6,也不能被也不能被8整除的數(shù)有整除的數(shù)有600個。個。 150 100 67 17 33 25 8 對上述子集計(jì)數(shù)：對上述子集計(jì)數(shù)： |S|=1000； |A|= 1000/5 =200； |B|= 1000/6 =133； |C|= 1000/8 =1

30、25； |A B|= 1000/30 =33； |B C| = 1000/40 =25 |B C|= 1000/24 =41； |A B C| = 1000/120 =8。 代入公式：代入公式： N = 1000 (200+133+125)+(33+25+41) 8=600。 這個方法叫這個方法叫容斥原理。容斥原理。 稱為包含排斥原理，簡稱稱為包含排斥原理，簡稱容斥原理容斥原理。 容斥原理容斥原理 定理：定理： 有窮集有窮集S中不具有中不具有p1,p2,pm元素?cái)?shù)是元素?cái)?shù)是 12 11 12 1 ( 1) m m iiij iij m m ijkm ij k m AAA SAAA AAAAAA

31、 m m kji kji ji ji m i i m i i AAA AAAAAAA 21 1 11 ) 1( 推論推論 設(shè)設(shè)A1,A2,An是是n個集合，則個集合，則 例例 某班有某班有2525個學(xué)生，其中個學(xué)生，其中1414人會打籃球，人會打籃球，1212人人 會打排球，會打排球，6 6人會打籃球和排球，人會打籃球和排球，5 5人會打籃球人會打籃球 和網(wǎng)球，還有和網(wǎng)球，還有2 2人會打這三種球。而人會打這三種球。而6 6個會打網(wǎng)個會打網(wǎng) 球的人都會打另外一種球球的人都會打另外一種球( (指籃球或排球指籃球或排球) )，求，求 不會打這三種球的人數(shù)。不會打這三種球的人數(shù)。 解：解：設(shè)會打排球

32、、網(wǎng)球、籃球的學(xué)生集合設(shè)會打排球、網(wǎng)球、籃球的學(xué)生集合 分別為分別為A，B 和和 C，則有，則有 A=12， B=6， C=14， S=25 AC=6，BC=5， ABC=2 現(xiàn)在求現(xiàn)在求 AB，因?yàn)闀蚓W(wǎng)球的人都會打另一種球，即籃，因?yàn)闀蚓W(wǎng)球的人都會打另一種球，即籃 球和排球，而其中會打籃球的有球和排球，而其中會打籃球的有5人，那么另一個人肯定人，那么另一個人肯定 會打排球但不會打籃球，再加上會打三種球的會打排球但不會打籃球，再加上會打三種球的2人，共有人，共有 3人會打排球和網(wǎng)球，即人會打排球和網(wǎng)球，即AB=3，根據(jù)容斥定理有，根據(jù)容斥定理有 ABC = 25-（12+6+14）+（3+

33、6+5）-2 = 5 32 4 排球排球1212 籃球籃球1414 網(wǎng)球網(wǎng)球6 6 1 5 5 不會打三種球人不會打三種球人 數(shù)為：數(shù)為： 25-(12+5+3)=5 課堂練習(xí)：證明下列等式課堂練習(xí)：證明下列等式 ()ABAAB ()ABABA ()()ABCABC ()AABB ()()()()ABCDADBC ( )( )ABP AP B ( )( )()P AP BP AB ( )( )()P AP BP AB 第四章第四章 二元關(guān)系和函數(shù)二元關(guān)系和函數(shù) 說起關(guān)系這個詞，對我們并不陌生，世界上存在說起關(guān)系這個詞，對我們并不陌生，世界上存在 著各種各樣的關(guān)系，人與人之間的著各種各樣的關(guān)系，

34、人與人之間的“同志同志”關(guān)系；關(guān)系； “同學(xué)同學(xué)”關(guān)系；關(guān)系；“朋友朋友”關(guān)系；關(guān)系；“師生師生”關(guān)系；關(guān)系；“上上 下級下級”關(guān)系；關(guān)系；“父子父子”關(guān)系；兩個數(shù)之間有關(guān)系；兩個數(shù)之間有“大于大于” 關(guān)系；關(guān)系；“等于等于”關(guān)系和關(guān)系和“小于小于”關(guān)系；兩個變量之間關(guān)系；兩個變量之間 有一定的有一定的“函數(shù)函數(shù)”關(guān)系；計(jì)算機(jī)內(nèi)兩電路間有導(dǎo)線關(guān)系；計(jì)算機(jī)內(nèi)兩電路間有導(dǎo)線 “連接連接”關(guān)系；程序間有關(guān)系；程序間有“調(diào)用調(diào)用”關(guān)系等等。所以對關(guān)系等等。所以對 關(guān)系進(jìn)行深刻的研究，對數(shù)學(xué)與計(jì)算機(jī)科學(xué)都有很大關(guān)系進(jìn)行深刻的研究，對數(shù)學(xué)與計(jì)算機(jī)科學(xué)都有很大 的用處。的用處。 集合的笛卡爾積與二元關(guān)系集合

35、的笛卡爾積與二元關(guān)系 由兩個元素由兩個元素x,y（允許（允許x=y）按一定順序排列成）按一定順序排列成 的二元組叫做一個的二元組叫做一個有序?qū)蛐蚺加行驅(qū)蛐蚺?，記作，記?其中其中x是是 它的它的第一元素第一元素，y是它的是它的第二元素第二元素。 有序?qū)τ行驅(qū)哂幸韵滦再|(zhì)：具有以下性質(zhì)： (1) 當(dāng)當(dāng)xy時，時， (2) = x=w y=v 例例：已知：已知 = ，求，求 x 和和 y。 解：由有序?qū)ο嗟鹊某湟獥l件得解：由有序?qū)ο嗟鹊某湟獥l件得 x+3 = y+7 y-2 = 3y-x 解得解得 x = 6, y = 2。 一個一個有序有序n元組元組 (n3)是一個有序?qū)?，其中第一個元素是一

36、個有序?qū)?，其中第一個元素 是一個有序是一個有序n-1元組，一個有序元組，一個有序n元組記作元組記作,即即 = , xn 例：例：空間直角坐標(biāo)系中點(diǎn)的坐標(biāo)空間直角坐標(biāo)系中點(diǎn)的坐標(biāo) , 等都是有序等都是有序3元組。元組。 n維空間中點(diǎn)的坐標(biāo)或維空間中點(diǎn)的坐標(biāo)或n維向量都是有序維向量都是有序n元組。元組。 形式上也可以把形式上也可以把看成有序看成有序1元組。元組。 設(shè)設(shè)A，B為集合，用為集合，用A中元素為第一元素，中元素為第一元素，B中中 元素為第二元素構(gòu)成有序?qū)ΑＫ羞@樣的有序?qū)υ貫榈诙貥?gòu)成有序?qū)?。所有這樣的有序?qū)?組成的集合叫做組成的集合叫做A和和B的的笛卡兒積笛卡兒積，記作，記作AB。

37、笛卡兒積的符號化表示為：笛卡兒積的符號化表示為： AB=|x A yB 例例：若：若A=1,2, B=a,b,c,則則 AB=, , , , , BA=, , , , , 易知：若易知：若|A|=m,(即集合即集合A的元素的個數(shù)的元素的個數(shù)),|B|=n,則則 | AB|= |BA|= m n 有序?qū)褪怯许樞虻臄?shù)組有序?qū)褪怯许樞虻臄?shù)組，如，如，x,y 的的 位置是確定的，不能隨意放置。位置是確定的，不能隨意放置。 注意注意：有序?qū)Γ河行驅(qū)?，以，以a,b為元素的集合為元素的集合 a,b=b,a；有序?qū)?；有序?qū)?a,a)有意義，而集合有意義，而集合a,a不成立。不成立。 笛卡兒積是一種集合合

38、成的方法笛卡兒積是一種集合合成的方法，把集合，把集合A，B合合 成集合成集合AB，規(guī)定，規(guī)定AB x A, y B。 由于有序?qū)τ捎谟行驅(qū)χ兄衳,y的位置是確定的，因此的位置是確定的，因此AB的的 記法也是確定的，不能寫成記法也是確定的，不能寫成BA。 笛卡兒積也可以多個集合合成笛卡兒積也可以多個集合合成 A1A2An。 笛卡兒積的運(yùn)算性質(zhì)。笛卡兒積的運(yùn)算性質(zhì)。 笛卡兒積的性質(zhì)：笛卡兒積的性質(zhì)： 1、對任意集合、對任意集合A，根據(jù)定義有，根據(jù)定義有 A = A= 2、一般來說，笛卡兒積不滿足交換律，即、一般來說，笛卡兒積不滿足交換律，即 ABBA （當(dāng)（當(dāng)A B B 、A 時）時） 3、笛卡兒

39、積不滿足結(jié)合律，即、笛卡兒積不滿足結(jié)合律，即 (AB) CA(B C) （當(dāng)（當(dāng)ABC時）時） 4、笛卡兒積運(yùn)算對并和交運(yùn)算滿足分配律，即、笛卡兒積運(yùn)算對并和交運(yùn)算滿足分配律，即 A(BC)= (AB)(A C) (BC) A = (BA)(C A) A(BC)= (AB) (A C) (BC) A = (BA) (C A) 例：例： 證明證明 (BC) A = (BA)(C A) 對于對于 (BC) A x(B C) y A xB x C y A xB x C y A y A (xB y A) (x C y A) B A C A (BA) (C A) (BC) A = (BA) (C A)

40、例例：設(shè)：設(shè)A， C， B， D為任意集合，為任意集合， 判斷以下命題是否為真，并說明理由。判斷以下命題是否為真，并說明理由。 (1) AB= AC =B= C。 (2) A-(BC)=( A-B)(A-C)。 (3) 存在集合存在集合A,使得使得A A A。 解：解：(1) (1) 不一定為真。反例不一定為真。反例A=, BA=, B、C C為任意不相為任意不相 等的非空集合。等的非空集合。 (2) (2) 不一定為真。反例不一定為真。反例A=1, B=2, C=3.A=1, B=2, C=3. (3) (3) 為真。當(dāng)為真。當(dāng) A= A= 時成立。時成立。 設(shè)設(shè)A1,A2,An,是集合是集

41、合(n2),它們的它們的n階笛卡兒積階笛卡兒積 記作記作A1A2An ，其中，其中 A1A2An= | x1 A1x2 A2xn An 。 當(dāng)當(dāng)A1=A2=An=A時時, 將起將起n階笛卡兒積記作階笛卡兒積記作An 例例，A= a ,b , 則：則： A3=AAA=a,ba,ba,b =, , , 。 例例：設(shè)集合：設(shè)集合 A=a,b,B=1,2,3,C=d, 求求ABC，BA。 解：解： 先計(jì)算先計(jì)算 AB, ABC ,d , BA, 。 例：例： 設(shè)集合設(shè)集合A1,2,求求AP(A)。 解：解： P(A)=,1,2,1,2 AP(A)1,2,1,2,1,2 =, , , 如果一個集合符合以

42、下條件之一：如果一個集合符合以下條件之一： (1) 集合非空，且它的元素都是有序?qū)戏强?，且它的元素都是有序?qū)?(2) 集合是空集集合是空集 則稱該集合為一個則稱該集合為一個二元關(guān)系二元關(guān)系，記作，記作R，簡稱為關(guān)系。，簡稱為關(guān)系。 對于二元關(guān)系對于二元關(guān)系R，若，若 R,可記作可記作xRy;如果如果 R, 則記作則記作xRy。 例例：R1=, aR1b, 1R12。 二元關(guān)系二元關(guān)系是兩種客體之間的聯(lián)系，例如某學(xué)生是兩種客體之間的聯(lián)系，例如某學(xué)生 學(xué)習(xí)語文、數(shù)學(xué)、外語，表示為：學(xué)習(xí)語文、數(shù)學(xué)、外語，表示為： A A 語文語文, , 數(shù)學(xué)數(shù)學(xué), , 外語外語 功課的成績分四個等級，記作功課的

43、成績分四個等級，記作B BAA，B B，C C，DD 于是該生成績的全部可能為于是該生成績的全部可能為A AB B A AB B ,D, ,D, ,D 而該生的實(shí)際成績而該生的實(shí)際成績 P P,D P P是是A AB B的一個子集，它表示了功課與其成績的一種關(guān)系。的一個子集，它表示了功課與其成績的一種關(guān)系。 由此可見：由此可見：兩個集合之間的二元關(guān)系，實(shí)際上就是兩個兩個集合之間的二元關(guān)系，實(shí)際上就是兩個 元素之間的某種相關(guān)性。元素之間的某種相關(guān)性。 設(shè)設(shè)A，B為集合，為集合，AB的任何子集所定義的的任何子集所定義的 二元關(guān)系叫做從二元關(guān)系叫做從A到到B的的二元關(guān)系二元關(guān)系； 特別當(dāng)特別當(dāng)A=B

44、時則叫做時則叫做A上的上的二元關(guān)系二元關(guān)系。 例：例：若若A=a,b，B=1,2,3，則，則 A B= , 令令 R1= , R2=, , R3=。 因?yàn)橐驗(yàn)镽1 A B， R2 A B， R3 A B，所以，所以R1, R2和和 R3均是由均是由A到到B的二元關(guān)系。的二元關(guān)系。 又例：若又例：若A=a,b，B=1,2,3，則，則 BA= , 令令 R4= , R5=, , 因?yàn)橐驗(yàn)镽4 BA， R5 BA， 所以所以R4和和 R5均是由均是由B到到A的關(guān)系。的關(guān)系。 又又 BB=, , , 。 令令 R6= ，, R7=, 因?yàn)橐驗(yàn)镽6 BB， R7 BB， 所以所以R6和和 R7均是集合均

45、是集合B上上的關(guān)系。的關(guān)系。 若集合若集合|A|=n,則集合則集合A上的二元關(guān)系有多少個？上的二元關(guān)系有多少個？ 答：答： |A|=n，則，則|A A|=n2, A A的任一個子集的任一個子集 就是就是A上的二元關(guān)系，即上的二元關(guān)系，即P(A)= 2n 個。個。 例例 A= 1,2 則則A A有有 2n 個不同的二元關(guān)系；個不同的二元關(guān)系； AA=1,21,2= ,。 AA的任一個子集就是的任一個子集就是A A的冪集，即的冪集，即P(A) P(A)= , , , , , , , , , , , , , , , , , , , , , , , , 三類特殊的關(guān)系三類特殊的關(guān)系 空關(guān)系：空關(guān)系：對

46、于任何集合對于任何集合A，空集，空集 是是A A的的 子集，稱作子集，稱作A上的上的空關(guān)系；空關(guān)系； 全關(guān)系：全關(guān)系：定義定義EA=|xA yA= AA為為全全 域關(guān)系；域關(guān)系； 恒等關(guān)系：恒等關(guān)系： 定義定義IA=|xA 為為A上上恒等關(guān)系。恒等關(guān)系。 例：例：若若A=1,2,3，則，則 EA= , , IA =, 。 例：例：設(shè)設(shè)A=1,2,3,4，請表示下列關(guān)系。，請表示下列關(guān)系。 (1) R= |x是是y的倍數(shù)的倍數(shù) (2) R= |(x-y)2 A (3) R= |x除除y是素?cái)?shù)是素?cái)?shù) (4) R= |xy 解：解：(1) R = , , , , ,； (2) R = , , ,；

47、(3) R = ,； (4) R= , , 關(guān)系表示法關(guān)系表示法 有窮集合上的二元關(guān)系的三種表示方法：有窮集合上的二元關(guān)系的三種表示方法： n 集合表示法集合表示法 （前已使用）（前已使用） n 關(guān)系矩陣法關(guān)系矩陣法 n 關(guān)系圖關(guān)系圖 關(guān)系矩陣是表示關(guān)系的另一種有效的方法，其關(guān)系矩陣是表示關(guān)系的另一種有效的方法，其 優(yōu)點(diǎn)是可以利用矩陣作為研究關(guān)系的手段，而且這優(yōu)點(diǎn)是可以利用矩陣作為研究關(guān)系的手段，而且這 樣做便于計(jì)算機(jī)進(jìn)行處理。樣做便于計(jì)算機(jī)進(jìn)行處理。 設(shè)設(shè)R：AB，A和和B都是有限集，且都是有限集，且 |A|=n, |B|=m, A , B中的元素已按一定的次序排列若中的元素已按一定的次序排

48、列若 A=x1,x2,xn ,B= y1,y2,ym 且且R A B,若若 則稱矩陣則稱矩陣為為R的的關(guān)系矩陣關(guān)系矩陣 關(guān)系矩陣法關(guān)系矩陣法 1, 0, ij ij ij x yR r x yR 0 1 1 1 MR= 0 0 1 1 0 0 0 1 0 0 0 0 例例 A=1,2,3,4, R為為A上的小于關(guān)系，上的小于關(guān)系， 則則R=, , , R的關(guān)系矩陣為：的關(guān)系矩陣為： 1 2 3 41 2 3 4 1 2 3 41 2 3 4 例例: 設(shè)集合設(shè)集合A2,3,4, B=8,9,12,14。 R是由是由 A到到B的二元關(guān)系，定義：的二元關(guān)系，定義：R= | a整除整除b 寫出寫出R的

49、表達(dá)式和關(guān)系矩陣。的表達(dá)式和關(guān)系矩陣。 解解：R=, R的關(guān)系矩陣：的關(guān)系矩陣： 101 1 0110 1010 R M 關(guān)系圖關(guān)系圖 關(guān)系圖是表示關(guān)系的一種直觀形象的方法，設(shè)關(guān)系圖是表示關(guān)系的一種直觀形象的方法，設(shè)R： AB，A和和B都是有限集，都是有限集， A=x1,x2,xn , B= y1,y2,ym 關(guān)系關(guān)系R的有序?qū)Φ挠行驅(qū)?可用圖中從結(jié)點(diǎn)可用圖中從結(jié)點(diǎn)xi 到到y(tǒng)j 的有向的有向 邊表示，這樣即可將關(guān)系用圖表示之。邊表示，這樣即可將關(guān)系用圖表示之。 例例 設(shè)設(shè) R: AB，A=x1,x2, x3, x4 , B= y1,y2,y3 R=, , ， R的關(guān)系如下圖所示的關(guān)系如下圖所

50、示 x1 x2 x3 x4 y1 y2 y3 設(shè)設(shè)R是在是在A上的二元關(guān)系，上的二元關(guān)系， A=x1,x2,xn 關(guān)系關(guān)系R的有序的有序 偶偶 可用圖中從結(jié)點(diǎn)可用圖中從結(jié)點(diǎn)xi 到到xj 的有向邊表示，這樣的有向邊表示，這樣 即可將關(guān)系用圖表示之。即可將關(guān)系用圖表示之。 例例 ：設(shè)設(shè) R: AA，A= a,b, c, d R=, , , R的關(guān)系如下圖所示：的關(guān)系如下圖所示： a b c d 例：例： 設(shè)集合設(shè)集合A=a,b,c,d,R是是A上的關(guān)系上的關(guān)系 R=,試以試以 關(guān)系矩陣和關(guān)系圖來表示關(guān)系關(guān)系矩陣和關(guān)系圖來表示關(guān)系R。 解：解： （1）關(guān)系矩陣為：）關(guān)系矩陣為： 1110 0010

51、 0001 0001 M bc da （2）關(guān)系圖為：）關(guān)系圖為： 關(guān)系的運(yùn)算關(guān)系的運(yùn)算 （1）R中所有的有序?qū)Φ牡谝辉貥?gòu)成的集合稱為中所有的有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R 的的定義域定義域，記作，記作domR。 domR=x| y( R （2）R中所有的有序?qū)Φ牡诙貥?gòu)成的集合稱為中所有的有序?qū)Φ牡诙貥?gòu)成的集合稱為R 的的值域值域，記作，記作ranR。 ranR=y| x R （3）R的定義域和值域的并集稱為的定義域和值域的并集稱為R的的域域，記作，記作fldR。 fldR=domR ranR 例：例： 設(shè)設(shè)R=,則則 domR=1，2，3 ranR=1，2，3，4 fldR=1，

52、2，3，4 限制關(guān)系限制關(guān)系 設(shè)設(shè)R為二元關(guān)系，為二元關(guān)系，A是集合是集合 （1）R在在A上的限制，記作上的限制，記作R A,其中其中 R A=|xRy x A （2）A在在R下的象，記作下的象，記作RA，其中，其中 RA=ran(R A) 例例：設(shè)集合：設(shè)集合A=1,2,3,4,R是是A上的關(guān)系上的關(guān)系 R=, 集合集合B=1,2,4,試求試求R B及及RB。 解：解：R B=,； RB=1，3，4。 逆運(yùn)算逆運(yùn)算 設(shè)設(shè)R為二元關(guān)系，稱為二元關(guān)系，稱 為為R的逆關(guān)系，其中的逆關(guān)系，其中 =| R 定理定理4.1 設(shè)設(shè)F是任意關(guān)系，則是任意關(guān)系，則 （1） （2） 1 R 1 R 11 ()F

53、F 證明：證明：（1）對任意的）對任意的 11 domFranF,ranFdomF 11 1 () F F F （2）對任意的）對任意的y 1 1 (,) (,) ydomF xy xF xx yF yranF 對任意的對任意的x 1 1 (,) (,) xranF yy xF yx yF xdomF 復(fù)合運(yùn)算復(fù)合運(yùn)算 設(shè)設(shè)F,G為二元關(guān)系為二元關(guān)系G對對F的右復(fù)合記作的右復(fù)合記作F?G,其中其中 F?G=| t( F G。 說明：說明： （1）本書采用右復(fù)合的規(guī)則，而有的教材采用左復(fù)合）本書采用右復(fù)合的規(guī)則，而有的教材采用左復(fù)合 規(guī)則，兩者都可行，只是需要注意它們的區(qū)別，從變換的規(guī)則，兩者都

54、可行，只是需要注意它們的區(qū)別，從變換的 角度來說，角度來說，G對對F的右復(fù)合是先的右復(fù)合是先F變換后變換后G變換，而變換，而G對對F 的左復(fù)合是先的左復(fù)合是先G變換后變換后F變換。變換。 （2）一般來說，并沒有）一般來說，并沒有F?G等于等于G?F，請讀者仔細(xì)注意，請讀者仔細(xì)注意 其區(qū)別。其區(qū)別。 例：例：設(shè)設(shè)F=,G=,則求則求F?F，G?G，F(xiàn)?G和和G? F。 解：解：F?F= ，G?G= F?G= G?F=。 例：例：設(shè)有集合設(shè)有集合 A=4,5,8,15, B=3,4,5,9,11 C=1,6,8,13, F 是由是由 A 到到 B 的關(guān)系的關(guān)系, G 是由是由 B 到到 C 的的

55、關(guān)系關(guān)系,分別定義為分別定義為 F=| |b-a|=1 G=| |b-c|=2或或|b-c|=4 求合成關(guān)系求合成關(guān)系G F和和F G 解：解： 先求先求G F, 由題意知由題意知 F=, ,； G=, ,； G F= ,。 定理：定理： 設(shè)設(shè)F、G、H是任意關(guān)系是任意關(guān)系, 則則 (1) (F-1)-1=F (2) dom(F-1)=ranF , ranF-1=domF (3) (F G) H= F (G H) (4) (F G)-1= G-1 F-1 證明證明: (1) 任取任取,由逆的定義有由逆的定義有 (F-1)-1 F-1 F (F-1) -1 = F (2) 任取任取x, xran

56、 F-1 y( F-1 ) y( F) x dom F ran F-1 = dom F 同理可證同理可證 dom (F-1) = ran F 證明證明: (3) 任取任取, (F G) H t( F G H ) t s( F G H ) s( F t ( G H ) s( F G 。H ) F (G H ) (4) 任取任取, (F G)-1 F G t( F G) t( G-1 F-1 ) G-1 F-1 定理：定理： 設(shè)設(shè)F、G、H是任意關(guān)系是任意關(guān)系,則則 (1) F (GH)= F G F H (2) (GH) F= G F H F (3) F (GH) F G F H (4) (GH

57、) F G F H F 證明證明: (1) 任取任取, F (GH) t( FG H ) t (F(GH ) t (FG)( FH) t (FG) t(FH) F G F H F G F H 證明證明: (3) 任取任取 , F (GH) t( F G H ) t ( F G H ) t (FG)( FH) = t(FG) t( F H) F G F H F G F H 本定理對有限個關(guān)系的并和交都成立。本定理對有限個關(guān)系的并和交都成立。 R (R1R2 Rn)= R R1R R2R Rn (R1R2 Rn) R= R1 RR2 RRn R R (R1 R2 Rn) R R1R R2 R Rn

58、 (R1R2 Rn) R R1 RR2 RRn R 冪運(yùn)算：冪運(yùn)算： 設(shè)設(shè)R是是A上的關(guān)系上的關(guān)系, n為自然數(shù)，則為自然數(shù)，則R的的n次冪規(guī)定如下：次冪規(guī)定如下： (1) R0= | xA (2) Rn= Rn-1 R n1 由定義可以知道由定義可以知道R0就是就是A上的恒等關(guān)系上的恒等關(guān)系IA，不難證，不難證 明下面的等式明下面的等式R R0 =R=R0 R 。 由這個等式立即可以得到由這個等式立即可以得到 R1 =R0 R =R 例：例： 設(shè)設(shè)A= a,b,c,d ,R= , 求求R0 ，R1，R2， R3 ，R4和和R5 解：解： R0 = , R1 = R0 R = , , = ,

59、。 R2 = R R = , , = , R3 = R2 R = , , =, R4 = R3 R = , , =, R5 = R4 R = , , =, 定理：定理：設(shè)設(shè)R是是A上的關(guān)系上的關(guān)系, m, n 為自然數(shù)，為自然數(shù)， 則下面的等式成立則下面的等式成立 (1) Rm Rn= Rm+n (2) (Rm)n= Rmn 證明：證明： (1) 任給任給m，對，對n作歸納法。作歸納法。 n=0時，時，Rm R0=Rm = Rm+0。 假設(shè)假設(shè)Rm Rn=Rm+n，那么，那么RmRn+1=Rm(RnR1)= (RmRn )R1= Rm+nR1= Rm+n+1= Rm+(n+1) 。 (2) 任

60、給任給m，對，對n作歸納法。作歸納法。 n=0時，時，(Rm)0= R0 = Rm 0。 假設(shè)假設(shè)(Rm)n=Rmn。那么。那么(Rm)n+1= (Rm)n Rm = Rmn Rm = Rmn+m= Rm(n+1) 例例: 已知集合已知集合A=a,b,c,d,A上的關(guān)系上的關(guān)系 R=,，求，求 。 解：解：法一法一：由復(fù)合定義知：由復(fù)合定義知 2 RR R 32 RRR =, =, 23 ,RR 法二法二：關(guān)系：關(guān)系R R矩陣為矩陣為 0100 1010 0001 0000 M 2 M 0100 1010 0001 0000 0100 1010 0001 0000 3 1010 0101 00