集合映射與運算PPT課件

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

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

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

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

5、A).第10頁/共96頁 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.集合中的元素原則上不重復, 如a, a, b, b, b, c還是集合A. 不含有任意元素的集合稱為空集不含有任意元素的集合稱為空集(empty set), 記為記為或或 . ?|AAAS第11頁/共96頁 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頁/共96頁 注意 與 的不同. 例1-2 由A B, B C可否得出A C? Solution 不成立,例如A = a, b, B = a, b, c, C = a, a, b, c. 課堂練習: 4, 5. , ,cbabaAba, ,cbabaAba第13頁/共96頁 3. 冪集(power set) X = a, b P(X) = , a, b, a, b. P(P() = P() = , (P5, 6(1). , , (P5, 2)|)(XAAXP第14頁/共96頁

7、Theorem 1-4 Proof(加法原理) 由乘法原理證明?.2| )(|nXPnX,.,21naaaX .2) 11 (.121nnnnnnCCC.22.22:,.,nnA 第15頁/共96頁 4.n元組 Def 1-4 將n個元素(?)x1, x2, xn按一定順序排列就得到一個n元(有序)組(n-tuple). 線性代數中的n維向量(?): n = 2, n = 3(see below).,., ,.,),.,(212121nnnxxxxxxxxx?,.,21nxxx),.,(21naaa第16頁/共96頁 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頁/共96頁 n維向量是n元組, 長度為n的線性表是n元組, 抽象數據結構Data_Structure = (D, S) 本身是一個2 元組. 2元組常稱為有序對(ordered pair)或序偶. 5.笛卡兒積(cross product).,.,2 , 1,| ),.,(.2121niAxxxxAAAiinn.,.,2 , 1,| ),.,(.21niAxxxxAAA

9、Ainnn第18頁/共96頁 例1-4(P4) 設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頁/共96頁 Theorem Hint 可推廣到更多個集合的笛卡兒積的情形: 作業(yè) 習題1.1 6, 9, 10.| ,|mnBAnBm

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

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

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

13、第28頁/共96頁 (3)雙射(bijection, one-to-one correspondence) 雙射又稱為一一對應:既單又滿. 例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頁/共96頁 Def 1-11 有限集合A上自身的雙射稱為A上的置換(permutation). 例1-10 第一種方式:123123f,3213211p,3123212p,1233213p,2313214p,1323215p.2133216p第30頁/共96頁

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

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

16、n u, u = x2 未引入運算符號,有時是不方便的. (2)順序問題: 有些專業(yè)書 但會出現一些混亂.sin2xy ).()(xfgxgf).()(xfgxfg第37頁/共96頁 例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頁/共96頁 IA: A A Theorem 1-9 理解:雙射BAf:.,11BAIffIffxx

17、 abc123abcf1f123abc1231ff第39頁/共96頁 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頁/共96頁 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頁/共96頁 顯然, g(f(x1) = g(f(x2), 即(fg)(x1) = (fg)(x2). 由于fg是單射, 因此 x1 = x2. 故f是單射. g不一定(見上圖)?ab123gfABC第42頁/共96頁 一般來說fg gf, 但 Theorem 1-12 作業(yè) 習題1.2: 3, 4, 7, 8, 12. Hint 7. 使用定理1-10和第3題. 8. 使用第7題結論. 12.使

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

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

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