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

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

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

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

4、，中的元素，元素與元素與集合的關系：集合的關系： 屬于屬于； 不屬于不屬于 若若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。特別注意：特別注意： 集合并不決定于它的元素展示方法。集合的元素集合并不決定于它的元素展示方法。集合的元素被重復或重新排列，集合并不改變，即被重復或重新排列，集合并不改變，即a, a ,b, c, d, c= a, b, c, d。集合的元素可以是具

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

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

7、=x|0 x10; B= x|x=a2,a是自然數(shù)是自然數(shù)。EAae文氏圖文氏圖 用一個大的矩形表示全集，在矩形內畫一些圓或用一個大的矩形表示全集，在矩形內畫一些圓或其它的幾何圖形，來表示集合，有時也用一些點來表其它的幾何圖形，來表示集合，有時也用一些點來表示集合中的特定元素。示集合中的特定元素。 例如：例如：集合集合A=a,b,c,d,e ，用，用文氏圖文氏圖表示如下表示如下:dcb幾類特殊集合幾類特殊集合:N=0,1,2,3,，即自然數(shù)集合。，即自然數(shù)集合。Z=,-2,-1,0,1,2,3,，即整數(shù)集合。，即整數(shù)集合。Z+=1,2,3,，即正整數(shù)集合。，即正整數(shù)集合。Q=有理數(shù)集合。有理數(shù)

8、集合。R=實數(shù)集合。實數(shù)集合。C=復數(shù)集合。復數(shù)集合。確定性；確定性；互異性；互異性；無序性；無序性；多樣性；多樣性； 任何一個對象，或者是這個集合的元素，或任何一個對象，或者是這個集合的元素，或者不是，二者必居其一；者不是，二者必居其一； 例如：例如：A=x| x是自然數(shù)，且是自然數(shù)，且x100； B=x| x+1=3； C=x| x是大學生是大學生。 集合中任何兩個元素都是不同的，即集集合中任何兩個元素都是不同的，即集合中不允許出現(xiàn)重復的元素。合中不允許出現(xiàn)重復的元素。 例如：例如： 集合集合A=a,b,c,c,b,dA=a,b,c,c,b,d，實際，實際 上，應該是上，應該是A=a,b,

9、c,dA=a,b,c,d 。 再如再如 1,2,3,2,4= 1,2,3,41,2,3,2,4= 1,2,3,4。 集合與其中的元素的順序無關；集合與其中的元素的順序無關； 例如：例如： 集合集合a,b,c,d,e、d,c,e,a,b、 e,c,d,b,a，都是表示同一個集合。都是表示同一個集合。 集合集合4,2,1,3 = 1,2,3,4。 集合中的元素可以是任意的對象，集合中的元素可以是任意的對象， 相互獨立，相互獨立，不要求一定要具備明顯不要求一定要具備明顯 的共同特征。的共同特征。 例如：例如： A=a,a,a,b,a, 1； A=1,a,*,-3,a,b,x| x是汽車是汽車,地球地

10、球 注意注意: 對于任何集合對于任何集合A, 都有都有A A。 設設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 設設A=a, b,c, a, a, b 試判斷下列表達試判斷下列表達式正確與否。式正確與否。（1）a A （2）a A （3）a A （4） A （5） A （6）b A（

11、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 則則A C 解解：（：（1） （2） （3） 對對(3)舉反例舉反例 A= , B= 1, C= 1。例例3.3 設設A=1,2,3, 4,5,

12、 6,7,8 下列選項正確的是（下列選項正確的是（ 3 ）；）； （1） 1 A （2）1,2,3 A （3）4,5 A （4） A 例例3.4 下列各選項錯誤的是（下列各選項錯誤的是（2）；）； （1） （2） （3） （4） 例例3.5 在在0 _ 之間填上正確的符號：（之間填上正確的符號：（4） （1） = （2） （3） （4） 當兩個集合當兩個集合A A和和B B的元素完全一樣，即的元素完全一樣，即A A，B B實實際上是同一個集合時，則稱集合際上是同一個集合時，則稱集合A A，B B相等，記為相等，記為A=BA=B。 符號化表示為：符號化表示為： A=B A B B A 例：例：設

13、設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）集合的包含關系也可表成集合的包含關系也可表成A B( x)(x Ax B)這表明，要證明這表明，要證明A B，只需對任意元素，只需對任意元素x，有下式有下式 x Ax B成立即可。成立即可。 不含任何元素的集合叫做空集，記作不含任何元素的集合叫做空集，記作 ?？占?/p>

14、符號化表示為：空集的符號化表示為：=x | P(x)P(x) 。 其中其中P(x)為任何謂詞公式。為任何謂詞公式。 如：如：A=x|xR x2+1=0。 該方程無實數(shù)解。該方程無實數(shù)解。 注意：注意： 由定義可知，對任何集合由定義可知，對任何集合A，有，有A。這是因為任。這是因為任意元素意元素x，公式，公式xx A總是為真?？偸菫檎?。注意：注意： 與與是不同的。是不同的。 是以是以為元素的集合，為元素的集合， 而而沒有任何元素，能用沒有任何元素，能用構成集合的無限序列：構成集合的無限序列：，該序列除第一項外，每項均以前一項為元素的集合。該序列除第一項外，每項均以前一項為元素的集合。定理：定理：

15、空集是一切集合的子集。空集是一切集合的子集。 證明：證明：對于任何集合對于任何集合A，由子集定義有，由子集定義有 , A x(x xA) 右邊的蘊涵式中前件為右邊的蘊涵式中前件為x為假，所以整個為假，所以整個蘊涵式對一切蘊涵式對一切 x 為真，所以為真，所以 A為真為真推論推論：空集是唯一的。：空集是唯一的。 證明證明: 如不唯一如不唯一, 設存在空集設存在空集1和和2, 由由空集是空集是一切集合的子集一切集合的子集得得1 2 和和2 1 。根據(jù)集合相等。根據(jù)集合相等的定義得，的定義得， 1 = 2 如果一個集合包含了所要討論的每一個如果一個集合包含了所要討論的每一個集合，則稱該集合為全集，記

16、為集合，則稱該集合為全集，記為E 或或 U。它可形式地表為它可形式地表為 E =x | P(x)P(x)。其中。其中P(x)為任何謂詞公式。為任何謂詞公式。注意符號注意符號 和和 意義的區(qū)別：意義的區(qū)別： 表示元素與集合之間的關系，而表示元素與集合之間的關系，而 則表則表示集合與集合之間的關系。但由于集合的抽象示集合與集合之間的關系。但由于集合的抽象性，集合中的元素可以是集合，故可以發(fā)生如：性，集合中的元素可以是集合，故可以發(fā)生如：A B且且A B的情形的情形 例例 設設A=1,2,3, 1,2,3， 則則 1,2,3 A 且且 1,2,3 A 。 注意：注意：對任意集合對任意集合A, 有有A

17、 A?？占侨我饧系淖蛹?，且空集是唯一的?？占侨我饧系淖蛹?，且空集是唯一的。對于任意兩個集合對于任意兩個集合A、B，A=B的充的充 要條件是要條件是A B且且B A。（。（這個結論非常簡單，但它非常重要，很多證這個結論非常簡單，但它非常重要，很多證明都是用這個方法或思路來證明。）明都是用這個方法或思路來證明。）設設A 是集合，是集合，A的所有子集為元素做成的集的所有子集為元素做成的集合稱為合稱為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

18、設設 A=a, a 下列選項錯誤的是下列選項錯誤的是 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 判斷下面的關系是否正確判斷下面的關系是否正確,并簡要說明理由。并簡要說明理由。 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 解答解答： 對選項對選項, 因為因為a,b 中每個元素中每個元素(只有只有a和和b)均在集合均在集合a

19、,b,c, a,b,c 對選項對選項, 因為因為a,b 中每個元素中每個元素(只有只有a和和b)均在集合均在集合a,b, a,b 對選項對選項 , 集合集合a,b,c, a,b,c中含有中含有4個元個元素，分別為素，分別為a, b, c, a,b,c沒有沒有a,b，所以不正確。，所以不正確。 對選項對選項, 集合集合a,b,a,b中含有中含有3個元素，個元素，分別為分別為a, b, a,b沒有沒有a,b，所以不正確。，所以不正確。1.若若A為有窮集，為有窮集，|A|=n，則，則|2A | = Cn0 + Cn1 + + Cnn =2n 。2.x P(A)當且僅當當且僅當x A。3.設設A、B是

20、兩個集合，是兩個集合，A B當且僅當當且僅當P(A) P(B)。并并 A B = x | x A x B ；交交 A B = x | x A x B ；相對補相對補 A B = x | x A x B ；對稱差對稱差 A B = (A B) (B A) = (A B) (A B) ；絕對補絕對補 A = E A 。 A B A A B A A B A B A-B A B A A B B C A B (A B)-C集合運算對應的文氏圖表示集合運算對應的文氏圖表示 并和交運算可以推廣到有窮個集合上，即并和交運算可以推廣到有窮個集合上，即 A1 A2 An= x | x A1 x A2 x An A

21、1 A2 An= x | x A1 x A2 x An某些重要結果：某些重要結果： A B A A B A B= A B= A B=A集合的廣義交和廣義并集合的廣義交和廣義并 設設S為集合，為集合，S的元素的元素構成的集合稱的元素的元素構成的集合稱為為S的的廣義并廣義并，記為，記為 S，其中，其中 S=xz(z S x z； 設設S非空集合，非空集合，S的元素的公共元素構成的的元素的公共元素構成的集合稱為集合稱為S的廣義交，記為的廣義交，記為 S，其中，其中 S=xz(z Sx z。說明：說明： （1 1）規(guī)定）規(guī)定 = = ， 無意義。無意義。 （2 2）若）若 ，則由定義不難證明，則由定義

22、不難證明 S=S= S=S=（3 3）并運算和廣義并運算的運算符相同，但前者是二元運算，）并運算和廣義并運算的運算符相同，但前者是二元運算，后者是一元運算，因此在運算過程中不會對后者是一元運算，因此在運算過程中不會對 產生誤解。產生誤解。123,nSS SSS123nSSSS123nSSSS 例：例：設集合設集合A=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ōu)先于優(yōu)先于 二元

23、運算符(差集,并集,交集,對稱差,笛卡兒積)； 二元運算符優(yōu)先于優(yōu)先于集合關系符(, , ) 。此外,許多集合表達式里還使用到聯(lián)結詞,和邏輯關系符以及括號,我們規(guī)定:(1) 集合運算優(yōu)先于邏輯運算；(2) 括號內優(yōu)先于括號外；(3) 同一括號內,同一優(yōu)先級按從左至右運算。集合運算律集合運算律冪等律冪等律：AAA； AAA同一律同一律：AA； AE=A零零 律：律：AE=E ； A結合律：結合律：(AB)CA(BC)； (AB)CA(BC)交換律交換律：ABBA； ABBA分配律分配律：A（BC）（）（AB）(AC)； A(BC)=(AB)(AC)排中律：排中律：矛盾律：矛盾律：吸收律吸收律：A

24、（AB）A A(AB)A摩根律：摩根律：雙重否定律雙重否定律：AAEAAABABABAB()()()ABCABAC()()()ABCABACAA AB A , AB B ； A AB , B AB ； A-B A ，A-B=AB； AB=BA BAB=A A-B= ； A B=B A； (A B) C=A ( B C) A =A； A A = ； A B=A CB=C。集合集合等式的證明，可采用命題邏輯的等值式證明，等式的證明，可采用命題邏輯的等值式證明，其基本思想是其基本思想是互為子集互為子集： 欲證欲證:A=B 即證即證:即證即證:對任意的對任意的 x , ，當上述過程可逆時，可以合并為當

25、上述過程可逆時，可以合并為對任意的對任意的x, ABBAxAxBxBxAxAxB 集合相等的證明方法集合相等的證明方法例：例： 證明下列集合恒等式。證明下列集合恒等式。（1 1）AA（BCBC）（）（ABAB）(AC)(AC)（2 2）（3 3）證明：證明：(1) (1) 對任意的對任意的x xA (BC)A(BC)A()(A)(A)()()xxxxxBxCxxBxxCxABxACxABACABAB()()()ABCABAC(2) 對任意的對任意的xBA()xABxAxxxBxAB(3) 對任意的對任意的x()()()()()()()()()()()xABCxAxBCxAxBCxAxBxCxA

26、xBxCxAxBxAxCxABxACxABAC 例例3.3.2 證明：（證明：（1） （2）A B=（AB）-（AB）ABABAB()()()EABEAEBAB證明證明：(1)(2) AB=（A-B）（B-A）()()()()()()()()()()ABBAABAABBBAABABABAB例例 證明證明(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)例例

27、證明證明證明：證明：(1)必要性必要性：對任意的：對任意的X,因此，因此， 。(2)充分性充分性：對任意的：對任意的x，因此因此 ，結論得證。，結論得證。( )( )ABP AP B( )( )xP AxAxBxP B( )( )P AP B ( ) ( ) xAxAxP AxP BxBxBAB例例 求在求在1和和1000之間不能被之間不能被5或或6，也不能被，也不能被8整整除的數(shù)的個數(shù)解：設除的數(shù)的個數(shù)解：設1到到1000之間的整數(shù)構成全之間的整數(shù)構成全集集E，A，B，C分別表示其中可被分別表示其中可被5，6或或8整除整除的數(shù)的集合。的數(shù)的集合。 解：解：在在ABC中的數(shù)一定可被中的數(shù)一定可

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

29、= 1000/5 =200； |B|= 1000/6 =133； |C|= 1000/8 =125； |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元素數(shù)是元素數(shù)是1211121( 1)mmiiiji

30、ij mmijkmij k mAAASAAAAAAAAA mmkjikjijijimiimiiAAAAAAAAAA21111) 1(推論推論 設設A1,A2,An是是n個集合，則個集合，則 例例 某班有某班有2525個學生，其中個學生，其中1414人會打籃球，人會打籃球，1212人人會打排球，會打排球，6 6人會打籃球和排球，人會打籃球和排球，5 5人會打籃球人會打籃球和網球，還有和網球，還有2 2人會打這三種球。而人會打這三種球。而6 6個會打網個會打網球的人都會打另外一種球球的人都會打另外一種球( (指籃球或排球指籃球或排球) )，求，求不會打這三種球的人數(shù)。不會打這三種球的人數(shù)。解：解：

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

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

33、學”關系；關系；“朋友朋友”關系；關系；“師生師生”關系；關系；“上上下級下級”關系；關系；“父子父子”關系；兩個數(shù)之間有關系；兩個數(shù)之間有“大于大于”關系；關系；“等于等于”關系和關系和“小于小于”關系；兩個變量之間關系；兩個變量之間有一定的有一定的“函數(shù)函數(shù)”關系；計算機內兩電路間有導線關系；計算機內兩電路間有導線“連接連接”關系；程序間有關系；程序間有“調用調用”關系等等。所以對關系等等。所以對關系進行深刻的研究，對數(shù)學與計算機科學都有很大關系進行深刻的研究，對數(shù)學與計算機科學都有很大的用處。的用處。集合的笛卡爾積與二元關系集合的笛卡爾積與二元關系 由兩個元素由兩個元素x,y（允許（允許

34、x=y）按一定順序排列成）按一定順序排列成的二元組叫做一個的二元組叫做一個有序對或序偶有序對或序偶，記作，記作,其中其中x是是它的它的第一元素第一元素，y是它的是它的第二元素第二元素。有序對有序對具有以下性質：具有以下性質：(1) 當當xy時，時， (2) = x=w y=v例例：已知：已知 = ，求，求 x 和和 y。解：由有序對相等的充要條件得解：由有序對相等的充要條件得 x+3 = y+7 y-2 = 3y-x 解得解得 x = 6, y = 2。一個一個有序有序n元組元組 (n3)是一個有序對，其中第一個元素是一個有序對，其中第一個元素是一個有序是一個有序n-1元組，一個有序元組，一個

35、有序n元組記作元組記作,即即 = , xn 例：例：空間直角坐標系中點的坐標空間直角坐標系中點的坐標 ,等都是有序等都是有序3元組。元組。 n維空間中點的坐標或維空間中點的坐標或n維向量都是有序維向量都是有序n元組。元組。形式上也可以把形式上也可以把看成有序看成有序1元組。元組。 設設A，B為集合，用為集合，用A中元素為第一元素，中元素為第一元素，B中中元素為第二元素構成有序對。所有這樣的有序對元素為第二元素構成有序對。所有這樣的有序對組成的集合叫做組成的集合叫做A和和B的的笛卡兒積笛卡兒積，記作，記作AB。 笛卡兒積的符號化表示為：笛卡兒積的符號化表示為： AB=|x A yB例例：若：若A

36、=1,2, B=a,b,c,則則AB=, , , , , BA=, , , , , 易知：若易知：若|A|=m,(即集合即集合A的元素的個數(shù)的元素的個數(shù)),|B|=n,則則| AB|= |BA|= m n 有序對就是有順序的數(shù)組有序對就是有順序的數(shù)組，如，如，x,y 的的位置是確定的，不能隨意放置。位置是確定的，不能隨意放置。 注意注意：有序對：有序對 ，以，以a,b為元素的集合為元素的集合a,b=b,a；有序對；有序對(a,a)有意義，而集合有意義，而集合a,a不成立。不成立。 笛卡兒積是一種集合合成的方法笛卡兒積是一種集合合成的方法，把集合，把集合A，B合合成集合成集合AB，規(guī)定，規(guī)定AB

37、 x A, y B。由于有序對由于有序對中中x,y的位置是確定的，因此的位置是確定的，因此AB的的記法也是確定的，不能寫成記法也是確定的，不能寫成BA。笛卡兒積也可以多個集合合成笛卡兒積也可以多個集合合成 A1A2An。笛卡兒積的運算性質。笛卡兒積的運算性質。笛卡兒積的性質：笛卡兒積的性質：1、對任意集合、對任意集合A，根據(jù)定義有，根據(jù)定義有 A = A= 2、一般來說，笛卡兒積不滿足交換律，即、一般來說，笛卡兒積不滿足交換律，即 ABBA （當（當A B B 、A 時）時）3、笛卡兒積不滿足結合律，即、笛卡兒積不滿足結合律，即 (AB) CA(B C) （當（當ABC時）時）4、笛卡兒積運算

38、對并和交運算滿足分配律，即、笛卡兒積運算對并和交運算滿足分配律，即 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)例例：設：設A， C， B， D為任意集合，為任意集合， 判斷以下命題是否為真，并說明理由。判斷以下命題是否為真，并說

39、明理由。(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) 為真。當為真。當 A= A= 時成立。時成立。 設設A1,A2,An,是集合是集合(n2),它們的它們的n階笛卡兒積階笛卡兒積記作記作A1A2An ，其中，其中 A1A2An= | x1 A1x2 A2xn

40、 An 。 當當A1=A2=An=A時時, 將起將起n階笛卡兒積記作階笛卡兒積記作An例例，A= a ,b , 則：則： A3=AAA=a,ba,ba,b =, , , 。例例：設集合：設集合 A=a,b,B=1,2,3,C=d, 求求ABC，BA。解：解： 先計算先計算AB,ABC ,d, BA, 。例：例： 設集合設集合A1,2,求求AP(A)。解：解： P(A)=,1,2,1,2AP(A)1,2,1,2,1,2=, , , 如果一個集合符合以下條件之一：如果一個集合符合以下條件之一：(1) 集合非空，且它的元素都是有序對集合非空，且它的元素都是有序對(2) 集合是空集集合是空集 則稱該集

41、合為一個則稱該集合為一個二元關系二元關系，記作，記作R，簡稱為關系。，簡稱為關系。 對于二元關系對于二元關系R，若，若 R,可記作可記作xRy;如果如果 R, 則記作則記作xRy。例例：R1=, aR1b, 1R12。二元關系二元關系是兩種客體之間的聯(lián)系，例如某學生是兩種客體之間的聯(lián)系，例如某學生學習語文、數(shù)學、外語，表示為：學習語文、數(shù)學、外語，表示為： A A 語文語文, , 數(shù)學數(shù)學, , 外語外語 功課的成績分四個等級，記作功課的成績分四個等級，記作B BAA，B B，C C，DD于是該生成績的全部可能為于是該生成績的全部可能為A AB BA AB B ,D, ,D, ,D而該生的實際

42、成績而該生的實際成績 P P,DP P是是A AB B的一個子集，它表示了功課與其成績的一種關系。的一個子集，它表示了功課與其成績的一種關系。 由此可見：由此可見：兩個集合之間的二元關系，實際上就是兩個兩個集合之間的二元關系，實際上就是兩個元素之間的某種相關性。元素之間的某種相關性。 設設A，B為集合，為集合，AB的任何子集所定義的的任何子集所定義的二元關系叫做從二元關系叫做從A到到B的的二元關系二元關系； 特別當特別當A=B時則叫做時則叫做A上的上的二元關系二元關系。 例：例：若若A=a,b，B=1,2,3，則，則 A B= , 令令 R1= , R2=, , R3=。因為因為R1 A B，

43、 R2 A B， R3 A B，所以，所以R1, R2和和 R3均是由均是由A到到B的二元關系。的二元關系。又例：若又例：若A=a,b，B=1,2,3，則，則 BA= , 令令 R4= , R5=, , 因為因為R4 BA， R5 BA，所以所以R4和和 R5均是由均是由B到到A的關系。的關系。又又 BB=, , , 。令令 R6= ，, R7=, 因為因為R6 BB， R7 BB， 所以所以R6和和 R7均是集合均是集合B上上的關系。的關系。若集合若集合|A|=n,則集合則集合A上的二元關系有多少個？上的二元關系有多少個？答：答： |A|=n，則，則|A A|=n2, A A的任一個子集的任

44、一個子集就是就是A上的二元關系，即上的二元關系，即P(A)= 2n 個。個。 例例 A= 1,2 則則A A有有 2n 個不同的二元關系；個不同的二元關系； AA=1,21,2= ,。 AA的任一個子集就是的任一個子集就是A A的冪集，即的冪集，即P(A)P(A)= , , , , , , , , , , , , , , , , , , , , , , , ,三類特殊的關系三類特殊的關系空關系：空關系：對于任何集合對于任何集合A，空集，空集 是是A A的的子集，稱作子集，稱作A上的上的空關系；空關系；全關系：全關系：定義定義EA=|xA yA= AA為為全全域關系；域關系；恒等關系：恒等關系：

45、 定義定義IA=|xA 為為A上上恒等關系。恒等關系。 例：例：若若A=1,2,3，則，則 EA= , , IA =, 。例：例：設設A=1,2,3,4，請表示下列關系。，請表示下列關系。(1) R= |x是是y的倍數(shù)的倍數(shù)(2) R= |(x-y)2 A(3) R= |x除除y是素數(shù)是素數(shù)(4) R= |xy解：解：(1) R = , , , , ,； (2) R = , , ,； (3) R = ,； (4) R= , , 關系表示法關系表示法有窮集合上的二元關系的三種表示方法：有窮集合上的二元關系的三種表示方法：n 集合表示法集合表示法 （前已使用）（前已使用）n 關系矩陣法關系矩陣法n

46、 關系圖關系圖 關系矩陣是表示關系的另一種有效的方法，其關系矩陣是表示關系的另一種有效的方法，其優(yōu)點是可以利用矩陣作為研究關系的手段，而且這優(yōu)點是可以利用矩陣作為研究關系的手段，而且這樣做便于計算機進行處理。樣做便于計算機進行處理。 設設R：AB，A和和B都是有限集，且都是有限集，且 |A|=n, |B|=m, A , B中的元素已按一定的次序排列若中的元素已按一定的次序排列若A=x1,x2,xn ,B= y1,y2,ym 且且R A B,若若則稱矩陣則稱矩陣為為R的的關系矩陣關系矩陣關系矩陣法關系矩陣法1,0,ijijijx yRrx yR 0 1 1 1MR= 0 0 1 1 0 0 0

47、1 0 0 0 0例例 A=1,2,3,4, R為為A上的小于關系，上的小于關系，則則R=, , , R的關系矩陣為：的關系矩陣為：1 2 3 41 2 3 41 2 3 41 2 3 4例例: 設集合設集合A2,3,4, B=8,9,12,14。 R是由是由A到到B的二元關系，定義：的二元關系，定義：R= | a整除整除b寫出寫出R的表達式和關系矩陣。的表達式和關系矩陣。 解解：R=, R的關系矩陣：的關系矩陣： 101 101101010RM關系圖關系圖 關系圖是表示關系的一種直觀形象的方法，設關系圖是表示關系的一種直觀形象的方法，設R：AB，A和和B都是有限集，都是有限集， A=x1,x

48、2,xn , B= y1,y2,ym 關系關系R的有序對的有序對 可用圖中從結點可用圖中從結點xi 到到y(tǒng)j 的有向的有向邊表示，這樣即可將關系用圖表示之。邊表示，這樣即可將關系用圖表示之。例例 設設 R: AB，A=x1,x2, x3, x4 , B= y1,y2,y3 R=, , ， R的關系如下圖所示的關系如下圖所示x1x2x3x4y1y2y3設設R是在是在A上的二元關系，上的二元關系， A=x1,x2,xn 關系關系R的有序的有序偶偶 可用圖中從結點可用圖中從結點xi 到到xj 的有向邊表示，這樣的有向邊表示，這樣即可將關系用圖表示之。即可將關系用圖表示之。 例例 ：設設 R: AA，

49、A= a,b, c, d R=, , , R的關系如下圖所示：的關系如下圖所示：abcd 例：例： 設集合設集合A=a,b,c,d,R是是A上的關系上的關系R=,試以試以關系矩陣和關系圖來表示關系關系矩陣和關系圖來表示關系R。解：解： （1）關系矩陣為：）關系矩陣為： 1110001000010001Mbcda（2）關系圖為：）關系圖為： 關系的運算關系的運算（1）R中所有的有序對的第一元素構成的集合稱為中所有的有序對的第一元素構成的集合稱為R的的定義域定義域，記作，記作domR。 domR=x| y( R（2）R中所有的有序對的第二元素構成的集合稱為中所有的有序對的第二元素構成的集合稱為R的

50、的值域值域，記作，記作ranR。 ranR=y| x R（3）R的定義域和值域的并集稱為的定義域和值域的并集稱為R的的域域，記作，記作fldR。 fldR=domR ranR例：例： 設設R=,則則 domR=1，2，3 ranR=1，2，3，4 fldR=1，2，3，4限制關系限制關系設設R為二元關系，為二元關系，A是集合是集合（1）R在在A上的限制，記作上的限制，記作R A,其中其中 R A=|xRy x A（2）A在在R下的象，記作下的象，記作RA，其中，其中 RA=ran(R A)例例：設集合：設集合A=1,2,3,4,R是是A上的關系上的關系R=,集合集合B=1,2,4,試求試求R

51、B及及RB。解：解：R B=,； RB=1，3，4。逆運算逆運算設設R為二元關系，稱為二元關系，稱 為為R的逆關系，其中的逆關系，其中 =| R 定理定理4.1 設設F是任意關系，則是任意關系，則（1） （2）1R1R11()FF證明：證明：（1）對任意的）對任意的11domFranF,ranFdomF111()FFF（2）對任意的）對任意的y11(,)(,)ydomFxy xFxx yFyranF 對任意的對任意的x11(,)(,)xranFyy xFyx yFxdomF 復合運算復合運算 設設F,G為二元關系為二元關系G對對F的右復合記作的右復合記作F?G,其中其中F?G=| t( F G

52、。說明：說明：（1）本書采用右復合的規(guī)則，而有的教材采用左復合）本書采用右復合的規(guī)則，而有的教材采用左復合規(guī)則，兩者都可行，只是需要注意它們的區(qū)別，從變換的規(guī)則，兩者都可行，只是需要注意它們的區(qū)別，從變換的角度來說，角度來說，G對對F的右復合是先的右復合是先F變換后變換后G變換，而變換，而G對對F的左復合是先的左復合是先G變換后變換后F變換。變換。（2）一般來說，并沒有）一般來說，并沒有F?G等于等于G?F，請讀者仔細注意，請讀者仔細注意其區(qū)別。其區(qū)別。例：例：設設F=,G=,則求則求F?F，G?G，F(xiàn)?G和和G?F。 解：解：F?F= ，G?G= F?G= G?F=。例：例：設有集合設有集合

53、 A=4,5,8,15, B=3,4,5,9,11C=1,6,8,13, F 是由是由 A 到到 B 的關系的關系, G 是由是由 B 到到 C 的的關系關系,分別定義為分別定義為 F=| |b-a|=1 G=| |b-c|=2或或|b-c|=4求合成關系求合成關系G F和和F G 解：解： 先求先求G F, 由題意知由題意知 F=, ,； G=, ,； G F= ,。 定理：定理： 設設F、G、H是任意關系是任意關系, 則則 (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

54、F-1證明證明: (1) 任取任取,由逆的定義有由逆的定義有 (F-1)-1 F-1 F (F-1) -1 = F (2) 任取任取x, xran 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 定理：定理： 設設F、G、H是任意關系是任

55、意關系,則則 (1) F (GH)= F G F H (2) (GH) F= G F H F (3) F (GH) F G F H (4) (GH) 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本定理對有限個關系的并和交都成立。本定理對有限個關系的并和交都成立。R (R1R2 Rn

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

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

58、1=Rm(RnR1)= (RmRn )R1= Rm+nR1= Rm+n+1= Rm+(n+1) 。(2) 任給任給m，對，對n作歸納法。作歸納法。 n=0時，時，(Rm)0= R0 = Rm 0。 假設假設(Rm)n=Rmn。那么。那么(Rm)n+1= (Rm)n Rm = Rmn Rm = Rmn+m= Rm(n+1) 例例: 已知集合已知集合A=a,b,c,d,A上的關系上的關系R=,，求，求 。解：解：法一法一：由復合定義知：由復合定義知2RR R32RRR=,=,23,RR 法二法二：關系：關系R R矩陣為矩陣為0100101000010000M2M010010100001000001

59、0010100001000031010010100000000M101001010000000001001010000100000101101000000000= =法三：法三：R的關系圖為的關系圖為bcda2R的關系圖為的關系圖為 bcda3R的關系圖為的關系圖為bcda定理定理 A為n元集,R為A上的關系,則存在自然數(shù)s和t， 使得Rs=Rt證明：證明：因為A為n元集，所以集合A上的關系為有限N= 個，而關系序列存在無限多個關系，故存在自然數(shù)s和t，使得Rs=Rt.。22n0121,NNRR RRR 設設 R 是是 A 上的關系，上的關系，R 的性質主要有以下的性質主要有以下 5 種種:(

60、1) 自反性：自反性：若若 x(x A R),則稱則稱 R 在在 A 上是上是自反自反的。的。 也就是說，對也就是說，對R A A，若，若A中每個中每個x，都有，都有xRx，則，則稱稱R是自反的，即是自反的，即A上關系上關系R是自反的是自反的x(x AxRx)。 該定義表明了，在自反的關系該定義表明了，在自反的關系R中，除其它有序對中，除其它有序對外，必須包括有全部由每個外，必須包括有全部由每個x A所組成的元素相同的有所組成的元素相同的有序對。序對。 例如：設例如：設A=1, 2, 3, R 是是 A 上的關系，上的關系， R=, , 則則 R 是自反的是自反的關系的性質關系的性質(2) 反