離散數(shù)學(xué)高教版屈婉玲.ppt

CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 1 離散數(shù)學(xué) Discrete Mathematics CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 2 第六章 集合代數(shù) 6.1 集合的基本概念 6.2 集合的運(yùn)算 6.3 有窮集合的計(jì)數(shù) 6.4集合恒等式 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 3 1.集合 ：將一些事物匯集到一起組成的整體，其中每個(gè)事物稱(chēng)為這個(gè)集合 的元素。 注：如果 x是集合 A的元素，則記為 xA 。 集合的表示方法： 列元素法 和 謂詞表示法 列元素法 ：列出集合的所有元素或部分元素，可用于有限集和有一定 規(guī)律的無(wú)限集。如： A=a， b， ， z Z=0， -1， 1， -2， 2， D=a， a， a， b集合中的元素還可以是集合。 謂詞表示法 ：用謂詞來(lái)描述集合中元素的性質(zhì)。 如： B=x | x R (x-1=0) 描述法 =x | F(x) G(x) 謂詞描述法 設(shè) F(x):x R ,G(x):x-1=0 . 集合的性質(zhì)： （ 1）集合的元素是彼此不同的，相同的元素應(yīng)該認(rèn)為是同一個(gè)元素。 （ 2）集合的元素是無(wú)序的。如： 1， 2， 3=2， 3， 1 6.1 集合的基本概念 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 4 注：元素與集合的關(guān)系是屬于 和不屬于 。 本書(shū)規(guī)定 集合的元素都是集合 。 對(duì)任何集合 A，都有 AA . 2.子集合 (Def 6.1):若集合 B中的元素都在集合 A中，則稱(chēng) B是 A的 子集合 (簡(jiǎn) 稱(chēng)子集 )。這時(shí)也稱(chēng) B被 A包含，或 A包含 B。記為 B A。 如果 B不被 A包含 ，則記為 BA。 注： (1)包含的符號(hào)化： BAx(xBx A)。 (2)對(duì)任何集合 A， 都有 AA。 3.集合的相等 (Def6.2):如果 AB且 BA,則稱(chēng)集合 A與 B相等 ，記為 A=B。 注：相等的符號(hào)化： A=B AB BA。 4.真子集 (Def6.3):對(duì)符號(hào) A,B,若 BA且 BA, 則稱(chēng) B是 A的 真子集 ,記為 BA 。 如果 B不是 A的真子集，則記為 BA 。 注：真子集的符號(hào)化： BA (BA) (B A)。 6.1 集合的基本概念 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 5 5.空集 (Def6.4)：不含任何元素的集合稱(chēng)為 空集 ， 記為 注 : 1. 空集的符號(hào)化： =x|x x 。 2. Th6.1 空集是一切集合的子集 。 （ 證明見(jiàn)教材 P85） 。 3. Cor 空集是唯一的 。 （ 證明見(jiàn)教材 P85） 。 6.n元集 ：含有 n個(gè)元素的集合 。 它共有 2n個(gè)子集合 。 例 6.1 設(shè) A=1,2,3,求 A的所有子集合 。 7.集合 A的冪集 (Def6.5)：由 A的所有子集作為元素形成的集合 。 記為 P(A)或 2A 。 注：冪集的符號(hào)化： P(A)= B | B A。 續(xù)例 6.1 設(shè) A=1,2,3,求 P(A)。 8.全集 (Def6.6)：如果一個(gè)問(wèn)題中所涉及的集合都是某一集合的子集 ， 則稱(chēng)該集 合為 全集 。 全集一般記為 E。 注：不同問(wèn)題有不同的全集 ， 同一問(wèn)題也可以取不同的全集 。 一般 總是將全集取得盡可能小 ， 以便描述和處理問(wèn)題更加簡(jiǎn)便 。 6.1 集合的基本概念 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 6 例 ：求下列集合的冪集合 。 (1), (2) (3)1,2,2,1,1,2,1,1,2 6.1 集合的基本概念 解： (1) P(,)=, , ,. (2) P( )=P()= ,. (3) P(1,2,2,1,1,2,1,1,2)=P(1,2)= ,1,2. 例 ：判斷真?zhèn)?。 (1)xx (2)x x (3)x x ,x (4)xx ,x (5)xxx (6)若 x A , A P(B), 則 x P(B) (7)若 x A , A P(B), 則 x P(B) CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 7 一 . 集合的基本運(yùn)算 設(shè) A,B是集合 (def6.76.9) 1.A與 B的 并 ： A B = x | x A x B 2.A與 B的 交 ： AB = x | x A x B 3.A與 B的 差 (B對(duì) A的相對(duì)補(bǔ) )： A B = x | x A x B 4.A與 B的 對(duì)稱(chēng)差 ： A B=(A B) (BA)=(A B) (AB) 5.A的 補(bǔ)集 (或稱(chēng)絕對(duì)補(bǔ) )： A = E A = x | x E x A 注 : (1)“并 ” 和 “ 交 ” 運(yùn)算可以推廣到有 （ 無(wú) ） 限個(gè)集合： 21 1 21 nn n i i AxAxAxxAAAA 2121 1 nn n i i AxAxAxxAAAA 6.2 集合的運(yùn)算 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 8 集合運(yùn)算的進(jìn)一步推廣 定義 6.10 設(shè) A為集合， A的元素的元素構(gòu)成的集合稱(chēng)為 A的 廣義并 ，記為 A。 符號(hào)化 A=x| z ( z A x z ) 若 A=A1， A2， ， An 則 A=A1 A2 An。 定義 6.11 設(shè) A為 非空集合 ， A的所有元素的公共元素構(gòu)成的集合稱(chēng)為 A的 廣 義交 ，記為 A。 符號(hào)化 A=x| z（ z Ax z） 若 A=A1， A2， ， An 則 A=A1A2A n。 例 6.2設(shè) A=a, b, c, a, c, d, a, e, f, B=a, C=a, c, d. C= 解： A= a, b, c, d, e, f B= a C= a c, d = A= B= 不是集合 ac,d a a CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 9 例 6.3 設(shè) A=a, a, b,計(jì)算 : A, A, A ( A- A). 解： A=a,b A=a A=a b A=a A=ab A=a A ( A- A) =(ab) (a b)-a) =(ab) (b-a) =b 集合運(yùn)算的進(jìn)一步推廣 一類(lèi)運(yùn)算 ：廣義并，廣義交，冪集，絕對(duì)補(bǔ) 二類(lèi)運(yùn)算 ：并，交，相對(duì)補(bǔ)，對(duì)稱(chēng)差 集合運(yùn)算的優(yōu)先順序 : 一類(lèi)運(yùn)算優(yōu)于二類(lèi)運(yùn)算 ; 一類(lèi)運(yùn)算由右向左順序進(jìn)行 ; 二類(lèi)運(yùn)算由括號(hào)決定先后順序。 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 10 E E B E B E A B AB= A AB=A E A B A-B E A B A B E A B AB E A A A AB B (AB)-C A C 6.3 有窮集的計(jì)數(shù) 集合間的關(guān)系與運(yùn)算的表示：文氏圖 (Venn Diagrams) CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 11 例 6.4 對(duì) 24名會(huì)外國(guó)語(yǔ)的科技人員進(jìn)行掌握外語(yǔ)情況的調(diào)查，起統(tǒng)計(jì) 結(jié)果如下：會(huì)英、日、德和法語(yǔ)的人分別為 13， 5， 10和 9人。其中同 時(shí)會(huì)英語(yǔ)和日語(yǔ)的有 2人，會(huì)英、德和法語(yǔ)中任兩種語(yǔ)言的都是 4人。 已知會(huì)日語(yǔ)的人既不會(huì)法語(yǔ)也不會(huì)德語(yǔ)，分別求只會(huì)一種語(yǔ)言的人數(shù) 和會(huì)三種語(yǔ)言的人數(shù)。 解 令 A,B,C,D分別表示會(huì)英、法、德、日語(yǔ)的人的集合，根據(jù)題意得 文氏圖 . A D B C y1 5-2 2 y3 x 4-x y2 4-x 4-x 設(shè)同時(shí)會(huì)三種語(yǔ)言有 x人，只會(huì)英、法或德語(yǔ) 一種語(yǔ)言的分別是 y1,y2,y3人。則有 y1+2(4-x)+x+2=13 y2+2(4-x)+x=9 y3+2(4-x)+x=10 y1+y2+y2+3(4-x)+x=19 解方程組得 x=1,y1=4,y2=2,y3=3. 6.3 有窮集的計(jì)數(shù) CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 12 例 6.5 求 1到 1000之間 (包含 1和 1000在內(nèi) ), 既不能被 5和 6, 也不能 被 8整除的數(shù)有多少個(gè) . 解 設(shè) S = x | xZ 1 x 1000 A = x | xS x可被 5整除 B = x | xS x可被 6整除 C = x | xS x可被 8整除 |A| = int(1000/5) = 200 |B| = int(1000/6) = 166 |C| = int(1000/8) = 125 |AB| = int(1000/lcm(5,6) = 33 |AC| = int(1000/lcm(5,8) = 25 |BC| = int(1000/lcm(6,8) = 41 |ABC| = int(1000/lcm(5,6,8) = 8 1000-(200+100+33+67)=600 33 B A C 8 100 25 200 166 125 67 17 150 6.3 有窮集的計(jì)數(shù) CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 13 定理 6.2(包含排斥原理 ) 設(shè) S為有窮集 , P1, P2, , P m是 m個(gè)性質(zhì) .S中 的任何元素 x或者具有性質(zhì) Pi, 或者不具有性質(zhì) Pi(i=1.m), 兩種情況必 居其一 . 令 Ai表示 S中具有性質(zhì) Pi的元素構(gòu)成的子集 , 則 S中不具有性質(zhì) P1, P2, , P m的元素?cái)?shù)為 : | 21 mAAA |)1(| | 21 1 11 m m mkji kji mji ji m i i AAAAAA AAAS 6.3 有窮集的計(jì)數(shù) CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 14 推論 S中至少具有一條性質(zhì)的元素?cái)?shù)為 根據(jù)包含排斥原理 , 例 6.5中所求的元素?cái)?shù)為 : |ABC| = |S| - (|A|+|B|+|C|) + (|AB|+|AC|+|BC|) - |ABC| =1000-(200+166+125)+(33+25+41)-8 = 600 |)1(| | 21 1 1 11 m m mkji kji mji ji m i i AAAAAA AAA | 21 mAAA 6.3 有窮集的計(jì)數(shù) CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 15 應(yīng)用 歐拉函數(shù)的值 例 6.6 計(jì)算歐拉函數(shù)的值 (n). 歐拉函數(shù) ：小于 n 且與 n 互素的自然數(shù)的個(gè)數(shù) 解 n 的素因子分解式 : Ai = x | 0 xn1，且 pi 整除 x ， kkpppn . . .21 21 12 1 2 1 2 1 3 1 12 12 ( ) | . | ( . ) ( . ) . ( 1 ) . 1 1 1 ( 1 ) ( 1 ) . ( 1 ) k k k k k k k n A A A n n n n n n n p p p p p p p p p n p p p n p p p , 1 , 2 , . . . , ; , 1 , . . . . . .i i j ij nnA i k A A i j n p pp 12( ) | . . . | .kn A A A 則 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 16 例 6.7 錯(cuò)排問(wèn)題的計(jì)數(shù)問(wèn)題 有 n個(gè) 人在參加晚會(huì)時(shí)寄存了自己的帽子，可是保管人忘記放寄 存號(hào)，當(dāng)每個(gè)人領(lǐng)取帽子時(shí)，他只能隨機(jī)選擇一頂帽子給寄存人。 問(wèn)在 n個(gè)元素的全排列 n!種領(lǐng)取帽子的方式中有多少種方式使得每 個(gè)人都沒(méi)有領(lǐng)到自己的帽子？如果將這些人與他們的帽子分別標(biāo) 號(hào)為 1,2, ,n. 設(shè) j 領(lǐng)到的帽子標(biāo)號(hào)為 ij ， j=1,2, ,n. 那么這些人領(lǐng) 到的帽子可以用排列來(lái) i1 i2 in表示，其中每個(gè)人都沒(méi)有領(lǐng)到自己 帽子的 排列 為 i1 i2 in 使得 ij j ， j=1,2, ,n. 稱(chēng)這種排列為錯(cuò)位排 列，錯(cuò)位排列數(shù)記作 Dn , 證明 1 1 1! 1 ( 1 ) . 1 ! 2 ! ! n nDn n 證 設(shè) S為 1,2, ,n的排列的集合 , Pi 是其中 i處在排列中第 i位的性 質(zhì) , Ai 是 S中具有性質(zhì) Pi 的排列的集合 , i=1,2, ,n. 那么錯(cuò)位排列數(shù) Dn 就是 S中不具有以上任何一條性質(zhì)的排列數(shù)。 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 17 ( 2 ) ! 1ijA A n i j n 例 6.7 錯(cuò)排問(wèn)題的計(jì)數(shù)問(wèn)題 那么 ( 3 ) ! 1i j kA A A n i k j n ( 1 ) ! 1iA n i n 12 . . . ( ) ! 0 ! 1nA A A n n 12 . . ! ( 1 ) ! ( 2 ) ! ( 1 ) 0 ! 12 1 1 1 ! 1 ( 1 ) ) 1 ! 2 ! ! n nn n n n n DA n n A A n n n n 故 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 18 設(shè) A,B,C是集合，則下列運(yùn)算律成立： 1. 冪等律： A A=A, AA=A 2. 結(jié)合律： (A B) C=A (B C), (AB)C =A(BC) 3. 交換律： A B=B A, AB=BA 4. 分配律： A (BC)=(A B)(A C), A(B C)=(AB) (AC) 5. 同一律： A = A, AE = A 6. 零律： A E = E, A = 7. 排中律： A A = E 8. 矛盾律： A A = 9. 吸收律： A (AB)=A, A(A B)=A 10. 德摩根律： A(B C)=(AB)(AC), A(BC)=(AB) (AC) (B C)= B C, (BC)= B C =E, E= 11.雙重否定律： ( A)=A 6.4 集合恒等式 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 19 其它重要運(yùn)算性質(zhì) ： 1.AB A, AB B 2. A A B , B A B 3. A B A 4. A B = A B 5. A B=B AB AB=A A B= 6. AB = BA 7. (AB) C = A(BC) 8. A = A 9. A A= 10. A B = AC B=C 6.4 集合恒等式 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 20 例 6.8 證明 A(B C)=(A B) (A C) 證：對(duì)任意的 x xA (B C) xA x(B C) xA xB xC (xA xB) (xA xC) x(A B) x(A C) x(A B) (A C) A (B C)=(A B) (A C) 證明集合恒等式的方法 ：欲證 P=Q 1.利用命題演算方法證明 PQ 且 QP。即證 xP xQ 且 xQ xP 2.直接利用運(yùn)算律和已知的集合恒等式做恒等變形 。 6.4 集合恒等式 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 21 例 6.9 證明 A E=A 證：對(duì)任意 x, xA E xA xE xA. 故 A E=A 例 6.10 證明 A (A B)=A 證： A (A B)= (A E) (A B) (同一律 ) = A (E B) （ 分配律 ） = A E （ 零律 ） = A （ 同一律 ） 6.4 集合恒等式 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 22 例 6.11 證明 A B= A B 證：對(duì)任意 x x(A B) xA xB xA x B x(A B) A B=A B 例 6.12 證明 (A B) B = A B 證 ： (AB) B = (A B) B = (A B)( B B) = (A B) E = A B 6.4 集合恒等式 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 23 例 6.13 證明 A B=B AB AB =A AB = 證明 :(1)先證 A B=B AB 對(duì) x, xA xA xB x(A B) xB, ( A B=B) AB (2) 再證 ABAB=A 顯然 ABA ， 下面只需證 AAB 對(duì) x， xA xA xA xA xB x(AB). ( AB) AB=A (3)下證 AB=A A B= A B = A B = (AB) B = A(B B)= A (4)最后證明 A B= A B B A B = (A B) B = B = B (由上例及 AB ) 6.4 集合恒等式 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 24 例 6.14 化簡(jiǎn) (A B C)(A B) ( A (B C)A) 解： 因 A B A B C， A A (B C), 故 (A B C) (A B) ( A (B C) A) =(A B) A =(A B) A =(A A) (B A) = (B A) =B A 例 6.15 已知 AB = AC, 證明 B=C 證： A(AB) = A(AC) （ 已知 ） (AA)B (AA)C) B= C B=C 6.4 集合恒等式