離散數(shù)學(xué)集合映射運(yùn)算市公開(kāi)課獲獎(jiǎng)?wù)n件

1、離散數(shù)學(xué)Discrete Mathematics鄧輝文編著清華大學(xué)出版社普通高等教育“十二五”國(guó)家級(jí)規(guī)劃教材/DetailNews.action?newsId=1031, 序號(hào)702.第1頁(yè)第1頁(yè)本講內(nèi)容什么是離散數(shù)學(xué)1計(jì)算機(jī)專(zhuān)業(yè)為何要學(xué)離散數(shù)學(xué)2離散數(shù)學(xué)基本內(nèi)容3學(xué)習(xí)離散數(shù)學(xué)辦法4離散數(shù)學(xué)學(xué)習(xí)資源5第2頁(yè)第2頁(yè)1、什么是離散數(shù)學(xué)第3頁(yè)第3頁(yè)離散: 分離、分開(kāi)、拆散、分散、.比如正整數(shù)、 土豆、 蘋(píng)果、 人、計(jì)算機(jī)等. 離散 孤立: 社會(huì)網(wǎng)絡(luò)(social networks)研究人與人之間關(guān)系, Internet研究計(jì)算機(jī)之間關(guān)系, WWW研究網(wǎng)頁(yè)之間關(guān)系, 第4頁(yè)第4頁(yè)離散數(shù)學(xué)就是研究離散對(duì)

2、象及其之間關(guān)系學(xué)科.事實(shí)上, 科學(xué)研究任務(wù)就是發(fā)覺(jué)對(duì)象之間內(nèi)在關(guān)系和規(guī)律.第5頁(yè)第5頁(yè)本講內(nèi)容什么是離散數(shù)學(xué)1計(jì)算機(jī)專(zhuān)業(yè)為何要學(xué)離散數(shù)學(xué)2離散數(shù)學(xué)基本內(nèi)容3學(xué)習(xí)離散數(shù)學(xué)辦法4離散數(shù)學(xué)學(xué)習(xí)資源5第6頁(yè)第6頁(yè)2、計(jì)算機(jī)專(zhuān)業(yè)為何要學(xué)離散數(shù)學(xué)第7頁(yè)第7頁(yè)(1) 當(dāng)今計(jì)算機(jī)處理對(duì)象均離散: 0和1.(2) 為后繼專(zhuān)業(yè)課程學(xué)習(xí)作知識(shí)上準(zhǔn)備.(3) 培養(yǎng)各種能力: 抽象思維能力, 邏輯思維能力, 計(jì)算思維(computational thinking, , Jeannette M. Wing )能力,.(4) (教育部, )離散數(shù)學(xué)是計(jì)算機(jī)各專(zhuān)業(yè)專(zhuān)業(yè)基礎(chǔ)課.第8頁(yè)第8頁(yè)程序設(shè)計(jì)語(yǔ)言離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)與算法計(jì)算

3、機(jī)構(gòu)成原理計(jì)算機(jī)網(wǎng)絡(luò)操作系統(tǒng)數(shù)據(jù)庫(kù)軟件工程第9頁(yè)第9頁(yè)本講內(nèi)容什么是離散數(shù)學(xué)1計(jì)算機(jī)專(zhuān)業(yè)為何要學(xué)離散數(shù)學(xué)2離散數(shù)學(xué)基本內(nèi)容3學(xué)習(xí)離散數(shù)學(xué)辦法4離散數(shù)學(xué)學(xué)習(xí)資源5第10頁(yè)第10頁(yè)3、離散數(shù)學(xué)基本內(nèi)容數(shù)學(xué)世界 第11頁(yè)第11頁(yè)1. 集合與關(guān)系Chapter 1 集合、映射與運(yùn)算 Chapter 2 關(guān)系2. 數(shù)理邏輯Chapter 3 命題邏輯Chapter 4 謂詞邏輯3. 代數(shù)結(jié)構(gòu)Chapter 5 代數(shù)結(jié)構(gòu)4. 圖論Chapter 6 圖論Chapter 7 幾類(lèi)特殊圖5. 組累計(jì)數(shù)(Chapter 8)第12頁(yè)第12頁(yè)各章內(nèi)容之間框架結(jié)構(gòu): 第13頁(yè)第13頁(yè)本講內(nèi)容什么是離散數(shù)學(xué)1計(jì)算機(jī)專(zhuān)

4、業(yè)為何要學(xué)離散數(shù)學(xué)2離散數(shù)學(xué)基本內(nèi)容3學(xué)習(xí)離散數(shù)學(xué)辦法4離散數(shù)學(xué)學(xué)習(xí)資源5第14頁(yè)第14頁(yè)4、學(xué)習(xí)離散數(shù)學(xué)辦法第15頁(yè)第15頁(yè)數(shù)學(xué)學(xué)習(xí)辦法1. 預(yù)習(xí)2. 聽(tīng)課3. 復(fù)習(xí)4. 作業(yè)這樣就能夠?qū)Ｐ闹轮镜貙W(xué)好離散數(shù)學(xué)理論知識(shí), 在后繼課程中有實(shí)際應(yīng)用價(jià)值.第16頁(yè)第16頁(yè)本講內(nèi)容什么是離散數(shù)學(xué)1計(jì)算機(jī)專(zhuān)業(yè)為何要學(xué)離散數(shù)學(xué)2離散數(shù)學(xué)基本內(nèi)容3學(xué)習(xí)離散數(shù)學(xué)辦法4離散數(shù)學(xué)學(xué)習(xí)資源5第17頁(yè)第17頁(yè)5、離散數(shù)學(xué)學(xué)習(xí)資源第18頁(yè)第18頁(yè)參考文獻(xiàn)(均為國(guó)家精品課程):屈婉玲, 耿素云, 張立昂, 離散數(shù)學(xué), 高等教育出版社, . (108144學(xué)時(shí))傅彥, 顧小豐, 王慶先, 離散數(shù)學(xué)及其應(yīng)用, 高等教育出版社

5、, . (兩個(gè)學(xué)期)王元元, 沈克勤, 李擁軍, 賀汛, 離散數(shù)學(xué)教程, 高等教育出版社, .Ebooks?第19頁(yè)第19頁(yè)相關(guān)網(wǎng)絡(luò)教學(xué)資源：Discrete Mathematics and Its Applications(世界上有600多所大學(xué)使用, 有影印本和翻譯本)(2) ArsDigita University: /courses/discrete/index.php?view=cw 第20頁(yè)第20頁(yè)(3) Harver Mudd College: videos/mathematics/discrete-mathematics.html(4) MIT(Massachusetts In

6、stitute of Technology): 第21頁(yè)第21頁(yè)離散數(shù)學(xué)是計(jì)算機(jī)相關(guān)專(zhuān)業(yè)主要專(zhuān)業(yè)基礎(chǔ)課程.好好學(xué)習(xí)天天向上第22頁(yè)第22頁(yè)第1章 集合、映射與運(yùn)算1.1 集合相關(guān)概念第23頁(yè)第23頁(yè)本講內(nèi)容集合1子集2冪集3n元組4笛卡兒積5第24頁(yè)第24頁(yè)1.1 集合相關(guān)概念1 集合集合是數(shù)學(xué)中最基本概念, 什么是集合?在一定范圍內(nèi), 集合(set)是其含有某種特定性質(zhì)對(duì)象匯集成一個(gè)整體, 其中每一個(gè)對(duì)象都稱(chēng)為該集合元素(element).第25頁(yè)第25頁(yè)這里所指范圍是全集U.在數(shù)學(xué)中慣用 表示整體. 能夠?qū)⒖紤]離散對(duì)象裝在集合中第26頁(yè)第26頁(yè)(classic set)若x是集合A中元素,

7、 則記xA, 不然xA.第27頁(yè)第27頁(yè)N是自然數(shù)集合,包括數(shù)0Z是整數(shù)集合Z+是正整數(shù)集合(N+)Q是有理數(shù)集合R是實(shí)數(shù)集合素?cái)?shù)集合P : 2, 3, 5, 7, 11, 13, 17, 19, 23等.第28頁(yè)第28頁(yè)(a) m, n Z, m|n: n = qm , q Z. m是n因數(shù), n是m倍數(shù). 2|6, -2|6, 2|-6, -2|-6. m|0, 0|0. (b) Dn表示n所有正因數(shù)構(gòu)成集合, 如D6 = 1, 2, 3, 6.(c) 設(shè)p 1, 若Dp = 1, p, 則稱(chēng)p為素?cái)?shù)(prime).第29頁(yè)第29頁(yè)表示集合慣用辦法:(1) 列舉法: 將集合中元素按一定規(guī)律

8、列舉出來(lái), 如2, b, s, n, N = 0, 1, 2, 3, , P?(2) 描述法: x|x滿足條件.x| 0 x 5, x; 0 x 5第30頁(yè)第30頁(yè)(3) 遞歸法遞歸思想: “知道他過(guò)去, 就知道他現(xiàn)在; 知道他過(guò)去和現(xiàn)在, 就知道他未來(lái)”. N遞歸定義:(a) 0N.(b)若nN, 則n后繼n+1N.(c) 有限次使用(1)和(2)得到元素是N中僅有元素. 其它辦法?第31頁(yè)第31頁(yè)Remarks (i) 集合中元素能夠是任意元素, 如集合, 比如A = a, a, b, b, c.a, bA. (ii) 集合之間元素原則上是沒(méi)有順序, 如 A = a, a, b, b, c

9、就是 a, b, c , a, b.(iii) 集合中元素原則上不重復(fù), 如a, a, b, b, b, c還是集合A = a, a, b, b, c. 第32頁(yè)第32頁(yè)本講內(nèi)容集合1子集2冪集3n元組4笛卡兒積5第33頁(yè)第33頁(yè)2. 子集(1) A B空集是任意集合子集.“小”(2) A = B第34頁(yè)第34頁(yè)Theorem 1-2(1) A A.(2) A B, B A A = B.(3) A B, B C A C.Theorem 1-3 A = B A B 且 B A.第35頁(yè)第35頁(yè)注意 與 不同:例1-2 由A B, B C可否得出A C?Solution 不成立,比如A = a,

10、b, B = a, b, c, C = a, a, b, c.A B?課堂練習(xí): 習(xí)題1.1 4, 5. 第36頁(yè)第36頁(yè)本講內(nèi)容集合1子集2冪集3n元組4笛卡兒積5第37頁(yè)第37頁(yè)3. 冪集(power set)(X), X = a, b P(X) = , a, b, a, b.為何要考慮冪集(結(jié)合其上運(yùn)算及性質(zhì))?第38頁(yè)第38頁(yè)P(yáng)() = .P(P() = P() = , .區(qū)別: , , .第39頁(yè)第39頁(yè)有限集合A元素個(gè)數(shù)|A|, card(A).Theorem 1-4 Hint 第40頁(yè)第40頁(yè)本講內(nèi)容集合1子集2冪集3n元組4笛卡兒積5第41頁(yè)第41頁(yè)4. n元組 (抽象!)De

11、f 1-4 將n個(gè)元素(?)x1, x2, xn按一定順序排列就得到一個(gè)n元(有序)組(n-tuple).第42頁(yè)第42頁(yè)線性代數(shù)中n維向量(?)元組在數(shù)據(jù)結(jié)構(gòu)中是一個(gè)線性表、?；蜿?duì)列, 在數(shù)據(jù)庫(kù)中是一條統(tǒng)計(jì), 如(張三, 男, 19, 重慶). n = 2, n = 3:第43頁(yè)第43頁(yè) n = 2: (x, y). n = 3: (x, y, z)4元組?普通說(shuō)來(lái)(x, y) (y, x).第44頁(yè)第44頁(yè)2元組常稱(chēng)為有序?qū)?ordered pair)或序偶.(x, y)第45頁(yè)第45頁(yè)本講內(nèi)容集合1子集2冪集3n元組4笛卡兒積5第46頁(yè)第46頁(yè)5. 笛卡兒積(cross product)

12、解析幾何之父笛卡兒(R. Cartesian, 1596-1650)是法國(guó)數(shù)學(xué)家, “我思故我在”和“越學(xué)習(xí)越發(fā)覺(jué)自己無(wú)知”是他名言. 第47頁(yè)第47頁(yè)例1-4 設(shè)A = a, b, B = 1, 2, C = , 求A B, B A, A B C , B C.Solution ABC =(a,1,), (b,1,), (a,2,), (b,2,). BC = (1, ), (2, )Remark A = B = .課堂練習(xí): 習(xí)題1.1 10第48頁(yè)第48頁(yè)Theorem 1-5Hint 第49頁(yè)第49頁(yè)小結(jié)與作業(yè)集合就是一些對(duì)象構(gòu)成整體習(xí)題1.1 6, 7, 10作業(yè)A B, A = B第

13、50頁(yè)第50頁(yè)第1章 集合、映射與運(yùn)算1.2 映射相關(guān)概念第51頁(yè)第51頁(yè)本講內(nèi)容映射定義1映射性質(zhì)2第52頁(yè)第52頁(yè)1.2 映射相關(guān)概念1. 映射定義映射(mapping) = 函數(shù)(function). y = f(x) = x2 , ceiling function , floor function , 編寫(xiě)C語(yǔ)言程序主要就是編寫(xiě)函數(shù): 從main開(kāi)始. 第53頁(yè)第53頁(yè)Def 任意給定兩個(gè)集合A和B, 若存在相應(yīng)法則f, 使得對(duì)于任意 xA, 均存在唯一yB與它相應(yīng), 則稱(chēng)f是集合A到B映射, 或稱(chēng)其為A到B函數(shù), 記為AB第54頁(yè)第54頁(yè)為何討論映射? 集合之間相應(yīng)關(guān)系.其它理解方式

14、:第55頁(yè)第55頁(yè)映射兩個(gè)特點(diǎn):(1)全函數(shù).(2)唯一性.注意區(qū)別函數(shù) f 與 f(x).y = f(x)?第56頁(yè)第56頁(yè)函數(shù)符號(hào)選取: f, g, F,G, , sin, exp, main, add, average, hanoi, delete_string, 第57頁(yè)第57頁(yè)例1-5 寫(xiě)出所有A到B映射. x1x2x3y1y2第58頁(yè)第58頁(yè)n元函數(shù)(n 1):第59頁(yè)第59頁(yè)float average(float array, int n)n = 0: C語(yǔ)言中無(wú)參函數(shù)? 第60頁(yè)第60頁(yè)本講內(nèi)容映射定義1映射性質(zhì)2第61頁(yè)第61頁(yè)2. 映射性質(zhì)(1) 單射(injection)

15、第62頁(yè)第62頁(yè)例1-6 設(shè)f: N N, f(x) = 2x, 則f是N到N單射, 試證實(shí)之.Proof 對(duì)任意x1, x2 A, 由f(x1) = f(x2), 可得出2x1= 2x2, 進(jìn)而x1= x2. 第63頁(yè)第63頁(yè)(2) 滿射(surjection)第64頁(yè)第64頁(yè)例1-7 闡明 是Z到N滿射, 但不是Z到Z滿射.第65頁(yè)第65頁(yè)(3) 雙射(bijection, one-to-one correspondence)雙射又稱(chēng)為一一相應(yīng):既單又滿.例1-8第66頁(yè)第66頁(yè)例1-9第67頁(yè)第67頁(yè)Def 1-11 有限集合A上本身雙射稱(chēng)為A上置換(permutation).例1-10

16、第一個(gè)方式:123123第68頁(yè)第68頁(yè)第二種方式:A = 1, 2, 3, 4上所有置換有多少個(gè)?4!主要應(yīng)用: 置換加密. 第69頁(yè)第69頁(yè)小結(jié)與作業(yè)映射(函數(shù))定義單射滿射雙射(一一相應(yīng))習(xí)題1.2 1, 2, 3作業(yè)第70頁(yè)第70頁(yè)第1章 集合、映射與運(yùn)算1.3 運(yùn)算定義及性質(zhì)第71頁(yè)第71頁(yè)本講內(nèi)容運(yùn)算定義1第72頁(yè)第72頁(yè)1. 運(yùn)算定義A1, A2, An到Bn元運(yùn)算(n-ary operation):第73頁(yè)第73頁(yè)A1 = 2, S, N, A2 = B, B = 2B, SB, NB第74頁(yè)第74頁(yè)A到B(或A上)n元運(yùn)算:A = 5角硬幣, 1元硬幣, B = 打火機(jī), 礦

17、泉水, 雪糕, 智能手機(jī), 平板電腦第75頁(yè)第75頁(yè)(運(yùn)算封閉性)A上n元封閉運(yùn)算(代數(shù)運(yùn)算):A = 1, 2, 3, A上取小運(yùn)算min:第76頁(yè)第76頁(yè)n元運(yùn)算就是n元函數(shù):n = 0? 普通處理方式: A到B一個(gè)0元運(yùn)算可理解為B中某一個(gè)元素.第77頁(yè)第77頁(yè)考慮運(yùn)算目標(biāo)? 運(yùn)算是由已知對(duì)象得出新對(duì)象一個(gè)方法. 例1-15(模運(yùn)算) f: Z N, f(x) = x(mod m), x = qm + r, 0 r 1)表示小于等于n且與n互素正整數(shù)個(gè)數(shù):第84頁(yè)第84頁(yè)(1) = 1, (2) = 1, (3) = 2, (4) = 2, (5) = 4, (6) = 2, 第85頁(yè)第

18、85頁(yè)D. Euclid算法:Solution 第86頁(yè)第86頁(yè)第87頁(yè)第87頁(yè)Remarks(1) 運(yùn)算符號(hào)(算符, 算子)選取函數(shù)符號(hào)f, g, , F, G, ,;常見(jiàn)運(yùn)算符號(hào)+, , /, ,;自定義符號(hào) , , , ,第88頁(yè)第88頁(yè)(2) 運(yùn)算符號(hào)位置 第89頁(yè)第89頁(yè)(3) 運(yùn)算表A = a, b, c, *:思考 A上封閉1元運(yùn)算, 2元運(yùn)算和3元運(yùn)算個(gè)數(shù)是多少?* a b cabc b a c b c c c a b第90頁(yè)第90頁(yè)運(yùn)算本質(zhì)上是映射. 為何還要研究運(yùn)算?但研究側(cè)重點(diǎn)不同, 在運(yùn)算中更重視于運(yùn)算滿足一些運(yùn)算性質(zhì), 而依據(jù)這些性質(zhì)能夠?qū)σ恍╇x散對(duì)象分門(mén)別類(lèi)進(jìn)行討論

19、.第91頁(yè)第91頁(yè)小結(jié)與作業(yè)n元運(yùn)算和n元封閉運(yùn)算定義模m運(yùn)算gcd(m,n)及Euclid算法, lcm(m, n)運(yùn)算符號(hào)及運(yùn)算表習(xí)題1.3 2, 3, 7作業(yè)第92頁(yè)第92頁(yè)第1章 集合、映射與運(yùn)算1.3 運(yùn)算定義及性質(zhì)第93頁(yè)第93頁(yè)本講內(nèi)容運(yùn)算性質(zhì)(常見(jiàn)有11種)2第94頁(yè)第94頁(yè)2. 運(yùn)算性質(zhì)(1) 對(duì)合(involutive)性 Def 1-15 設(shè)*是A上1元代數(shù)運(yùn)算, 例 第95頁(yè)第95頁(yè)(2) 冪等(idempotent)性 冪等元x: A關(guān)于*含有冪等性: A中每個(gè)元素對(duì)于*都是冪等元.第96頁(yè)第96頁(yè)兩個(gè)例子:* 1 2 3123 1 3 2 2 3 2 3 1 3第9

20、7頁(yè)第97頁(yè)(3) 互換(commutative)性 Def 設(shè)*是A上2元代數(shù)運(yùn)算, 若對(duì)于任意x, y A, 都有 則稱(chēng)*滿足互換律.映射復(fù)合運(yùn)算不滿足互換律:加法運(yùn)算”+”滿足互換律, 而減法運(yùn)算”-”不滿足互換律: 2 3 3 2.如何依據(jù)定義運(yùn)算判斷運(yùn)算含有互換性?第98頁(yè)第98頁(yè)(4) 結(jié)合(associative)性 映射復(fù)合運(yùn)算滿足結(jié)合律:加法運(yùn)算“+”滿足結(jié)合律, 而減法運(yùn)算“-”不滿足結(jié)合律: (2 - 3) - 5 2 - (3 5).第99頁(yè)第99頁(yè)(5) 幺元律 Def 1-19 設(shè)*是A上2元代數(shù)運(yùn)算, 若存在e A, 對(duì)于任意x A, 下列條件均成立： 則稱(chēng)e為集

21、合A關(guān)于*運(yùn)算單位元素或幺元素第100頁(yè)第100頁(yè)例 Z關(guān)于加法運(yùn)算+單位元素為0, 而Z關(guān)于乘法運(yùn)算“.”單位元素為1, Z關(guān)于減法運(yùn)算-沒(méi)有單位元素. 第101頁(yè)第101頁(yè)(6) 零元律 Def 設(shè)*是A上2元代數(shù)運(yùn)算, 若存在 A,對(duì)于任意x A, 下列條件均成立： 則稱(chēng)為集合A關(guān)于*運(yùn)算零元素.第102頁(yè)第102頁(yè)例1-28 Z關(guān)于加法運(yùn)算+和減法運(yùn)算-均沒(méi)有零元素, 而Z關(guān)于乘法運(yùn)算零元素為0. 第103頁(yè)第103頁(yè)(7) 逆元律若A關(guān)于運(yùn)算*有單位元素e, 則能夠討論A中取定元素x是否有逆元. Def 設(shè)*是A上2元代數(shù)運(yùn)算且有單位元素e,若對(duì)于x A,存在y A,使得下列條件均成

22、立: 則稱(chēng)y為x關(guān)于*逆元素.第104頁(yè)第104頁(yè)一個(gè)映射關(guān)于函數(shù)復(fù)合運(yùn)算逆元就是其逆映射, 當(dāng)然只有雙射才有逆元,其單位元素是恒等映射.例1-29 R中各元素關(guān)于加法運(yùn)算+和乘法運(yùn)算逆元素.第105頁(yè)第105頁(yè)(8) 消去(cancellation)性. Def 設(shè)*是A上2元代數(shù)運(yùn)算, 若A關(guān)于*運(yùn)算有零元?jiǎng)t記為 , 假如對(duì)于任意x, y , z A, 只要x , 那么下列條件均成立： 則稱(chēng)*含有消去性, 或稱(chēng)*滿足消去律.第106頁(yè)第106頁(yè)例1-31 Z上加法運(yùn)算+和乘法運(yùn)算均滿足消去律.例1-32 實(shí)數(shù)集R上所有2階方陣構(gòu)成集合, 關(guān)于矩陣乘法運(yùn)算不滿足消去律. 第107頁(yè)第107頁(yè)

23、(9) 分派(distributive)性. Def 設(shè)*和是集合A上兩個(gè)2元代數(shù)運(yùn)算,若對(duì)于任意x, y , z A, 有 則稱(chēng)*對(duì)于是可分派.第108頁(yè)第108頁(yè)例1-33 實(shí)數(shù)集合R上乘法運(yùn)算對(duì)加法運(yùn)算+可分派,但加法運(yùn)算+對(duì)乘法運(yùn)算不可分派. 矩陣乘法和加法運(yùn)算?集合并和交運(yùn)算?第109頁(yè)第109頁(yè)(10) 吸取(absorptive)性 Def 設(shè)*和是集合A上兩個(gè)2元代數(shù)運(yùn)算,若對(duì)于任意x, y A, 有 則稱(chēng)*對(duì)于是可吸取. 集合并和交運(yùn)算?第110頁(yè)第110頁(yè)(11) 德摩根(De Morgan)律 Def 設(shè)是集合A上1元代數(shù)運(yùn)算, *和是A上兩個(gè)2元代數(shù)運(yùn)算, 若對(duì)于任意x

24、, y A, 都有下面兩個(gè)等式成立: 則稱(chēng)這三種運(yùn)算滿足德摩根律. 集合補(bǔ)、并和交運(yùn)算?第111頁(yè)第111頁(yè)小結(jié)與作業(yè)對(duì)合律冪等律、互換律、結(jié)合律、幺元律、零元律、逆元律、消去律分派律、吸取律De Morgan律習(xí)題1.3 8, 12, 15作業(yè)第112頁(yè)第112頁(yè)第1章 集合、映射與運(yùn)算1.4 集合運(yùn)算1.5 集合劃分與覆蓋第113頁(yè)第113頁(yè)本講內(nèi)容123并運(yùn)算交運(yùn)算45補(bǔ)運(yùn)算差運(yùn)算對(duì)稱(chēng)差運(yùn)算集合劃分與覆蓋6第114頁(yè)第114頁(yè)最常見(jiàn)集合運(yùn)算是并、交和補(bǔ). 1. 并(union)運(yùn)算第115頁(yè)第115頁(yè)Theorem1-17 (并運(yùn)算滿足性質(zhì))(1)(2)(3)(4) A = A = A(

25、5) A U = U A = U第116頁(yè)第116頁(yè)第117頁(yè)第117頁(yè)本講內(nèi)容123并運(yùn)算交運(yùn)算45補(bǔ)運(yùn)算差運(yùn)算對(duì)稱(chēng)差運(yùn)算集合劃分與覆蓋6第118頁(yè)第118頁(yè)2. 交(intersection)運(yùn)算第119頁(yè)第119頁(yè)Theorem1-19 (交運(yùn)算滿足性質(zhì))(1)(2)(3)(4) A = A = (5) A U = U A = A第120頁(yè)第120頁(yè)Theorem 1-20(并運(yùn)算與交運(yùn)算之間所滿足性質(zhì).)(1)吸取性.(2)分派性.第121頁(yè)第121頁(yè)例1-41第122頁(yè)第122頁(yè)本講內(nèi)容123并運(yùn)算交運(yùn)算45補(bǔ)運(yùn)算差運(yùn)算對(duì)稱(chēng)差運(yùn)算集合劃分與覆蓋6第123頁(yè)第123頁(yè)3. 補(bǔ)(comp

26、lement)運(yùn)算例1-42 (A補(bǔ)集依賴(lài)于全集U選取.) A=a, b, c:(1)U = a, b, c, d(2)U = a, b, c, d,a,b,b,c,c第124頁(yè)第124頁(yè)排中律成立: .排中律: x U, x A或 x A兩者必居其一, 沒(méi)有中間情況. 第125頁(yè)第125頁(yè)集合補(bǔ)運(yùn)算和集合并交運(yùn)算滿足De Morgan律:推廣?第126頁(yè)第126頁(yè)P(yáng)(n), nn0.第一數(shù)學(xué)歸納法:(1) P(n0)成立.(2) 假定P(n -1)時(shí)成立, 證實(shí)P(n)成立. 第二數(shù)學(xué)歸納法:(1) P(n0)成立.(2) 假定比n小都成立, 證實(shí)P(n)成立. 第127頁(yè)第127頁(yè)本講內(nèi)容

27、123并運(yùn)算交運(yùn)算45補(bǔ)運(yùn)算差運(yùn)算對(duì)稱(chēng)差運(yùn)算集合劃分與覆蓋6第128頁(yè)第128頁(yè)4. 差(subtraction)運(yùn)算例1-43 第129頁(yè)第129頁(yè)Theorem 1-23Proof(1)(2)第130頁(yè)第130頁(yè)例1-45 對(duì)于任意集合A, B和C, 證實(shí): (A B) C = A (B C)Poof第131頁(yè)第131頁(yè)例1-46 .例1-47 (A B) (A C) = 充要條件?Solution由上例知, A (B C) = 第132頁(yè)第132頁(yè)本講內(nèi)容123并運(yùn)算交運(yùn)算45補(bǔ)運(yùn)算差運(yùn)算對(duì)稱(chēng)差運(yùn)算集合劃分與覆蓋6第133頁(yè)第133頁(yè)5. 對(duì)稱(chēng)差(symmetric difference

28、)運(yùn)算See Venn Figure below.例1-48第134頁(yè)第134頁(yè)第135頁(yè)第135頁(yè)Theorem(對(duì)稱(chēng)差運(yùn)算性質(zhì))(1)互換性:(2)單位元: A = A.(3) A A = .(4)結(jié)合性:第136頁(yè)第136頁(yè)例1-49(消去律)Hint第137頁(yè)第137頁(yè)例1-50 A B = A = B.Proof ()顯然.()A B = A B = 且B A = 第138頁(yè)第138頁(yè)思考 還能定義集合其它運(yùn)算(共9種！)?加法原理推廣:容斥原理:第139頁(yè)第139頁(yè)容斥原理另一個(gè)形式:第140頁(yè)第140頁(yè)1.5 集合劃分與覆蓋第141頁(yè)第141頁(yè)集合劃分就是集合元素間一個(gè)分類(lèi). 流

29、行術(shù)語(yǔ): 聚類(lèi).比集合劃分更廣概念是集合覆蓋. 這些內(nèi)容在下章會(huì)用到. 1. 集合劃分(partition) 第142頁(yè)第142頁(yè)Def 1-31(1) , iI.(2) , i j.(3)分組, 磁盤(pán)分區(qū)?第143頁(yè)第143頁(yè)例1-53 設(shè)A = a, b, c, 則A全部不同劃分分別為:第144頁(yè)第144頁(yè)1和2交叉劃分: .1是2加細(xì)劃分:第145頁(yè)第145頁(yè)|A| = n, A不同劃分個(gè)數(shù)N = N(n): S(n, k): n個(gè)元素劃分成k個(gè)塊方案數(shù).Theorem n 1.Proof(?)第146頁(yè)第146頁(yè)2. 集合覆蓋Def 設(shè)A是集合, 由A若干非空子集構(gòu)成集合稱(chēng)為A覆蓋(c

30、overing), 假如這些非空子集并等于A.a, b, b, c集合劃分集合覆蓋, 但反過(guò)來(lái)不成立.第147頁(yè)第147頁(yè)小結(jié)與作業(yè)集合并、交、補(bǔ)運(yùn)算及其性質(zhì)集合差和對(duì)稱(chēng)差運(yùn)算及結(jié)論數(shù)學(xué)歸納法容斥原理習(xí)題1.4 1, 8, 10 習(xí)題1.5 1 作業(yè)集合劃分與覆蓋第148頁(yè)第148頁(yè)第1章 集合、映射與運(yùn)算1.6 集合對(duì)等第149頁(yè)第149頁(yè)本講內(nèi)容集合對(duì)等定義1234不可數(shù)集合5無(wú)限集合集合基數(shù)可數(shù)集合6基數(shù)比較第150頁(yè)第150頁(yè)集合對(duì)等, 它是集合間另一個(gè)關(guān)系. 通過(guò)集合對(duì)等以及相關(guān)內(nèi)容學(xué)習(xí), 加深對(duì)函數(shù)概念理解, 提升正確使用函數(shù)工具作為研究手段能力. 1.集合對(duì)等(equivalen

31、t)Def 1-33 若存在雙射f : A B, 則 A B.第151頁(yè)第151頁(yè)N EZ N(0, 1) RN N N (see below):第152頁(yè)第152頁(yè)第153頁(yè)第153頁(yè)Theorem 1-28(對(duì)等性質(zhì))(1) A A.(2) A B B A.(3) A B, B C A C.第154頁(yè)第154頁(yè)本講內(nèi)容集合對(duì)等定義1234不可數(shù)集合5無(wú)限集合集合基數(shù)可數(shù)集合6基數(shù)比較第155頁(yè)第155頁(yè)2. 無(wú)限集合有了集合對(duì)等概念, 就能夠給出無(wú)限集合及有限集合嚴(yán)格定義.Def 1-34 設(shè)A是集合, 若存在A一個(gè)子集與自然數(shù)集合N對(duì)等, 則稱(chēng)A為無(wú)限集合(infinite set),

32、不然稱(chēng)A為有限集合(finite set).N.0, 1a, b, c?第156頁(yè)第156頁(yè)本講內(nèi)容集合對(duì)等定義1234不可數(shù)集合5無(wú)限集合集合基數(shù)可數(shù)集合6基數(shù)比較第157頁(yè)第157頁(yè)3. 集合基數(shù)有限集合基數(shù)就是元素個(gè)數(shù)(由于0 = , 1 = , n + 1 = n n),無(wú)限集合?Def 若集合A和B對(duì)等, 則稱(chēng)這兩個(gè)集合基數(shù)(cardinality)相同.|A|, card(A), #(A).第158頁(yè)第158頁(yè)G. Cantor(18451918,德國(guó)數(shù)學(xué)家)被這些問(wèn)題所折磨難以自拔(除自己牙齒外, 尚有什么不能自拔).1884年后患精神病(受到諸多人批評(píng)和襲擊, 包括他老師L.K

33、ronecker(18231891).用腦過(guò)度嗎?第159頁(yè)第159頁(yè)本講內(nèi)容集合對(duì)等定義1234不可數(shù)集合5無(wú)限集合集合基數(shù)可數(shù)集合6基數(shù)比較第160頁(yè)第160頁(yè)4. 可數(shù)集合(可數(shù)名詞?)Def 1-36 能與自然數(shù)集合N對(duì)等集合稱(chēng)為可數(shù)集合(countable set)或可列集合. 第161頁(yè)第161頁(yè)可列集合:N0, 2, 4, 6, ZQ第162頁(yè)第162頁(yè)無(wú)限集合特性性質(zhì):Theorem 1-29 設(shè)A是無(wú)限集合, 則存在A一個(gè)真子集B, 使得 A B.Proof 由于A是無(wú)限集合, 存在可數(shù)子集合考慮第163頁(yè)第163頁(yè)本講內(nèi)容集合對(duì)等定義1234不可數(shù)集合5無(wú)限集合集合基數(shù)可數(shù)

34、集合6基數(shù)比較第164頁(yè)第164頁(yè)5. 不可數(shù)集合(不可數(shù)名詞?)是否所有沒(méi)有限集合都是可數(shù)? 例 證實(shí): (0,1)是不可數(shù)集合.Proof(反證) 取(see below)第165頁(yè)第165頁(yè)第166頁(yè)第166頁(yè)本講內(nèi)容集合對(duì)等定義1234不可數(shù)集合5無(wú)限集合集合基數(shù)可數(shù)集合6基數(shù)比較第167頁(yè)第167頁(yè)6. 基數(shù)比較Def 1-37 給定集合A和B, 若存在A到B單射, 則稱(chēng)A基數(shù)小于等于B基數(shù), 記為|A| |B|. 若進(jìn)一步, 不存在A到B雙射, 則稱(chēng)A基數(shù)小于B基數(shù), 記為|A| |B|. 第168頁(yè)第168頁(yè)由定義易知, 若存在B到A滿射, 則|B| |A|. 顯然, Probl

35、em 是否存在集合A, 滿足(著名連續(xù)統(tǒng)假設(shè)?!)第169頁(yè)第169頁(yè)小結(jié)與作業(yè)A B無(wú)限集合與集合基數(shù)可數(shù)集合與不可數(shù)集合習(xí)題1.6 4, 5, 6 作業(yè)基數(shù)比較第170頁(yè)第170頁(yè)離散數(shù)學(xué)第1章復(fù)習(xí)小結(jié)第171頁(yè)第171頁(yè)1、集合相關(guān)概念 集合就是一些對(duì)象構(gòu)成整體. 若x是集合A中元素, 記為x A, 不然x A. 理解集合就是要把集合中元素弄清楚, 需要知道一些背景知識(shí), 如整數(shù)、整除、偶數(shù)、素?cái)?shù)、因數(shù)、空集、元組等. 第172頁(yè)第172頁(yè)表示集合能夠用列舉法、描述法和遞歸法. 集合中元素能夠是任意對(duì)象, 如元素本身又能夠是集合; 集合中元素本身沒(méi)有順序關(guān)系; 集合中元素原則上不重復(fù).

36、第173頁(yè)第173頁(yè)給定集合B, B子集A就是集合B中一些元素構(gòu)成“新”集合, 記為A B. 要注意 和 區(qū)別. 例1 判斷題.(1) .(2) .(3) .(4) .第174頁(yè)第174頁(yè)例2 由A B, B C可否得出A C?Solution 不成立, 比如A = a, b, B = a, b, c, C = a, a, b, c.A B?第175頁(yè)第175頁(yè)證實(shí)兩個(gè)集合相等慣用到“A = B充要條件是A B且B A. ”結(jié)論. 第176頁(yè)第176頁(yè)集合X冪集P(X)是X所有子集構(gòu)成集合. 注意P(X), 要求會(huì)計(jì)算給定集合冪集. 主要結(jié)論是: 若|X| = n, 則|P(X)| = 2n.

37、 第177頁(yè)第177頁(yè)例3 計(jì)算P(), P(P()和P(, a)Solution P() = .P(P() = P() = , .P(, a) = ?X = , a P(X) = ?第178頁(yè)第178頁(yè)選取n個(gè)元素x1, x2, xn按一定順序排列排列起來(lái)就是一個(gè)元組, 記為 (x1, x2, xn). 數(shù)據(jù)結(jié)構(gòu): (D, R).圖G = (V, E).文法G = (V, T, P, S) 自動(dòng)機(jī)M = (Q, , , q0, F)第179頁(yè)第179頁(yè)笛卡兒積A1 A2 An = (x1, x2, xn)| xi Ai, i = 1, 2, , n. 能純熟計(jì)算笛卡兒積. 若|X| = m,

38、 |Y| = n, 則|XY| = mn. 第180頁(yè)第180頁(yè)例4 設(shè)A = a, b, B = 1, 2, C = , 求A B, A B C , B C.SolutionABC =(a,1,), (b,1,), (a,2,), (b,2,). BC = (1, ), (2, )Remark A = B = .第181頁(yè)第181頁(yè)2、映射相關(guān)概念 映射 f: AB 就是將集合A元素唯一對(duì)應(yīng)到集合B中元素. 要深入了解映射含義, 包含函數(shù)符號(hào)選取和多元函數(shù), 區(qū)分f和f(x)不同, 了解天花板函數(shù)和地板函數(shù). 第182頁(yè)第182頁(yè)映射f: AB:若不同A中元素對(duì)應(yīng)不同B中元素, f就是單射;

39、 若函數(shù)值充滿整個(gè)集合B, f就是滿射; 既是單射又是滿射即為雙射. 第183頁(yè)第183頁(yè)設(shè)f: AB, 若將f方向逆轉(zhuǎn)能得到B到A函數(shù), 它就是f逆函數(shù)或反函數(shù), 記為f -1. 函數(shù)f有反函數(shù)充要條件是f是雙射. 第184頁(yè)第184頁(yè)先進(jìn)行映射,再進(jìn)行映射, 可得到A到C映射, 它就是f與g復(fù)合映射, 記為f g. 要求掌握兩個(gè)函數(shù)復(fù)合運(yùn)算. 普通來(lái)說(shuō), f g g f, 但 (f g) h = f (g h). 尤其應(yīng)注意函數(shù)復(fù)合運(yùn)算與單射、滿射和雙射之間關(guān)系. 第185頁(yè)第185頁(yè)例5 (習(xí)題1.2, 4) 假定f: AB, 證實(shí)(1) f IB = f(2) IAf = f.Proo

40、f (1)xA, (f IB)(x) = IB(f(x) = f(x) f IB = f.(2) xA, (IAf )(x) = f(IA(x) = f(x) IAf = f.第186頁(yè)第186頁(yè)例6(習(xí)題1.2, 8) 設(shè)f: AB, 若存在g: BA, 使得f g = IA且g f = IB, 則f是雙射且f -1 = g.Proof 由f g = IA, 知f是單射. 由g f = IB, 知f是滿射. 于是 f是雙射, 進(jìn)而f -1 存在.由于f -1 (f g) = f -1 IA ,而f -1 (f g) = ( f -1 f )g = IB g = g且 f -1 IA = f

41、-1 ,因此f -1 = g.第187頁(yè)第187頁(yè)例7(習(xí)題1.2, 13) 設(shè)f: AB, g: BC, h: CA, 若f g h = IA, g h f = IB, h f g = IC, 則f, g, h均可逆, 并求出f -1, g -1和 h -1 .Hint f?f g h = IA, g h f = IB f是雙射.f -1 = g h .第188頁(yè)第188頁(yè)補(bǔ)充練習(xí)1 設(shè)R為實(shí)數(shù)集合, 定義f: R R R R為(1)證實(shí)f是雙射.(2)求f逆函數(shù)f -1.(3)計(jì)算f -1 f 及f f. 第189頁(yè)第189頁(yè)補(bǔ)充練習(xí)2 設(shè)N為自然數(shù)集合, 定義N 到 N函數(shù)f 和g下列:

42、xN, f(x) = x + 1, g(x) = max0, x - 1. 證實(shí)：(1) f是單射而不是滿射, g是滿射而不是單射.(2) f g = IN, 而g f IN. 第190頁(yè)第190頁(yè)3、運(yùn)算定義及性質(zhì) 運(yùn)算目的就是從已知元素得出新元素, n元運(yùn)算就是n元函數(shù). 集合A上n元封閉運(yùn)算f是指對(duì)于任意A中n個(gè)元素進(jìn)行f運(yùn)算后結(jié)果仍屬于集合A. 第191頁(yè)第191頁(yè)要求掌握封閉運(yùn)算定義, 了解整數(shù)集合Z上模m運(yùn)算mod m, 兩個(gè)不同時(shí)為0兩個(gè)整數(shù)最大公因數(shù)運(yùn)算gcd和任意兩個(gè)整數(shù)最小公倍數(shù)運(yùn)算lcm. 了解運(yùn)算符號(hào)選取、運(yùn)算符號(hào)位置和運(yùn)算表. 第192頁(yè)第192頁(yè)進(jìn)一步理解:一元運(yùn)算含有對(duì)合性;二元運(yùn)算含有冪等性、互換性、結(jié)合性、幺元性、零元性、逆元性和消去性等性質(zhì);兩個(gè)二元運(yùn)算含有分派性、吸取性;一個(gè)一元運(yùn)算和兩個(gè)二元