離散數(shù)學(xué)精品課件

1、關(guān)于離散數(shù)學(xué)25.09.2022離散數(shù)學(xué)1第一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)23.1 基本概念定義3.1.1： 設(shè)A，B是兩個(gè)集合，是A到B的二元關(guān)系，若對(duì)A中每個(gè)元素a，有唯一的 bB，使得 ，則稱為A到B的映射，記為： : AB 或 所謂從A到B的映射就是A中的每個(gè)人都向B中的人射了一箭，并且都射中了B中的一個(gè)人。既沒有人偷懶不射，也沒有人一箭雙雕。這時(shí)，B中的人，有的可能身中數(shù)箭，有的可能一箭未中。當(dāng)然也可能剛好每人中了一箭。第二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)3幾個(gè)概念映象：若 ，則稱b為a的映象。 (被射中

2、的人)象源：若 ,則a為b的象源,記為 (a)=b。 (射箭的人)映象集： (A)=bB|存在aA,使 (a)=b 稱為A的映象集。(全體被射中的人的集合。) 顯然， (A) B 。變換：A到A的映射稱為變換。(窩里斗)第三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)4下列關(guān)系是否構(gòu)成映射？R1abcef gAB嗨！R1可不是映射喔。有人偷懶了。R2abcefgAB嗨！R2也不是映射喔。有人一箭雙雕。R3abcefgAB啊哈！R3才是一個(gè)映射呢。第四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)5滿射、單射、雙射定義3.1.2：若是A到B的映射

3、，且對(duì)bB, aA, 使得 (a)=b，則稱是A到B上的映射，簡(jiǎn)稱滿射。此時(shí)每個(gè)bB 必是A 中至少一個(gè)元素a 的映象，且 (A)=B。糟糕！全被射中了。定義3.1.3：設(shè)是A到B的映射，若對(duì)a,bA, ab,均有 (a) (b)，則稱為A到B的單射或入射。此時(shí)| (A)|=|A|， B中每個(gè)元素最多是A中一個(gè)元素的映象。還好，只中了一箭。定義3.1.4：設(shè)是A到B的映射，若既是滿射又是單射，則為A到B的雙射或11映射。哼！你能射我，我也能射你。第五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)6滿射、單射和雙射的例子設(shè)：N N，N 是自然數(shù)集，(n)= 2n，nN。則

4、是單射，但不是滿射。設(shè)：0， 0， 1，() = sin()， 0, 。則是滿射，但不是單射。設(shè)：N E，N 是自然數(shù)集合，E是自然數(shù)中的所有偶數(shù)的集合，(n)= 2n，n N。 則是單射且是滿射，所以是雙射。第六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)7判斷下列映射是否單射，滿射和雙射。1、設(shè)：N N，N 是自然數(shù)集，(n)= 2n，nN。 （是變換）解： 取b=2n+1，bN，由的定義知： (n) b，n,bN。 不是滿射。 任取i，jN，且ij。若(i)= (j)，即2i=2j，則i=j，此與ij矛盾。 (i)(j)。故是單射。綜上所述： 是單射但不是滿射。

5、第七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)82、：RR RR，R為實(shí)數(shù)集。 (x,y)=解：(單射性) 任取(x,y),(u,v), 假設(shè)(x,y)(u,v),若(x,y)= (u,v),即= 則: x+y=u+v 得: x=u x-y=u-v y=v 從而(x，y)=(u，v),與假設(shè)矛盾.故是單射.(滿射性) 對(duì)任意RR,令: (x,y)= ,即: x+y=u 解得: x=(u+v)/2 x-y=v y=(u-v)/2 顯然(u+v)/2, (u-v)/2)RR,且滿足 (u+v)/2, (u-v)/2)= ,故是滿射.總之, 是雙射.第八張，PPT共六十四

6、頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)93、：NNN，N是自然數(shù)集(0N)，()=|x2-y2|解: 取, NN ()=|1212|=0 ()=|2222|=0 故不是單射. 又取2N, 因不存在自然數(shù)x,yN 滿足: |x2y2|=2 故不是滿射. 既不是單射也不是滿射.第九張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)10等勢(shì)有限集合間的單射即滿射定理3.1.1 設(shè)A，B是兩個(gè)有限集，且|A|=|B| .于是， : AB是單射當(dāng)且僅當(dāng)是滿射。證明：(必要性)設(shè)是單射，則 |A|= |(A)| , 因?yàn)閨A|=|B| ,所以 |(A)|= |B| ,又因

7、(A) B且B有限，所以(A) = B，從而是滿射。 (充分性)設(shè)是滿射，則(A) = B，于是， |A|=|B|=|(A)| , 即|A|=| (A)| 。又因A有限，所以是單射。第十張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)113.2 映射的運(yùn)算逆映射的概念定義3.2.1 設(shè)：AB，定義關(guān)系RBA為：R= | yB , xA,且(x)=y；如果R是B到A的映射，則稱R為的逆映射。記為 1。例如：設(shè)：N E，N 是自然數(shù)集合，E是自然數(shù)中所有偶數(shù)的集合，(n) = 2n，nN。則的逆映射-1為： -1 ：E N，-1(m)=m/2，mE。第十一張，PPT共六十四頁(yè)

8、，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)12雙射才有逆映射證明：必要性：設(shè)-1存在， -1：BA。若不是滿射，則yB ,使得y不是A中任何元素的映象，即y沒有象源。若不是單射，則 x1, x2A , x1x2且 (x1)= (x2)=y，則y的象源不唯一。不論哪種情況，都說明的逆關(guān)系不是B到A的映射，此與假設(shè)矛盾。故是雙射。充分性：設(shè)是雙射，考慮的逆關(guān)系，易知，對(duì)于B中的每個(gè)元素y，都對(duì)應(yīng)著A中唯一的一個(gè)在下以y為映象的元素x，因此， 的逆關(guān)系是B到A的映射。定理3.2.1 設(shè)是A到B的映射，于是， 存在逆映射當(dāng)且僅當(dāng)是雙射。第十二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09

9、.2022離散數(shù)學(xué)13雙射的逆也是雙射顯然，若是A到B的雙射，則其逆映射 1也是B到A的雙射，并且對(duì)任意的xA，均有： 1(x) = x . 第十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)14復(fù)合映射定義3.2.2：設(shè)是A到B的映射， 是B到C的映射，對(duì)任意xA, 定義( )(x) = (x)，易知， 是A到C的映射，稱此映射為映射與映射的乘積或復(fù)合映射。說明：(1) 是映射時(shí)， 不一定是映射； (2)假如 和 都是映射，不一定有 = ，即映射的乘法不滿足交換律； (3)映射的乘法滿足結(jié)合律。?第十四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離

10、散數(shù)學(xué)15 復(fù)合映射交換后不一定是映射12345678ACB因此，上例中 是映射， 不是映射。 (1) = (4) = 7； (2) = (4) = 7； (3) = (5) = 8 .而 (x) 都不存在,其中，x B .令是A到B的映射， 是B到C的映射，第十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)16映射的乘法不滿足交換律假如 和 都是映射,如下所示：ABCxyzabxy (x)= (a) = x ; (y)= (b) = y ; (z)= (b) = y ; (a)= (x) = a ; (b)= (y) = b ;所以， ，即映射的乘法不滿足交換律。第

11、十六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)17映射的乘法滿足結(jié)合律定理3.2.2 設(shè)是A到B的映射， 是B到C的映射，是C到D的映射，于是 ( ) = ( ) (式3.1)證明：對(duì)任意xA,有 ( ( ) )(x) = ( ( )(x) ) = ( (x) ( ) )(x) = ( ) (x) = ( (x) 因此，(式3.1)成立。即映射的乘法滿足結(jié)合律。第十七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)18雙射兩次求逆后不變定理3.2.3 設(shè)是A到B的雙射，則 ( 1 ) 1 = 證明：因?yàn)槭请p射，所以 1 是B到A的雙射，從而(

12、1) 1是A到B的雙射。對(duì)任意xA,設(shè) (x) =y ,則 1(y) = x ,由于 1也是雙射，所以( 1) 1(x) = y,故( 1) 1 = 。 第十八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)19復(fù)合雙射的逆先讓我們來(lái)回憶一下復(fù)合關(guān)系的逆（定理2.2.3）：(RS)-1 = S-1R-1。定理3.2.4 設(shè)是A到B的雙射， 是B到C的雙射，于是 ( ) 1 = 1 1 (式3.2)證明： 由假設(shè)不難知道， ( ) 1 和 1 1均是C到A的雙射。對(duì)任意zC,因?yàn)?1也是雙射，所以有唯一的yB,使 1(z) = y. 又因?yàn)?1也是雙射，所以對(duì)y有唯一的xA

13、 ,使 1(y) = x.于是， 1 1 (z) = 1 ( 1(z) = 1 (y) = x 又因( )(x) = (x) = (y) = z ,且 也是雙射，所以 ( ) 1(z) = x . 從而對(duì)任意zC , 有( ) 1(z) = 1 1 (z)。因此， (式3.2)成立。注意：要使 為雙射，不必要求和均是雙射，只 須是單射， 是滿射即可，但要（3.2）成立，則和 必須為雙射。第十九張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)20第四章 可數(shù)集與不可數(shù)集 對(duì)于兩個(gè)有限集，要比較這兩個(gè)集合中元素的多少，只需分別數(shù)出它們的元素個(gè)數(shù)，再加以比較即可。但對(duì)于無(wú)限集，

14、采用這種數(shù)數(shù)和比較元素個(gè)數(shù)的方法則行不通。 本章將利用“映射”的概念建立集合間的等勢(shì)關(guān)系，并拓廣集合中元素個(gè)數(shù)的概念，引進(jìn)集合的基數(shù)的概念，最后討論可數(shù)集與不可數(shù)集。第二十張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)214.1 等 勢(shì) 如何比較兩個(gè)集合中元素的多少呢？引入等勢(shì)的概念。定義4.1.1 設(shè)A和B是集合，若存在A到B的雙射，則稱A與B等勢(shì)，記為A B 。(可形象理解為A與B的元素一樣多。)“”是一個(gè)等價(jià)關(guān)系。例1 自然數(shù)集N與偶自然數(shù)集E是等勢(shì)的，其中定義N到E的雙射為：(n) = 2n nN.第二十一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2

15、022離散數(shù)學(xué)22證明“”是一個(gè)等價(jià)關(guān)系證明：設(shè)S=X|任意兩個(gè)元素之間存在雙射，X是集合，是S上的二元關(guān)系： =|A,BS,存在雙射:AB 對(duì)每個(gè)AS,存在恒等映射I:AA，I是雙射,于是AA，故是自反的。對(duì)任意A,BS，若AB，則存在雙射:AB，顯然雙射-1:BA存在，于是BA，故是對(duì)稱的。對(duì)任意A,B,CS，若AB,BC,則存在雙射 :AB和:BC，而(A)=(A)=(B)=C，即雙射:AC存在，于是AC，故是傳遞的。 綜上所述，是等價(jià)關(guān)系。第二十二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)23有限與無(wú)限定義4.1.2：設(shè)Nn=0,1, , n 1 , n1

16、,若集合A與Nn等勢(shì)，則稱A為有限集；否則稱A為無(wú)限集。第二十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)24無(wú)限多的自然數(shù) 定理4.1.1 自然數(shù)集合N是無(wú)限集。證明：設(shè)nN，n 1 , 令是從Nn到N的映射，Nn=0,1, , n1 ，下證不是雙射。 令k=1+max(0), (1), , (n1) , 于是kN，但對(duì)任意xNn ,均有(x) k , 因此，不是滿射，更不是雙射。由定義4.1.2知，N為無(wú)限集。啊哈！這下我們知道有無(wú)限多個(gè)自然數(shù)了！第二十四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)25抽屜原理（鴿巢原理） 我們知道，若

17、A，B均為有限集，且A與B之間存在雙射，則A和B的元素個(gè)數(shù)相等，即AB。但是：定理4.1.2 任何有限集均不能和其真子集等勢(shì)。此定理也稱為抽屜原則：若將n+1個(gè)物體放入n個(gè)抽屜中，則至少有一個(gè)抽屜中放了兩個(gè)或兩個(gè)以上的物體。抽屜原則對(duì)無(wú)限集并不總是成立，即無(wú)限集能夠與其真子集等勢(shì)。這是無(wú)限集合的一個(gè)非常重要的性質(zhì)。我們已經(jīng)看到自然數(shù)集等勢(shì)于它的真子集偶數(shù)集合。下面我們?cè)倏磶讉€(gè)例子。第二十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)26正實(shí)數(shù)和全體實(shí)數(shù)一樣多例2：令R和R+分別為實(shí)數(shù)集合和正實(shí)數(shù)集合，即R+=xR | x 0 ，顯然，R+ R ，即R+是R的真子集。但

18、是RR+證明：定義映射 f 如下： f (x) = ex , xR 于是，對(duì)任意的xR，存在唯一的yR+ ,使 y = ex = f (x) ； 另一方面，對(duì)任意的yR+ ,存在唯一的 x =lnyR , 使 f (x) = ex = elny = y , 這說明 f 是R到R+的一個(gè)雙射。因此， RR+ 。 第二十六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)27例3：A=0, 1）, B=0, 1 , A,BR.顯然 A B.構(gòu)造一A到B的雙射,說明AB.解: 令 A1=0,1/2,1/3,1/n,.作f: AB為: 任取x1,x2A, x1x2 , 顯然, f(

19、x1)f(x2) , 且對(duì) 任意yB:若y=0 , 則取x=0 , 有f(0)=0若y=1, 則取x=1/2A1, 于是f(1/2)=1/(2-1)=y若y=1/n,取x=1/(n+1)A1,故f(1/(n+1)=1/n=y若yBA1,則取x=y,于是f(x)=x=y 綜上所述f是A到B的雙射,于是AB. f(0)=0 f(1/n)=1/(n-1) (n1 , 1/nA1 , nN) f(x)=x (x0,1)A1 )第二十七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)284.2 集合的基數(shù)幾個(gè)記號(hào)：同有限集合中元素的個(gè)數(shù)的記法一樣，集合A的基數(shù)用 |A|表示。每個(gè)有

20、限集合都恰與某個(gè)集合Nn= 0,1, , n1等勢(shì)，其中n 0 , N0 = 。如果A Nn , 則A中有n個(gè)元素，即|A| = n;若A為無(wú)限集，則用一個(gè)特殊的符號(hào)i(讀作阿列夫i，i是一個(gè)正整數(shù))來(lái)表示它的基數(shù)。例如，對(duì)于自然數(shù)集合N，令|N| = 0 ( 讀作 “ 阿列夫零 ” ) 。第二十八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)29如何比較集合的大小(1)若AB , 則稱A的基數(shù)與B的基數(shù)相等, 記為|A|=|B|，否則記為|A|B|。(2)若存在A到B的單射，則稱A的基數(shù)小于或等于B的基數(shù)，記為|A| |B|；或稱B的基數(shù)大于或等于A的基數(shù)，記為|B|

21、 |A|。(3)若|A|B|，且|A|B| ，則稱A的基數(shù)小于B的基數(shù)，記為|A| |A| 。 根據(jù)集合的基數(shù)來(lái)比較它們的大小。定義4.2.1 令A(yù)、B為兩個(gè)集合， 由定義，|A|=|B|可形象地理解為A中的元素與B中的元素一樣多。第二十九張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)30集合大小是可比的 定理4.2.1 設(shè)A和B為兩個(gè)集合，總有 |A| |B|或者|B| |A| 。即任意兩個(gè)集合總可比較大小。 像實(shí)數(shù)一樣，任何兩個(gè)基數(shù)都可以比較大小，所以有第三十張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)31基數(shù)之間的相等關(guān)系是等價(jià)關(guān)系定理4

22、.2.2 基數(shù)之間的相等關(guān)系“= ”是一個(gè)等價(jià)關(guān)系,即對(duì)任何集合A , B和C, 有: (1)|A|=|A|; (2)若|A|=|B| ,則 |B|=|A|; (3)若|A|=|B|且|B|=|C| , 則|A|=|C| .第三十一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)32基數(shù)間的是偏序關(guān)系定理4.2.3 基數(shù)之間的小于或等于關(guān)系“ ”是一個(gè)偏序關(guān)系,即對(duì)任何集合A , B和C, 有: (1)|A| |A|; (2)若|A| |B|且|B| |A| ,則 |A|=|B|; (3)若|A| |B|且|B| |C| , 則|A| |C| .第三十二張，PPT共六十四

23、頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)33幾個(gè)關(guān)于基數(shù)的問題我們知道自然數(shù)有無(wú)限多個(gè)。那么自然數(shù)集合是不是就是最大集合的呢？如果自然數(shù)集合不是最大的，那么比它更大的集合是什么樣的呢？是不是存在最大的基數(shù)呢？不！不存在最大的集合。山外有山，天外有天。我們的口號(hào)是：只有更大，沒有最大！第三十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)34山外青山樓外樓 定理4.2.4 對(duì)任意集合A,均有|A|(A) |,其中(A)為A的冪集。證明： 令 f : A(A)。f (a) =a， aA。 顯然，f 是單射,于是|A| |(A)| . 顯然，象集 a | aA 是

24、(A)的真子集，所以，f 不是滿射，從而不是雙射。于是我們有|A| |(A)|。 錯(cuò)！錯(cuò)！錯(cuò)！錯(cuò)誤是：雖然f不是雙射，但不能說明A與 (A)之間不存在其它的映射是雙射。正確的作法是證明A與 (A)存在任何的雙射都是不可能的。 第三十四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)35山外青山樓外樓 假設(shè)|A| = |(A)|，則存在A到(A)的雙射g . 令B=aA | a g(a) (g(a)是a所對(duì)應(yīng)的A的子集)，顯然B(A)。bA,使g(b) =B 。但是 (1)若bB，則由B之定義有bg(b)，即bB ; (2)若bB，即bg(b)，則由B之定義有bB。 總之有

25、bB當(dāng)且僅當(dāng)b B，矛盾。 故|A|(A)|。綜合以上，定理得證。定理4.2.4 對(duì)任意集合A,均有|A| | (A)| ,其中(A)為A的冪集。證明： 令f ：A(A)。f (a) =a， aA。顯然，f 是單射，于是|A| |(A)| 。 討論B的存在性：雙射g：A(A)， aA，g(a)(A)即： g(a)是A的子集。又：作集合D=AA，AA，顯然，D A，即D(A) 。令： aA，g(a)=D，于是，aD，即a g(a)，但aA A。第三十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)36無(wú)限集也分大小，且無(wú)最大者 定理4.2.4說明：對(duì)任意無(wú)限集，它的冪集就

26、比它大。因此對(duì)任意無(wú)限集都存在更大的集合。我們記自然數(shù)集合N的冪集的基數(shù)為1，也就是| (N)| =1 ， 由定理4.2.4知， 0 1 ?？梢宰C明 |R| = | (N)| , 其中R為實(shí)數(shù)集，于是， | N | |R|。實(shí)際上N是最小的無(wú)限集。依次可以推得實(shí)數(shù)集合的冪集的基數(shù)為2，第三十六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)374.3 可數(shù)集與不可數(shù)集定義4.3.1：設(shè)A是一個(gè)集合，若A與N等勢(shì)，則稱A為可數(shù)無(wú)限集；若A是有限集，則稱A為可數(shù)集。有時(shí)也將可數(shù)無(wú)限集簡(jiǎn)稱為可數(shù)集。（遇到討論可數(shù)集的問題時(shí)要注意區(qū)分無(wú)限和有限兩種情況。）不是可數(shù)集的集合就稱為不

27、可數(shù)集。第三十七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)38整數(shù)集是可數(shù)集例1：整數(shù)集Z是可數(shù)集。 證明：可定義N到Z的映射如下： (n) =n/2 (n為偶數(shù)） (n) =(1-n)/2 (n為奇數(shù)） 不難驗(yàn)證為雙射,故NZ, 則Z是可數(shù)集。說明：映射 將 10，偶數(shù)正整數(shù)， 奇數(shù)（除1外） 負(fù)整數(shù)。第三十八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)39定理4.3.1 A是可數(shù)無(wú)限集當(dāng)且僅當(dāng)A的所有元素可以如下編號(hào)排出： a1 , a2 , a3 , , an , 此定理告訴我們，任何集合只要它的元素可以排序，就是可數(shù)的。如何判別一集

28、合是可數(shù)的第三十九張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)40可數(shù)集的子集仍是可數(shù)的定理4.3.2 可數(shù)集的子集仍是可數(shù)集。 證明：設(shè)A是可數(shù)集，若A是有限集，則它的子集仍是有限集，當(dāng)然也是可數(shù)集。若A是無(wú)限集，則由定理4.3.1知，A的元素可排列成： a1 , a2 , a3 , , an , (3.3) 顯然，A的無(wú)限子集可如下得到： 從左向右看式(3.3)，可以依據(jù)子集中元素出現(xiàn)的次序?qū)⒃撟蛹脑嘏帕袨椋?ai1 , ai2 , ai3 , , ain , 由定理4.3.1知，該子集是可數(shù)集。第四十張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.20

29、22離散數(shù)學(xué)41有理數(shù)集Q是可數(shù)集。例2：有理數(shù)集是可數(shù)集。 證明：已知任何非零有理數(shù)均可表示成確定的既約分?jǐn)?shù)，故把全體有理數(shù)按如下方式排列： (1)0排在最前面； (2)對(duì)正分?jǐn)?shù)，按它的分子與分母的和數(shù)由小到大排列，若和數(shù)相等，則分子小的排前面； (3)對(duì)負(fù)分?jǐn)?shù)，把它緊排在相應(yīng)的正分?jǐn)?shù)后面。 顯然，任意有理數(shù)總會(huì)排入此序列中。由定理4.3.1知，Q是可數(shù)集。這種排序的方法稱為字典排序法。第四十一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)42三角形方法有理數(shù)還可以按下表排序：顯然用此方法可將所有的有理數(shù)排序。分子分母 1 2 3 4 5 6 1234 . . . 此

30、方法稱為三角形方法，是很有用的方法。第四十二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)43符號(hào)串的集合是可數(shù)的令為一字母表， 上的符號(hào)串為+： + = 1 +2 +3 +4+=i i=1 這里i為長(zhǎng)度為i的符號(hào)串的集合。 +為可數(shù)集。 事實(shí)上，若| = k， 則每一個(gè)符號(hào)串就是一個(gè) k 進(jìn)制的數(shù)，顯然它們是可以按序排列起來(lái)。所以+為可數(shù)集。 第四十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)44不是所有的集合都能排序如果一個(gè)集合的元素可以排序，那么我們就可以一個(gè)一個(gè)地去數(shù)。是不是所有的集合的元素都能排序呢？不！不是所有的集合都能排序。比如

31、0，1中實(shí)數(shù)的集合。讓我們來(lái)設(shè)想一下將它的元素排一個(gè)序： 0理所當(dāng)然排在第一位。 但是0之后應(yīng)該排哪個(gè)呢？0.1？不！0.01？不！0.001？不！.？你會(huì)發(fā)現(xiàn)第二個(gè)就不知道排哪個(gè)好了。這樣看來(lái)實(shí)數(shù)集合是沒法去數(shù)了！?第四十四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)45實(shí)數(shù)集是不可數(shù)的定理4.3.3 實(shí)數(shù)集是不可數(shù)的。 證明：取R的子集 (0,1)=xR | 0 x 1 ,由定理4.3.2知，只需證明(0,1)是不可數(shù)集即可。 若(0,1)可數(shù)，則可將(0,1)中的數(shù)排成序列： 1： 0.a11 a12 a13 2： 0.a21 a22 a23 3： 0.a31

32、a32 a33 考慮數(shù)r =0.r1 r2 rk，其中當(dāng)akk1則rk=1 ;當(dāng)akk=1則 rk=2，k = 1,2, 。這樣就保證了r不等于序列中任何數(shù)，因?yàn)閷?duì)任意k，r的第k位rk與序列中第k號(hào)數(shù)的第k位akk不相等。 因?yàn)閞不在序列中，所以，(0,1)是不可數(shù)集。第四十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)46對(duì)角線方法定理4.3.3中所使用的方法稱為對(duì)角線方法。a11a22a33r1r2r31 2 3 對(duì)角線方法是一種非常有用的方法。第四十六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)47連續(xù)統(tǒng)問題已知N是可數(shù)集，而|N|R

33、|.能否找到一個(gè)實(shí)數(shù)集R的子集A，使得： NAR ,但又不存在A到R的雙射？這個(gè)問題稱為“連續(xù)統(tǒng)問題”?，F(xiàn)已證明：在現(xiàn)有公理系統(tǒng)中，證明它成立與否都不可能。第四十七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)48新春曉信息時(shí)代到，處處有電腦。夜來(lái)打字聲，程序知多少？ 答曰： 詩(shī)中的問題是計(jì)算機(jī)上所有程序有多少？為何如此？有詩(shī)為證：計(jì)算機(jī)，靠程序，它的本事知底細(xì)。程序都是符號(hào)串，理應(yīng)是個(gè)可數(shù)集。程序時(shí)時(shí)新， 落花處處飄。它們同為0 ，數(shù)數(shù)便知道。第四十八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)49第一篇的總結(jié)集合；關(guān)系；映射；可數(shù)集與不可數(shù)

34、集。本篇內(nèi)容有：第四十九張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)50集合基本概念：集合、子集、冪集。集合之間的關(guān)系：(真)含于( / )，相等()。集合的基本運(yùn)算： 并()、交()、差()和對(duì)稱差()。笛卡爾直積： n個(gè)集合的笛卡爾直積是它們的 n元有序組的集合。它仍然是個(gè)集合。集合的表示：列舉法和描述法。第五十張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)51關(guān)系關(guān)系的概念： A到B的二元關(guān)系R是笛卡爾直積AB的子集。關(guān)系仍然是集合。關(guān)系的表示：仍然可以采用集合的表示方法。若A、B是有限集合，或者說R是有限集上的關(guān)系，則R的表示還可以采用

35、：關(guān)系矩陣 和 關(guān)系圖。第五十一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)52關(guān)系的性質(zhì)自反性： x A xRx。 反自反性： x A (xRx)。對(duì)稱性： x ，yA， 若xRy yRx。反對(duì)稱性：x ，yA， 若xRy且yRx x = y 。傳遞性： x ，y，zA， 若xRy且yRz xRz 。令R是定義在集合A上的關(guān)系。第五十二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)53關(guān)系的運(yùn)算關(guān)系是集合，可具有集合的各種運(yùn)算。復(fù)合運(yùn)算：RS = x，z | yB：xRy 且ySz，其中，R，S分別為A到B和B到C的關(guān)系。逆關(guān)系：R-1 =

36、y，x | x，y R。注意復(fù)合運(yùn)算的逆： (RS) 1 = S-1R-1。在一個(gè)集合A上的關(guān)系的冪運(yùn)算： R0 =x，x | x A , Rk = Rk-1R 。第五十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)54關(guān)系的閉包某關(guān)系的具有某種性質(zhì)的閉包是：包含該關(guān)系的最小的有此性質(zhì)的關(guān)系。依據(jù)關(guān)系的性質(zhì)有：r(R)、 s(R)和t(R)，即自反閉包、對(duì)稱閉包和傳遞閉包。r(R) = RR0。s(R) = RR-1。 t(R) =Ri。 i=1第五十四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)55用關(guān)系矩陣實(shí)現(xiàn)關(guān)系的運(yùn)算MRS = MR MS。MR0為R0的關(guān)系矩陣。顯然R-1的關(guān)系矩陣就是MRT。顯然的Rk關(guān)系矩陣是MRk = MRk-1 MR。R的自反閉包為MRMR0。R的對(duì)稱閉包為MRMRT。 nR的傳遞閉包為 MRk。 k=1令R、S為有限集上的關(guān)系，關(guān)系矩陣為MR 和 MS：第五十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月25.09.2022離散數(shù)學(xué)56等價(jià)、劃