




下載本文檔
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、離散數(shù)學是計算機各專業(yè)的專業(yè)基礎課. 離散數(shù)學研究的對象: 離散量及其之間的關系. 離散量與連續(xù)量及其之間的轉換. 現(xiàn)今計算機的處理對象是非常特殊的離散量: 0和1. 學習離散數(shù)學的目的: 1.培養(yǎng)各種能力. 2.為后繼專業(yè)課程的學習作知識上的準備.,離散數(shù)學的基本內容: 1.集合與關系 Chapter 1 集合、映射與運算 Chapter 2 關系 2.數(shù)理邏輯 Chapter 3 命題邏輯 Chapter 4 謂詞邏輯 3.代數(shù)結構 Chapter 5 群、環(huán)和域 Chapter 6 格與布爾代數(shù) 4.圖論 Chapter 7 圖論 Chapter 8 幾類特殊的圖,學習離散數(shù)學的方法:
2、1.預習. 2.聽課. 3.復習. 4.作業(yè). 參考文獻: 耿素云 屈婉玲,離散數(shù)學(修訂版),高等教育出版社,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ù)學的最基本概念(?). 映射又稱為函數(shù), 它是現(xiàn)代數(shù)學的基本概念, 可以借助于集合下定義. 運算本質上是映射, 但其研究有其特殊性. 集合、
3、映射、運算及關系(Chapter 2)是貫穿于本書的一條主線.,1.1 集合的有關概念,1. 集合 集合(用處?)已滲透到自然科學以及社會科學的各個研究領域, 在信息的表示及處理中,可以借助于集合去實現(xiàn)數(shù)據(jù)的刪節(jié)、插入、排序以及描述數(shù)據(jù)間的關系. 在一定范圍內, 集合(set)是其具有某種特定性質的對象匯集成的一個整體, 其中的每一個對象都稱為該集合的元素(element). 這里所指范圍是全集U(見圖1-1).(避免悖論!) 在數(shù)學中常用 表示整體. 若x是集合A中元素,則記xA, 否則xA.,常見的數(shù)的集合用黑正體字母表示: N是自然數(shù)集合,包括數(shù)0;Z是整數(shù)集合;Q是有理數(shù)集合;R是實數(shù)
4、集合;C是復數(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.集合中的元素原則上不重復, 如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. 課堂練習: 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ù)結構中就是一個線性表.,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ù)結構Data_Structure = (D, S) 本身是一個2
7、 元組. 2元組常稱為有序對(ordered pair)或序偶. 5.笛卡兒積(cross product),例1-4(P4) 設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è) 習題1.1 6, 9, 10.,1.2 映射的有關概念,1.映射的定義 映射mapping=函數(shù)function.
8、 C語言是一種函數(shù)型語言: 從main開始. Def,A,B,函數(shù)的表示: (1)解析式 (2)圖形 (3)表格(數(shù)值計算中出現(xiàn)較多) 函數(shù)符號的選取(P6):f, g, F,G, , sin, exp, main, add, average, 注意區(qū)別函數(shù)f與函數(shù)表達式f(x). 映射的兩個特點: (1)全函數(shù); (2)唯一性.,B上A: 例1-5 Theorem 1-6 注意B上A的記號與該結論的關系.,x1 x2 x3,y1 y2,像與原像,X,f(X),Y,f-1(Y),n元函數(shù)(n 1): float average(float array, int n),2.映射的性質 (1)單射
9、(injection),(2)滿射(surjection) 例1-7 是Z到N的滿射, 但不是Z到Z的滿射(?).,(3)雙射(bijection, one-to-one correspondence) 雙射又稱為一一對應:既單又滿. 例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. 逆映射 設f: AB, 將對應關系f逆轉(改變方向), 一般來說, 不能得到B到A的映射:,a b c,1 2 3,Def 1-12 設f: AB, 若
10、將對應關系f逆轉后能得出一個得到B到A的映射, 則稱該映射為f的逆映射(invertible function), 記為f-1.,a b c,1 2 3,Theorem 1-7 f 的逆映射存在的充要條件是f是雙射. 對于y = sin x, 當 時, 有反函數(shù), 常記為 當 時, y = sin x仍有反函數(shù), 但不能 記為arcsin. 顯然, 當 時, 無反函數(shù).,4. 復合映射(composition function) Theorem1-8 設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 未引入運算符號,有時是不方便的. (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è) 習題1.2: 3, 4, 7, 8, 12. Hint 7. 使用定理1-10和第3題. 8. 使用第7題結論. 12.使用第7題結論.,1.3 運算的定義及性質,運算是討論對象之間有何聯(lián)系的一種方法. 其實,我們已經接觸過很多運算,如數(shù)之間的加法運算、多項式之間的乘法運算、矩陣的逆運算、向量的線性運算等.在討論離散數(shù)據(jù)結構時也會經常遇到各種各樣的運算
14、,如在下節(jié)即將研究的集合間的運算. 雖然運算本質上是映射,但研究的側重點不同,在運算中更注重于運算滿足的一些運算性質,而根據(jù)這些性質可以對一些離散對象分門別類進行討論. 因此,有必要先把運算的一般定義及其性質進行討論.,1. 運算的定義 (1)定義 A1, A2, An到B的n元運算(n-ary operation): A到B(或A上)的n元運算: A上的n元封閉運算(代數(shù)運算):,例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)運算符號的選取 函數(shù)符號f, g, , F, G, ,; 常見運算符號+, , /, ,; 自定義符號 , , (3)運算符號的位置,(4)運算表 A = a, b, c, *: 思考 A上封閉的1元運算, 2元運算和3元運算的個數(shù)是多少?,2.運算的性質 (1)對合(involutive)性 Def 設*是A上的1元代數(shù)運算, 例,(2)冪等(idempotent)性 冪等元x: A關于*具有冪等性: A中每個元素對于*都是冪等元. 兩個例子:,(3)交換(commutative)性 Def 設*是A上的2元代數(shù)運算, 若對于任意的x, y A, 均有 則稱*滿足交換
16、律. 顯然, 映射的復合運算不滿足交換律: 加法運算”+”滿足交換律, 而減法運算”-”不滿足交換律: 2 3 3 2. 如何根據(jù)定義的運算得出運算具有交換性?,(4)結合(associative)性 映射的復合運算滿足結合律: 加法運算“+”滿足結合律, 而減法運算“-”不滿足結合律: (2 - 3) - 5 2 - (3 5). 如何根據(jù)運算表判斷運算是否可(交換)結合?,(5)單位元素. Def 設*是A上的2元代數(shù)運算, 若存在e A,對于任意的x A, 下列條件均成立: 則稱e為集合A關于*運算的單位元素或幺元素.(幺元律?) 例 Z關于加法運算+的單位元素為0,而Z關于乘法運算“.
17、”的單位元素為1,Z關于減法運算-沒有單位元素. 定理:若A關于*運算存在單位元素,則單位元素是唯一的,(6)零元素(zero element). Def 設*是A上的2元代數(shù)運算, 若存在 A,對于任意的x A, 下列條件均成立: 則稱為集合A關于*運算的零元素.(零元律?) 例1-28 Z關于加法運算+和減法運算-均沒有零元素, 而Z關于乘法運算的零元素為0. 定理:若A關于*運算存在零元素,則零元素是唯一的,(7)逆元素(invertible element) 若A關于運算*有單位元素e, 則可以討論A中取定的元素x是否有逆元. Def 設*是A上的2元代數(shù)運算且有單位元素e,若對于x
18、A,存在y A,使得下列條件均成立: 則稱y為x的關于*的逆元素.,顯然,一個方陣關于乘法運算的逆元就是其逆矩陣, 因為單位元素是單位矩陣. 對于函數(shù)來說,一個映射關于函數(shù)的復合運算的逆元就是其逆映射, 當然只有雙射才有逆元,其單位元素是恒等映射. 例1-29 R中各元素關于加法運算+和乘法運算逆元素. 逆元素唯一?,(8)消去(cancellation)性. Def 設*是A上的2元代數(shù)運算, 若A關于*運算有零元則記為 , 如果對于任意的x, y , z A, 只要x , 那么下列條件均成立: 則稱*具有消去性, 或稱*滿足消去律. 例1-31 Z上的加法運算+和乘法運算均滿足消去律. 例
19、1-32 實數(shù)集R上的所有2階方陣組成的集合,關于矩陣乘法運算不滿足消去律.,(9)分配(distributive)性. Def 設*和是集合A上的兩個2元代數(shù)運算,若對于任意x, y , z A, 有 則稱*對于是可分配的. 例1-33 實數(shù)集合R上的乘法運算對加法運算+可分配,但加法運算+對乘法運算不可分配.,(10)吸收(absorptive)性 Def 設*和是集合A上的兩個2元代數(shù)運算,若對于任意x, y A, 有 則稱*對于是可吸收的. 如果*和是集合A上的兩個可交換的2元代數(shù)運算,則*運算對運算可吸收只需要滿足兩條件之一即可,但吸收性本身不需要*和可交換.,(11)德摩根(De
20、Morgan)律 Def 設是集合A上的1元代數(shù)運算, *和是A上的兩個2元代數(shù)運算, 若對于任意x, y A, 均有下面兩個等式成立: 則稱這三種運算滿足德摩根律. 課堂練習 習題1.3 4. 作業(yè) 習題1.3 7, 11.,1.4 集合的運算,最常見的集合運算是并、交和補. 1.并(union)運算,Theorem 是包含A和B的最小集合. Theorem1-17 (并運算滿足的性質) (1) (2) (3) (4)單位元 (5)零元,例1-38 設f : A B, X, Y A, 則 Proof (1) (2),2. 交(intersection)運算 Theorem 是包含在A和B的最
21、大集合.,Theorem1-19 (交運算滿足的性質) (1) (2) (3) (4)單位元 (5)零元 例1-40:舉例?,Theorem 1-20(并運算與交運算之間所滿足的性質.) (1)吸收性. (2)分配性. 例1-41(P20),3. 補(complement)運算 例1-42 (A的補集依賴于全集U的選取.) A=a, b, c: (1)U = a, b, c, d (2)U = a, b, c, d,a,b,b,c,c,排中律成立: . 排中律?,集合的補運算和集合的并交運算滿足De Morgan律: 表(P21). (cf. P86 & P182,與布爾代數(shù)的性質完全類似?!
22、 因為它們是特殊的, 常見的布爾代數(shù).),4. 差(subtraction)運算 例1-43,Theorem 1-23(P22) Proof 例1-45(P22),例1-46 . 例1-47(P22) Solution 由上例知, A (B C) = ,5. 對稱差(symmetric difference)運算 See Venn Figure below. 例1-48,Theorem(對稱差運算的性質) (1)交換性: (2)單位元: A = A. (3) A A = . (4)結合性:,例1-49(消去律) Hint,例1-50 A B = A = B. Proof ()顯然. () A
23、B = A B = 且B A = 例1-51 ( 對 可分配),思考 還能定義集合的其他運算? 加法原理. 乘法原理. 容斥原理: 容斥原理的另一種形式: 推廣到n個集合情形(P24, 15)? 作業(yè) 習題1.4 5, 8, 10, 13.,1.5 集合的劃分與覆蓋,集合的劃分與覆蓋是集合中的重要內容之一. 集合的劃分就是集合元素間的一種分類. 在信息科學中,可以將知識庫看作集合的一種劃分. 因此, 研究集合的劃分具有特別重要的意義. 比集合的劃分更廣的概念是集合的覆蓋. 這些內容在下章會用到. 1. 集合的劃分(partition),Def (1) , iI. (2) , i j. (3)
24、Hardware?,例1-53 設A = a, b, c, 則A的所有不同的劃分分別為:,1和2的交叉劃分: . 1是2的加細劃分:,|A| = n, A的不同劃分的個數(shù)N: S(n, k)? Theorem n 1. Proof (?),2. 集合的覆蓋 Def 設A是集合, 由A的若干非空子集構成的集合稱為A的覆蓋(covering), 如果這些非空子集的并等于A. a, b, b, c,集合的劃分 集合的覆蓋, 但反過來不成立. A = a, b, c上所有不同的覆蓋有哪些? 作業(yè) 習題1.5 1, 4, 7.,1.6 集合的對等,集合的對等, 它是集合間的另一種關系. 通過集合對等以及相關內容的學習, 加深對
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 小學生生活小達人課件
- 尊重生命班會課件
- 26 必修2 素養(yǎng)加強課4 基因在染色體上位置的判斷與探究
- 05 必修1 第一單元 第5講 細胞器之間的分工合作
- pbl教學課件模板
- 2025年長沙市中考數(shù)學試卷真題(含標準答案)
- 部門承包經營品牌建設與維護合同
- 大數(shù)據(jù)產業(yè)園廠房場地租賃合同樣本
- 成都市環(huán)城生態(tài)區(qū)農用地租賃合作開發(fā)合同
- 茶葉市場推廣與茶園使用權租賃合同
- 2022-2023學年北京市東城區(qū)高二(下)期末化學試卷(含解析)
- 三年級下冊道德與法治課件-第二單元《我在這里長大》教材解讀-人教(新版)
- 防溺水老師培訓課件
- 鐵路行車組織(高職)全套教學課件
- 如何預防錯混料
- 全新版大學進階英語綜合教程2綜合訓練第二單元(含答案)
- 安全責任家校共育
- (外標兩點法對數(shù)方程)桔梗含量為例
- 道路運輸防汛應急演練方案范文
- 道路管線施工地鐵保護施工方案
- 體格檢查技術操作考核評分標準(胸部)
評論
0/150
提交評論