1、1離散數學主講：韓蘭勝 博士 副教授 H88學時2課課 程程 說說 明明 一、離散數學課程的地位和作用 離散數學是計算機專業的一門核心基礎課程。離散數學是計算機專業的一門核心基礎課程。 1 離散數學為計算機專業的后繼課程如數據結構、操作系統、數離散數學為計算機專業的后繼課程如數據結構、操作系統、數據庫、編譯原理、網絡和算法設計等課程提供必要的數學基礎。據庫、編譯原理、網絡和算法設計等課程提供必要的數學基礎。 2 2 為學生今后從事計算機科學和技術各方面的工作提供有力的為學生今后從事計算機科學和技術各方面的工作提供有力的工具。工具。 3 3 離散數學是現代數學的一個重要分支，通過該課程的學習可離

2、散數學是現代數學的一個重要分支，通過該課程的學習可以提高學生的抽象思維、嚴格推理以及綜合歸納分析能力，培養以提高學生的抽象思維、嚴格推理以及綜合歸納分析能力，培養出高素質的人才。出高素質的人才。 3二、離散數學課程的特點二、離散數學課程的特點 離散數學課程是應計算機科學和技術發展的離散數學課程是應計算機科學和技術發展的需要，綜合了高等數學的多個分支而形成的。其需要，綜合了高等數學的多個分支而形成的。其特點是以離散量為研究對象，內容豐富，涉及面特點是以離散量為研究對象，內容豐富，涉及面較寬。因此概念多、定理多、推理多并且內容較較寬。因此概念多、定理多、推理多并且內容較為抽象。但由于它是為學生后繼

3、專業知識的學習為抽象。但由于它是為學生后繼專業知識的學習做必要的數學準備，因此它研究的內容均比較基做必要的數學準備，因此它研究的內容均比較基礎，難度不大。礎，難度不大。 4 三、如何學好離散數學三、如何學好離散數學 要學好這門課程，首先必須充分認識到這門課程的上述特要學好這門課程，首先必須充分認識到這門課程的上述特點，需要做到以下幾點：點，需要做到以下幾點：1 熟讀教材。熟讀教材。準確理解各個概念和定理的含義（結合多個例子準確理解各個概念和定理的含義（結合多個例子來理解），必要的推理過程要看懂、理解（它可以幫助你熟悉來理解），必要的推理過程要看懂、理解（它可以幫助你熟悉和深刻理解定理的含義）。

4、和深刻理解定理的含義）。 2 獨立思考，大量練習。獨立思考，大量練習。僅靠熟讀教材并不能將書本上的知識僅靠熟讀教材并不能將書本上的知識 變成你自己的知識，在熟讀教材的基礎上，必須通過大量練變成你自己的知識，在熟讀教材的基礎上，必須通過大量練 習，獨立思考來真正獲取知識。習，獨立思考來真正獲取知識。 3 注重抽象思維能力的培養。注重抽象思維能力的培養。數學與其他學科相比較具有數學與其他學科相比較具有較高的抽象性，而離散數學的抽象性特點更為顯著，它有著大較高的抽象性，而離散數學的抽象性特點更為顯著，它有著大量抽象的概念和抽象的推理，要學好這門課程必須具有較好的量抽象的概念和抽象的推理，要學好這門課

5、程必須具有較好的抽象思維能力，才能深入地掌握課程內容。抽象思維能力，才能深入地掌握課程內容。5第四部分第四部分 數理邏輯。數理邏輯。包括命題邏輯和謂詞邏輯。（教材的包括命題邏輯和謂詞邏輯。（教材的第九、十章第九、十章 四、四、 離散數學課程的主要內容離散數學課程的主要內容離散數學課程的主要內容可以分為四個部分：離散數學課程的主要內容可以分為四個部分：第一部分第一部分 集合論。集合論。包括集合、關系和函數。（教材的第一、包括集合、關系和函數。（教材的第一、二、三章）二、三章）第二部分第二部分 代數系統。代數系統。包括代數系統的一般概念，幾類典型包括代數系統的一般概念，幾類典型的代數系統。（教材的

6、第四、五、六、七章）的代數系統。（教材的第四、五、六、七章）第三部分第三部分 圖論。圖論。包括圖的基本概念，幾種特殊的圖。（教包括圖的基本概念，幾種特殊的圖。（教材的第八章）材的第八章）6五、五、 教材及參考書教材及參考書2 參考書：參考書：離散數學習題題解離散數學習題題解 洪帆、付小青編，華中洪帆、付小青編，華中理工大學出版社。理工大學出版社。 1、教材：教材：離散數學基礎離散數學基礎 第二版，洪帆主編，華中理第二版，洪帆主編，華中理工大學出版社工大學出版社。7第一章第一章 集集 合合 本章采用樸素集合論的方法，介紹有關集合的一些基本本章采用樸素集合論的方法，介紹有關集合的一些基本知識，內容

7、顯得較為直觀，學起來易于接受。但集合及其相知識，內容顯得較為直觀，學起來易于接受。但集合及其相關的概念是本門課程后面各章內容的基礎，讀者務必熟練的關的概念是本門課程后面各章內容的基礎，讀者務必熟練的掌握。掌握。 主要內容如下：主要內容如下：1.1 1.1 集合及其表示方法集合及其表示方法 1.2 1.2 集合間的關系集合間的關系 1.3 1.3 集合的運算和運算定律集合的運算和運算定律1.4 1.4 集合成員表集合成員表 1.5 1.5 集合的分劃與覆蓋集合的分劃與覆蓋8又例如又例如 所有的正整數組成一個集合，每一個正整數均是這個集 合的元素。例如例如 全體中國人可組成一個集合，每一個中國人均

8、是這個集合的 元素第一章第一章 集集 合合 1.11.1集合及其表示方法集合及其表示方法一、集合和元素一、集合和元素v 把一些確定的、彼此不同的事物作為一個整體來 看待時，這個整體便稱為是一個集合集合。 v 組成集合的那些個體稱為集合的元素元素。 通常用大寫英文字母來標記集合，用小寫英文字母標記組成集合的個體若個體a是集合A的元素，則記作“aA”若a不是集合A的元素，則記作“a A” 9幾個常見的集合的表示符號：N：所有正整數的集合。：所有正整數的集合。 Q Q：所有有理數的集合。：所有有理數的集合。Z Z：所有非負整數的集合。：所有非負整數的集合。 R R：所有實數的集合。：所有實數的集合。

9、I I：所有整數的集合。：所有整數的集合。 N Nm m：從：從1 1到到m m，這，這m m個正整數的集合。個正整數的集合。P P：所有素數的集合。：所有素數的集合。 Z Zm m：從：從0 0到到m-1m-1，這，這m m個非負整數的集合。個非負整數的集合。 于是于是2N2N，2.5 N2.5 N，-3 N-3 N，但，但2.5Q2.5Q，-3I-3I。 10二、集合的表示方法二、集合的表示方法(1)(1)列舉法列舉法：按任意順序逐一列舉集合中的元素于花括號：按任意順序逐一列舉集合中的元素于花括號內，元素之間用逗號隔開。內，元素之間用逗號隔開。例如：例如：A=2,a,b,9,B=4,5,6

10、,7,8A=2,a,b,9,B=4,5,6,7,8(2)(2)描述法描述法：給定一個條件：給定一個條件P(x)P(x)，當且僅當個體，當且僅當個體a a使使P(a)P(a)成立時，成立時，aAaA。其一般形式為。其一般形式為A=aP(a)A=aP(a) 例如例如 上述集合上述集合B=aaNB=aaN且且4a84a8 又如又如 C=2C=2i iiZ,iZ,即即C=2C=20 0,2,21 1,2,22 2,2,23 3, , D=2xxZ D=2xxZ且且x50,x50,即即D=0,2,4,6,D=0,2,4,6,98,100,98,10011三、集合的基數三、集合的基數集合集合A A中不同元

11、素的個數稱為集合中不同元素的個數稱為集合A A的的基數基數，記作，記作#A#A。例如例如 上頁中的集合，上頁中的集合，#A=4#A=4，#B=5#B=5，#D=51#D=51，集合，集合C C有無窮多個元素，因此有無窮多個元素，因此C C的基數是無窮大。的基數是無窮大。若若#A#A是有限數，則稱是有限數，則稱A A為有限集，否則稱為有限集，否則稱A A為無限集。為無限集。例如例如 N , Z , I , R 等均為無限集等均為無限集。 四、空集四、空集定義定義1-11-1 不含有任何元素的集合，稱為空集空集，記作。 例如例如 A=x | xR 且 x2+8=0 = 12練習練習1-11-1 1

12、. 用列舉法表示下列集合用列舉法表示下列集合（1）A=a|aPP且且a20a20（2）B=a|a|4且且a為奇數為奇數2. 用描述法表示下列集合用描述法表示下列集合 (1) A=0,2,4,200 (2) B=2,4,8,1024 2,3,5,7,11,13,17,19 - -3,- -1,1,3 2x|xZZ且且x100 x1002n|nNN且且n10n10 13 1.2 1.2集合間的關系集合間的關系集合的包含和相等是集合間的兩個基本關系。集合的包含和相等是集合間的兩個基本關系。例如例如 設設 A=a, b, c, d, B=a, e, x, y, z, C=a, x B A，A B。則

13、，C A， BC 一、集合的包含一、集合的包含定義定義1-21-2 設有集合設有集合A A、B B，如果，如果A A的每一個元素都是的每一個元素都是B B的元素，則稱的元素，則稱A A是是B B的子集或的子集或B B是是A A的包含集，記的包含集，記 。如果如果A A不是不是B B的子集，則記作的子集，則記作A BA B。 BA 14集合的包含關系具有如下幾條性質： 證明性質（1） （反證法）（反證法）假設 ，（1）對任意集合）對任意集合A， ； A （2）對任意集合）對任意集合A， ；AA （3）對任意集合）對任意集合A、B、C，若，若 ， ，則，則 。 BACB CA則至少有一個元素但 ，

14、這與空集的定義相矛盾，因此成立。AxAx15二、集合的相等二、集合的相等例如例如 設設A=x | xN 且且 x能整除能整除24， B=1, 2, 3, 4, 6, 8, 12, 24 則則 A=B=又例如又例如 （1）a, b, c b, c, a （2）a, b, c, c a, b, c （3）a, b, c a, b, c （4） =定義定義1-31-3 設有集合設有集合A、B，若，若 且且 ，則稱，則稱集合集合A與與B相等，記作相等，記作A=B。 BA AB 16例如例如 設設A=0A=0，11，B=0B=0，1 1，22，C=0C=0則但四、空集的唯一性四、空集的唯一性定理定理1-

15、11-1 空集是唯一的空集是唯一的 因為空集被包含于每一個集合中因為空集被包含于每一個集合中，三、集合的真包含三、集合的真包含定義定義1-41-4 設有集合設有集合A、B，若，若 , 且且ABB，則稱，則稱A A是是B B的真的真子集，記作子集，記作 ，若，若A A不是不是B B的真子集，則記作的真子集，則記作 。 BA BA BABA BC BBB 證明證明 假設有兩個空集假設有兩個空集 和和 ， 12所以有所以有 ， ， 2112由定義由定義1-31-3， , , 故空集是唯一的。故空集是唯一的。 2117五、冪集五、冪集定義定義1-51-5 設有集合設有集合A A，由，由A A的所有子集

16、組成的集合，的所有子集組成的集合， 稱為集合稱為集合A A的冪集，記作的冪集，記作2 2A A 即 ASSA|2例例1 1 設設A=aA=a 則則0 0個元素的子集：個元素的子集： 1個元素的子集：個元素的子集：a因此 aA,2設設B=a,bB=a,b 則則0 0個元素的子集個元素的子集： 1個元素的子集：個元素的子集：a,b 2個元素的子集個元素的子集：a,b 因此 babaB,2設設C=a,b,cC=a,b,c 則則0 0個元素的子集：個元素的子集： ； 1個元素的子集：個元素的子集：a,b,c2個元素的子集：個元素的子集：a,b,a,c,b,c 3個元素的子集：個元素的子集：a,b,c

17、因此 cbacbcabacbaC,218定理定理1-21-2 設設A A是有限集，則是有限集，則#(2#(2A A)= 2)= 2#A#A nnnnnnnACCCCC1210)2(#在二項式定理在二項式定理 nnnnnnnnnnnyCxyCyxCxCyx11110)(中，令中，令 x=y=1, 便有便有 nnnnnnnnCCCCC12102 因此因此 #(2 2A A)= 2 2n n 即即 #(2 2A A) = 2 2#A #A :0nC1nC:a1,:a2 ,an2nC:a1,a2,a1,a3 nnC:a1,a2 , , an證明證明 設設A= A= a1,a2 , , an, ,從從n

18、 n個元素中選取個元素中選取m m個元素的方個元素的方法有法有 種，所以種，所以A A的子集個數為的子集個數為mnC19例例2 2 設設 , 求求2A和和2B A aaB,解解 對于集合對于集合A，它只有一個子集，它只有一個子集 ， 即 A2 對于集合對于集合B，有，有 1個元素的子集：個元素的子集： ，a，a 2個元素的子集：個元素的子集： , , a, a, aa,3個元素的子集：個元素的子集： aa, 0個元素的子集：個元素的子集： 因此因此 ,2Baaaa , ,aaaa20答案：答案： ABD2 2 設設 , 試判斷下列各式是否正試判斷下列各式是否正確，并將正確的題號填入括號內。確，

19、并將正確的題號填入括號內。 A. B. C. D.S SS S , 4, 3,aS答案：答案：A BCA. B. C. D. aa 練習練習1-21-2 1 試判斷下列各式是否正確，并將正確的題試判斷下列各式是否正確，并將正確的題號填入括號內。號填入括號內。 aaa, aa aaa,213 設設 , , ，判斷下列論斷，判斷下列論斷是否正確，并將是否正確，并將“Y”或或“N”填入相應論斷填入相應論斷后面的括號中。后面的括號中。 A)2(2AB (1)(2)(3)(4)BB B B B B B, B,( )( )( )( )( )( )( )( )YYYYYYNN2AC,2CB令令則則22 1.

20、3 1.3集合的運算和運算定律集合的運算和運算定律二、文氏圖二、文氏圖定義定義1-61-6 如果在某個問題中，所討論的一切集合均是某個集合的子集，則稱這個集合是該問題的全集合。記作U（或E）。 一、全集合一、全集合例如例如 UABA AB23三、集合的運算三、集合的運算定義定義1-71-7 設有集合設有集合A、B，屬于，屬于A或屬于或屬于B的所有元的所有元素組成的集合稱為素組成的集合稱為A與與B的并集，記作的并集，記作 。即。即BuAuuBA或|BA例如例如 設設A=a,b,c, B=c,d,f, C=b,e則 fdcbaBA,ecbaCA,fedcbCB,由定義由定義1-7知知， BABBA

21、A,BAAB24定義定義1-81-8 設有集合設有集合A、B，屬于，屬于A同時又屬于同時又屬于B的所有元素組成的集合稱為的所有元素組成的集合稱為A與與B的交集，記的交集，記作作 。即。即BABuAuuBA且|例如例如 設設A=a,b,c,d, B=d,f,a, C=e,f,g則 adBA,由定義由定義1-8可知可知， ABABBACAfCBBAAB25定義定義1-91-9 設有集合設有集合A、B，所有屬于，所有屬于B而不屬于而不屬于A的元素組成的集合，稱為的元素組成的集合，稱為A相對于相對于B的補集，記作的補集，記作B-A。即。即AuBuuAB但|例如例如 設設A=a,b,c,d, B=d,f

22、,a, C=e,f,g 則則B-A= f , C-A= e ,f , g =C AB BA32頁頁26定義定義1-101-10 集合集合A相對于全集合相對于全集合U的補集稱為的補集稱為A的的絕對補集，簡稱為絕對補集，簡稱為A的補集，記作的補集，記作 。即。即AAuuAuUuuAUA|但例如例如 設設U=1，2，3，4，10，A=2，4，6，8，10 則9 , 7 , 5 , 3 , 1AUA又例如又例如 設設U=I（I是整數集），是整數集）， 0,|iIiiA且則0|iIiiAUA且27四、集合運算的定律四、集合運算的定律對于全集合對于全集合U的任意子集的任意子集A、B、C，有：，有： 交換律

23、交換律ABBAABBA結合律結合律CBACBA)()(CBACBA)()(分配律分配律)()()(CABACBA)()()(CABACBA同一律同一律AAAUA28互補律互補律UAA AA對合律對合律AA)(等冪律等冪律AAAAAA零一律零一律UUAA吸收律吸收律ABAA)(ABAA)(德德摩根律摩根律BABA)(BABA)(29（1）根據定義進行證明）根據定義進行證明若要證明集合若要證明集合S=H，根據集合相等關系的定義，根據集合相等關系的定義，我們需證明我們需證明 且且HS SH 例例 1 1 證明證明BABA)(證明證明 若若 , 則則 ，)(BAuBAu因此因此 或者或者AuBu于是于

24、是 或者或者AuBu從而從而 ，則，則BAuBABA)(反之反之 若若 ， 故故 或者或者 。BAuAuBu因此，因此， 或者或者 ,AuBu于是于是 ，BAu從而從而 ，故有，故有 。)(BAu)(BABA由上證得，由上證得， 。 BABA)(30例例 2 2 證明證明BABA證明證明 若若 則則 且且 ，BAuAuBu即即 且且 ，AuBu因因 此此 ，BAu故故 。BABA反之反之 若若 ，BAu則則 且且 ，AuBu即即 且且 ，AuBu因此因此 。BAu故故 。BABA由上證得，由上證得，BABA31（2）利用已有的集合恒等式證明新的恒等式）利用已有的集合恒等式證明新的恒等式例如例如

25、 假設交換律、分配律、同一律和零一律都成立，假設交換律、分配律、同一律和零一律都成立，則可以證明吸收律則可以證明吸收律 也成立。也成立。 ABAA)(證明證明 )(BAA)()(BAA（由同一律）（由同一律） )(BA（由分配律）由分配律）)(BA（由交換律）（由交換律） A（由零一律）（由零一律） A（由同一律）（由同一律） 又例如又例如 證明等冪律證明等冪律 AAA證明證明 = =AAA)(AAAA(3)(3)利用下一節介紹的集合成員表證明集合恒等式利用下一節介紹的集合成員表證明集合恒等式 32D 若若 ，則，則 A=B 練習練習1-31-3 1 設設A、B、C是任意集合，判斷下述論斷是否

26、是任意集合，判斷下述論斷是否正確，并將正確的題號填入括號內。正確，并將正確的題號填入括號內。 A 若若 ，則，則 B=CCABAB 若若 ，則，則 B=CCABA C 若若A-B=A-C，則，則 B=C BA( )D 反例反例 設設A= a , b , c , B= b , d , C= c , d 則則 但但,dcbaCABACB 23頁頁33CBA)(2 設設U=1，2，3，4，5，A=2，4，B=4，3，5，C=2，5，3，確定下列，確定下列集合的元素，將其填入相應的花括號內。集合的元素，將其填入相應的花括號內。 (1) (2) (3) (4) (5 BA)(CBACABCA)(21,

27、42, 3, 4, 54343 設設U表示劉平擁有的所有書的集合，其中表示劉平擁有的所有書的集合，其中A是離散數學是離散數學參考書的集合，參考書的集合，B是操作系統參考書的集合，是操作系統參考書的集合，C是今年出版是今年出版的新書的集合，的新書的集合，D是從圖書館借來的書的集合?，F知道如下是從圖書館借來的書的集合?，F知道如下情形：情形：（1）所有離散數學參考書都是今年出版的新書。（）所有離散數學參考書都是今年出版的新書。（ ） （2）所有操作系統參考書都是從圖書館借來的。（）所有操作系統參考書都是從圖書館借來的。（ ） （3）今年出版的新書不是從圖書館借來的。（）今年出版的新書不是從圖書館借來

28、的。（ ） （4）沒有一本操作系統的參考書是今年出版的。（）沒有一本操作系統的參考書是今年出版的。（ ） 3157試用集合的方法分別表示上述四種情形，可供選擇的答案試用集合的方法分別表示上述四種情形，可供選擇的答案如下，請從下述答案中挑選出相應表達式的編號填入每一如下，請從下述答案中挑選出相應表達式的編號填入每一種情形后面的括號中。種情形后面的括號中。1. 2. 3. 4. 5. 6. 7.DB BC CA DADCCB CB354 判斷下列論斷是否正確，對正確的論斷在相應題后的括判斷下列論斷是否正確，對正確的論斷在相應題后的括號中標入號中標入“Y”，對錯誤的論斷在相應題后的括號中標入，對錯誤

29、的論斷在相應題后的括號中標入“N”。1） 若若 ，則，則 （ ） 2） 若若 ，則，則 （ ） 3） 若若 ，則，則 （ ） 4） 若若 ，則，則 （ ） 5） 若若 ，則，則 ( )6） 若若 ，則，則 ( )7） 若若 ，則，則 ( )8） 若若 ，則，則 ( )AaBAaAaBAaBAaBaBAaBaBA BBABA ABAAaBAaAaBAaYYYYNNNN36 1.4 1.4集合成員表集合成員表一、并、交和補集的成員表一、并、交和補集的成員表根據集合的并和交運算的定義，全集合根據集合的并和交運算的定義，全集合U中的元素中的元素u可分為可分為如下四種情形：如下四種情形：（ 1） ， （

30、 2） ， （ 3） ， （ 4） ， AuBuBAuBAuAu BuBAuBAuAuBuBAuBAuAuBuBAuBAuA B 0 00 11 01 1BABA 0 0 1 0 1 0 1 137設設A是全集合是全集合U的子集，根據補集的定義，全集合的子集，根據補集的定義，全集合U中的元素可分為兩種情形，中的元素可分為兩種情形，（1）若）若 ，則，則（2）若）若 ，則，則Au AuAu Au的成員表的成員表 AA01 A1038二、由集合二、由集合A A1 1、A A2 2、A Ar r所產生的集合所產生的集合的成員表。的成員表。 設設A1、A2、Ar是全集合是全集合U的子集，對這些集合以及

31、的子集，對這些集合以及和和U有限次地施加補、并、交運算，可以產生出一些有限次地施加補、并、交運算，可以產生出一些新的集合，這樣產生的集合稱為是由新的集合，這樣產生的集合稱為是由A1、A2、Ar所所產生的集合。產生的集合。例例 如如 S)()(CBCBABBAT)(39例例 1 構造構造 T= 的成員表的成員表 BBA)(A B0 00 11 01 1BABBBA)(01111010001040例例 2 構造構造 S 的成員表的成員表 )()(CBCBAA B C0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1BCB CCB)()(CBCBS11001100010

32、001001010101000100010011001100000011041三、利用集合成員表證明集合恒等式三、利用集合成員表證明集合恒等式例例 設設A、B、C是任意集合，試問等式是任意集合，試問等式 S=TS=T是否成立？是否成立？ 解解 令令S= T= )()(CABA)()(BACA分別構造分別構造S和和T的成員表如下：的成員表如下： A B C 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABACA SBA CAT1111000000111111111101010011010100110000000001010011010142 1.5 1.5 集

33、合的分劃與覆蓋集合的分劃與覆蓋一、集合的分劃一、集合的分劃定義定義1-111-11 設有非空集合設有非空集合A，H=A1、A2、Am，其中其中 ，且，且 （i=1，2，m），若），若 AAiiA（1） ，當，當ij時時 ( 2 )jiAAAAimi1例例 1 1 設設A=1，2，3，4 則則 H1=1，2，3，4 H2=2，3，1，4 H3=1，2，3，4 。 都是都是A的分劃的分劃則稱則稱H是集合是集合A的一個分劃，每一個的一個分劃，每一個 稱為這個分劃的一個分塊。稱為這個分劃的一個分塊。iA43例例 2 2 設設A=2A=2，3 3，4 4，8 8，9 9，1010，15 15 定義定義A A的如下子集：的如下子集： 整除能被且2|2xAxxA整除能被且3|3xAxxA整除能被且5|5xAxxA試問試問 是否是否A的一個分劃。的一個分劃。 ,532AAA解解根據題意根據題意 2，4，8，10 2A3，9，153A10，155A 不是不是A的分劃，的分劃，,532AAA,32AA 可成為可成為A的一個分劃。的一個分劃。 44二、集合的覆蓋二、集合的覆蓋定義定義1