集合概念和表示法

1、關(guān)于集合的概念與表示法17.08.2022第一張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.1 集合的概念與表示法 3.1.1 集合的概念 集合作為數(shù)學(xué)的一個基本而又簡單的原始概念，是不能精確定義的。一般我們把一些確定的互不相同的對象的全體稱為集合，集合中的對象稱為集合的元素。通常用大寫字母(如A、B等)表示集合，用小寫字母(如a、b)表示集合中的元素。給定一個集合A和一個元素a，可以判定a是否在集合A中。如果a在A中，我們稱a屬于A，記為aA。否則，稱a不屬于A，記為aA。 例如，某大學(xué)計算機(jī)系的全體學(xué)生、所有自然數(shù)等都是集合。第二張，PPT共八十二頁，創(chuàng)作于2022年6

2、月17.08.2022由集合的概念可知，集合中的元素具有確定性、互異性、無序性和抽象性的特征。其中：(1)確定性是指：一旦給定了集合A，對于任意元素a，我們就可以準(zhǔn)確地判定a是否在A中，這是明確的。(2)互異性是指：集合中的元素之間是彼此不同的。即集合a，b，b，c與集合a，b，c是一樣的。(3)無序性是指：集合中的元素之間沒有次序關(guān)系。即集合a，b，c與集合c，b，a是一樣的。(4)抽象性是指：集合中的元素是抽象的，甚至可以是集合。如A1，2，1，2，其中1，2是集合A的元素。第三張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022集合是多種多樣的，我們可以根據(jù)集合中元素的個數(shù)對其

3、進(jìn)行分類。集合中元素的個數(shù)稱為集合的基數(shù)，記為|A|。當(dāng)|A|有限時，稱A為有限集合；否則，稱A為無限集合。下面將本書中常用的集合符號列舉如下：N：表示全體自然數(shù)組成的集合。Z：表示全體整數(shù)組成的集合。Q：表示全體有理數(shù)組成的集合。R：表示全體實數(shù)組成的集合。Zm：表示模m同余關(guān)系所有剩余類組成的集合。第四張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.1.2 集合的表示法 表示一個集合通常有兩種方法：列舉法和謂詞表示法。 1. 列舉法(或枚舉法) 列舉法就是將集合的元素全部寫在花括號內(nèi)，元素之間用逗號分開。例如：Aa，b，c，B0，1，2，3，。 列舉法一般用于有限集合和有

4、規(guī)律的無限集合。 2. 謂詞表示法(或描述法) 謂詞表示法是用謂詞來概括集合中元素的屬性。通常用x|p(x)來表示具有性質(zhì)p的一些對象組成的集合。例如：x|1x6x為整數(shù)為由1、2、3、4、5、6組成的集合。 下面討論集合之間的關(guān)系。第五張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.1.3 集合的包含與相等 包含與相等是集合間的兩種基本關(guān)系，也是集合論中的兩個基本概念。兩個集合相等是按照下述原理定義的。外延性原理 兩個集合A和B是相等的，當(dāng)且僅當(dāng)它們有相同的元素。記為AB。例如，若A2，3，B小于4的素數(shù)，則AB。定義3.1 設(shè)A和B為兩個集合，若對于任意的aA必有aB，則

5、稱A是B的子集，也稱A包含于B或B包含A，記作AB。如果B不包含A，記作AB。B包含A的符號化表示為：ABx(xAxB)。例如，若A1，2，3，4，B1，2，C2，3，則BA且CA，但CB。第六張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.1 集合A和B相等當(dāng)且僅當(dāng)這兩個集合互為子集。即：ABABBA。證明 若AB，則A和B具有相同的元素，于是x(xAxB)、x(xBxA)都為真，即AB且BA。反之，若AB且BA，假設(shè)AB，則A與B元素不完全相同。不妨設(shè)有某個元素xA但xB，這與AB矛盾，所以AB。這個定理非常重要，是證明兩個集合相等的基本思路和依據(jù)。第七張，PPT共八

6、十二頁，創(chuàng)作于2022年6月17.08.2022定理3.2 設(shè)A、B和C是三個集合，則：(1)AA。(2)ABBCAC。證明 (1)由定義顯然成立。(2)ABBCx(xAxB)x(xBxC)x(xAxB)(xBxC)x(xAxC)AC。定義3.2 設(shè)A和B是兩個集合，若AB且B中至少有一個元素b使得bA，則稱A是B的真子集，也稱A真包含于B或B真包含A，記作AB。否則，記作AB。B真包含A的符號化表示：第八張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022ABx(xAxB)x(xBxA)。若兩個集合A和B沒有公共元素，我們說A和B是不相交的。例如，若Aa，b，c，d，Bb，c，則B

7、是A的真子集，但A不是A的真子集。需要指出的是，與表示元素和集合的關(guān)系，而、與表示集合和集合的關(guān)系。例如，若A0，1，B0，1，0，1，則AB且AB。定理3.3 設(shè)A、B和C是三個集合，則(1)(AA)。 (2)AB(BA)。(3)ABBCAC。第九張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022證明 僅證(2)和(3)(2)ABx(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(xBxC)x(xCxB

8、)x(xAxBxBxC)(x(xBxA)x(xCxB)x(xAxC)(x(xCxA)AC。第十張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.1.4 空集、集族、冪集和全集定義3.3 沒有任何元素的集合稱為空集，記作。以集合為元素的集合稱為集族。例如，x|xx是空集；xx是某大學(xué)的學(xué)生社團(tuán)是集族。定理3.4 空集是任何集合的子集。證明 任給集合A，則Ax(xxA)。由于x是假的，所以x(xxA)為真，于是有A為真。推論 空集是惟一的。對于任一集合A，我們稱空集和其自身A為A的平凡子集。第十一張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022特別要注意與的區(qū)別，是不

9、含任何元素的集合，是任意集合的子集，而是含有一個元素的集合。定義3.4 一個集合A的所有子集組成的集合稱為A的冪集，記作P(A)或2A。例1 求冪集P()、P()、P(，)、P(1，2，3)。解 P()P()，P(，)，P(1，2，3)，1，2，3，1，2，3。第十二張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.5 若|A|n，則|P(A)|2n。證明 因為A的m個元素的子集的個數(shù)為Cnm，所以|P(A)|Cn0Cn1Cnn2n。定理3.6 設(shè)A和B是兩個集合，則：(1)BP(A)BA。(2)ABP(A)P(B)。(3)P(A)P(B)AB。(4)P(A)P(B)AB。

10、(5)P(A)P(B)P(AB)。(6)P(A)P(B)P(AB)。第十三張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定義3.5 所要討論的集合都是某個集合的子集，稱這個集合為全集，記作U或E。全集是一個相對的概念。由于所研究的問題不同，所取的全集也不同。例如，在研究整數(shù)間的問題時，可把整數(shù)集Z取作全集。在研究平面幾何的問題時，可把整個坐標(biāo)平面取作全集。第十四張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.1.5 有限冪集元素的編碼表示 為便于在計算機(jī)中表示有限集，可對集合中的元素規(guī)定一種次序，在集合和二進(jìn)制之間建立對應(yīng)關(guān)系。設(shè)Ua1，a2，an，對U的任意

11、子集A，A與一個n位二進(jìn)制數(shù)b1b2bn對應(yīng)，其中bi1當(dāng)且僅當(dāng)aiA。對于一個n位二進(jìn)制數(shù)b1b2bn，使之對應(yīng)一個集合Aai|bi1。 例如，若Aa，b，c，則A的冪集為P(A)Ai|iJ，其中Ji|i是二進(jìn)制數(shù)且000i111，其中A000，A011b，c等。 一般地P(A)Ai|iJ，其中Ji|i是二進(jìn)制數(shù)且 i 。第十五張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.2 集合的運算與性質(zhì) 3.2.1 集合的交、并、補(bǔ) 定義3.6 設(shè)A和B為兩個集合，A和B的交集AB、并集AB分別定義如下：ABx|xAxBABx|xAxB 顯然，AB是由A和B的公共元素組成的集合，A

12、B由A和B的所有元素組成的集合。 例如，若A1，2，3，B1，4，則AB1，AB1，2，3，4。集合的交與并可以推廣到n個集合的情況，即A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn第十六張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例1 設(shè)A和B為兩個集合，且AB，則ACBC。證明 對任意的xAC，則有xA且xC。而AB，由xA得xB，則xB且xC，從而xBC。所以，ACBC。例2 設(shè)A和B為兩個集合，則ABABBABA。證明 對任意的xAB，則xA或xB。又AB，所以xB，于是ABB。又顯然有BAB，故ABB。反之，若ABB，因AAB，所以AB。同理可

13、證ABABA。第十七張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定義3.7 設(shè)A和B為兩個集合，所有屬于A而不屬于B的元素組成的集合稱為B對于A的補(bǔ)集，或相對補(bǔ)。記作ABx|xAxB。AB也稱為A和B的差集。例如，若A1，2，3，B1，4，則AB2，3，BA4。定義3.8 設(shè)U為全集，集合A關(guān)于U的補(bǔ)集UA稱為集合A的絕對補(bǔ)或余集，記為( 或A或Ac)。即 x|xU且xA。例3 設(shè)A和B為兩個集合，則ABA 。證明 因為xABxAxBxAx xA ，所以ABA 。第十八張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.7 對于任意3個集合A、B和C，其交、

14、并、補(bǔ)滿足下面10個定律：(1)冪等律 AAA，AAA(2)結(jié)合律 (AB)CA(BC)，(AB)CA(BC)(3)交換律 ABBA，ABBA(4)分配律 A(BC)(AB)(AC)，A(BC)(AB)(AC)(5)同一律 AA，AUA第十九張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022(6)零律 AUU，A(7)互補(bǔ)律 A U，A (8)吸收律 A(AB)A，A(AB)A(9)德摩根律 ， ，A(BC)(AB)(AC)，A(BC)(AB)(AC)(10)雙重否定律 A以上等式的證明主要用到命題演算的等價式，即欲證集合AB，只需證明xAxB。也可利用已有的公式證明。第二十張，P

15、PT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.8 任意集合A和B，B ABU且AB。證明 如B ，則ABA U，ABA 。反之，若ABU且AB，則BBUB(A )(BA)(B )(B )(A )(B )(AB) U 。例4 證明A(BC)(AB)(AC)。證明 因為xA(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。第二十一張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例5 證明 。證明 因為x xABxAxBx x x ，所以 。例6 證明A(BC)(AB)(AC)。證明

16、因為xA(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。第二十二張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例7 證明A(BC)(AB)(AC)。證明 A(BC)A(B )(AB )(AB )(AB)( )(AB) (AB)(AC)。例8 已知ABAC，ABAC，試證BC。證明 BB(AB)B(AC)(BA)(BC)(AC)(BC)(AB)C(AC)CC。第二十三張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.2.2 集合的對稱差 定義3.9 集合A和B的對稱差定義為AB(

17、AB)(BA)。例如，若A0，0，則P(A)A(P(A)A)(AP(A)，0，0，0，0。 定理3.9 設(shè)A、B和C為三個集合，則： (1)ABBA。 (2)(AB)CA(BC)。 (3)A(BC)(AB)(AC)。第二十四張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022 (4)AA；AU；AA；AU。 (5)AB(AB)(AB)。 證明 僅證(5) AB(AB)(BA)(A)(B)(A)B)(A)(AB)(B)(A)()(AB)()(AB)(AB)。第二十五張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.2.3 廣義并、廣義交運算 定義3.10 集合A的所有元

18、素的元素組成的集合稱為A的廣義并。符號化表示為：Ax|B(BAxB)。 定義3.11 集合A的所有元素的公共元素組成的集合稱為A的廣義交。符號化表示為：Ax|B(BAxB)。 例如，若Aa，b，c，a，d，e，a，f，則Aa，b，c，d，e，f，Aa。 由定義可知，廣義交和廣義并是針對集族而言的，對于非集族來說，其廣義交和廣義并均為空集。第二十六張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.10設(shè)A和B為兩個集合，則：(1)AA。 (2)(AB)(A)(B)。證明 (1)因為xAB(BAxB)AAxAxA，所以AA(2)因為x(AB)C(CABxC)C(CACB)xC)

19、C(CAxC)(CBxC)C(CAxC)C(CBxC)xAxBx(A)(B)，所以(AB)(A)(B)。第二十七張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.11 設(shè)A和B為兩個集合，則：(1)AA。(2)A，BAB。證明 (1)因為xAB(BAxB)AAxAxA，所以AA。(2) 因為xA，BC(CA，BxC)(AA，BxA)(BA，BxB)xAxBxAB，所以A，BAB。第二十八張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.2.4 集合的文氏圖 集合之間的相互關(guān)系和運算還可以用文氏圖來描述，它有助于我們理解問題，有時對解題也很有幫助。在不要求有求

20、解步驟的題目中，我們可以使用文氏圖求解，但它不能用于題目的證明。 在文氏圖中，用矩形表示全集U，矩形內(nèi)部的點均為全集中的元素，用圓或橢圓表示U的子集，其內(nèi)部的點表示不同集合的元素，并將運算結(jié)果得到的集合用陰影部分表示。圖3-1表示了集合的5種基本運算，陰影部分表示經(jīng)過相應(yīng)運算得到的。第二十九張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022第三十張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.3 集合的劃分與覆蓋 在集合的研究中，除了進(jìn)行集合之間的比較外，還要對集合的元素進(jìn)行分類。這一節(jié)將討論集合的劃分問題。定義3.12 設(shè)SA1，A2，An是集合A的某些非空子集

21、組成的集合，若 A，則稱S為集合A的一個覆蓋。定義3.13 設(shè)A1，A2，An是集合A的某些非空子集組成的集合，若 A，且AiAj(ij)，則稱為A的一個劃分，稱中的元素為A的劃分塊。第三十一張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022由定義知，劃分一定是覆蓋，但反之則不然。例如，Sa，b，c，c是Aa，b，c的覆蓋，但不是A的劃分。例1 設(shè)有整數(shù)集Z，res5(x)表示整數(shù)x被5除后所得的余數(shù)。令A(yù)ix|xZres5(x)iiZ5，則A0，A1，A2，A3，A4作成Z的一個劃分。解 由題設(shè)得：A0，10，5，0，5，10，A1，9，4，1，6，11，A2，8，3，2，7，1

22、2，A3，7，2，3，8，13，A4，6，1，4，9，14，。于是， Z，且AiAj(ij)。所以，A0，A1，A2，A3，A4是Z的一個劃分。第三十二張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例2 求集合Aa，b，c的所有不同的劃分。解 其不同的劃分共有5個：1a，b，c，2a，b，c，3a，c，b，4a，b，c，5a，b，c 。定理3.12 設(shè)A1，A2，Ar和B1，B2，Bs是同一集合A的兩種劃分，則其所有AiBj組成的集合也是原集合的一種劃分。定義3.14 設(shè)A1，A2，Ar和B1，B2，Bs是同一集合A的兩種劃分，則稱其所有AiBj組成的集合為原來兩劃分的交叉劃分

23、。第三十三張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定義3.15 給定A的兩個劃分A1，A2，Ar和B1，B2，Bs，若對于每個Aj都有Bk使得AjBk，則稱A1，A2，Ar為B1，B2，Bs的加細(xì)。定理3.13 任何兩種劃分的交叉劃分，都是原來各劃分的一種加細(xì)。證明 設(shè)A1，A2，Ar和B1，B2，Bs的交叉劃分為T，對于T中任意元素AiBj必有AiBjAi和AiBjBj，故T必是原劃分的加細(xì)。例3 設(shè)A1、A2和A3是全集U的子集，則形如 Ai(Ai為Ai或 )的集合稱為由A1、A2和A3產(chǎn)生的小項。試證由A1、A2和A3所產(chǎn)生的所有非空小項的集合構(gòu)成全集U的一個劃分。

24、第三十四張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022證明 小項共8個，設(shè)有r個非空小項s1、s2、sr(r8)。對任意的aU，則aAi或a ，兩者必有一個成立，取Ai為包含元素a的Ai或 ，則a Ai，即有a si，于是U si。又顯然有 siU，所以U si。任取兩個非空小項sp和sq，若spsq，則必存在某個Ai和 分別出現(xiàn)在sp和sq中，于是spsq。綜上可知，s1，s2，sr是U的一個劃分。第三十五張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.4 排列與組合3.4.1 加法與乘法原理 在組合計數(shù)的計算和研究中，加法原理和乘法原理是兩個最常用也是最基

25、本的原理。 加法原理 若事件的有限集合SS1S2Sn，且S1、S2、Sn兩兩不相交，則|S|S1|S2|Sn| 乘法原理 若事件的有限集合S是依次取自有限集合S1、S2、Sn中事件的序列的集合，則|S|S1|S2|Sn|第三十六張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例1 求由數(shù)字1、2、3、4、5組成的小于1000的數(shù)(每個數(shù)字都允許重復(fù)出現(xiàn))的個數(shù)。解 在三位數(shù)中，每一個數(shù)位上的數(shù)字都有5種不同的選取法，由乘法原理知，滿足條件的三位數(shù)的個數(shù)是53個。同理可知，滿足條件的二位數(shù)和一位數(shù)的個數(shù)分別為52個和5個。再由加法原理知，滿足條件的自然數(shù)總共有53525155個。第

26、三十七張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.4.2 排列和組合 1.排列 定義3.16 集合S有n個元素，從中選取r個元素作有序排列，且在排列中不允許任何元素重復(fù)出現(xiàn)，則稱這種排列為S的r無重復(fù)排列。當(dāng)rn時，稱其為全排列。S的所有r無重復(fù)排列的個數(shù)記為P(n，r)或Pnr。 定理3.14 n個元素的r無重復(fù)排列的個數(shù)為：P(n，r)n(n1)(n2)(nr1)。當(dāng)rn時，P(n，n)n! 證明 在從n個不同的元素中按順序取出r個元素時，第一個元素有n種不同的選法，第2個元素有n1種不同的選法，第r個元素從剩下的nr1個元素中選取，有nr1種不同的選法。根據(jù)乘法原理

27、，順序選取r個元素共有的不同選取方法數(shù)為：P(n，r)n(n1)(n2)(nr1)。第三十八張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例2 從1、2、9中選取數(shù)字構(gòu)成3位數(shù)，如要求每個數(shù)字都不相同，問共有多少種方法？解 從1、2、9中選取百位數(shù)，共9種選法，再從剩下的數(shù)字中選取十位數(shù)，共8種選法，最后從剩下的數(shù)字中選取個位數(shù)，共7種選法。因此，從1、2、9中選取數(shù)字構(gòu)成3位數(shù)共有987504種方法。定義3.17 r無重復(fù)排列可以看作是將選出的r個元素排列在一條直線上的排列，這時也稱為r線狀排列。如果把這r個元素排列在一個圓周上，則這種排列稱為S的r圓排列。對兩個圓排列，若其

28、中一個圓排列可以由另一個圓排列通過旋轉(zhuǎn)而得到，則認(rèn)為這兩個圓排列在本質(zhì)上是同一個圓排列。于是有下面的結(jié)論成立。第三十九張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.15 n個元素的r圓排列的個數(shù)N(n，r)為證明 為了得到n個元素的r無重復(fù)排列，可以先從n個元素中選取r個元素作r圓排列，這種圓排列的個數(shù)是N(n，r)。然后，將這個r圓排列斷開后即可得到線狀的r無重復(fù)排列。因為從r個不同的位置處斷開，由乘法原理可得P(n，r)rN(n，r)，即例3 有8個人圍著圓桌進(jìn)餐，如果要求每餐坐的順序不同，那么他們在一起最多能共進(jìn)幾天餐？解 首先8圓排列數(shù)為8!/8，又一日三餐，故

29、他們一起能共餐8!/(83)1680天。第四十張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20222.組合定義3.18 集合S有n個元素，從中選取r個元素，若不考慮它們的排列順序，且在選取中不允許元素重復(fù)出現(xiàn)，稱這種選取方式為S的r無重復(fù)組合。S的所有r無重復(fù)組合的個數(shù)記為C(n，r)或Cnr。定理3.16 n個元素的r無重復(fù)組合的個數(shù)為C(n，r) 。證明 為了得到n個元素的r無重復(fù)排列，可以先從n個元素中選取r個元素作r無重復(fù)組合，這種無重復(fù)組合的個數(shù)是C(n，r)，然后將這r個取出的元素作r無重復(fù)排列，這種r無重復(fù)排列的個數(shù)是P(r，r)r!。由乘法原理可得P(n，r)r!C(

30、n，r)，即C(n，r) 。第四十一張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例4 從1、2、300之中任取3個數(shù)，使得它們的和能被3整除，問有多少種方法？解 把1、2、300分成A、B和C三組，A3k1|kZ，B3k2|kZ，C3k|kZ。任取三個數(shù)i、j、k，那么選取是無序的且滿足ijk能被3整除。將選法分為兩類：都取自同一組，方法數(shù)3C(100，3)。分別取自A、B和C，方法數(shù)(C(100，1)3。由加法原則，總?cè)?shù)為3C(100，3)(C(100，1)31485100。第四十二張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.4.3 排列與組合的生成

31、 1.排列的生成 排列的生成算法有詞典順序法、逆序法和遞歸排序法等。在這里僅介紹詞典順序法。 設(shè)S1，2，n，(a1，a2，an)和(b1，b2，bn)是S的兩個排列，若存在i1，2，n，使得對一切j1，2，i有ajbj而ai1bi1，則稱排列(a1，a2，an)字典序小于(b1，b2，bn)，并記為(a1，a2，an)(b1，b2，bn)。若(a1，a2，an)(b1，b2，bn)，且不存在異于(a1，a2，an)和(b1，b2，bn)的排列(c1，c2，cn)，使得(a1，a2，an)(c1，c2，cn)(b1，b2，bn)，則稱(b1，b2，bn)為(a1，a2，an)的下一個排列。第四

32、十三張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.17 對S的兩個排列，(b1，b2，bn)是(a1，a2，an)的下一個排列的充要條件是：(1)存在m1，2，n，使得對一切i1，2，m1有aibi，ambm，amam1且am1am2an；(2)bmminaj| ajam，jm1，m2，n；(3)bm1bm2bn。由此定理可建立生成所有排列的算法：步1：置(a1，a2，an)(1，2，n)步2：設(shè)已有排列(a1，a2，an)，置in；步2.1：若aiai1，則記mi1，令bmminaj|ajam，ji，i1，n，并將(am，am1，an)bm第四十四張，PPT共八十二頁

33、，創(chuàng)作于2022年6月17.08.2022中的元素由小到大排起來，記這個排列為(bm1，am2，an)。置(a1，a2，am1，am，am1，an)(a1，a2，am1，bm，bm1，bn)然后返回步2。步2.2：若aiai1，則當(dāng)i11時，置ii1，返回步2.1。當(dāng)i11時，算法終止。例5 S1，2，3，4，求其全排列。解 123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321。第四十五張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20222. 組

34、合的生成定理3.18 (a1，a2，ar)和(b1，b2，br)是S的兩個不同的r子集，則(b1，b2，br)是(a1，a2，ar)的下一個子集的充要條件是：(1)存在1mr，使得對一切i1，2，m1有aibi，對一切im有amnri；(2)bmam1；(3)對于mjr1，有bj1bj1。由此定理可建立生成所有子集的算法：步1：設(shè)S1，2，n，取(a1，a2，ar)(1，2，r)第四十六張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022步2：設(shè)已有S的r子集(a1，a2，ar)，置ir；步2.1：若ainri，則令biai1，并且對ji，i1，r1，置bj1bj1。然后置(a1，a

35、2，ar)(a1，a2，ai1，bi，bi1，br)，然后返回步2。步2.2：若ainri，則當(dāng)i1時，置ii1，返回步2.1。當(dāng)i1時，算法終止。例6 S1，2，3，4，5，6，求其所有4元素子集。解 123412351236124512461256134513461356145623452346235624563456。第四十七張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.5 歸納原理 3.5.1 結(jié)構(gòu)歸納原理 設(shè)集合A是歸納定義的集合，現(xiàn)欲證A中所有元素具有性質(zhì)P，即證：對于任意xA有P(x)為真?？蛇M(jìn)行如下證明： (1)(歸納基礎(chǔ))證明歸納定義基礎(chǔ)條款中規(guī)定的A的基

36、本元素x均使P(x)為真。 (2)(歸納推理)證明歸納定義的歸納條款是“保性質(zhì)P的”。即在假設(shè)歸納條款中已確定元素x1、x2、xn使P(xi)(i1，2，n)真的前提下，證明用歸納條款中的操作g所生成元素g(x1，x2，xn)依然具有性質(zhì)P，即P(g(x1，x2，xn)為真。第四十八張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022由于A僅由(1)和(2)條款所確定的元素組成，因此當(dāng)上述證明過程完成時，“A中所有元素具有性質(zhì)P”得證。這種推理原理稱為歸納原理，應(yīng)用這一原理進(jìn)行證明的方法稱為歸納法。為區(qū)別通常所說的數(shù)學(xué)歸納法，它又稱為“結(jié)構(gòu)歸納法”。數(shù)學(xué)歸納法是其一種特例。第四十九張

37、，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.5.2 數(shù)學(xué)歸納原理 將上述原理應(yīng)用到自然數(shù)集上進(jìn)行歸納推理，就是我們所說的數(shù)學(xué)歸納法。 1.第一數(shù)學(xué)歸納法 用第一數(shù)學(xué)歸納法證明所有自然數(shù)具有性質(zhì)P時，只要如下推理： (1)歸納基礎(chǔ)：證P(0)真，即證明數(shù)0具有性質(zhì)P。 (2)歸納過程：對任意k(0)，假設(shè)P(k)真(歸納假設(shè)“k滿足性質(zhì)P”)時，推出P(k1)真。 (3)結(jié)論：所有自然數(shù)具有性質(zhì)P。第五十張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例1 用歸納法證明：對任意的自然數(shù)n，有(012n)2031323n3。證明 當(dāng)n0時，n203。假設(shè)nk時，(

38、012k)2031323k3，那么nk1時，(012kk1)2(012k)22(012k)(k1)(k1)2 031323k3k(k1)2(k1)2031323k3(k1)3所以，對任意自然數(shù)結(jié)論成立。第五十一張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20222.第二數(shù)學(xué)歸納法用第二數(shù)學(xué)歸納法證明所有自然數(shù)具有性質(zhì)P時，只要如下推理：(1)歸納基礎(chǔ)：證P(0)真，即證明數(shù)0具有性質(zhì)P。(2)歸納過程：對任意k(0)，假設(shè)P(i)真，ki0(歸納假設(shè)“0，1，k1滿足性質(zhì)P”)時，推出P(k)真。(3)結(jié)論：所有自然數(shù)具有性質(zhì)P。例2 有數(shù)目相同的兩堆棋子(每堆棋子數(shù)為n)，甲、乙兩

39、人玩取棋子游戲。規(guī)定兩人輪流取棋子，每次兩人取子數(shù)相同，不能不取，也不能同時在兩堆中取子，取得最后一枚棋子者為勝者。求證：后取者必勝。第五十二張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022證明 不妨設(shè)甲為先取者，乙為后取者。當(dāng)n1時，兩堆各有一枚棋子，甲必先從一堆中取走一枚棋子，余下最后一枚棋子必被乙取走，乙勝。假設(shè)nk時乙必勝。下證nk時也是乙必勝。設(shè)第一輪取子時，甲從一堆中取走r枚棋子，余下krk枚棋子，那么，乙從另一堆中也取走r枚棋子，亦留下krk枚棋子。若(1)rk，那么乙取走最后一枚棋子，乙勝。(2)1rk，那么1krk。對留下的兩堆棋子，每一堆為kr枚，由歸納假設(shè)，

40、在以后甲乙的搏奕中乙必勝。因此全局也是乙必勝。第五十三張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.6 容斥原理和抽屜原理 3.6.1 容斥原理 設(shè)集合A是歸納定義的集合，現(xiàn)欲證A中所有元素具有性質(zhì)P，即證：對于任意xA有P(x)為真?？蛇M(jìn)行如下證明： (1)(歸納基礎(chǔ))證明歸納定義基礎(chǔ)條款中規(guī)定的A的基本元素x均使P(x)為真。 (2)(歸納推理)證明歸納定義的歸納條款是“保性質(zhì)P的”。即在假設(shè)歸納條款中已確定元素x1、x2、xn使P(xi)(i1，2，n)真的前提下，證明用歸納條款中的操作g所生成元素g(x1，x2，xn)依然具有性質(zhì)P，即P(g(x1，x2，xn)為真

41、。第五十四張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022集合的運算，可用于有限個元素的計數(shù)問題。在有限集的元素計數(shù)問題中，容斥原理有著廣泛的應(yīng)用。定理3.19(容斥原理) 對有限集合A和B，有|AB|A|B|AB|。證明 因為ABB(AB)且B(AB)，所以|AB|B|AB|。又因為A(AB)(AB)且(AB)(AB)，所以|A|AB|AB|。故|AB|A|B|AB| 。定理3.20 推廣到n個集合A1，A2，An的情形，有：|A1A2An|i|Ai|ij|AiAj|ijk|AiAjAk|(1)n1|A1A2An|。第五十五張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.

42、2022例1 一個班有50個學(xué)生，在第一次考試中得95分的有26人，在第二次考試中得95分的有21人，如果兩次考試中沒有得95分的有17人，那么兩次考試都得95分的有多少人？解 設(shè)A和B分別表示在第一次和第二次考試中得95分的學(xué)生的集合。則：|A|26，|B|21， 17。于是 50 50(|A|B|AB|)，從而|AB| 50|A|B|1750262114。所以，兩次考試都得95分的有14人。例2 從1，2，3，4，5，6，7，8，9中取7個不同的數(shù)字構(gòu)成7位數(shù)，如不允許5和6相鄰，總共有多少種方法？第五十六張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022解 任取7個不同的數(shù)字

43、構(gòu)成7位數(shù)的個數(shù)為 9!/2，5和6相鄰的個數(shù)為6！(2！ )67！，根據(jù)容斥原理，總共有9!/267!151200種方法。例3 某班有25名學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)。解 設(shè)A、B、C分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。則：第五十七張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022|A|12，|B|6，|C|14，|AC|6， |BC|=5,|ABC|2，|(AC)B|6。因為|(AC)B|(AB)(BC)|(AB)|(BC)|ABC|(AB

44、)|526，所以|(AB)|3。于是|ABC|12614653220， 25205。故，不會打這三種球的共5人。在不要求嚴(yán)格步驟的情況下，以上各題也可通過文氏圖的方法來求解。下面以例3加以說明：設(shè)A、B、C分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。該問題的文氏圖如圖3-2所示。由題意可得：第五十八張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022|I2|I3|I4|I5|12|I4|I5|I6|I7|6|I1|I2|I5|I6|14|I2|I5|6|I5|I6|5|I5|2|I4|I5|I6|6根據(jù)上面各等式，依次求得：第五十九張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2

45、022|I1|5，|I2|4，|I3|5，|I4|1，|I5|2，|I6|3，|I7|0。所以，25|ABC|25(|I1|I2|I3|I4|I5|I6|I7|)25(5451230)5。 故，不會打這三種球的共5人。第六十張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.6.2 抽屜原理(鴿巢原理) 抽屜原理是一個十分基本、非常重要、應(yīng)用極其廣泛的數(shù)學(xué)原理，是解決數(shù)學(xué)中的一類存在性問題的基本工具。 定理3.21(抽屜原理) (1)把多于n個元素的集合S分成n個子集S1、S2、Sn的并集，那么至少存在一個集合Si，它包含S中的兩個或兩個以上的元素。 (2)把多于mn個元素的集合

46、S分成n個子集S1、S2、Sn的并集，那么至少存在一個集合Si，它包含S中的m1或m1以上的元素。 證明 僅證(2),反證法。 (2)若結(jié)論不成立，則對于任意子集Si，有|Si|m，于是|S|S1|S2|Sn|mn，矛盾。第六十一張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例3 在從1到2n的整數(shù)中，任意選取n1個數(shù)，證明在這n1個數(shù)中總存在兩個數(shù)，使得其中一個數(shù)是另一個的倍數(shù)。證明 設(shè)S1，2，2n，Sia|aS，且存在kN使得a2k(2i1)，i1，2，n。于是SS1S2Sn，則n1個數(shù)中必有兩個數(shù)在S的同一個子集Si中，這兩個數(shù)中的一個數(shù)是另一個的偶數(shù)倍。例4 在邊長為

47、1的正方形內(nèi)任意放置九個點，證明其中必存在三個點，使得由它們組成的三角形(可能是退化的)面積不超過1/8。證明 把邊長為1的正方形分成四個全等的小正方形，則至少有一個小正方形內(nèi)有三個點，它們組成的三角形(可能是退化的)面積不超過小正方形的一半，即1/8。第六十二張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.7 遞推關(guān)系 3.7.1 遞推關(guān)系的概念 有些計數(shù)問題往往與求一個數(shù)列的通項有關(guān)。但在一些復(fù)雜的特定條件下要直接求出這個數(shù)列的通項公式，有時十分困難。而在同樣的條件下，寫出該數(shù)列相鄰項之間的關(guān)系，再利用一定的方法和技巧，卻往往能很容易的得到所要的結(jié)論。 例1 斐波那契數(shù)列

48、(Fibonacci)問題 假定一對兔子兩個月成熟后，每月生一對兔子。按照假定，一對剛出生的兔子在n個月后，共有多少對兔子？ 解 設(shè)第n個月的兔子數(shù)為Fn，由題意得F01 F11 FnFn1Fn2，n2第六十三張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例2 漢諾塔(Hanoi)問題 有三根立柱A、B、C以及n個大小不同的圓盤套在立柱A上，大的圓盤在下面，小的圓盤在上面，構(gòu)成一個塔形。現(xiàn)在要把這n個圓盤移到立柱B上?？梢岳眠@三根立柱，每次只能移動一個圓盤，但不允許將它放在較小的圓盤上，問最少需移動多少次？解 令Hn為完成這樣的一次移動至少必須移動圓盤的次數(shù)。為了把n個圓盤從

49、立柱A移到立柱B，可先將n1個圓盤從立柱A移到立柱C，留下最大的圓盤，移動的次數(shù)為Hn1；然后再將最大的圓盤移動到立柱B，移動1次；最后將n1個圓盤從立柱C移到立柱B，移動次數(shù)為Hn1。第六十四張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022于是有Hn2Hn11，n2，其中H11。以上的例子有一個共同的特點，即從我們在計數(shù)問題所得出的數(shù)列中，它的一般項可用它自身數(shù)列中的前面若干項來表達(dá)。這樣，從給定的初始值出發(fā)，利用所建立的關(guān)系式可以依次算出數(shù)列中的每一項。我們稱這些關(guān)系式為遞推關(guān)系。下面我們介紹遞推關(guān)系的幾種解法。第六十五張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2

50、0221.遞推關(guān)系的生成函數(shù)解法設(shè)a0，a1，an，為一個無窮數(shù)列，我們稱f(t)a0a1tantn為該數(shù)列的生成函數(shù)。例3 數(shù)列1，1，1，的生成函數(shù)為 1ttn。將遞推關(guān)系代入數(shù)列的生成函數(shù)的系數(shù)中去，通過計算可以得到生成函數(shù)的顯式，然后再將它展開成冪級數(shù)就可求得數(shù)列的通項。例4 斐波那契數(shù)列問題解 設(shè)F(x) 為斐波那契數(shù)列的生成函數(shù)，則有第六十六張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022F(x)F0F1x 1x 1xxxn 1xx (F(x)1)x2F(x)從上面關(guān)系式可以解出F(x) 比較等式兩邊xn的系數(shù)，得到Fn 。第六十七張，PPT共八十二頁，創(chuàng)作于2022

51、年6月17.08.20222.常系數(shù)線性齊次遞推關(guān)系的解法我們把形如H(n)b1H(n1)b2H(n2)bkH(nk)0(其中H(n)、H(n1)、H(nk)是n的函數(shù))的遞推關(guān)系式稱為常系數(shù)線性齊次遞推關(guān)系，并稱xkb1xk1b2xk2bk0為其特征方程，它的根稱為其特征根。在使用特征根方法求解遞推關(guān)系時要用到下面三個定理，其證明參見相關(guān)文獻(xiàn)。定理3.22 設(shè)q為非零的實數(shù)或復(fù)數(shù)，則H(n)qn是遞推關(guān)系式H(n)b1H(n1)b2H(n2)bkH(nk)0(kn，bk0)的解當(dāng)且僅當(dāng)q是它的一個特征根。第六十八張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.23 設(shè)q

52、1、q2、qk為非零的實數(shù)或復(fù)數(shù)，則H(n)C1q1nC2q2nCkqkn(C1、C2、Ck是確定的常數(shù))是遞推關(guān)系式H(n)b1H(n1)b2H(n2)bkH(nk)0(kn，bk0)的解當(dāng)且僅當(dāng)q1、q2、qk是它的k個不同的特征根。定理3.24 設(shè)q1、q2、qk為非零的實數(shù)或復(fù)數(shù)，它們是遞推關(guān)系式H(n)b1H(n1)b2H(n2)bkH(nk)0(kn，bk0)的特征方程的t(tk)個不同的特征根，各有e1、e2、et重。則遞推關(guān)系式的一般解是H(n)H1(n)H2(n)Ht(n)，其中Hi(n)C1qinC2nqinqin(i1，2，t；C1，C2，為確定的常數(shù))。例6 斐波那契數(shù)

53、列問題第六十九張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022解 遞推關(guān)系FnFn1Fn2的特征方程為x2x10，其解為：x1 ，x2 。于是遞推關(guān)系的通解為FnC1 C2 。將F01，F(xiàn)11代入得C1C21C1 C2 1解上述式子得：C1 ，C2 。于是Fn 。第七十張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.常系數(shù)線性非齊次遞推關(guān)系的解法我們把形如H(n)b1H(n1)b2H(n2)bkH(nk)f(n)(其中H(n)、H(n1)、H(nk)是n的函數(shù)，f(n)是n的多項式或an)的遞推關(guān)系式稱為常系數(shù)線性非齊次遞推關(guān)系。這類遞推關(guān)系的求解可通過將非齊次

54、遞推關(guān)系歸約為齊次遞推關(guān)系的方法來求解。下面我們通過一個例子來說明。例7 漢諾塔問題解 遞推關(guān)系Hn2Hn11對應(yīng)的齊次方程的通解為HnC2n。利用常系數(shù)變易法作代換Hnan2n可得anan1，從而ana0a01，Hnan2n(1a0)2n1。由H11得a01。因此，Hn2n1。第七十一張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.20223.8 集合論在命題邏輯中的應(yīng)用 3.8.1 命題邏輯中的集合表示 首先引入以下幾個符號： (A)：命題公式A的主析取范式中所有小項mi的下標(biāo)組成的集合。 A：命題公式A的主合取范式中所有大項Mi的下標(biāo)組成的集合。 令U0，1，2，2n1，則U為n個

55、命題變元所組成的所有小項(或大項)對應(yīng)的下標(biāo)組成的集合。 下面，我們先通過一個例子來說明命題公式的主范式可以用集合來表示，然后證明命題公式的主范式和推理都可通過集合運算而得到。第七十二張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022例1 求命題公式PQ與PQ的主析取范式。解 命題公式PQ與PQ的真值表如表3-1所示：表3-1于是(PQ)3，(PQ)1，2，3。 將上述例子推廣到含有n個命題變元的命題公式中，則有以下的重要結(jié)論。第七十三張，PPT共八十二頁，創(chuàng)作于2022年6月17.08.2022定理3.25 設(shè)VP1，P2，Pn，A是命題公式，其包含的命題變元均在集合V中，則AU(A)。定理3.26 設(shè)VP1，P2，Pn，U0，1，2，2n1，對于任意PiV，則(Pi)x|xUx的n位二進(jìn)制表示中第i位元素為1，Pix|xUx的n位二進(jìn)制表示中第i位元素為0。約定，x的n位二進(jìn)制表示中從左到右依次為第1