離散數(shù)學(xué)第三章課件ppt

1、3.1 集合的概念與表示法集合的概念與表示法3.2 集合的運(yùn)算與性質(zhì)集合的運(yùn)算與性質(zhì) 3.4 排列與組合排列與組合3.3 集合的劃分與覆蓋集合的劃分與覆蓋 3.5 歸納原理歸納原理3.6 容斥原理和抽屜原理容斥原理和抽屜原理3.8 集合論在命題邏輯中的應(yīng)用集合論在命題邏輯中的應(yīng)用 3.7 遞推關(guān)系遞推關(guān)系3.1集合的概念與表示法集合的概念與表示法 3.1.1 集合的概念集合的概念3.1.2 集合的表示法集合的表示法 3.1.3 集合的包含與相等集合的包含與相等 3.1.4 空集、集族、冪集和全集空集、集族、冪集和全集3.1.5 有限冪集元素的編碼表示有限冪集元素的編碼表示3.1.1 集合的概念

2、集合的概念 通常用大寫字母通常用大寫字母(如如A、B等等)表示集合，用小寫字表示集合，用小寫字母母(如如a、b)表示集合中的元素。給定一個(gè)集合表示集合中的元素。給定一個(gè)集合A和一和一個(gè)元素個(gè)元素a，可以判定，可以判定a是否在集合是否在集合A中。如果中。如果a在在A中，中，我們稱我們稱a屬于屬于A，記為，記為aA。否則，稱。否則，稱a不屬于不屬于A，記，記為為a A。 一般我們把一些確定的互不相同的對(duì)象的一般我們把一些確定的互不相同的對(duì)象的全體稱為集合，集合中的對(duì)象稱為集合的元素。全體稱為集合，集合中的對(duì)象稱為集合的元素。 例如，某大學(xué)計(jì)算機(jī)系的全體學(xué)生、所有自然例如，某大學(xué)計(jì)算機(jī)系的全體學(xué)生、

3、所有自然數(shù)等都是集合。數(shù)等都是集合。 說明：一個(gè)集合是作為整體識(shí)別的、確定的、互相區(qū)別的一些事物的全體。嚴(yán)格地講，這只是一種描述，不能算是集合的定義。類似于幾何中的點(diǎn)、線、面等概念，在樸素集合論中，集合也是一種不加定義而直接引入的最基本的原始概念（一給出定義就要引入悖論（Paradox）。而集合論中的其他概念，則都是從它出發(fā)給予了嚴(yán)格的定義。 集合元素的特征：集合元素的特征：確定性、互異性、無序確定性、互異性、無序性和抽象性。性和抽象性。 確定性：一旦給定了集合確定性：一旦給定了集合A，對(duì)于任意元素，對(duì)于任意元素a，可準(zhǔn)確地判定可準(zhǔn)確地判定a是否在是否在A中，這是明確的。中，這是明確的。 互異

4、性：集合中的元素之間是彼此不同的。即集互異性：集合中的元素之間是彼此不同的。即集合合a，b，b，c與集合與集合a，b，c是一樣的。是一樣的。 無序性：集合中的元素之間沒有次序關(guān)系。即集無序性：集合中的元素之間沒有次序關(guān)系。即集合合a，b，c與集合與集合c，b，a是一樣的。是一樣的。 抽象性：集合中的元素是抽象的，甚至可以是集抽象性：集合中的元素是抽象的，甚至可以是集合。如合。如A1，2，1，2，其中，其中1，2是集合是集合A的元的元素。素。 集合中元素的個(gè)數(shù)稱為集合的基數(shù)，記為集合中元素的個(gè)數(shù)稱為集合的基數(shù)，記為|A|。當(dāng)當(dāng)|A|有限時(shí)，稱有限時(shí)，稱A為有限集合為有限集合（Finite set

5、）， ；否則，；否則，稱稱A為無限集合為無限集合（Infinite set） 。下面將本書中常用的集合符號(hào)列舉如下：N：表示全體自然數(shù)組成的集合。Z：表示全體整數(shù)組成的集合。Q：表示全體有理數(shù)組成的集合。R：表示全體實(shí)數(shù)組成的集合。Zm：表示模m同余關(guān)系所有剩余類組成的集合。3.1.2 集合的表示法集合的表示法1.列舉法 列舉法就是將集合的元素全部寫在花括號(hào)內(nèi)，元素之間用逗號(hào)分開。 例如：Aa，b，c，B0，1，2，。 列舉法一般用于有限集合和有規(guī)律的無限集合。2.謂詞表示法 謂詞表示法是用謂詞來概括集合中元素的屬性。通常用x|p(x)來表示具有性質(zhì)p的一些對(duì)象組成的集合。 例如：x|1x6x

6、為整數(shù)為由1、2、3、4、5、6組成的集合。3.1.3 集合的包含與相等集合的包含與相等 外延性原理：兩個(gè)集合外延性原理：兩個(gè)集合A和和B是相等的，是相等的，當(dāng)且僅當(dāng)它們有相同的元素。記為當(dāng)且僅當(dāng)它們有相同的元素。記為AB。 例如，若A2，3，B小于4的素?cái)?shù)，則AB。 定義定義3.1 設(shè)設(shè)A和和B為兩個(gè)集合，若對(duì)于任意為兩個(gè)集合，若對(duì)于任意的的aA必有必有aB，則稱，則稱A是是B的的子集，子集，也稱也稱A包含于包含于B或或B包含包含A，記作記作A B。如果如果B不包含不包含A，記作，記作A B。B包含包含A的符號(hào)化表示為：的符號(hào)化表示為：A Bx(xAxB)。 定理定理3.1 集合集合A和和B

7、相等當(dāng)且僅當(dāng)這兩個(gè)集相等當(dāng)且僅當(dāng)這兩個(gè)集合互為子集。即：合互為子集。即：ABA BB A。 例如，若A1，2，3，4，B1，2，C2，3，則BA且CA，但C B。證證明明 若AB，則A和B具有相同的元素，于是x(xAxB)、x(xBxA)都為真，即AB且BA。 反之，若AB且BA，假設(shè)AB，則A與B元素不完全相同。不妨設(shè)有某個(gè)元素xA但xB，這與AB矛盾，所以AB。定理定理3.2 設(shè)設(shè)A、B和和C是三個(gè)集合，則：是三個(gè)集合，則：(1)A A。(2)A BB CA C。證證明明(1)由定義顯然成立。(2)ABBCx(xAxB)x(xBxC)x(xAxB)(xBxC)x(xAxC)AC。定義定義3

8、.2 設(shè)設(shè)A和和B是兩個(gè)集合，若是兩個(gè)集合，若A B且且B中中至少有一個(gè)元素至少有一個(gè)元素b使得使得b A，則稱，則稱A是是B的的真子集，真子集，也稱也稱A真包含于真包含于B或或B真包含真包含A，記作，記作A B。否則，否則，記作記作A B。B真包含真包含A的符號(hào)化表示：的符號(hào)化表示：A Bx(xAxB) x(xBx A)。若兩個(gè)集合若兩個(gè)集合A和和B沒有公共元素，我們說沒有公共元素，我們說A和和B是是不相交的。不相交的。例如，若Aa，b，c，d，Bb，c，則B是A的真子集，但A不是A的真子集。注：與表示元素和集合的關(guān)系，而、與表示集合和集合的關(guān)系。例如，若A0，1，B0，1，0，1，則AB且

9、AB。定理定理3.3 設(shè)設(shè)A、B和和C是三個(gè)集合，則是三個(gè)集合，則(1) (A A)。 (2)A B(B A)。(3)A BB CA C。證證明明僅證(2)和(3)(2)AB x(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xAxB)(x(xAxB)x(xAxB)(x(xAxB)x(xBxA)(BA)。(3)ABBC(x(xAxB)x(xBxA)x(xAxBxBxC)x(xAxC)(x(xCxA)AC。(x(xBxC)x(xCxB)(x(xBxA)x(xCxB)定義定義3.3 沒有任何元素的集合稱為沒有任何元素的集合稱為空集，記空集，記作作

10、。以集合為元素的集合稱為以集合為元素的集合稱為集族集族。3.1.4 空集、集族、冪集和全集空集、集族、冪集和全集例如，x|xx是空集；xx是某大學(xué)的學(xué)生社團(tuán)是集族。定理定理3.4 空集是任何集合的子集?？占侨魏渭系淖蛹?。任給集合A，則Ax(xxA)。由于x是假的，所以x(xxA)為真，于是有A為真。證證明明特別要注意與的區(qū)別，是不含任何元素的集合，是任意集合的子集，而是含有一個(gè)元素的集合。 定義定義3.4 一個(gè)集合一個(gè)集合A的所有子集組成的集合的所有子集組成的集合稱為稱為A的冪集的冪集（Power Set） ，記作記作P(A)或或2A。推論推論 空集是惟一的?？占俏┮坏摹?對(duì)于任一集合A

11、，我們稱空集和其自身A為A的平凡子集。例例1 1 求冪集P()、P()、P(，)、P(1，2，3)。解解P()P()，P(，)，P(1，2，3)，1，2，3， 1，2，3。定理定理3.5 若若|A|n，則，則|P(A)|2n。證明證明 因?yàn)锳的m個(gè)元素的子集的個(gè)數(shù)為Cnm，所以|P(A)|Cn0Cn1Cnn2n。定理定理3.6 設(shè)設(shè)A和和B是兩個(gè)集合，則：是兩個(gè)集合，則：(1)BP(A)B A。(2)A BP(A) P(B)。(3)P(A)P(B)AB。(4)P(A)P(B)AB。(5)P(A)P(B)P(AB)。(6)P(A)P(B) P(AB)。定義定義3.5 所要討論的集合都是某個(gè)集合的

12、所要討論的集合都是某個(gè)集合的子集，稱這個(gè)集合為子集，稱這個(gè)集合為全集全集（Universal set），記作記作U或或E。全集是一個(gè)相對(duì)的概念。由于所研究的問題不同，所取的全集也不同。例如，在研究整數(shù)間的問題時(shí)，可把整數(shù)集Z取作全集。在研究平面幾何的問題時(shí)，可把整個(gè)坐標(biāo)平面取作全集。 Assignments（作業(yè)） 第74頁: 1（偶數(shù)小題），2（偶數(shù)小題），3（偶數(shù)小題）3.2 集合的運(yùn)算與性質(zhì)集合的運(yùn)算與性質(zhì)3.2.1 集合的交、并、補(bǔ)集合的交、并、補(bǔ) 3.2.2 集合的對(duì)稱差集合的對(duì)稱差 3.2.3 廣義并、廣義交運(yùn)算廣義并、廣義交運(yùn)算3.2.4 集合的文氏圖集合的文氏圖3.2.1集合的

13、交、并、補(bǔ)集合的交、并、補(bǔ) 定義定義3.6 設(shè)設(shè)A和和B為兩個(gè)集合，為兩個(gè)集合，A和和B的的交集交集AB （Intersection） 、并集、并集AB （Union）分別定義如下：分別定義如下： ABx|xAxB ABx|xAxB 例如，若A1，2，3，B1，4，則AB1，AB1，2，3，4。集合的交與并可以推廣到n個(gè)集合的情況，即A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn例例1 設(shè)A和B為兩個(gè)集合，且AB，則ACBC。 對(duì)任意的xAC，則有xA且xC。而AB，由xA得xB，則xB且xC，從而xBC。所以，ACBC。例例2 設(shè)A和B為兩個(gè)集合，則ABABBABA。

14、反之，若ABB，因AAB，所以AB。 證證明明證證明明 對(duì)任意的xAB，則xA或xB。又AB，所以xB，于是ABB。又顯然有BAB，故ABB。同理可證ABABA。 定義定義3.7 設(shè)設(shè)A和和B為兩個(gè)集合，所有屬于為兩個(gè)集合，所有屬于A而不而不屬于屬于B的元素組成的集合稱為的元素組成的集合稱為B對(duì)于對(duì)于A的的補(bǔ)集補(bǔ)集( C o m p l e m e n t )， 或 相 對(duì) 補(bǔ) ?；?相 對(duì) 補(bǔ) 。 記 作記 作 A B x|xAx B。AB也稱為也稱為A和和B的差集的差集(Difference)。 例如，若A1，2，3，B1，4，則AB2，3，BA4。 定義定義3.8 設(shè)設(shè)U為全集，集合為全

15、集，集合A關(guān)于關(guān)于U的補(bǔ)集的補(bǔ)集UA稱為集合稱為集合A的的絕對(duì)補(bǔ)絕對(duì)補(bǔ)或或余集，余集，記為記為Ac。即即:Ac x|xU且且x A。例例3 設(shè)A和B為兩個(gè)集合，則ABABc 。因?yàn)閤AB證證明明xAxBxAxBc所以ABABc。xABc定理定理3.7 對(duì)于任意對(duì)于任意3個(gè)集合個(gè)集合A、B和和C，其交、，其交、并、補(bǔ)滿足下面并、補(bǔ)滿足下面10個(gè)定律：個(gè)定律：(1)冪等律冪等律 AAA，AAA(2)結(jié)合律結(jié)合律 (AB)CA(BC) (AB)CA(BC)(3)交換律交換律 ABBA，ABBA(4)分配律分配律 A(BC)(AB)(AC) A(BC)(AB)(AC)(5)同一律同一律 AA，AUA(

16、6)零律零律 AUU，A(7)互補(bǔ)律互補(bǔ)律 AAc U，AAc以上等式的證明主要用到命題演算的等價(jià)式，即欲證集合AB，只需證明xAxB。(8)吸收律吸收律 A(AB)A，A(AB)A(9)德德摩根律摩根律 (A B)c Ac Bc (AB)cAcBc A(BC)(AB)(AC) A(BC)(AB)(AC)(10)雙重否定律雙重否定律 (Ac)c A 定理定理3.8 任意集合任意集合A和和B，BAc ABU且且AB。證證明明如BAc， 則ABAAcU，ABAAc。反之，若ABU且AB，則BBUB(AAc)(BA)(BAc)(BAc) (AAc)(BAc)(AB)AcUAcAc例例4 證明A(BC

17、)(AB)(AC)。證證明明因?yàn)閤A(BC) xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)所以A(BC)(AB)(AC)。例例5 證明(AB)cAcBc。因?yàn)閤(AB)c證證明明xAcBcxABxAxBxAcxBc所以(AB)cAcBc。3.2.2 集合的對(duì)稱差集合的對(duì)稱差 定義定義3.9 集合集合A和和B的的對(duì)稱差對(duì)稱差(Symmetric Difference)定義為定義為A B(AB)(BA)。 例如，若A0，0，則P(A)A(P(A)A)(AP(A)，0，0，0，0。定理定理3.9 設(shè)設(shè)A、B和和C為三個(gè)集合，則：為三個(gè)集合，則： (1)

18、A BB A。 (2)(A B) CA (B C)。 (3)A(B C)(AB) (AC)。 (4)AA；A UAc； A A；A AcU。 (5)A B(AB)(AB)。 證證明明僅證(5)： A B(AB)(AB) AB(AB)(BA)(ABc)(BAc)(ABc)B)(ABc)Ac)(AB)(AB)。(AB)(AcBc)3.2.4 集合的文氏圖集合的文氏圖 在文氏圖中，用矩形表示全集U，矩形內(nèi)部的點(diǎn)均為全集中的元素，用圓或橢圓表示U的子集，其內(nèi)部的點(diǎn)表示不同集合的元素，并將運(yùn)算結(jié)果得到的集合用陰影部分表示。圖3-1表示了集合的5種基本運(yùn)算，陰影部分表示經(jīng)過相應(yīng)運(yùn)算得到的。 集合之間的相互

19、關(guān)系和運(yùn)算還可以用文氏圖來描述，它有助于我們理解問題，有時(shí)對(duì)解題也很有幫助。在不要求有求解步驟的題目中，我們可以使用文氏圖求解，但它不能用于題目的證明。 Assignments（作業(yè)） 3.3集合的劃分與覆蓋集合的劃分與覆蓋 定義定義3.13 設(shè)設(shè) A1，A2，An是集合是集合A的某些非空子集組成的集合，若的某些非空子集組成的集合，若A1AnA，且且AiAj(ij)，則稱，則稱 為為A的一個(gè)的一個(gè)劃分劃分（Partition），），稱稱 中的元素為中的元素為A的的劃分塊劃分塊(Block)。定義定義3.12 設(shè)設(shè)SA1，A2，An是集合是集合A的的某些非空子集組成的集合，若某些非空子集組成的集

20、合，若 A1A2AnA，則稱則稱S為集合為集合A的一個(gè)的一個(gè)覆蓋（覆蓋（Overlay）。）。由定義知，劃分一定是覆蓋，但反之則不然。例如，Sa，b，c，c是Aa，b，c的覆蓋，但不是A的劃分。例例1 1 求集合Aa，b，c的所有不同的劃分。解解 其不同的劃分共有5個(gè)：1a，b，c，2a，b，c，3a，c，b，4a，b，c，5a，b，c 。定理定理3.12 設(shè)設(shè)A1，A2，Ar和和B1，B2，Bs是同一集合是同一集合A的兩種劃分，則其所的兩種劃分，則其所有有AiBj組成的集合也是原集合的一種劃分。組成的集合也是原集合的一種劃分。定義定義3.14 設(shè)設(shè)A1，A2，Ar和和B1，B2，Bs是同一集

21、合是同一集合A的兩種劃分，則稱其的兩種劃分，則稱其所有所有AiBj組成的集合為原來兩劃分的組成的集合為原來兩劃分的交叉交叉劃分。劃分。定義定義3.15 給定給定A的兩個(gè)劃分的兩個(gè)劃分A1，A2，Ar和和B1，B2，Bs，若對(duì)于每個(gè)，若對(duì)于每個(gè)Aj都有都有Bk使得使得Aj Bk，則稱，則稱A1，A2，Ar為為B1，B2，Bs的的加細(xì)。加細(xì)。定理定理3.13 任何兩種劃分的交叉劃分，都是任何兩種劃分的交叉劃分，都是原來各劃分的一種加細(xì)。原來各劃分的一種加細(xì)。證明 設(shè)A1，A2，Ar和B1，B2，Bs的交叉劃分為T，對(duì)于T中任意元素AiBj必有AiBjAi和AiBjBj，故T必是原劃分的加細(xì)。 As

22、signments（作業(yè)） 第75頁: 14（偶數(shù)小題）3.6容斥原理和抽屜原理容斥原理和抽屜原理 3.6.1 容斥原理容斥原理3.6.2 抽屜原理抽屜原理3.6.1容斥原理容斥原理 定理定理3.19(容斥原理容斥原理) 對(duì)有限集合對(duì)有限集合A和和B，有，有|AB|A|B|AB|。因?yàn)橐驗(yàn)锳BB(AB)且且B(AB)證明又又A(AB)(AB)且且(AB)(AB)所以所以|AB|B|AB|。所以所以|A|AB|AB|。故故|AB|A|B|AB| 。 定理定理3.20 推廣到推廣到n個(gè)集合個(gè)集合A1，A2，An的情形，有：的情形，有： |A1A2An| i|Ai|ij|AiAj| ijk|AiAj

23、Ak| (1)n1|A1A2An|。 例例1 一個(gè)班有50個(gè)學(xué)生，在第一次考試中得95分的有26人，在第二次考試中得95分的有21人，如果兩次考試中沒有得95分的有17人，那么兩次考試都得95分的有多少人？設(shè)A和B分別表示在第一次和第二次考試中得95分的學(xué)生的集合。解解則：|A|26，|B|21，|(AB)c|17。于是 |(AB)c| =50- |AB|=50-(|A|+|B|-|AB|)所以，兩次考試都得95分的有14人。從而|AB|=17-50+|A|+|B|=17-50+26+21=14。 例例2 從1，2，3，4，5，6，7，8，9中取7個(gè)不同的數(shù)字構(gòu)成7位數(shù)，如不允許5和6相鄰，總

24、共有多少種方法？任取7個(gè)不同的數(shù)字構(gòu)成7位數(shù)的個(gè)數(shù)為P79=9!/2，5和6相鄰的個(gè)數(shù)為 6 x 2 x P57 67！，根據(jù)容斥原理，總共有9!/267!151200種方法。解解 例例3 某班有25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)。解解設(shè)A、B、C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。則：|A|12，|B|6，|C|14，|AC|6， |BC|=5|ABC|2，|(AC)B|6。所以|(AB)|3。 因?yàn)閨(AC)B|=|(AB)(BC)|=|(AB)|(BC

25、)|ABC|(AB)|526 于是|ABC|=12+6+14-6-5-3+2=20，|(ABC)c|=25-20=5。故，不會(huì)打這三種球的共5人。3.6.2 抽屜原理抽屜原理(鴿巢原理鴿巢原理) 抽屜原理是一個(gè)十分基本、非常重要、應(yīng)用極其廣泛的數(shù)學(xué)原理，是解決數(shù)學(xué)中的一類存在性問題的基本工具。 (2)把多于把多于mn個(gè)元素的集合個(gè)元素的集合S分成分成n個(gè)子集個(gè)子集S1、S2、Sn的并集，那么至少存在一個(gè)的并集，那么至少存在一個(gè)集合集合Si，它包含，它包含S中的中的m1或或m1以上的元以上的元素。素。 定理定理3.21(抽屜原理抽屜原理) (1)把多于把多于n個(gè)元素的集合個(gè)元素的集合S分成分成n個(gè)子集個(gè)子集S1、S2、Sn的并集，那