離散數學高教版屈婉玲.ppt

《離散數學高教版屈婉玲.ppt》由會員分享，可在線閱讀，更多相關《離散數學高教版屈婉玲.ppt（24頁珍藏版）》請在裝配圖網上搜索。

1、CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 1 離散數學 Discrete Mathematics CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 2 第六章 集合代數 6.1 集合的基本概念 6.2 集合的運算 6.3 有窮集合的計數 6.4集合恒等式 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 3 1.集合 ：將一些事物匯集到一起組成的整體，其中每個事物稱為這個集

2、合 的元素。 注：如果 x是集合 A的元素，則記為 xA 。 集合的表示方法： 列元素法 和 謂詞表示法 列元素法 ：列出集合的所有元素或部分元素，可用于有限集和有一定 規(guī)律的無限集。如： A=a， b， ， z Z=0， -1， 1， -2， 2， D=a， a， a， b集合中的元素還可以是集合。 謂詞表示法 ：用謂詞來描述集合中元素的性質。 如： B=x | x R (x-1=0) 描述法 =x | F(x) G(x) 謂詞描述法 設 F(x):x R ,G(x):x-1=0 . 集合的性質： （ 1）集合的元素是彼此不同的，相同的元素應該認為是同一個元素。 （ 2）集合的元素是無序的。

3、如： 1， 2， 3=2， 3， 1 6.1 集合的基本概念 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 4 注：元素與集合的關系是屬于 和不屬于 。 本書規(guī)定 集合的元素都是集合 。 對任何集合 A，都有 AA . 2.子集合 (Def 6.1):若集合 B中的元素都在集合 A中，則稱 B是 A的 子集合 (簡 稱子集 )。這時也稱 B被 A包含，或 A包含 B。記為 B A。 如果 B不被 A包含 ，則記為 BA。 注： (1)包含的符號化： BAx(xBx A)。 (2)對任何集合 A， 都有 AA。 3.集合

4、的相等 (Def6.2):如果 AB且 BA,則稱集合 A與 B相等 ，記為 A=B。 注：相等的符號化： A=B AB BA。 4.真子集 (Def6.3):對符號 A,B,若 BA且 BA, 則稱 B是 A的 真子集 ,記為 BA 。 如果 B不是 A的真子集，則記為 BA 。 注：真子集的符號化： BA (BA) (B A)。 6.1 集合的基本概念 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 5 5.空集 (Def6.4)：不含任何元素的集合稱為 空集 ， 記為 注 : 1. 空集的符號化： =x|x x 。

5、 2. Th6.1 空集是一切集合的子集 。 （ 證明見教材 P85） 。 3. Cor 空集是唯一的 。 （ 證明見教材 P85） 。 6.n元集 ：含有 n個元素的集合 。 它共有 2n個子集合 。 例 6.1 設 A=1,2,3,求 A的所有子集合 。 7.集合 A的冪集 (Def6.5)：由 A的所有子集作為元素形成的集合 。 記為 P(A)或 2A 。 注：冪集的符號化： P(A)= B | B A。 續(xù)例 6.1 設 A=1,2,3,求 P(A)。 8.全集 (Def6.6)：如果一個問題中所涉及的集合都是某一集合的子集 ， 則稱該集 合為 全集 。 全集一般記為 E。 注：不同問

6、題有不同的全集 ， 同一問題也可以取不同的全集 。 一般 總是將全集取得盡可能小 ， 以便描述和處理問題更加簡便 。 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 (

7、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 一 . 集合的基本運算 設 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對 A的相對補 )： A B = x | x A x B 4.A與 B的 對稱差 ： A B=(A B) (BA)=(A B

8、) (AB) 5.A的 補集 (或稱絕對補 )： A = E A = x | x E x A 注 : (1)“并 ” 和 “ 交 ” 運算可以推廣到有 （ 無 ） 限個集合： 21 1 21 nn n i i AxAxAxxAAAA 2121 1 nn n i i AxAxAxxAAAA 6.2 集合的運算 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 8 集合運算的進一步推廣 定義 6.10 設 A為集合， A的元素的元素構成的集合稱為 A的 廣義并 ，記為 A。 符號化 A=x| z ( z A x z ) 若 A

9、=A1， A2， ， An 則 A=A1 A2 An。 定義 6.11 設 A為 非空集合 ， A的所有元素的公共元素構成的集合稱為 A的 廣 義交 ，記為 A。 符號化 A=x| z（ z Ax z） 若 A=A1， A2， ， An 則 A=A1A2A n。 例 6.2設 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

10、 liujia 9 例 6.3 設 A=a, a, b,計算 : 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ōu)先順序 : 一類運算優(yōu)于二類運算 ; 一類運算由右向左順序進行 ; 二類運算由括號決定先后順序。 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 10 E E B E B

11、 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 有窮集的計數 集合間的關系與運算的表示：文氏圖 (Venn Diagrams) CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 11 例 6.4 對 24名會外國語的科技人員進行掌握外語情況的調查，起統(tǒng)計 結果如下：會英、日、德和法語的人分別為 13， 5， 10和 9人。其中同 時會英語和日語的有 2人，會英、德和法語中任兩種語言的都是 4人。 已知會日語的人既不會法語也

12、不會德語，分別求只會一種語言的人數 和會三種語言的人數。 解 令 A,B,C,D分別表示會英、法、德、日語的人的集合，根據題意得 文氏圖 . A D B C y1 5-2 2 y3 x 4-x y2 4-x 4-x 設同時會三種語言有 x人，只會英、法或德語 一種語言的分別是 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 有窮集的計數 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math

13、. , huang liujia 12 例 6.5 求 1到 1000之間 (包含 1和 1000在內 ), 既不能被 5和 6, 也不能 被 8整除的數有多少個 . 解 設 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

14、| = 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 有窮集的計數 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 13 定理 6.2(包含排斥原理 ) 設 S為有窮集 , P1, P2, , P m是 m個性質 .S中 的任何元素 x或者具有性質 Pi, 或者不具有性質 Pi(i=1.m), 兩種情況必 居其一 . 令

15、Ai表示 S中具有性質 Pi的元素構成的子集 , 則 S中不具有性質 P1, P2, , P m的元素數為 : | 21 mAAA |)1(| | 21 1 11 m m mkji kji mji ji m i i AAAAAA AAAS 6.3 有窮集的計數 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 14 推論 S中至少具有一條性質的元素數為 根據包含排斥原理 , 例 6.5中所求的元素數為 : |ABC| = |S| - (|A|+|B|+|C|) + (|AB|+|AC|+|BC|) - |ABC| =100

16、0-(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 有窮集的計數 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 15 應用 歐拉函數的值 例 6.6 計算歐拉函數的值 (n). 歐拉函數 ：小于 n 且與 n 互素的自然數的個數 解 n 的素因子分解式 : Ai = x | 0 xn1，且 pi 整除 x ， kkpppn . . .21 21 12 1 2 1 2

17、 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 1

18、6 例 6.7 錯排問題的計數問題 有 n個 人在參加晚會時寄存了自己的帽子，可是保管人忘記放寄 存號，當每個人領取帽子時，他只能隨機選擇一頂帽子給寄存人。 問在 n個元素的全排列 n!種領取帽子的方式中有多少種方式使得每 個人都沒有領到自己的帽子？如果將這些人與他們的帽子分別標 號為 1,2, ,n. 設 j 領到的帽子標號為 ij ， j=1,2, ,n. 那么這些人領 到的帽子可以用排列來 i1 i2 in表示，其中每個人都沒有領到自己 帽子的 排列 為 i1 i2 in 使得 ij j ， j=1,2, ,n. 稱這種排列為錯位排 列，錯位排列數記作 Dn , 證明 1 1 1! 1

19、( 1 ) . 1 ! 2 ! ! n nDn n 證 設 S為 1,2, ,n的排列的集合 , Pi 是其中 i處在排列中第 i位的性 質 , Ai 是 S中具有性質 Pi 的排列的集合 , i=1,2, ,n. 那么錯位排列數 Dn 就是 S中不具有以上任何一條性質的排列數。 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 17 ( 2 ) ! 1ijA A n i j n 例 6.7 錯排問題的計數問題 那么 ( 3 ) ! 1i j kA A A n i k j n ( 1 ) ! 1iA n i n 12 .

20、. . ( ) ! 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 設 A,B,C是集合，則下列運算律成立： 1. 冪等律： A A=A, AA=A 2. 結合律： (A B) C=A (B C), (AB)C =A(BC) 3. 交換律： A B=B A, AB=BA 4. 分配律：

21、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 其它

22、重要運算性質 ： 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) 證：對任意的 x xA (B C) xA x(B C) xA xB xC (xA xB) (xA xC)

23、 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.直接利用運算律和已知的集合恒等式做恒等變形 。 6.4 集合恒等式 CHAPTER SIX 1/23/2021 11:50 PM Discrete Math. , huang liujia 21 例 6.9 證明 A E=A 證：對任意 x, xA E xA xE xA. 故 A E=A 例 6.10 證明 A (A B)=A 證： A (A B)= (A E) (A B) (同一律

24、 ) = 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 證：對任意 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 Di

25、screte Math. , huang liujia 23 例 6.13 證明 A B=B AB AB =A AB = 證明 :(1)先證 A B=B AB 對 x, xA xA xB x(A B) xB, ( A B=B) AB (2) 再證 ABAB=A 顯然 ABA ， 下面只需證 AAB 對 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 化簡 (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 集合恒等式