集合映射與運(yùn)算PPT課件

1、 離散數(shù)學(xué)是計(jì)算機(jī)各專業(yè)的專業(yè)基礎(chǔ)課. (1) 程序設(shè)計(jì)語(yǔ)言 (2) 離散數(shù)學(xué) (3) 數(shù)據(jù)結(jié)構(gòu)與算法 (4) 計(jì)算機(jī)組成原理 (5) 計(jì)算機(jī)網(wǎng)絡(luò) (6) 操作系統(tǒng) (7) 數(shù)據(jù)庫(kù) (8) 軟件工程第1頁(yè)/共96頁(yè) 離散數(shù)學(xué)研究的對(duì)象: 離散量及其之間的關(guān)系. 離散量與連續(xù)量及其之間的轉(zhuǎn)換. 現(xiàn)今計(jì)算機(jī)的處理對(duì)象是非常特殊的離散量: 0和1. 學(xué)習(xí)離散數(shù)學(xué)的目的: 1.培養(yǎng)各種能力. 2.為后繼專業(yè)課程的學(xué)習(xí)作知識(shí)上的準(zhǔn)備.第2頁(yè)/共96頁(yè) 離散數(shù)學(xué)的主要內(nèi)容: 1. 集合與關(guān)系 Chapter 1 集合、映射與運(yùn)算 Chapter 2 關(guān)系 2. 數(shù)理邏輯 Chapter 3 命題邏輯 Ch

2、apter 4 謂詞邏輯 3. 代數(shù)結(jié)構(gòu)(Chapter 5) 4. 圖論 Chapter 6 圖論 Chapter 7 幾類特殊的圖 5. 組合計(jì)數(shù)(Chapter 8)第3頁(yè)/共96頁(yè) 學(xué)習(xí)離散數(shù)學(xué)的方法: 1.預(yù)習(xí). 2.聽課. 3.復(fù)習(xí). 4. (分組)作業(yè).第4頁(yè)/共96頁(yè) 參考文獻(xiàn): 屈婉玲,耿素云, 張立昂, 離散數(shù)學(xué), 高等教育出版社, 2007. (108144學(xué)時(shí)) 傅彥, 顧小豐, 王慶先, 離散數(shù)學(xué)及其應(yīng)用, 高等教育出版社, 2008. (兩個(gè)學(xué)期)第5頁(yè)/共96頁(yè)Chapter 1 Sets, Mappings and Operations 集合是現(xiàn)代數(shù)學(xué)的最基本概

3、念(?). 映射又稱為函數(shù), 它是現(xiàn)代數(shù)學(xué)的基本概念, 可以借助于集合下定義. 運(yùn)算本質(zhì)上是映射, 但其研究有其特殊性. (關(guān)系也是集合)集合、映射、運(yùn)算及關(guān)系(Chapter 2)是貫穿于本書的一條主線.第6頁(yè)/共96頁(yè)1.1 集合的有關(guān)概念 1. 集合 在一定范圍內(nèi), 集合(set)是其具有某種特定性質(zhì)的對(duì)象匯集成的一個(gè)整體, 其中的每一個(gè)對(duì)象都稱為該集合的元素(element). 這里所指范圍是全集U(見圖1-1).(避免悖論!) 在數(shù)學(xué)中常用 表示整體. U第7頁(yè)/共96頁(yè) 若x是集合A中元素,則記xA, 否則xA. Fuzzy set ? 集合通常用大寫字母A, B, C, D,表示

4、. N是自然數(shù)集合,包括數(shù)0；Z是整數(shù)集合；Q是有理數(shù)集合；R是實(shí)數(shù)集合；C是復(fù)數(shù)集合.第8頁(yè)/共96頁(yè) P : 2, 3, 5, 7, 11, 13, 17, 19, 23等. (1) m|n: n = mq. (2) Dn. (3) 素?cái)?shù)測(cè)試與Mersenne素?cái)?shù): 2p - 1.第9頁(yè)/共96頁(yè) 表示集合的常用方法: (1)列舉法:0, 2, 4, 6, 8, N = 0, 1, 2, 3, . (2)描述法:x|x滿足的條件. 可簡(jiǎn)記: 直角三角形, 所有人 (3)遞歸法 自然數(shù)集合N可遞歸定義, 在后面章節(jié)定義命題公式及謂詞公式時(shí)還會(huì)用此法. 有限集合A的元素個(gè)數(shù)|A|, card(

5、A).第10頁(yè)/共96頁(yè) Remarks 1.集合中的元素可以是集合, 例如A = a, a, b, b, c. a, bA, a, bA. 2.集合之間的元素原則上是沒有次序的, 如 A = a, a, b, b, c就是 a, b, c , a, b; 3.集合中的元素原則上不重復(fù), 如a, a, b, b, b, c還是集合A. 不含有任意元素的集合稱為空集不含有任意元素的集合稱為空集(empty set), 記為記為或或 . ?|AAAS第11頁(yè)/共96頁(yè) 2.子集 A B, 特別地是任意集合的子集. A = B. Theorem 1-2(P3) (1) A A. (2) A B, B

6、 A A = B. (3) A B, B C A C. Theorem 1-3 A = B A B 且 B A.第12頁(yè)/共96頁(yè) 注意 與 的不同. 例1-2 由A B, B C可否得出A C? Solution 不成立,例如A = a, b, B = a, b, c, C = a, a, b, c. 課堂練習(xí): 4, 5. , ,cbabaAba, ,cbabaAba第13頁(yè)/共96頁(yè) 3. 冪集(power set) X = a, b P(X) = , a, b, a, b. P(P() = P() = , (P5, 6(1). , , (P5, 2)|)(XAAXP第14頁(yè)/共96頁(yè)

7、Theorem 1-4 Proof(加法原理) 由乘法原理證明?.2| )(|nXPnX,.,21naaaX .2) 11 (.121nnnnnnCCC.22.22:,.,nnA 第15頁(yè)/共96頁(yè) 4.n元組 Def 1-4 將n個(gè)元素(?)x1, x2, xn按一定順序排列就得到一個(gè)n元(有序)組(n-tuple). 線性代數(shù)中的n維向量(?): n = 2, n = 3(see below).,., ,.,),.,(212121nnnxxxxxxxxx?,.,21nxxx),.,(21naaa第16頁(yè)/共96頁(yè) n = 2: (x, y). n = 3: (x, y, z) 4元組? 顯

8、然, 一般說來(x, y) (y, x). 注意區(qū)別(a, b, c), (a, b), c), (a, (b, c)的不同.),(yxO),(zyxO.,),.,(),.,(2121iyxyyyxxxiinn),(xy第17頁(yè)/共96頁(yè) n維向量是n元組, 長(zhǎng)度為n的線性表是n元組, 抽象數(shù)據(jù)結(jié)構(gòu)Data_Structure = (D, S) 本身是一個(gè)2 元組. 2元組常稱為有序?qū)?ordered pair)或序偶. 5.笛卡兒積(cross product).,.,2 , 1,| ),.,(.2121niAxxxxAAAiinn.,.,2 , 1,| ),.,(.21niAxxxxAAA

9、Ainnn第18頁(yè)/共96頁(yè) 例1-4(P4) 設(shè)A = a, b, B = 1, 2, C = , 求A B, B A, A B C , B C. Solution AB C = (a, 1, ), (b, 1, ), (a, 2, ), (b, 2, ). BC = (1, ), (2, ) Remark A = B = . P5, 10?)2 ,(),1 ,(),2 ,(),1 ,(bbaaBA), 2(), 1 (), 2(), 1(bbaaAB第19頁(yè)/共96頁(yè) Theorem Hint 可推廣到更多個(gè)集合的笛卡兒積的情形: 作業(yè) 習(xí)題1.1 6, 9, 10.| ,|mnBAnBm

10、A.,| ),(ByAxyxBA.,.,2 , 1,| ),.,(.2121niAxxxxAAAiinn第20頁(yè)/共96頁(yè)1.2 映射的有關(guān)概念 1.映射的定義 映射mapping = 函數(shù)function. C語(yǔ)言是一種函數(shù)型語(yǔ)言: 從main開始. Def A, B:ABfBAf:第21頁(yè)/共96頁(yè) Ceiling function: Floor function: (取整函數(shù)) 復(fù)雜度: x x xbnnanT) 1(2)( RZ:T第22頁(yè)/共96頁(yè) 函數(shù)的表示: (1)解析式 (2)圖形 (3)表格(數(shù)值計(jì)算中出現(xiàn)較多) 函數(shù)符號(hào)的選取(P6):f, g, F,G, , sin, e

11、xp, main, add, average, 注意區(qū)別函數(shù)f與函數(shù)表達(dá)式f(x). 映射的兩個(gè)特點(diǎn): (1)全函數(shù); (2)唯一性. 1)( R,R:2xxff第23頁(yè)/共96頁(yè) B上A: 例1-5 Theorem 1-6 注意B上A的記號(hào)與該結(jié)論的關(guān)系.:|BAffBA.8,.,2 , 1|ifBiAx1x2x3y1y2BAf:.| ,|mAnBnBmABA第24頁(yè)/共96頁(yè) : )(),(1YfXf| )()(,:XxxfXfAXBAf)(,|)(,:1YxfAxxYfBYBAfXf(X)Y f-1(Y)第25頁(yè)/共96頁(yè) n元函數(shù)(n 1): float average(flot ar

12、ray, int n) n = 0: C語(yǔ)言中的無參函數(shù)? 一般處理方式: A到B的一個(gè)0元函數(shù)是B中某一個(gè)元素(see P136).,.,:21nAAAABAf,.),.,(2121nnAAAxxxxAx.),.,(),.,()(2121yxxxfxxxfxfnn第26頁(yè)/共96頁(yè) 2.映射的性質(zhì) (1)單射(injection)BAf:.)()(,212121xxxfxfAxx).()(,212121xfxfxxAxxfBA第27頁(yè)/共96頁(yè) (2)滿射(surjection) 例1-7 是Z到N的滿射, 但不是Z到Z的滿射(?). ).(,xfyAxBy.ran Bf f|)(xxfBA

13、第28頁(yè)/共96頁(yè) (3)雙射(bijection, one-to-one correspondence) 雙射又稱為一一對(duì)應(yīng):既單又滿. 例1-8 例1-9(P8),.3 , 2 , 1 , 0 , 1, 2, 3.,:Z,.6 , 5 , 4 , 3 , 2 , 1 , 0:N1O.21tanxyNZ :fR) , 0( :f第29頁(yè)/共96頁(yè) Def 1-11 有限集合A上自身的雙射稱為A上的置換(permutation). 例1-10 第一種方式:123123f,3213211p,3123212p,1233213p,2313214p,1323215p.2133216p第30頁(yè)/共96頁(yè)

14、 第二種方式: A = 1, 2, 3, 4上的所有置換有多少個(gè)? 4!),2)(13(),3)(12(),3)(2)(1 (321ppp).132(),123(),23)(1 (654ppp第31頁(yè)/共96頁(yè) 3. 逆映射 設(shè)f: AB, 將對(duì)應(yīng)關(guān)系f逆轉(zhuǎn)(改變方向), 一般來說, 不能得到B到A的映射: abc123第32頁(yè)/共96頁(yè) Def 1-12 設(shè)f: AB, 若將對(duì)應(yīng)關(guān)系f逆轉(zhuǎn)后能得出一個(gè)得到B到A的映射, 則稱該映射為f的逆映射(invertible function), 記為f-1.abc123第33頁(yè)/共96頁(yè) Theorem 1-7 f 的逆映射存在的充要條件是f是雙射.

15、 對(duì)于y = sin x, 當(dāng) 時(shí), 有反函數(shù), 常記為 當(dāng) 時(shí), y = sin x仍有反函數(shù), 但不能 記為arcsin. 顯然, 當(dāng) 時(shí), 無反函數(shù). 1 , 12,2:sin2,2x.2,2 1 , 1 :arcsin23,2x23, 0 x第34頁(yè)/共96頁(yè) 4. 復(fù)合映射(composition function) Theorem1-8 設(shè)f: A B, g: B C: 則h: A C.).()(,xfgxhAxxy=f(x)z=g(y)=g(f(x)hfg第35頁(yè)/共96頁(yè) Def 1-13 例1-12abc123fggfh第36頁(yè)/共96頁(yè) Remarks (1) y = si

16、n u, u = x2 未引入運(yùn)算符號(hào),有時(shí)是不方便的. (2)順序問題: 有些專業(yè)書 但會(huì)出現(xiàn)一些混亂.sin2xy ).()(xfgxgf).()(xfgxfg第37頁(yè)/共96頁(yè) 例1-13(P9) f: RR, f(x) = x2, g: RR, g(x) = x + 2, 求fg和gf. Solution x R: (fg)(x) = g(f(x) = g(x2) = x2 + 2. (gf)(x) = f(g(x) = f(x+2) = (x+2)2. Remark fg gf.第38頁(yè)/共96頁(yè) IA: A A Theorem 1-9 理解:雙射BAf:.,11BAIffIffxx

17、 abc123abcf1f123abc1231ff第39頁(yè)/共96頁(yè) Theorem 1-10 (1)若f和g是單射, 則fg是單射. (2)若f和g是滿射, 則fg是滿射. (3)若f和g是雙射, 則fg是雙射. Proof (2)任意z C, 由于g是滿射, 存在y B, 使得z = g(y). 又由于f是滿射, 存在x A, 使得y = f(x). 于是z = g(y) = g(f(x) = (fg)(x). 故fg是滿射(see below).:,:CBgBAf第40頁(yè)/共96頁(yè) Theorem 1-11 (1)若fg是單射, 則f是單射, g不一定. (2)若fg是滿射, 則g是滿射

18、, f 不一定. (3)若fg是雙射, 則f是單射且g是滿射. Proof (1)任意x1, x2 A, 若f(x1) = f(x2), x)(xfy zyg)()(xgfz.:,:CBgBAf第41頁(yè)/共96頁(yè) 顯然, g(f(x1) = g(f(x2), 即(fg)(x1) = (fg)(x2). 由于fg是單射, 因此 x1 = x2. 故f是單射. g不一定(見上圖)?ab123gfABC第42頁(yè)/共96頁(yè) 一般來說fg gf, 但 Theorem 1-12 作業(yè) 習(xí)題1.2: 3, 4, 7, 8, 12. Hint 7. 使用定理1-10和第3題. 8. 使用第7題結(jié)論. 12.使

19、用第7題結(jié)論.)()(hgfhgfhgf第43頁(yè)/共96頁(yè)1.3 運(yùn)算的定義及性質(zhì) 運(yùn)算是討論對(duì)象之間有何聯(lián)系的一種方法. 其實(shí)，我們已經(jīng)接觸過很多運(yùn)算,如數(shù)之間的加法運(yùn)算、多項(xiàng)式之間的乘法運(yùn)算、矩陣的逆運(yùn)算、向量的線性運(yùn)算等.在討論離散數(shù)據(jù)結(jié)構(gòu)時(shí)也會(huì)經(jīng)常遇到各種各樣的運(yùn)算，如在下節(jié)即將研究的集合間的運(yùn)算. 雖然運(yùn)算本質(zhì)上是映射，但研究的側(cè)重點(diǎn)不同，在運(yùn)算中更注重于運(yùn)算滿足的一些運(yùn)算性質(zhì)，而根據(jù)這些性質(zhì)可以對(duì)一些離散對(duì)象分門別類進(jìn)行討論. 因此，有必要先把運(yùn)算的一般定義及其性質(zhì)進(jìn)行討論.第44頁(yè)/共96頁(yè) 1. 運(yùn)算的定義 (1)定義 A1, A2, An到B的n元運(yùn)算(n-ary opera

20、tion): A到B(或A上)的n元運(yùn)算: A上的n元封閉運(yùn)算(代數(shù)運(yùn)算):BAAAfn.:21BAAAfn.:AAAAfn.:.),.,(,.,2121AxxxfAxxxnn?),.,(21nxxxfy 第45頁(yè)/共96頁(yè) (n = 0? 一般處理方式: A到B的一個(gè)0元運(yùn)算可理解為B中某一個(gè)元素.) 例1-14 f: Z N, f(x) = |x|. 例1-15(模運(yùn)算) f: Z N, f(x) = x(mod k), x = qk + r, 0 r 1. Proof (?)nkknSN1),()., 1() 1, 1(),(knkSknSknS第85頁(yè)/共96頁(yè) 2. 集合的覆蓋 De

21、f 設(shè)A是集合, 由A的若干非空子集構(gòu)成的集合稱為A的覆蓋(covering), 如果這些非空子集的并等于A. a, b, b, cabc第86頁(yè)/共96頁(yè) 集合的劃分 集合的覆蓋, 但反過來不成立. A = a, b, c上所有不同的覆蓋有哪些? 作業(yè) 習(xí)題1.5 1, 4, 7.第87頁(yè)/共96頁(yè)1.6 集合的對(duì)等 集合的對(duì)等, 它是集合間的另一種關(guān)系. 通過集合對(duì)等以及相關(guān)內(nèi)容的學(xué)習(xí), 加深對(duì)函數(shù)概念的理解, 提高正確使用函數(shù)工具作為研究手段的能力. 1.集合對(duì)等(equivalent) Def A B: 存在雙射f : A B.第88頁(yè)/共96頁(yè) N E. ZN? (0, 1) R. G. Cantor. N N N. Theorem 1-28(對(duì)等的性質(zhì)) (1) A A. (2) A B B A. (3) A B, B C A C.第89頁(yè)/共96頁(yè) 2. 無限集合 有了集合對(duì)等的概念, 就可以給出無限集合及有限集合的嚴(yán)格定義. Def 設(shè)A是集合, 若存在A的一個(gè)子集與自然數(shù)集合N對(duì)等, 則稱A為無限集合(infinite set), 否則稱A為有限集合(finite set). N. 0, 1.第90頁(yè)/共96頁(yè) 3. 集合的基數(shù) 有限集合的基數(shù)就是的元素個(gè)數(shù). 借助于集合對(duì)等概念, 可以將其擴(kuò)展到無限集合.