第1章-集合映射與運(yùn)算.ppt

1、離散數(shù)學(xué)是計(jì)算機(jī)各專業(yè)的專業(yè)基礎(chǔ)課. 離散數(shù)學(xué)研究的對象: 離散量及其之間的關(guān)系. 離散量與連續(xù)量及其之間的轉(zhuǎn)換. 現(xiàn)今計(jì)算機(jī)的處理對象是非常特殊的離散量: 0和1. 學(xué)習(xí)離散數(shù)學(xué)的目的: 1.培養(yǎng)各種能力. 2.為后繼專業(yè)課程的學(xué)習(xí)作知識上的準(zhǔn)備.,離散數(shù)學(xué)的基本內(nèi)容: 1.集合與關(guān)系 Chapter 1 集合、映射與運(yùn)算 Chapter 2 關(guān)系 2.數(shù)理邏輯 Chapter 3 命題邏輯 Chapter 4 謂詞邏輯 3.代數(shù)結(jié)構(gòu) Chapter 5 群、環(huán)和域 Chapter 6 格與布爾代數(shù) 4.圖論 Chapter 7 圖論 Chapter 8 幾類特殊的圖,學(xué)習(xí)離散數(shù)學(xué)的方法:

2、1.預(yù)習(xí). 2.聽課. 3.復(fù)習(xí). 4.作業(yè). 參考文獻(xiàn): 耿素云 屈婉玲,離散數(shù)學(xué)(修訂版),高等教育出版社,2004. Kenneth H. Rosen, Discrete Mathematics and Its Applications (Fourth Edition), McGraw-Hill Companies, Inc.1998.(有中譯本,2002),Chapter 1 Sets, Mappings and Operations,集合是現(xiàn)代數(shù)學(xué)的最基本概念(?). 映射又稱為函數(shù), 它是現(xiàn)代數(shù)學(xué)的基本概念, 可以借助于集合下定義. 運(yùn)算本質(zhì)上是映射, 但其研究有其特殊性. 集合、

3、映射、運(yùn)算及關(guān)系(Chapter 2)是貫穿于本書的一條主線.,1.1 集合的有關(guān)概念,1. 集合 集合(用處?)已滲透到自然科學(xué)以及社會科學(xué)的各個研究領(lǐng)域, 在信息的表示及處理中,可以借助于集合去實(shí)現(xiàn)數(shù)據(jù)的刪節(jié)、插入、排序以及描述數(shù)據(jù)間的關(guān)系. 在一定范圍內(nèi), 集合(set)是其具有某種特定性質(zhì)的對象匯集成的一個整體, 其中的每一個對象都稱為該集合的元素(element). 這里所指范圍是全集U(見圖1-1).(避免悖論!) 在數(shù)學(xué)中常用 表示整體. 若x是集合A中元素,則記xA, 否則xA.,常見的數(shù)的集合用黑正體字母表示: N是自然數(shù)集合,包括數(shù)0；Z是整數(shù)集合；Q是有理數(shù)集合；R是實(shí)數(shù)

4、集合；C是復(fù)數(shù)集合. 表示集合的常用方法: (1)列舉法:0, 2, 4, 6, 8, N = 0, 1, 2, 3, . (2)描述法:x|x滿足的條件. (3)遞歸法 自然數(shù)集合N可遞歸定義, 在后面章節(jié)定義命題公式及謂詞公式時還會用此法. 有限集合A的元素個數(shù)|A|.,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. 不含有任意元

5、素的集合稱為空集(empty set), 記為或 .,2.子集 A B, 特別地是任意集合的子集. A = B. Theorem 1-2(P3) (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.,注意 與 的不同. 例1-2 由A B, B C可否得出A C? Solution 不成立,例如A = a, b, B = a, b, c, C = a, a, b, c. 課堂練習(xí): 4, 5. 3. 冪集(power set) X = a, b P(X) = , a, b, a, b. P(P()

6、 = P() = , (P5, 6(1). , , (P5, 2),Theorem 1-4 Proof 由乘法原理證明?,4.n元組 Def 1-4 將n個元素(?)x1, x2, xn按一定順序排列就得到一個n元(有序)組(n-tuple). 在數(shù)據(jù)結(jié)構(gòu)中就是一個線性表.,n = 2: (x, y). n = 3: (x, y, z) 4元組? 顯然, 一般說來(x, y) (y, x). 注意區(qū)別(a, b, c), (a, b), c), (a, (b, c)的不同.,n維向量是n元組, 長度為n的線性表是n元組, 抽象數(shù)據(jù)結(jié)構(gòu)Data_Structure = (D, S) 本身是一個2

7、 元組. 2元組常稱為有序?qū)?ordered pair)或序偶. 5.笛卡兒積(cross product),例1-4(P4) 設(shè)A = a, b, B = 1, 2, C = , 求AB, BA, BC, ABC. Solution BC = (1, ), (2, ) AB C = (a, 1, ), (b, 1, ), (a, 2, ), (b, 2, ).,Remark A = A = . P5, 10? Theorem Hint 可推廣到更多個集合的笛卡兒積的情形: 作業(yè) 習(xí)題1.1 6, 9, 10.,1.2 映射的有關(guān)概念,1.映射的定義 映射mapping=函數(shù)function.

8、 C語言是一種函數(shù)型語言: 從main開始. Def,A,B,函數(shù)的表示: (1)解析式 (2)圖形 (3)表格(數(shù)值計(jì)算中出現(xiàn)較多) 函數(shù)符號的選取(P6):f, g, F,G, , sin, exp, main, add, average, 注意區(qū)別函數(shù)f與函數(shù)表達(dá)式f(x). 映射的兩個特點(diǎn): (1)全函數(shù); (2)唯一性.,B上A: 例1-5 Theorem 1-6 注意B上A的記號與該結(jié)論的關(guān)系.,x1 x2 x3,y1 y2,像與原像,X,f(X),Y,f-1(Y),n元函數(shù)(n 1): float average(float array, int n),2.映射的性質(zhì) (1)單射

9、(injection),(2)滿射(surjection) 例1-7 是Z到N的滿射, 但不是Z到Z的滿射(?).,(3)雙射(bijection, one-to-one correspondence) 雙射又稱為一一對應(yīng):既單又滿. 例1-8 例1-9(P8),例1-10 Def 1-11 有限集合A上自身的雙射稱為A上的置換(permutation). A = 1, 2, 3, 4上的所有置換有多少個? 4!,1 2 3,1 2 3,3. 逆映射 設(shè)f: AB, 將對應(yīng)關(guān)系f逆轉(zhuǎn)(改變方向), 一般來說, 不能得到B到A的映射:,a b c,1 2 3,Def 1-12 設(shè)f: AB, 若

10、將對應(yīng)關(guān)系f逆轉(zhuǎn)后能得出一個得到B到A的映射, 則稱該映射為f的逆映射(invertible function), 記為f-1.,a b c,1 2 3,Theorem 1-7 f 的逆映射存在的充要條件是f是雙射. 對于y = sin x, 當(dāng) 時, 有反函數(shù), 常記為 當(dāng) 時, y = sin x仍有反函數(shù), 但不能 記為arcsin. 顯然, 當(dāng) 時, 無反函數(shù).,4. 復(fù)合映射(composition function) Theorem1-8 設(shè)f: A B, g: B C: 則h: A C.,x,y=f(x),z=g(y)= g(f(x),Def 1-13 例1-12,a b c,1

11、 2 3, ,Remarks (1) y = sin u, u = x2 未引入運(yùn)算符號,有時是不方便的. (2)順序問題: 有些專業(yè)書 但會出現(xiàn)一些混亂.,例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.,IA: A A Theorem 1-9 理解:,a b c,1 2 3,a b c,1 2 3,a b c,1 2 3,Theor

12、em 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).,Theorem 1-11 (1)若fg是單射, 則f是單射, g不一定. (2)若fg是滿射, 則g是滿射, f 不一定. (3)若fg是雙射, 則f是單射且g是滿射. Proof (1)任意x1, x2 A, 若f(x1

13、) = f(x2),顯然, g(f(x1) = g(f(x2), 即(fg)(x1) = (fg)(x2). 由于fg是單射, 因此 x1 = x2. 故f是單射. g不一定(見上圖)?,一般來說fg gf, 但 Theorem 1-12 作業(yè) 習(xí)題1.2: 3, 4, 7, 8, 12. Hint 7. 使用定理1-10和第3題. 8. 使用第7題結(jié)論. 12.使用第7題結(jié)論.,1.3 運(yùn)算的定義及性質(zhì),運(yùn)算是討論對象之間有何聯(lián)系的一種方法. 其實(shí)，我們已經(jīng)接觸過很多運(yùn)算,如數(shù)之間的加法運(yùn)算、多項(xiàng)式之間的乘法運(yùn)算、矩陣的逆運(yùn)算、向量的線性運(yùn)算等.在討論離散數(shù)據(jù)結(jié)構(gòu)時也會經(jīng)常遇到各種各樣的運(yùn)算

14、，如在下節(jié)即將研究的集合間的運(yùn)算. 雖然運(yùn)算本質(zhì)上是映射，但研究的側(cè)重點(diǎn)不同，在運(yùn)算中更注重于運(yùn)算滿足的一些運(yùn)算性質(zhì)，而根據(jù)這些性質(zhì)可以對一些離散對象分門別類進(jìn)行討論. 因此，有必要先把運(yùn)算的一般定義及其性質(zhì)進(jìn)行討論.,1. 運(yùn)算的定義 (1)定義 A1, A2, An到B的n元運(yùn)算(n-ary operation): A到B(或A上)的n元運(yùn)算: A上的n元封閉運(yùn)算(代數(shù)運(yùn)算):,例1-14 f: Z N, f(x) = |x|. 例1-15 f: Z N, f(x) = x(mod k), x = qk + r, 0 r k: 8 = 2 3 + 2; -5 = -2 3 + 1. 例1-

15、16 例1-17,(2)運(yùn)算符號的選取 函數(shù)符號f, g, , F, G, ,; 常見運(yùn)算符號+, , /, ,; 自定義符號 , , (3)運(yùn)算符號的位置,(4)運(yùn)算表 A = a, b, c, *: 思考 A上封閉的1元運(yùn)算, 2元運(yùn)算和3元運(yùn)算的個數(shù)是多少?,2.運(yùn)算的性質(zhì) (1)對合(involutive)性 Def 設(shè)*是A上的1元代數(shù)運(yùn)算, 例,(2)冪等(idempotent)性 冪等元x: A關(guān)于*具有冪等性: A中每個元素對于*都是冪等元. 兩個例子:,(3)交換(commutative)性 Def 設(shè)*是A上的2元代數(shù)運(yùn)算, 若對于任意的x, y A, 均有 則稱*滿足交換

16、律. 顯然, 映射的復(fù)合運(yùn)算不滿足交換律: 加法運(yùn)算”+”滿足交換律, 而減法運(yùn)算”-”不滿足交換律: 2 3 3 2. 如何根據(jù)定義的運(yùn)算得出運(yùn)算具有交換性?,(4)結(jié)合(associative)性 映射的復(fù)合運(yùn)算滿足結(jié)合律: 加法運(yùn)算“+”滿足結(jié)合律, 而減法運(yùn)算“-”不滿足結(jié)合律: (2 - 3) - 5 2 - (3 5). 如何根據(jù)運(yùn)算表判斷運(yùn)算是否可(交換)結(jié)合?,(5)單位元素. Def 設(shè)*是A上的2元代數(shù)運(yùn)算, 若存在e A,對于任意的x A, 下列條件均成立： 則稱e為集合A關(guān)于*運(yùn)算的單位元素或幺元素.(幺元律?) 例 Z關(guān)于加法運(yùn)算+的單位元素為0,而Z關(guān)于乘法運(yùn)算“.

17、”的單位元素為1,Z關(guān)于減法運(yùn)算-沒有單位元素. 定理：若A關(guān)于*運(yùn)算存在單位元素，則單位元素是唯一的,(6)零元素(zero element). Def 設(shè)*是A上的2元代數(shù)運(yùn)算, 若存在 A,對于任意的x A, 下列條件均成立： 則稱為集合A關(guān)于*運(yùn)算的零元素.(零元律?) 例1-28 Z關(guān)于加法運(yùn)算+和減法運(yùn)算-均沒有零元素, 而Z關(guān)于乘法運(yùn)算的零元素為0. 定理：若A關(guān)于*運(yùn)算存在零元素，則零元素是唯一的,(7)逆元素(invertible element) 若A關(guān)于運(yùn)算*有單位元素e, 則可以討論A中取定的元素x是否有逆元. Def 設(shè)*是A上的2元代數(shù)運(yùn)算且有單位元素e,若對于x

18、A,存在y A,使得下列條件均成立: 則稱y為x的關(guān)于*的逆元素.,顯然,一個方陣關(guān)于乘法運(yùn)算的逆元就是其逆矩陣, 因?yàn)閱挝辉厥菃挝痪仃? 對于函數(shù)來說,一個映射關(guān)于函數(shù)的復(fù)合運(yùn)算的逆元就是其逆映射, 當(dāng)然只有雙射才有逆元,其單位元素是恒等映射. 例1-29 R中各元素關(guān)于加法運(yùn)算+和乘法運(yùn)算逆元素. 逆元素唯一？,(8)消去(cancellation)性. Def 設(shè)*是A上的2元代數(shù)運(yùn)算, 若A關(guān)于*運(yùn)算有零元則記為 , 如果對于任意的x, y , z A, 只要x , 那么下列條件均成立： 則稱*具有消去性, 或稱*滿足消去律. 例1-31 Z上的加法運(yùn)算+和乘法運(yùn)算均滿足消去律. 例

19、1-32 實(shí)數(shù)集R上的所有2階方陣組成的集合,關(guān)于矩陣乘法運(yùn)算不滿足消去律.,(9)分配(distributive)性. Def 設(shè)*和是集合A上的兩個2元代數(shù)運(yùn)算,若對于任意x, y , z A, 有 則稱*對于是可分配的. 例1-33 實(shí)數(shù)集合R上的乘法運(yùn)算對加法運(yùn)算+可分配,但加法運(yùn)算+對乘法運(yùn)算不可分配.,(10)吸收(absorptive)性 Def 設(shè)*和是集合A上的兩個2元代數(shù)運(yùn)算,若對于任意x, y A, 有 則稱*對于是可吸收的. 如果*和是集合A上的兩個可交換的2元代數(shù)運(yùn)算,則*運(yùn)算對運(yùn)算可吸收只需要滿足兩條件之一即可,但吸收性本身不需要*和可交換.,(11)德摩根(De

20、Morgan)律 Def 設(shè)是集合A上的1元代數(shù)運(yùn)算, *和是A上的兩個2元代數(shù)運(yùn)算, 若對于任意x, y A, 均有下面兩個等式成立: 則稱這三種運(yùn)算滿足德摩根律. 課堂練習(xí) 習(xí)題1.3 4. 作業(yè) 習(xí)題1.3 7, 11.,1.4 集合的運(yùn)算,最常見的集合運(yùn)算是并、交和補(bǔ). 1.并(union)運(yùn)算,Theorem 是包含A和B的最小集合. Theorem1-17 (并運(yùn)算滿足的性質(zhì)) (1) (2) (3) (4)單位元 (5)零元,例1-38 設(shè)f : A B, X, Y A, 則 Proof (1) (2),2. 交(intersection)運(yùn)算 Theorem 是包含在A和B的最

21、大集合.,Theorem1-19 (交運(yùn)算滿足的性質(zhì)) (1) (2) (3) (4)單位元 (5)零元 例1-40:舉例?,Theorem 1-20(并運(yùn)算與交運(yùn)算之間所滿足的性質(zhì).) (1)吸收性. (2)分配性. 例1-41(P20),3. 補(bǔ)(complement)運(yùn)算 例1-42 (A的補(bǔ)集依賴于全集U的選取.) A=a, b, c: (1)U = a, b, c, d (2)U = a, b, c, d,a,b,b,c,c,排中律成立: . 排中律?,集合的補(bǔ)運(yùn)算和集合的并交運(yùn)算滿足De Morgan律: 表(P21). (cf. P86 & P182,與布爾代數(shù)的性質(zhì)完全類似?!

22、 因?yàn)樗鼈兪翘厥獾? 常見的布爾代數(shù).),4. 差(subtraction)運(yùn)算 例1-43,Theorem 1-23(P22) Proof 例1-45(P22),例1-46 . 例1-47(P22) Solution 由上例知, A (B C) = ,5. 對稱差(symmetric difference)運(yùn)算 See Venn Figure below. 例1-48,Theorem(對稱差運(yùn)算的性質(zhì)) (1)交換性: (2)單位元: A = A. (3) A A = . (4)結(jié)合性:,例1-49(消去律) Hint,例1-50 A B = A = B. Proof ()顯然. () A

23、B = A B = 且B A = 例1-51 ( 對 可分配),思考 還能定義集合的其他運(yùn)算? 加法原理. 乘法原理. 容斥原理: 容斥原理的另一種形式: 推廣到n個集合情形(P24, 15)? 作業(yè) 習(xí)題1.4 5, 8, 10, 13.,1.5 集合的劃分與覆蓋,集合的劃分與覆蓋是集合中的重要內(nèi)容之一. 集合的劃分就是集合元素間的一種分類. 在信息科學(xué)中,可以將知識庫看作集合的一種劃分. 因此, 研究集合的劃分具有特別重要的意義. 比集合的劃分更廣的概念是集合的覆蓋. 這些內(nèi)容在下章會用到. 1. 集合的劃分(partition),Def (1) , iI. (2) , i j. (3)

24、Hardware?,例1-53 設(shè)A = a, b, c, 則A的所有不同的劃分分別為:,1和2的交叉劃分: . 1是2的加細(xì)劃分:,|A| = n, A的不同劃分的個數(shù)N: S(n, k)? Theorem n 1. Proof (?),2. 集合的覆蓋 Def 設(shè)A是集合, 由A的若干非空子集構(gòu)成的集合稱為A的覆蓋(covering), 如果這些非空子集的并等于A. a, b, b, c,集合的劃分 集合的覆蓋, 但反過來不成立. A = a, b, c上所有不同的覆蓋有哪些? 作業(yè) 習(xí)題1.5 1, 4, 7.,1.6 集合的對等,集合的對等, 它是集合間的另一種關(guān)系. 通過集合對等以及相關(guān)內(nèi)容的學(xué)習(xí), 加深對