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

上傳人:xin****828 文檔編號(hào):20000923 上傳時(shí)間:2021-01-23 格式:PPT 頁數(shù):24 大?。?83.56KB
收藏 版權(quán)申訴 舉報(bào) 下載
離散數(shù)學(xué)高教版屈婉玲.ppt_第1頁
第1頁 / 共24頁
離散數(shù)學(xué)高教版屈婉玲.ppt_第2頁
第2頁 / 共24頁
離散數(shù)學(xué)高教版屈婉玲.ppt_第3頁
第3頁 / 共24頁

下載文檔到電腦,查找使用更方便

9.9 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《離散數(shù)學(xué)高教版屈婉玲.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《離散數(shù)學(xué)高教版屈婉玲.ppt(24頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、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è)事物稱為這個(gè)集

2、合 的元素。 注:如果 x是集合 A的元素,則記為 xA 。 集合的表示方法: 列元素法 和 謂詞表示法 列元素法 :列出集合的所有元素或部分元素,可用于有限集和有一定 規(guī)律的無限集。如: A=a, b, , z Z=0, -1, 1, -2, 2, D=a, a, a, b集合中的元素還可以是集合。 謂詞表示法 :用謂詞來描述集合中元素的性質(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)集合的元素是無序的。

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

4、的相等 (Def6.2):如果 AB且 BA,則稱集合 A與 B相等 ,記為 A=B。 注:相等的符號(hào)化: A=B AB BA。 4.真子集 (Def6.3):對(duì)符號(hào) A,B,若 BA且 BA, 則稱 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):不含任何元素的集合稱為 空集 , 記為 注 : 1. 空集的符號(hào)化: =x|x x 。

5、 2. Th6.1 空集是一切集合的子集 。 ( 證明見教材 P85) 。 3. Cor 空集是唯一的 。 ( 證明見教材 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è)問題中所涉及的集合都是某一集合的子集 , 則稱該集 合為 全集 。 全集一般記為 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 一 . 集合的基本運(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ì)稱差 : A B=(A B) (BA)=(A B

8、) (AB) 5.A的 補(bǔ)集 (或稱絕對(duì)補(bǔ) ): A = E A = x | x E x A 注 : (1)“并 ” 和 “ 交 ” 運(yùn)算可以推廣到有 ( 無 ) 限個(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)成的集合稱為 A的 廣義并 ,記為 A。 符號(hào)化 A=x| z ( z A x z ) 若 A

9、=A1, A2, , An 則 A=A1 A2 An。 定義 6.11 設(shè) A為 非空集合 , A的所有元素的公共元素構(gòu)成的集合稱為 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

10、 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)一步推廣 一類運(yùn)算 :廣義并,廣義交,冪集,絕對(duì)補(bǔ) 二類運(yùn)算 :并,交,相對(duì)補(bǔ),對(duì)稱差 集合運(yùn)算的優(yōu)先順序 : 一類運(yùn)算優(yōu)于二類運(yùn)算 ; 一類運(yùn)算由右向左順序進(jìn)行 ; 二類運(yùn)算由括號(hào)決定先后順序。 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 有窮集的計(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ì)外國語的科技人員進(jìn)行掌握外語情況的調(diào)查,起統(tǒng)計(jì) 結(jié)果如下:會(huì)英、日、德和法語的人分別為 13, 5, 10和 9人。其中同 時(shí)會(huì)英語和日語的有 2人,會(huì)英、德和法語中任兩種語言的都是 4人。 已知會(huì)日語的人既不會(huì)法語也

12、不會(huì)德語,分別求只會(huì)一種語言的人數(shù) 和會(huì)三種語言的人數(shù)。 解 令 A,B,C,D分別表示會(huì)英、法、德、日語的人的集合,根據(jù)題意得 文氏圖 . A D B C y1 5-2 2 y3 x 4-x y2 4-x 4-x 設(shè)同時(shí)會(huì)三種語言有 x人,只會(huì)英、法或德語 一種語言的分別是 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

13、. , 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

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 有窮集的計(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), 兩種情況必 居其一 . 令

15、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| =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 有窮集的計(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

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 錯(cuò)排問題的計(jì)數(shù)問題 有 n個(gè) 人在參加晚會(huì)時(shí)寄存了自己的帽子,可是保管人忘記放寄 存號(hào),當(dāng)每個(gè)人領(lǐng)取帽子時(shí),他只能隨機(jī)選擇一頂帽子給寄存人。 問在 n個(gè)元素的全排列 n!種領(lǐng)取帽子的方式中有多少種方式使得每 個(gè)人都沒有領(lǐng)到自己的帽子?如果將這些人與他們的帽子分別標(biāo) 號(hào)為 1,2, ,n. 設(shè) j 領(lǐng)到的帽子標(biāo)號(hào)為 ij , j=1,2, ,n. 那么這些人領(lǐng) 到的帽子可以用排列來 i1 i2 in表示,其中每個(gè)人都沒有領(lǐng)到自己 帽子的 排列 為 i1 i2 in 使得 ij j , j=1,2, ,n. 稱這種排列為錯(cuò)位排 列,錯(cuò)位排列數(shù)記作 Dn , 證明 1 1 1! 1

19、( 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ò)排問題的計(jì)數(shù)問題 那么 ( 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 設(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. 分配律:

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、重要運(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)

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.直接利用運(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) (同一律

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 證:對(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 Di

25、screte 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 化簡 (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 集合恒等式

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!

五月丁香婷婷狠狠色,亚洲日韩欧美精品久久久不卡,欧美日韩国产黄片三级,手机在线观看成人国产亚洲