離散數(shù)學(xué)第六章)

1、,第二部分 集合代數(shù),6.1 集合的基本概念6.2 集合的運算6.3 集合恒等式,,第二部分 集合代數(shù),掌握：集合的概念，集合的表示方法，元素與集合的關(guān)系，集合與集合的關(guān)系，冪集，集合的交、并、相對補、絕對補、對稱差運算,,§6.1 集合的基本概念,1、集合與元素（1）集合：具有某種特殊性質(zhì)的客體的聚合。討論：①一些不同的確定的對象之全體。②客體：是泛指一切，可以是具體的、抽象的③元素（成員）：屬于任何集合的任何

2、客體。④符號：用大寫英文字母A，B….表示集合，用小寫英文字母a，b….或其它符號表示元素。⑤元素與集合間的關(guān)系： a是集合S中的元素，則寫成a? S ；b不是集S合中的元素，則寫成b? S 。,,§6.1 集合的基本概念,(2)本書中常用集合符: Im(m≥1) 有限個正數(shù)的集合{1,2,3……m} Nm(m≥0) 有限個自然數(shù)的集合{0,1,2……m} 以上是有限集合,下面是無限集合：N

3、 然數(shù)集合 {0,1,2……}I+ 正整數(shù)集合 {1,2,3……}I 整數(shù)集合 {……-1,0,1,2……}P 素數(shù)集合 {大于1的正整數(shù)，只能被1和自己整除}Q 有理數(shù)集合 {i/j. i、j均為整數(shù)且j≠0}R 實數(shù)集合 {有理數(shù)、無理數(shù)}C 復(fù)數(shù)集合 {a+bi，a、b可為實數(shù) i= √-1 },,§6.1 集合的基本概念,(3)集合的表示方法:(a)枚舉法 (

4、列舉法) 把集合的元素列于花括號內(nèi)。 例： 命題的真假值組成的集合：S={T,F} 自然數(shù)0,1,2,3,4五個元素的集合：P={0,1,2,3,4}(b)謂詞公式描述法 所有集合均可用謂詞公式來表示：S={x | p(x) },,§6.1 集合的基本概念,例:大于10的整數(shù)的集合：S1={x | x? I ∧ x>10} 偶整數(shù)集合：S2={x | ?y (y ?I ∧

5、 x=2y)} 有限個元素集合： S3={1,2,3,4,5}={x | x ?I ∧ (1 ≤ x ≤ 5) } S4={F,T}={x | x=T ∨ x=F} S5={1,4}={ x | (x²-5x+4=0) } (c)同一集合可以用多種不同的形式表示。(d)集合也可作為某一集合的元素。 例：S={a,{1,2},p,{q}},,§6.1 集合的

6、基本概念,(4)三個特殊集合 全集：如果一個集合包含了所要討論的每一個集 合，則稱該集合為全集合，用E表示。 E={x | p(x)∨? p(x)} p(x)為任何謂詞公式 空集：不擁有任何元素的集合稱為空集（或稱零 集），用?表示, ?={x | p(x) ∧ ? p(x) }={ } 注意,? ≠ {?} 前者是

7、空集，是沒有元素的集合； 后者是以?作為元素的集合。,,§6.1 集合的基本概念,集合族：集合中的元素均為集合，稱這樣的集合為集合族。例A={{a}，，{c、d}}2、集合之間的關(guān)系 相等：給定二個集合A和B，當(dāng)且僅當(dāng)A和B具有同樣的元素（成員），則A和B相等，記作A=B, 并規(guī)定 ：（A=B）??x (x? A ? x? B) 例：{a, b, c}={

8、b, a, a, c, c} 例：設(shè)P={{1,2},4}，Q={1,2,4}，則P?Q,,§6.1 集合的基本概念,包含：設(shè)A、B是任意二個集合，如果集合A的 每 一個元素都是B的一個元素，則稱A 是B的子集，或者說A包含于B，或者說B 包含A ，記作A?B，或者B?A。 并規(guī)定： A?B?B?A??x(x?

9、 A → x ?B) 例：A1={1,2,3} A2={0} A3={1,2,3,0} B={1,2,3,0} 則A1、A2、A3均為B的子集合，并記為 A1?B，A2?B，A3?B,,§6.1 集合的基本概念,集合的包含關(guān)系具有如下幾條性質(zhì)：,（1）對任意集合A， ；,（2）對任意集合A， ；,（3）對任意集合A、B、C，若

10、 ， ，則 。,,§6.1 集合的基本概念,真包含:設(shè)A、B是任意二個集合，若A?B且A≠B， 則稱 A是B的真子集，記作A?B（A真包含 于B）,并規(guī)定：A?B?（A?B ∧ A≠B） 注意區(qū)分“?”和“?”的關(guān)系： “?”關(guān)系是指集合和該集合中元素間的關(guān)系 例：S={a,,c} 則a? S，

11、?S，c? S 而“?”關(guān)系是指二個集合之間的關(guān)系。 例：S1={a, b} S2={a,b,1,2} 則S1? S2 若A不包含于B，則也可表示成A?B,,§6.1 集合的基本概念,[定理]設(shè)有空集?和任一集合A，則??A證明：設(shè)x?A，要證明??A，只要證：（?x）(x??→ x?A)為“T”∵?中沒有元素，∴x??為假，（?x）（x

12、??→ x?A）為“T” [推論] ?是唯一的。證明：設(shè)有二個空集合?1和?2 ∵?是任何集合的子集∴（?1? ?2∧?2 ??1） ?(?1=?2),,§6.1 集合的基本概念,3、冪集 （1）子集： 例：S1={a} 則子集為?，{a} S2={1，{2}} 則子集為?，{1}，{{2}}，{1，{2}} S3=? 則子集有?（而不是{?}） 由此可見,給定一個集合

13、S,則?和S一定是S的子集,,§6.1 集合的基本概念,冪集:設(shè)A是集合，A的所有子集（作為元素）的集 合稱為A的冪集,記作ρ(A)或2A ,且有： ρ(A)(=2A)={x | x ?A} 例： 若A1=?，則ρ(A1)={?} 若A2={a}，則ρ(A2)={?，{a}} 若A3={1，2},則ρ(A3

14、)={?，{1}，{2}，{1，2}},,§6.2 集合的運算,1.交集（交運算）交集:二個集合A和B的交集A∩B是由A和B所共有的 全部元素構(gòu)成的集合，即： A∩B={x | x? A∧ x ?B} 例：A={a，b} B={a，c} A∩B={a}[定理]集合的相交運算是可交換的和可結(jié)合的，即 對于任何集合A，B，C有

15、 A∩B=B∩A，（A∩B）∩C=A∩（B∩C）證明：設(shè)x是A∩B中任一元素 則x? A∩B?x? {x | x? A ∧x? B}?x ?{x | x? B ∧x? A}?x? B∩A ∴A∩B=B∩A,§6.2 集合的運算,[定理]設(shè)A是E的任一子集，則有 （1）A∩A=A （2）A∩?=? （3）A∩E=A不相交:A、B是二個集合，若A∩B=?，則稱

16、A和B 是不相交的，或者說A和B沒有相同的元素。,§6.2 集合的運算,2.并集（并運算） [定義]A、B是任意二個集合，A和B的并集A∪B是 由A和B的所有元素構(gòu)成的集合，即： A∪B={x│ x?A∨x?B}。例：A={a, b, c} B={1,2,3} 則 A∪B={a,b,c,1,2,3} [定理]集合的并

17、運算是可交換的和可結(jié)合的，即對 任何A，B，C,有 A∪B=B∪A和（A∪B）∪C=A∪（B∪C）,§6.2 集合的運算,[定理]集合的并和交運算，每一個對另一個都是可 分配的。即： (1)A∪（B∩C）=（A∪B）∩（A∪C） (2)A∩（B∪C）=（A∩B）∪（A∩C）,§6.2 集合的運算,[定理]設(shè)A、B、

18、C是全集E的任意子集，則有： (1)A∪A=A (2)A∪?=A (3)A∪E=E,,§6.2 集合的運算,3.相對補集：[定義]設(shè)A和B是二個任意集合，B對A的相對補 集（A-B）是由A中且不屬于B的所有元素 組成的集合。即： A-B={x│x?A∧x?B}={x│x?A∧?x?B}例：設(shè)

19、A={0，1，2} B={2，3，4} 則 A-B={0,1} B-A={3，4}注意，A-B≠B-A。,,§6.2 集合的運算,[定理]設(shè)A，B，C，D是E的子集，則有： (1 )A-B?A， (2 )若A?B和C?D，則A∩C?B∩D， (3 )若A?B和C?D，則A∪C? B∪D， (4 ) 若A?A∪B，則 B?A∪

20、B (5 ) 若A∩B?A，則A∩B?B (6 ) 若A?B，則A∪B=B (7 ) 若A?B，則A∩B=A (8 )A-?=A (9 )A∩(B-A)=? (10)A∪(B-A)=A∪B,,§6.2 集合的運算,(11)A-（B∪C）=（A-B）∩（A-C） (12)A-（B∩C）=（A-B

21、）∪（A-C）,,§6.2 集合的運算,4、絕對補集（補運算 ）[定義]設(shè)E是全集，任一集合A對E的相對補集稱 為A的絕對補集（或稱補集）記作~A（或 ?A）。即： ~A=E-A={x| x?E∧x?A}={x| x?A}例：設(shè)E={a，b，c，d} A={a，b} 則?A={c，d},,§6.2 集合的運算,[定理]A是E的任一子集，

22、則有 (1)A∪?A=E (2)A∩?A=? [定理]設(shè)A、B是E的二個子集，當(dāng)且僅當(dāng) A∪B=E和A∩B=?才有B= ~A（或A= ~ B）證明： (ⅰ) 充分性：B= ~A ?（A∪B=E）∧（A∩B=?）∵B=~A ∴A∪B=A∪~A=E A∩B=A∩~A=?成立,,§6.2 集合的運算,(ⅱ)必要性： (A∪B=E)∧(A∩B=?)?B=?

23、A ∵B=E∩B=(A∪~A)∩B =(A∩B)∪(~A∩B) =?∪（~A∩B） =（~A∩A）∪（~A∩B） =~A∩（A∪B） =~A∩E=~A,,§6.2 集合的運算,補集的性質(zhì)：（1）~（~A）=A（2）~（A∪B）=~A∩~B（3）~（A∩B）=~A∪~B（4）~?=E（5）A-B=A∩~B 例：設(shè)A={2，5，6}，B={2，3，

24、4}，C={1，3，4}， E={1，2，3，4，5，6}則A-B={5，6}=A∩~B ={2，5，6}∩{1，5，6}={5，6},,§6.2 集合的運算,5、對稱差[定義]設(shè)A、B是任意二集合，A和B的對稱差記作 A⊕B。即： A⊕B=(A-B)∪(B-A)=(A∩~B)∪(B∩~A) 或者x?(A⊕B)?x?{x

25、 |x?A?x?B} 例：設(shè)A={2，5，6}，B={2，3，4} 則 A?B={3，4，5，6},,§6.2 集合的運算,對稱差的性質(zhì)：(1)A?B=B?A (可交換)(2)(A?B)?C=A?(B?C) (可結(jié)合)(3)A?B=(A-B)∪(B-A) =(A∩~B)∪(B∩~A)=(A∪B)∩(~A∪~B)(4)A?A=?(5)A??=A(6)~A?~B=(

26、~A∩~(~B))∪(~B∩~(~A)) =(~A∩B)∪(~B∩A)=(B-A)∪(A-B)=A?B(7)A∩(B?C)=(A∩B)?(A∩C) (∩對?可分配),,§6.2 集合的運算,文氏圖可以用來描述集合間的關(guān)系及其運算.在文氏圖中,全集用矩形表示,子集用圓形表示,陰影部分表示運算結(jié)果的集合.,6、文氏圖,,,§6.3 有窮集的計數(shù),加法原理中，S1, S2 , …, Sn

27、兩兩不相交，|S| = |S1| + |S2| + … + |Sn|若取消兩兩不相交的限制，該如何計算？考慮兩個集合的情況,|A∪B| = |A| + |B| － |A∩B|,,三個集合的情況,|A U B U C | = |A| + |B| + |C|－|A∩B|－|A∩C|－|B∩C| + |A∩B ∩C |,,A,B,C,,,§6.3 有窮集的計數(shù),,用數(shù)學(xué)歸納法證明 | S1∪S2∪…∪Sn |對n進(jìn)行歸

28、納基礎(chǔ)步：n=1,2時，根據(jù)上面的驗證，等式成立；歸納步：假設(shè)n=k (k≥1)時等式成立，則n=k+1時…………等式依然成立綜上，對任意自然數(shù)n ≥1，均有等式成立,§6.3 有窮集的計數(shù),第七章 二元關(guān)系7.1 有序?qū)εc笛卡爾積7.2 二元關(guān)系7.3 關(guān)系的運算7.4 關(guān)系的性質(zhì)7.5 關(guān)系的閉包7.6 等價關(guān)系與劃分7.7 偏序關(guān)系,,§7.1 有序?qū)εc笛卡爾積,1.序偶： [定義

29、]由二個具有給定次序的客體所組成的序列稱 為序偶。記作〈x，y〉例：X—Y二維平面上點的坐標(biāo)〈x，y〉就是序偶。說明：在序偶中二個元素要有確定的排列次序。即： 若a?b時，則〈a，b〉?〈b，a〉 若〈x，y〉=〈a，b〉?（x=a?y=b）,,§7.1 有序?qū)εc笛卡爾積,2.笛卡爾乘積[定義]設(shè)A，B為二個任意集合，若序偶的第一個成

30、員（左元素）是A的一個元素，序偶的第 二個成員（右元素）是B的一個元素，則所 有這樣的序偶的集合稱為A和B的笛卡爾乘積 記作：A?B={〈x，y〉|（x?A）?（y?B）}例：設(shè)A={1，2} B={a，b} 則A?B={,,,,,,} ∴A?B?B?A 即“?”是不滿足交換律。,,§7.1 有序?qū)εc笛卡爾積,例：設(shè)A={a，

31、b}，B={1，2}，C={z} 則 (A?B)?C={,,,}?{z} ={,,,} A? ( B?C ) ={a,b}?{〈1,z〉,〈2,z〉} ={>,>,>,>>} ∴（A?B）?C?A?（B?C）“?”不滿足結(jié)合律,,§7.1 有序?qū)εc笛卡爾積,[性質(zhì)]若A，B，C

32、是三個集合，則有： (1)A?（B?C）=（A?B）?（A?C） (2)A?（B?C）=（A?B）?（A?C） (3)（A?B）?C=（A?C）?（B?C） (4)（A?B）?C=（A?C）?（B?C）,,§7.1 有序?qū)εc笛卡爾積,證明：（2）設(shè)是A?(B?C)中的任一元素,則?A?（B?C）? ?{〈 x,y 〉|x?A?y?B?C} ? ?{|x?A?y

33、?B?y?C}? ?{|(x?A?y?B)?(x?A?y?C)} ? ?(A?B)?(A?C)即 A?(B?C)=(A?B)?(A?C),,§7.1 有序?qū)εc笛卡爾積,例：設(shè)A={1}，B={1，2}，C={2，3} 則A?（B?C） ={1}?{1，2，3} ={〈1，1〉，〈1，2〉，〈1，3〉} （A?B）?（A?C）={1}?{1，2}?{1}?{2，3}

34、 ={〈1，1〉，〈1，2〉，〈1，3〉} A?（B?C）={1}?{2}={〈1，2〉} （A?B）?（A?C） ={〈1,1〉,〈1，2〉}?{〈1,2〉,〈1,3〉} ={〈1，2〉},,§7.2 二元關(guān)系,序偶〈a，b〉實際上反映了二個元素之間的關(guān)系，關(guān)系反映了事物的結(jié)構(gòu)。1.關(guān)系：指事物之間（客體之間）的相互聯(lián)系

35、。日常生活中：父子關(guān)系，母子關(guān)系，兄弟關(guān)系等均為二個客體之間的關(guān)系。而祖孫關(guān)系是三個客體之間的關(guān)系（父子關(guān)系和父子關(guān)系的合成）。n元笛卡爾積A1×A2×??×An是n元關(guān)系。,,§7.2 二元關(guān)系,[定義]若若R ?A×B,則R是一個二元關(guān)系。 即：序偶作為元素的 任何集合都是一個二元關(guān)系。２．關(guān)系表示方法（1）枚舉法（直觀法、列舉法）設(shè)R表示二元關(guān)系，用 xRy表示特

36、定的序偶， 若 ，則也可寫成：x R y。,,,,,?,,§7.2 二元關(guān)系,例：二元關(guān)系定義如圖： 可寫成：由定義可見：關(guān)系是一個集合，∴定義集合的方法都可以來定義關(guān)系。（2）謂詞公式表示法前面講述，一個集合可用謂詞公式來表達(dá)，所以關(guān)系也可用謂詞公式來表達(dá)。,,§7.2 二元關(guān)系,例：實數(shù)集合R上的“>”

37、關(guān)系可表達(dá)為： 大于關(guān)系：“>”= 父子關(guān)系：“F”=（3）關(guān)系矩陣表示法 規(guī)定：(a)二元關(guān)系中的序偶中左元素表示行，右元素表示列；(b)若xiRyi，則在對應(yīng)位置記上“1”，否則為“0”。,,,,,,§7.2 二元關(guān)系,例1：設(shè)并定義為列出關(guān)系矩陣：,,,,3.關(guān)系圖表示法關(guān)系圖由結(jié)點和邊組成,例如， 例7中的 ， ,,A,B,,則 的

38、關(guān)系圖如下,,例如,的關(guān)系圖如下：,,二、特殊關(guān)系,,§7.3 關(guān)系的運算,顯然有,定義1：設(shè)R是由A到B的一個關(guān)系，R的定義域或前域記作domR，R的值域記作ranR，分別定義為：,1．定義域和值域,,例3:設(shè)A={1,2,3,4,5,6},B={a,b,c,d},R={,,,,},求domR,ranR.,解:domR={2,3,4,6},ranR={a,b,d},§7.3 關(guān)系的運算,,R={,,,,},R-1

39、={,,,,},討論定義：（1）只要將R中每一個序偶中的元素全部調(diào)換位置，就可得到R的逆關(guān)系 （2）關(guān)系矩陣為原始關(guān)系矩陣的轉(zhuǎn)置 （3）在R的關(guān)系圖中，只要把所有箭頭改換方向就可得到（自回路箭頭改變與否無關(guān)）,2．逆關(guān)系,§7.3 關(guān)系的運算,,定義3:設(shè)R1是由A到B的關(guān)系， R2是由B到C的關(guān)系，則R1和R2的復(fù)合關(guān)系是一個由A到C 的關(guān)系，用R1○R2 表示，定義為：當(dāng)且僅當(dāng)存在元素b，使得b? C時，有 aR1○

40、 R2c這種由R1和R2 求復(fù)合關(guān)系R1○R2的運算稱為關(guān)系的復(fù)合運算。 由定義可知:,3．復(fù)合關(guān)系,§7.3 關(guān)系的運算,于是復(fù)合關(guān)系,例2 設(shè) 是由 到 的關(guān) 系。 是由 B 到 的關(guān)系。 分別定義為：,,,2. A={1，2，3，4，5}，R，S是A上的二元關(guān)系R={，，}S={，，，},∴合成關(guān)系不滿足交換律，滿足結(jié)合

41、律。,§7.3 關(guān)系的運算,,關(guān)系是以序偶為元素的集合，故可對關(guān)系進(jìn)行集合的運算以產(chǎn)生新的關(guān)系。作為關(guān)系，絕對補運算是對全關(guān)系而言的。,4. 逆運算的性質(zhì),§7.3 關(guān)系的運算,,,,5. 復(fù)合運算的性質(zhì),定理2：設(shè)F,G,H是任意的關(guān)系，則(1)(F○G)○H= F ○ (G○ H)(2) (F○G)-1= G-1○F-1,定理3：設(shè)R為A上的關(guān)系，則R○IA)= IA○ R=R,§7.3 關(guān)系的運

42、算,,[定義]給定集合X，R是X中的二元關(guān)系，設(shè)n為自然數(shù)，則R的n次冪Rn定義為：,,,（1）,,（2）,,例：設(shè)R,S是,,中的二元關(guān)系，且,,則：,,§7.3 關(guān)系的運算,,,,,,,冪運算的求解：,①若R是列舉法表示，可進(jìn)行多次右復(fù)合；,例：設(shè)A={a，b，c，d}，R={，，，}，則R0， R2 ，R3，R4。,R0={，，，},R2={，，，},R3={，，，，},R4={，，，},,§7.3 關(guān)系的運算

43、,②若R用關(guān)系矩陣M表示，則Rn的關(guān)系矩陣是Mn；,③若R是用關(guān)系圖G表示的，則可由G得Rn的關(guān)系圖G’。G’與G的頂點集合相同，考察G中每個頂點x，若在G中從x出發(fā)經(jīng)過n步長的路徑到達(dá)頂點y，則在G’中加一條從x到y(tǒng)的邊。當(dāng)把所有頂點都考察完后，就得到G’。,§7.3 關(guān)系的運算,,定理10.冪運算滿足指數(shù)定律：Rn ? Rm=Rn+m （