集合的概念與表示法

關(guān)于集合的概念與表示法第一頁(yè)，共八十二頁(yè)，2022年，8月28日3.1集合的概念與表示法3.1.1集合的概念

集合作為數(shù)學(xué)的一個(gè)基本而又簡(jiǎn)單的原始概念，是不能精確定義的。一般我們把一些確定的互不相同的對(duì)象的全體稱為集合，集合中的對(duì)象稱為集合的元素。通常用大寫字母(如A、B等)表示集合，用小寫字母(如a、b)表示集合中的元素。給定一個(gè)集合A和一個(gè)元素a，可以判定a是否在集合A中。如果a在A中，我們稱a屬于A，記為a∈A。否則，稱a不屬于A，記為aA。例如，某大學(xué)計(jì)算機(jī)系的全體學(xué)生、所有自然數(shù)等都是集合。第二頁(yè)，共八十二頁(yè)，2022年，8月28日由集合的概念可知，集合中的元素具有確定性、互異性、無(wú)序性和抽象性的特征。其中：(1)確定性是指：一旦給定了集合A，對(duì)于任意元素a，我們就可以準(zhǔn)確地判定a是否在A中，這是明確的。(2)互異性是指：集合中的元素之間是彼此不同的。即集合{a，b，b，c}與集合{a，b，c}是一樣的。(3)無(wú)序性是指：集合中的元素之間沒(méi)有次序關(guān)系。即集合{a，b，c}與集合{c，b，a}是一樣的。(4)抽象性是指：集合中的元素是抽象的，甚至可以是集合。如A＝{1，2，{1，2}}，其中{1，2}是集合A的元素。第三頁(yè)，共八十二頁(yè)，2022年，8月28日集合是多種多樣的，我們可以根據(jù)集合中元素的個(gè)數(shù)對(duì)其進(jìn)行分類。集合中元素的個(gè)數(shù)稱為集合的基數(shù)，記為|A|。當(dāng)|A|有限時(shí)，稱A為有限集合；否則，稱A為無(wú)限集合。下面將本書中常用的集合符號(hào)列舉如下：N：表示全體自然數(shù)組成的集合。Z：表示全體整數(shù)組成的集合。Q：表示全體有理數(shù)組成的集合。R：表示全體實(shí)數(shù)組成的集合。Zm：表示模m同余關(guān)系所有剩余類組成的集合。第四頁(yè)，共八十二頁(yè)，2022年，8月28日3.1.2集合的表示法

表示一個(gè)集合通常有兩種方法：列舉法和謂詞表示法。

1.列舉法(或枚舉法)

列舉法就是將集合的元素全部寫在花括號(hào)內(nèi)，元素之間用逗號(hào)分開(kāi)。例如：A＝{a，b，c}，B＝{0，1，2，3，…}。列舉法一般用于有限集合和有規(guī)律的無(wú)限集合。

2.謂詞表示法(或描述法)

謂詞表示法是用謂詞來(lái)概括集合中元素的屬性。通常用{x|p(x)}來(lái)表示具有性質(zhì)p的一些對(duì)象組成的集合。例如：{x|1≤x≤6∧x為整數(shù)}為由1、2、3、4、5、6組成的集合。下面討論集合之間的關(guān)系。第五頁(yè)，共八十二頁(yè)，2022年，8月28日3.1.3集合的包含與相等

包含與相等是集合間的兩種基本關(guān)系，也是集合論中的兩個(gè)基本概念。兩個(gè)集合相等是按照下述原理定義的。外延性原理兩個(gè)集合A和B是相等的，當(dāng)且僅當(dāng)它們有相同的元素。記為A＝B。例如，若A＝{2，3}，B＝{小于4的素?cái)?shù)}，則A＝B。定義3.1

設(shè)A和B為兩個(gè)集合，若對(duì)于任意的a∈A必有a∈B，則稱A是B的子集，也稱A包含于B或B包含A，記作AB。如果B不包含A，記作AB。B包含A的符號(hào)化表示為：ABx(x∈A→x∈B)。例如，若A＝{1，2，3，4}，B＝{1，2}，C＝{2，3}，則BA且CA，但CB。第六頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.1集合A和B相等當(dāng)且僅當(dāng)這兩個(gè)集合互為子集。即：A＝BAB∧BA。證明若A＝B，則A和B具有相同的元素，于是x(x∈A→x∈B)、x(x∈B→x∈A)都為真，即AB且BA。反之，若AB且BA，假設(shè)A≠B，則A與B元素不完全相同。不妨設(shè)有某個(gè)元素x∈A但xB，這與AB矛盾，所以A＝B。這個(gè)定理非常重要，是證明兩個(gè)集合相等的基本思路和依據(jù)。第七頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.2設(shè)A、B和C是三個(gè)集合，則：(1)AA。(2)AB∧BCAC。證明

(1)由定義顯然成立。(2)AB∧BCx(x∈A→x∈B)∧x(x∈B→x∈C)x((x∈A→x∈B)∧(x∈B→x∈C))x(x∈A→x∈C)AC。定義3.2

設(shè)A和B是兩個(gè)集合，若AB且B中至少有一個(gè)元素b使得bA，則稱A是B的真子集，也稱A真包含于B或B真包含A，記作AB。否則，記作AB。B真包含A的符號(hào)化表示：第八頁(yè)，共八十二頁(yè)，2022年，8月28日ABx(x∈A→x∈B)∧x(x∈B∧xA)。若兩個(gè)集合A和B沒(méi)有公共元素，我們說(shuō)A和B是不相交的。例如，若A＝{a，b，c，d}，B＝{b，c}，則B是A的真子集，但A不是A的真子集。需要指出的是，∈與表示元素和集合的關(guān)系，而、與＝表示集合和集合的關(guān)系。例如，若A＝{0，1}，B＝{0，1，{0，1}}，則AB且AB。定理3.3設(shè)A、B和C是三個(gè)集合，則(1)(AA)。(2)AB(BA)。(3)AB∧BCAC。第九頁(yè)，共八十二頁(yè)，2022年，8月28日證明僅證(2)和(3)(2)ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))(BA)。(3)AB∧BC(x(x∈A→x∈B)∧x(x∈B∧xA))∧(x(x∈B→x∈C)∧x(x∈C∧xB))x(x∈A→x∈B∧x∈B→x∈C)∧(x(x∈B∧xA)∧x(x∈C∧xB))x(x∈A→x∈C)∧(x(x∈C∧xA)AC。第十頁(yè)，共八十二頁(yè)，2022年，8月28日3.1.4空集、集族、冪集和全集定義3.3沒(méi)有任何元素的集合稱為空集，記作。以集合為元素的集合稱為集族。例如，{x|x≠x}是空集；{x｜x是某大學(xué)的學(xué)生社團(tuán)}是集族。定理3.4

空集是任何集合的子集。證明任給集合A，則Ax(x∈→x∈A)。由于x∈是假的，所以x(x∈→x∈A)為真，于是有A為真。推論空集是惟一的。對(duì)于任一集合A，我們稱空集和其自身A為A的平凡子集。第十一頁(yè)，共八十二頁(yè)，2022年，8月28日特別要注意與{}的區(qū)別，是不含任何元素的集合，是任意集合的子集，而{}是含有一個(gè)元素的集合。定義3.4

一個(gè)集合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}}}。第十二頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.5

若|A|＝n，則|P(A)|＝2n。證明因?yàn)锳的m個(gè)元素的子集的個(gè)數(shù)為Cnm，所以|P(A)|＝Cn0＋Cn1＋…＋Cnn＝2n。定理3.6設(shè)A和B是兩個(gè)集合，則：(1)B∈P(A)BA。(2)ABP(A)P(B)。(3)P(A)＝P(B)A＝B。(4)P(A)∈P(B)A∈B。(5)P(A)∩P(B)＝P(A∩B)。(6)P(A)∪P(B)P(A∪B)。第十三頁(yè)，共八十二頁(yè)，2022年，8月28日定義3.5

所要討論的集合都是某個(gè)集合的子集，稱這個(gè)集合為全集，記作U或E。全集是一個(gè)相對(duì)的概念。由于所研究的問(wèn)題不同，所取的全集也不同。例如，在研究整數(shù)間的問(wèn)題時(shí)，可把整數(shù)集Z取作全集。在研究平面幾何的問(wèn)題時(shí)，可把整個(gè)坐標(biāo)平面取作全集。第十四頁(yè)，共八十二頁(yè)，2022年，8月28日3.1.5有限冪集元素的編碼表示為便于在計(jì)算機(jī)中表示有限集，可對(duì)集合中的元素規(guī)定一種次序，在集合和二進(jìn)制之間建立對(duì)應(yīng)關(guān)系。設(shè)U＝{a1，a2，…，an}，對(duì)U的任意子集A，A與一個(gè)n位二進(jìn)制數(shù)b1b2…bn對(duì)應(yīng)，其中bi＝1當(dāng)且僅當(dāng)ai∈A。對(duì)于一個(gè)n位二進(jìn)制數(shù)b1b2…bn，使之對(duì)應(yīng)一個(gè)集合A＝{ai|bi＝1}。例如，若A＝{a，b，c}，則A的冪集為P(A)＝{Ai|i∈J}，其中J＝{i|i是二進(jìn)制數(shù)且000≤i≤111}，其中A000＝，A011＝{b，c}等。一般地P(A)＝{Ai|i∈J}，其中J＝{i|i是二進(jìn)制數(shù)且≤i≤}。第十五頁(yè)，共八十二頁(yè)，2022年，8月28日3.2集合的運(yùn)算與性質(zhì)3.2.1集合的交、并、補(bǔ)

定義3.6

設(shè)A和B為兩個(gè)集合，A和B的交集A∩B、并集A∪B分別定義如下：A∩B＝{x|x∈A∧x∈B}A∪B＝{x|x∈A∨x∈B}

顯然，A∩B是由A和B的公共元素組成的集合，A∪B由A和B的所有元素組成的集合。例如，若A＝{1，2，3}，B＝{1，4}，則A∩B＝{1}，A∪B＝{1，2，3，4}。集合的交與并可以推廣到n個(gè)集合的情況，即A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An}第十六頁(yè)，共八十二頁(yè)，2022年，8月28日例1設(shè)A和B為兩個(gè)集合，且AB，則A∩CB∩C。證明對(duì)任意的x∈A∩C，則有x∈A且x∈C。而AB，由x∈A得x∈B，則x∈B且x∈C，從而x∈B∩C。所以，A∩CB∩C。例2設(shè)A和B為兩個(gè)集合，則ABA∪B＝BA∩B＝A。證明對(duì)任意的x∈A∪B，則x∈A或x∈B。又AB，所以x∈B，于是A∪BB。又顯然有BA∪B，故A∪B＝B。反之，若A∪B＝B，因AA∪B，所以AB。同理可證ABA∩B＝A。第十七頁(yè)，共八十二頁(yè)，2022年，8月28日定義3.7

設(shè)A和B為兩個(gè)集合，所有屬于A而不屬于B的元素組成的集合稱為B對(duì)于A的補(bǔ)集，或相對(duì)補(bǔ)。記作A－B＝{x|x∈A∧xB}。A－B也稱為A和B的差集。例如，若A＝{1，2，3}，B＝{1，4}，則A－B＝{2，3}，B－A＝{4}。定義3.8

設(shè)U為全集，集合A關(guān)于U的補(bǔ)集U－A稱為集合A的絕對(duì)補(bǔ)或余集，記為(或～A或Ac)。即＝{x|x∈U且xA}。例3

設(shè)A和B為兩個(gè)集合，則A－B＝A∩。證明因?yàn)閤∈A－Bx∈A∧xBx∈A∧x∈x∈A∩，所以A－B＝A∩。第十八頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.7

對(duì)于任意3個(gè)集合A、B和C，其交、并、補(bǔ)滿足下面10個(gè)定律：(1)冪等律A∩A＝A，A∪A＝A(2)結(jié)合律(A∪B)∪C＝A∪(B∪C)，(A∩B)∩C＝A∩(B∩C)(3)交換律A∪B＝B∪A，A∩B＝B∩A(4)分配律A∪(B∩C)＝(A∪B)∩(A∪C)，A∩(B∪C)＝(A∩B)∪(A∩C)(5)同一律A∪＝A，A∩U＝A第十九頁(yè)，共八十二頁(yè)，2022年，8月28日(6)零律A∪U＝U，A∩＝(7)互補(bǔ)律A∪＝U，A∩＝(8)吸收律A∪(A∩B)＝A，A∩(A∪B)＝A(9)德·摩根律＝∩，＝∪，A－(B∪C)＝(A－B)∩(A－C)，A－(B∩C)＝(A－B)∪(A－C)(10)雙重否定律＝A以上等式的證明主要用到命題演算的等價(jià)式，即欲證集合A＝B，只需證明x∈Ax∈B。也可利用已有的公式證明。第二十頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.8

任意集合A和B，B＝A∪B＝U且A∩B＝。證明如B＝，則A∪B＝A∪＝U，A∩B＝A∩＝。反之，若A∪B＝U且A∩B＝，則B＝B∩U＝B∩(A∪)＝(B∩A)∪(B∩)＝∪(B∩)＝(A∩)∪(B∩)＝(A∪B)∩＝U∩＝。例4

證明A∩(B∪C)＝(A∩B)∪(A∩C)。證明因?yàn)閤∈A∩(B∪C)x∈A∧x∈(B∪C)x∈A∧(x∈B∨x∈C)(x∈A∧x∈B)∨(x∈A∧x∈C)x∈(A∩B)∨x∈(A∩C)x∈(A∩B)∪(A∩C)，所以A∩(B∪C)＝(A∩B)∪(A∩C)。第二十一頁(yè)，共八十二頁(yè)，2022年，8月28日例5

證明＝∩。證明因?yàn)閤∈xA∪BxA∧xBx∈∧x∈x∈∩，所以＝∩。例6

證明A－(B∪C)＝(A－B)∩(A－C)。證明因?yàn)閤∈A－(B∪C)x∈A∧x(B∪C)x∈A∧(xB∧xC)(x∈A∧xB)∧(x∈A∧xC)x∈(A－B)∧x∈(A－C)x∈(A－B)∩(A－C)，所以A－(B∪C)＝(A－B)∩(A－C)。第二十二頁(yè)，共八十二頁(yè)，2022年，8月28日例7

證明A∩(B－C)＝(A∩B)－(A∩C)。證明

A∩(B－C)＝A∩(B∩)＝(A∩B∩)∪(A∩B∩)＝(A∩B)∩(∪)＝(A∩B)∩＝(A∩B)－(A∩C)。例8

已知A∪B＝A∪C，A∩B＝A∩C，試證B＝C。證明

B＝B∩(A∪B)＝B∩(A∪C)＝(B∩A)∪(B∩C)＝(A∩C)∪(B∩C)＝(A∪B)∩C＝(A∪C)∩C＝C。第二十三頁(yè)，共八十二頁(yè)，2022年，8月28日3.2.2集合的對(duì)稱差定義3.9

集合A和B的對(duì)稱差定義為AB＝(A－B)∪(B－A)。例如，若A＝{0，{0}}，則P(A)A＝(P(A)－A)∪(A－P(A))＝{，0，{{0}}，{0，{0}}}。定理3.9設(shè)A、B和C為三個(gè)集合，則：

(1)AB＝BA。

(2)(AB)C＝A(BC)。

(3)A∩(BC)＝(A∩B)(A∩C)。第二十四頁(yè)，共八十二頁(yè)，2022年，8月28日(4)A＝A；AU＝；AA＝；A＝U。

(5)AB＝(A∪B)－(A∩B)。

證明僅證(5)AB＝(A－B)∪(B－A)＝(A∩)∪(B∩)＝((A∩)∪B)∩((A∩)∪)＝(A∪B)∩(∪B)∩(A∪)∩(∪)＝(A∪B)∩(∪)＝(A∪B)－(A∩B)。第二十五頁(yè)，共八十二頁(yè)，2022年，8月28日3.2.3廣義并、廣義交運(yùn)算定義3.10

集合A的所有元素的元素組成的集合稱為A的廣義并。符號(hào)化表示為：∪A＝{x|B(B∈A∧x∈B)}。定義3.11集合A的所有元素的公共元素組成的集合稱為A的廣義交。符號(hào)化表示為：∩A＝{x|B(B∈Ax∈B)}。例如，若A＝{{a，b，c}，{a，d，e}，{a，f}}，則∪A＝{a，b，c，d，e，f}，∩A＝{a}。由定義可知，廣義交和廣義并是針對(duì)集族而言的，對(duì)于非集族來(lái)說(shuō)，其廣義交和廣義并均為空集。第二十六頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.10設(shè)A和B為兩個(gè)集合，則：(1)∪{A}＝A。(2)∪(A∪B)＝(∪A)∪(∪B)。證明

(1)因?yàn)閤∈∪{A}B(B∈{A}∧x∈B)A∈{A}∧x∈Ax∈A，所以∪{A}＝A(2)因?yàn)閤∈∪(A∪B)C(C∈A∪B∧x∈C)C((C∈A∨C∈B)∧x∈C)C((C∈A∧x∈C)∨(C∈B∧x∈C))C(C∈A∧x∈C)∨C(C∈B∧x∈C)x∈∪A∨x∈∪Bx∈(∪A)∪(∪B)，所以∪(A∪B)＝(∪A)∪(∪B)。第二十七頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.11設(shè)A和B為兩個(gè)集合，則：(1)∩{A}＝A。(2)∩{A，B}＝A∩B。證明

(1)因?yàn)閤∈∩{A}B(B∈{A}x∈B)A∈{A}x∈Ax∈A，所以∩{A}＝A。(2)因?yàn)閤∈∩{A，B}C(C∈{A，B}x∈C)(A∈{A，B}x∈A)∧(B∈{A，B}x∈B)x∈A∧x∈Bx∈A∩B，所以∩{A，B}＝A∩B。第二十八頁(yè)，共八十二頁(yè)，2022年，8月28日3.2.4集合的文氏圖集合之間的相互關(guān)系和運(yùn)算還可以用文氏圖來(lái)描述，它有助于我們理解問(wèn)題，有時(shí)對(duì)解題也很有幫助。在不要求有求解步驟的題目中，我們可以使用文氏圖求解，但它不能用于題目的證明。在文氏圖中，用矩形表示全集U，矩形內(nèi)部的點(diǎn)均為全集中的元素，用圓或橢圓表示U的子集，其內(nèi)部的點(diǎn)表示不同集合的元素，并將運(yùn)算結(jié)果得到的集合用陰影部分表示。圖3-1表示了集合的5種基本運(yùn)算，陰影部分表示經(jīng)過(guò)相應(yīng)運(yùn)算得到的。第二十九頁(yè)，共八十二頁(yè)，2022年，8月28日第三十頁(yè)，共八十二頁(yè)，2022年，8月28日3.3集合的劃分與覆蓋在集合的研究中，除了進(jìn)行集合之間的比較外，還要對(duì)集合的元素進(jìn)行分類。這一節(jié)將討論集合的劃分問(wèn)題。定義3.12

設(shè)S＝{A1，A2，…，An}是集合A的某些非空子集組成的集合，若＝A，則稱S為集合A的一個(gè)覆蓋。定義3.13

設(shè)＝{A1，A2，…，An}是集合A的某些非空子集組成的集合，若＝A，且Ai∩Aj＝(i≠j)，則稱為A的一個(gè)劃分，稱中的元素為A的劃分塊。第三十一頁(yè)，共八十二頁(yè)，2022年，8月28日由定義知，劃分一定是覆蓋，但反之則不然。例如，S＝{{a}，{b，c}，{c}}是A＝{a，b，c}的覆蓋，但不是A的劃分。例1設(shè)有整數(shù)集Z，res5(x)表示整數(shù)x被5除后所得的余數(shù)。令A(yù)i＝{x|x∈Z∧res5(x)＝i∧i∈Z5}，則{A0，A1，A2，A3，A4}作成Z的一個(gè)劃分。解由題設(shè)得：A0＝{…，－10，－5，0，5，10，…}，A1＝{…，－9，－4，1，6，11，…}，A2＝{…，－8，－3，2，7，12，…}，A3＝{…，－7，－2，3，8，13，…}，A4＝{…，－6，－1，4，9，14，…}。于是，＝Z，且Ai∩Aj＝(i≠j)。所以，{A0，A1，A2，A3，A4}是Z的一個(gè)劃分。第三十二頁(yè)，共八十二頁(yè)，2022年，8月28日例2

求集合A＝{a，b，c}的所有不同的劃分。解其不同的劃分共有5個(gè)：1＝{{a}，，{c}}，2＝{{a}，{b，c}}，3＝{{a，c}，}，4＝{{a，b}，{c}}，5＝{{a，b，c}}。定理3.12

設(shè){A1，A2，…，Ar}和{B1，B2，…，Bs}是同一集合A的兩種劃分，則其所有Ai∩Bj≠組成的集合也是原集合的一種劃分。定義3.14

設(shè){A1，A2，…，Ar}和{B1，B2，…，Bs}是同一集合A的兩種劃分，則稱其所有Ai∩Bj≠組成的集合為原來(lái)兩劃分的交叉劃分。第三十三頁(yè)，共八十二頁(yè)，2022年，8月28日定義3.15

給定A的兩個(gè)劃分{A1，A2，…，Ar}和{B1，B2，…，Bs}，若對(duì)于每個(gè)Aj都有Bk使得AjBk，則稱{A1，A2，…，Ar}為{B1，B2，…，Bs}的加細(xì)。定理3.13

任何兩種劃分的交叉劃分，都是原來(lái)各劃分的一種加細(xì)。證明設(shè){A1，A2，…，Ar}和{B1，B2，…，Bs}的交叉劃分為T，對(duì)于T中任意元素Ai∩Bj必有Ai∩BjAi和Ai∩BjBj，故T必是原劃分的加細(xì)。例3

設(shè)A1、A2和A3是全集U的子集，則形如Ai(Ai為Ai或)的集合稱為由A1、A2和A3產(chǎn)生的小項(xiàng)。試證由A1、A2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個(gè)劃分。第三十四頁(yè)，共八十二頁(yè)，2022年，8月28日證明小項(xiàng)共8個(gè)，設(shè)有r個(gè)非空小項(xiàng)s1、s2、…、sr(r≤8)。對(duì)任意的a∈U，則a∈Ai或a∈，兩者必有一個(gè)成立，取Ai為包含元素a的Ai或，則a∈Ai，即有a∈si，于是Usi。又顯然有siU，所以U＝si。任取兩個(gè)非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個(gè)Ai和分別出現(xiàn)在sp和sq中，于是sp∩sq＝。綜上可知，{s1，s2，…，sr}是U的一個(gè)劃分。第三十五頁(yè)，共八十二頁(yè)，2022年，8月28日3.4排列與組合3.4.1加法與乘法原理在組合計(jì)數(shù)的計(jì)算和研究中，加法原理和乘法原理是兩個(gè)最常用也是最基本的原理。加法原理若事件的有限集合S＝S1∪S2∪…∪Sn，且S1、S2、…、Sn兩兩不相交，則|S|＝|S1|＋|S2|＋…＋|Sn|

乘法原理若事件的有限集合S是依次取自有限集合S1、S2、…、Sn中事件的序列的集合，則|S|＝|S1|×|S2|×…×|Sn|第三十六頁(yè)，共八十二頁(yè)，2022年，8月28日例1

求由數(shù)字1、2、3、4、5組成的小于1000的數(shù)(每個(gè)數(shù)字都允許重復(fù)出現(xiàn))的個(gè)數(shù)。解在三位數(shù)中，每一個(gè)數(shù)位上的數(shù)字都有5種不同的選取法，由乘法原理知，滿足條件的三位數(shù)的個(gè)數(shù)是53個(gè)。同理可知，滿足條件的二位數(shù)和一位數(shù)的個(gè)數(shù)分別為52個(gè)和5個(gè)。再由加法原理知，滿足條件的自然數(shù)總共有53＋52＋5＝155個(gè)。第三十七頁(yè)，共八十二頁(yè)，2022年，8月28日3.4.2排列和組合

1.排列定義3.16集合S有n個(gè)元素，從中選取r個(gè)元素作有序排列，且在排列中不允許任何元素重復(fù)出現(xiàn)，則稱這種排列為S的r―無(wú)重復(fù)排列。當(dāng)r＝n時(shí)，稱其為全排列。S的所有r―無(wú)重復(fù)排列的個(gè)數(shù)記為P(n，r)或Pnr。定理3.14

n個(gè)元素的r―無(wú)重復(fù)排列的個(gè)數(shù)為：P(n，r)＝n(n－1)(n－2)…(n－r＋1)。當(dāng)r＝n時(shí)，P(n，n)＝n!

證明在從n個(gè)不同的元素中按順序取出r個(gè)元素時(shí)，第一個(gè)元素有n種不同的選法，第2個(gè)元素有n－1種不同的選法，…，第r個(gè)元素從剩下的n－r＋1個(gè)元素中選取，有n－r＋1種不同的選法。根據(jù)乘法原理，順序選取r個(gè)元素共有的不同選取方法數(shù)為：P(n，r)＝n(n－1)(n－2)…(n－r＋1)。第三十八頁(yè)，共八十二頁(yè)，2022年，8月28日例2

從1、2、…、9中選取數(shù)字構(gòu)成3位數(shù)，如要求每個(gè)數(shù)字都不相同，問(wèn)共有多少種方法？解從1、2、…、9中選取百位數(shù)，共9種選法，再?gòu)氖Ｏ碌臄?shù)字中選取十位數(shù)，共8種選法，最后從剩下的數(shù)字中選取個(gè)位數(shù)，共7種選法。因此，從1、2、…、9中選取數(shù)字構(gòu)成3位數(shù)共有9×8×7＝504種方法。定義3.17r―無(wú)重復(fù)排列可以看作是將選出的r個(gè)元素排列在一條直線上的排列，這時(shí)也稱為r―線狀排列。如果把這r個(gè)元素排列在一個(gè)圓周上，則這種排列稱為S的r―圓排列。對(duì)兩個(gè)圓排列，若其中一個(gè)圓排列可以由另一個(gè)圓排列通過(guò)旋轉(zhuǎn)而得到，則認(rèn)為這兩個(gè)圓排列在本質(zhì)上是同一個(gè)圓排列。于是有下面的結(jié)論成立。第三十九頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.15

n個(gè)元素的r―圓排列的個(gè)數(shù)N(n，r)為證明為了得到n個(gè)元素的r―無(wú)重復(fù)排列，可以先從n個(gè)元素中選取r個(gè)元素作r―圓排列，這種圓排列的個(gè)數(shù)是N(n，r)。然后，將這個(gè)r―圓排列斷開(kāi)后即可得到線狀的r―無(wú)重復(fù)排列。因?yàn)閺膔個(gè)不同的位置處斷開(kāi)，由乘法原理可得P(n，r)＝rN(n，r)，即例3

有8個(gè)人圍著圓桌進(jìn)餐，如果要求每餐坐的順序不同，那么他們?cè)谝黄鹱疃嗄芄策M(jìn)幾天餐？解首先8－圓排列數(shù)為8!/8，又一日三餐，故他們一起能共餐8!/(8×3)＝1680天。第四十頁(yè)，共八十二頁(yè)，2022年，8月28日2.組合定義3.18集合S有n個(gè)元素，從中選取r個(gè)元素，若不考慮它們的排列順序，且在選取中不允許元素重復(fù)出現(xiàn)，稱這種選取方式為S的r―無(wú)重復(fù)組合。S的所有r―無(wú)重復(fù)組合的個(gè)數(shù)記為C(n，r)或Cnr。定理3.16n個(gè)元素的r―無(wú)重復(fù)組合的個(gè)數(shù)為C(n，r)＝＝。證明為了得到n個(gè)元素的r―無(wú)重復(fù)排列，可以先從n個(gè)元素中選取r個(gè)元素作r―無(wú)重復(fù)組合，這種無(wú)重復(fù)組合的個(gè)數(shù)是C(n，r)，然后將這r個(gè)取出的元素作r―無(wú)重復(fù)排列，這種r―無(wú)重復(fù)排列的個(gè)數(shù)是P(r，r)＝r!。由乘法原理可得P(n，r)＝r!C(n，r)，即C(n，r)＝＝。第四十一頁(yè)，共八十二頁(yè)，2022年，8月28日例4

從1、2、…、300之中任取3個(gè)數(shù)，使得它們的和能被3整除，問(wèn)有多少種方法？解把1、2、…、300分成A、B和C三組，A＝{3k＋1|k∈Z}，B＝{3k＋2|k∈Z}，C＝{3k|k∈Z}。任取三個(gè)數(shù)i、j、k，那么選取是無(wú)序的且滿足i＋j＋k能被3整除。將選法分為兩類：都取自同一組，方法數(shù)3C(100，3)。分別取自A、B和C，方法數(shù)(C(100，1))3。由加法原則，總?cè)?shù)為3C(100，3)＋(C(100，1))3＝1485100。第四十二頁(yè)，共八十二頁(yè)，2022年，8月28日3.4.3排列與組合的生成

1.排列的生成排列的生成算法有詞典順序法、逆序法和遞歸排序法等。在這里僅介紹詞典順序法。設(shè)S＝{1，2，…，n}，(a1，a2，…，an)和(b1，b2，…，bn)是S的兩個(gè)排列，若存在i∈{1，2，…，n}，使得對(duì)一切j＝1，2，…，i有aj＝bj而ai＋1＜bi＋1，則稱排列(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)的下一個(gè)排列。第四十三頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.17對(duì)S的兩個(gè)排列，(b1，b2，…，bn)是(a1，a2，…，an)的下一個(gè)排列的充要條件是：(1)存在m∈{1，2，…，n}，使得對(duì)一切i＝1，2，…，m－1有ai＝bi，am＜bm，am＜am＋1且am＋1＞am＋2＞…＞an；(2)bm＝min{aj|aj＞am，j＝m＋1，m＋2，…，n}；(3)bm＋1＜bm＋2＜…＜bn。由此定理可建立生成所有排列的算法：步1：置(a1，a2，…，an)＝(1，2，…，n)步2：設(shè)已有排列(a1，a2，…，an)，置i＝n；步2.1：若ai＞ai－1，則記m＝i－1，令bm＝min{aj|aj＞am，j＝i，i＋1，…，n}，并將(am，am＋1，…，an)\{bm}第四十四頁(yè)，共八十二頁(yè)，2022年，8月28日中的元素由小到大排起來(lái)，記這個(gè)排列為(bm＋1，am＋2，…，an)。置(a1，a2，…，am－1，am，am＋1，…，an)＝(a1，a2，…，am－1，bm，bm＋1，…，bn)然后返回步2。步2.2：若ai＜ai－1，則當(dāng)i－1＞1時(shí)，置i＝i－1，返回步2.1。當(dāng)i－1＝1時(shí)，算法終止。例5S＝{1，2，3，4}，求其全排列。解123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321。第四十五頁(yè)，共八十二頁(yè)，2022年，8月28日2.組合的生成定理3.18(a1，a2，…，ar)和(b1，b2，…，br)是S的兩個(gè)不同的r－子集，則(b1，b2，…，br)是(a1，a2，…，ar)的下一個(gè)子集的充要條件是：(1)存在1≤m≤r，使得對(duì)一切i＝1，2，…，m－1有ai＝bi，對(duì)一切i＞m有am＝n－r＋i；(2)bm＝am＋1；(3)對(duì)于m≤j≤r－1，有bj＋1＝bj＋1。由此定理可建立生成所有子集的算法：步1：設(shè)S＝{1，2，…，n}，取(a1，a2，…，ar)＝(1，2，…，r)第四十六頁(yè)，共八十二頁(yè)，2022年，8月28日步2：設(shè)已有S的r子集(a1，a2，…，ar)，置i＝r；步2.1：若ai＜n－r＋i，則令bi＝ai＋1，并且對(duì)j＝i，i＋1，…，r－1，置bj＋1＝bj＋1。然后置(a1，a2，…，ar)＝(a1，a2，…，ai－1，bi，bi＋1，…，br)，然后返回步2。步2.2：若ai＝n－r＋i，則當(dāng)i＞1時(shí)，置i＝i－1，返回步2.1。當(dāng)i＝1時(shí)，算法終止。例6

S＝{1，2，3，4，5，6}，求其所有4元素子集。解

123412351236124512461256134513461356145623452346235624563456。第四十七頁(yè)，共八十二頁(yè)，2022年，8月28日3.5歸納原理

3.5.1結(jié)構(gòu)歸納原理設(shè)集合A是歸納定義的集合，現(xiàn)欲證A中所有元素具有性質(zhì)P，即證：對(duì)于任意x∈A有P(x)為真?？蛇M(jìn)行如下證明：

(1)(歸納基礎(chǔ))證明歸納定義基礎(chǔ)條款中規(guī)定的A的基本元素x均使P(x)為真。

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

1.第一數(shù)學(xué)歸納法用第一數(shù)學(xué)歸納法證明所有自然數(shù)具有性質(zhì)P時(shí)，只要如下推理：

(1)歸納基礎(chǔ)：證P(0)真，即證明數(shù)0具有性質(zhì)P。

(2)歸納過(guò)程：對(duì)任意k(≥0)，假設(shè)P(k)真(歸納假設(shè)“k滿足性質(zhì)P”)時(shí)，推出P(k＋1)真。

(3)結(jié)論：所有自然數(shù)具有性質(zhì)P。第五十頁(yè)，共八十二頁(yè)，2022年，8月28日例1

用歸納法證明：對(duì)任意的自然數(shù)n，有(0＋1＋2＋…＋n)2＝03＋13＋23＋…＋n3。證明當(dāng)n＝0時(shí)，n2＝03。假設(shè)n＝k時(shí)，(0＋1＋2＋…＋k)2＝03＋13＋23＋…＋k3，那么n＝k＋1時(shí)，(0＋1＋2＋…＋k＋k＋1)2＝(0＋1＋2＋…＋k)2＋2(0＋1＋2＋…＋k)(k＋1)＋(k＋1)2

＝03＋13＋23＋…＋k3＋k(k＋1)2＋(k＋1)2＝03＋13＋23＋…＋k3＋(k＋1)3所以，對(duì)任意自然數(shù)結(jié)論成立。第五十一頁(yè)，共八十二頁(yè)，2022年，8月28日2.第二數(shù)學(xué)歸納法用第二數(shù)學(xué)歸納法證明所有自然數(shù)具有性質(zhì)P時(shí)，只要如下推理：(1)歸納基礎(chǔ)：證P(0)真，即證明數(shù)0具有性質(zhì)P。(2)歸納過(guò)程：對(duì)任意k(≥0)，假設(shè)P(i)真，k＞i≥0(歸納假設(shè)“0，1，…，k－1滿足性質(zhì)P”)時(shí)，推出P(k)真。(3)結(jié)論：所有自然數(shù)具有性質(zhì)P。例2

有數(shù)目相同的兩堆棋子(每堆棋子數(shù)為n)，甲、乙兩人玩取棋子游戲。規(guī)定兩人輪流取棋子，每次兩人取子數(shù)相同，不能不取，也不能同時(shí)在兩堆中取子，取得最后一枚棋子者為勝者。求證：后取者必勝。第五十二頁(yè)，共八十二頁(yè)，2022年，8月28日證明不妨設(shè)甲為先取者，乙為后取者。當(dāng)n＝1時(shí)，兩堆各有一枚棋子，甲必先從一堆中取走一枚棋子，余下最后一枚棋子必被乙取走，乙勝。假設(shè)n＜k時(shí)乙必勝。下證n＝k時(shí)也是乙必勝。設(shè)第一輪取子時(shí)，甲從一堆中取走r枚棋子，余下k－r＜k枚棋子，那么，乙從另一堆中也取走r枚棋子，亦留下k－r＜k枚棋子。若(1)r＝k，那么乙取走最后一枚棋子，乙勝。(2)1＜r＜k，那么1＜k－r＜k。對(duì)留下的兩堆棋子，每一堆為k－r枚，由歸納假設(shè)，在以后甲乙的搏奕中乙必勝。因此全局也是乙必勝。第五十三頁(yè)，共八十二頁(yè)，2022年，8月28日3.6容斥原理和抽屜原理3.6.1容斥原理設(shè)集合A是歸納定義的集合，現(xiàn)欲證A中所有元素具有性質(zhì)P，即證：對(duì)于任意x∈A有P(x)為真?？蛇M(jìn)行如下證明：

(1)(歸納基礎(chǔ))證明歸納定義基礎(chǔ)條款中規(guī)定的A的基本元素x均使P(x)為真。

(2)(歸納推理)證明歸納定義的歸納條款是“保性質(zhì)P的”。即在假設(shè)歸納條款中已確定元素x1、x2、…、xn使P(xi)(i＝1，2，…，n)真的前提下，證明用歸納條款中的操作g所生成元素g(x1，x2，…，xn)依然具有性質(zhì)P，即P(g(x1，x2，…，xn))為真。第五十四頁(yè)，共八十二頁(yè)，2022年，8月28日集合的運(yùn)算，可用于有限個(gè)元素的計(jì)數(shù)問(wèn)題。在有限集的元素計(jì)數(shù)問(wèn)題中，容斥原理有著廣泛的應(yīng)用。定理3.19(容斥原理)

對(duì)有限集合A和B，有|A∪B|＝|A|＋|B|－|A∩B|。證明因?yàn)锳∪B＝B∪(A－B)且B∩(A－B)＝，所以|A∪B|＝|B|＋|A－B|。又因?yàn)锳＝(A－B)∪(A∩B)且(A－B)∩(A∩B)＝，所以|A|＝|A－B|＋|A∩B|。故|A∪B|＝|A|＋|B|－|A∩B|。定理3.20

推廣到n個(gè)集合A1，A2，…，An的情形，有：|A1∪A2∪…∪An|＝∑i|Ai|－∑i＜j|Ai∩Aj|＋∑i＜j＜k|Ai∩Aj∩Ak|－…＋(－1)n－1|A1∩A2∩…∩An|。第五十五頁(yè)，共八十二頁(yè)，2022年，8月28日例1

一個(gè)班有50個(gè)學(xué)生，在第一次考試中得95分的有26人，在第二次考試中得95分的有21人，如果兩次考試中沒(méi)有得95分的有17人，那么兩次考試都得95分的有多少人？解設(shè)A和B分別表示在第一次和第二次考試中得95分的學(xué)生的集合。則：|A|＝26，|B|＝21，＝17。于是＝50－＝50－(|A|＋|B|－|A∩B|)，從而|A∩B|＝－50＋|A|＋|B|＝17－50＋26＋21＝14。所以，兩次考試都得95分的有14人。例2

從{1，2，3，4，5，6，7，8，9}中取7個(gè)不同的數(shù)字構(gòu)成7位數(shù)，如不允許5和6相鄰，總共有多少種方法？第五十六頁(yè)，共八十二頁(yè)，2022年，8月28日解任取7個(gè)不同的數(shù)字構(gòu)成7位數(shù)的個(gè)數(shù)為＝9!/2，5和6相鄰的個(gè)數(shù)為6！(2！)＝6×7！，根據(jù)容斥原理，總共有9!/2－6×7!＝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é)生集合。則：第五十七頁(yè)，共八十二頁(yè)，2022年，8月28日|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，

|B∩C|=5,|A∩B∩C|＝2，|(A∪C)∩B|＝6。因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不會(huì)打這三種球的共5人。在不要求嚴(yán)格步驟的情況下，以上各題也可通過(guò)文氏圖的方法來(lái)求解。下面以例3加以說(shuō)明：設(shè)A、B、C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。該問(wèn)題的文氏圖如圖3-2所示。由題意可得：第五十八頁(yè)，共八十二頁(yè)，2022年，8月28日|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ù)上面各等式，依次求得：第五十九頁(yè)，共八十二頁(yè)，2022年，8月28日|I1|＝5，|I2|＝4，|I3|＝5，|I4|＝1，|I5|＝2，|I6|＝3，|I7|＝0。所以，＝25－|A∪B∪C|＝25－(|I1|＋|I2|＋|I3|＋|I4|＋|I5|＋|I6|＋|I7|)＝25－(5＋4＋5＋1＋2＋3＋0)＝5。故，不會(huì)打這三種球的共5人。第六十頁(yè)，共八十二頁(yè)，2022年，8月28日3.6.2抽屜原理(鴿巢原理)

抽屜原理是一個(gè)十分基本、非常重要、應(yīng)用極其廣泛的數(shù)學(xué)原理，是解決數(shù)學(xué)中的一類存在性問(wèn)題的基本工具。定理3.21(抽屜原理)(1)把多于n個(gè)元素的集合S分成n個(gè)子集S1、S2、…、Sn的并集，那么至少存在一個(gè)集合Si，它包含S中的兩個(gè)或兩個(gè)以上的元素。

(2)把多于mn個(gè)元素的集合S分成n個(gè)子集S1、S2、…、Sn的并集，那么至少存在一個(gè)集合Si，它包含S中的m＋1或m＋1以上的元素。證明僅證(2),反證法。

(2)若結(jié)論不成立，則對(duì)于任意子集Si，有|Si|≤m，于是|S|≤|S1|＋|S2|＋…＋|Sn|≤mn，矛盾。第六十一頁(yè)，共八十二頁(yè)，2022年，8月28日例3

在從1到2n的整數(shù)中，任意選取n＋1個(gè)數(shù)，證明在這n＋1個(gè)數(shù)中總存在兩個(gè)數(shù)，使得其中一個(gè)數(shù)是另一個(gè)的倍數(shù)。證明設(shè)S＝{1，2，…，2n}，Si＝{a|a∈S，且存在k∈N使得a＝2k(2i－1)}，i＝1，2，…，n。于是S＝S1∪S2∪…∪Sn，則n＋1個(gè)數(shù)中必有兩個(gè)數(shù)在S的同一個(gè)子集Si中，這兩個(gè)數(shù)中的一個(gè)數(shù)是另一個(gè)的偶數(shù)倍。例4

在邊長(zhǎng)為1的正方形內(nèi)任意放置九個(gè)點(diǎn)，證明其中必存在三個(gè)點(diǎn)，使得由它們組成的三角形(可能是退化的)面積不超過(guò)1/8。證明把邊長(zhǎng)為1的正方形分成四個(gè)全等的小正方形，則至少有一個(gè)小正方形內(nèi)有三個(gè)點(diǎn)，它們組成的三角形(可能是退化的)面積不超過(guò)小正方形的一半，即1/8。第六十二頁(yè)，共八十二頁(yè)，2022年，8月28日3.7遞推關(guān)系

3.7.1遞推關(guān)系的概念

有些計(jì)數(shù)問(wèn)題往往與求一個(gè)數(shù)列的通項(xiàng)有關(guān)。但在一些復(fù)雜的特定條件下要直接求出這個(gè)數(shù)列的通項(xiàng)公式，有時(shí)十分困難。而在同樣的條件下，寫出該數(shù)列相鄰項(xiàng)之間的關(guān)系，再利用一定的方法和技巧，卻往往能很容易的得到所要的結(jié)論。

例1

斐波那契數(shù)列(Fibonacci)問(wèn)題假定一對(duì)兔子兩個(gè)月成熟后，每月生一對(duì)兔子。按照假定，一對(duì)剛出生的兔子在n個(gè)月后，共有多少對(duì)兔子？解設(shè)第n個(gè)月的兔子數(shù)為Fn，由題意得F0＝1F1＝1Fn＝Fn－1＋Fn－2，n≥2第六十三頁(yè)，共八十二頁(yè)，2022年，8月28日例2漢諾塔(Hanoi)問(wèn)題有三根立柱A、B、C以及n個(gè)大小不同的圓盤套在立柱A上，大的圓盤在下面，小的圓盤在上面，構(gòu)成一個(gè)塔形?，F(xiàn)在要把這n個(gè)圓盤移到立柱B上?？梢岳眠@三根立柱，每次只能移動(dòng)一個(gè)圓盤，但不允許將它放在較小的圓盤上，問(wèn)最少需移動(dòng)多少次？解令Hn為完成這樣的一次移動(dòng)至少必須移動(dòng)圓盤的次數(shù)。為了把n個(gè)圓盤從立柱A移到立柱B，可先將n－1個(gè)圓盤從立柱A移到立柱C，留下最大的圓盤，移動(dòng)的次數(shù)為Hn－1；然后再將最大的圓盤移動(dòng)到立柱B，移動(dòng)1次；最后將n－1個(gè)圓盤從立柱C移到立柱B，移動(dòng)次數(shù)為Hn－1。第六十四頁(yè)，共八十二頁(yè)，2022年，8月28日于是有Hn＝2Hn－1＋1，n≥2，其中H1＝1。以上的例子有一個(gè)共同的特點(diǎn)，即從我們?cè)谟?jì)數(shù)問(wèn)題所得出的數(shù)列中，它的一般項(xiàng)可用它自身數(shù)列中的前面若干項(xiàng)來(lái)表達(dá)。這樣，從給定的初始值出發(fā)，利用所建立的關(guān)系式可以依次算出數(shù)列中的每一項(xiàng)。我們稱這些關(guān)系式為遞推關(guān)系。下面我們介紹遞推關(guān)系的幾種解法。第六十五頁(yè)，共八十二頁(yè)，2022年，8月28日1.遞推關(guān)系的生成函數(shù)解法設(shè){a0，a1，…，an，…}為一個(gè)無(wú)窮數(shù)列，我們稱f(t)＝a0＋a1t＋…＋antn＋…為該數(shù)列的生成函數(shù)。例3

數(shù)列{1，1，…，1，…}的生成函數(shù)為＝1＋t＋…＋tn＋…。將遞推關(guān)系代入數(shù)列的生成函數(shù)的系數(shù)中去，通過(guò)計(jì)算可以得到生成函數(shù)的顯式，然后再將它展開(kāi)成冪級(jí)數(shù)就可求得數(shù)列的通項(xiàng)。例4

斐波那契數(shù)列問(wèn)題解設(shè)F(x)＝為斐波那契數(shù)列的生成函數(shù)，則有第六十六頁(yè)，共八十二頁(yè)，2022年，8月28日F(x)＝F0＋F1x＋＝1＋x＋＝1＋x＋x＋xn＝1＋x＋x(F(x)－1)＋x2F(x)從上面關(guān)系式可以解出F(x)＝＝＝＝比較等式兩邊xn的系數(shù)，得到Fn＝。第六十七頁(yè)，共八十二頁(yè)，2022年，8月28日2.常系數(shù)線性齊次遞推關(guān)系的解法我們把形如H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(其中H(n)、H(n－1)、…、H(n－k)是n的函數(shù))的遞推關(guān)系式稱為常系數(shù)線性齊次遞推關(guān)系，并稱xk＋b1xk－1＋b2xk－2＋…＋bk＝0為其特征方程，它的根稱為其特征根。在使用特征根方法求解遞推關(guān)系時(shí)要用到下面三個(gè)定理，其證明參見(jiàn)相關(guān)文獻(xiàn)。定理3.22

設(shè)q為非零的實(shí)數(shù)或復(fù)數(shù)，則H(n)＝qn是遞推關(guān)系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的解當(dāng)且僅當(dāng)q是它的一個(gè)特征根。第六十八頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.23

設(shè)q1、q2、…、qk為非零的實(shí)數(shù)或復(fù)數(shù)，則H(n)＝C1q1n＋C2q2n＋…＋Ckqkn(C1、C2、…、Ck是確定的常數(shù))是遞推關(guān)系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的解當(dāng)且僅當(dāng)q1、q2、…、qk是它的k個(gè)不同的特征根。定理3.24

設(shè)q1、q2、…、qk為非零的實(shí)數(shù)或復(fù)數(shù)，它們是遞推關(guān)系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的特征方程的t(t≤k)個(gè)不同的特征根，各有e1、e2、…、et重。則遞推關(guān)系式的一般解是H(n)＝H1(n)＋H2(n)＋…＋Ht(n)，其中Hi(n)＝C1qin＋C2nqin＋…＋qin(i＝1，2，…，t；C1，C2，…，為確定的常數(shù))。例6

斐波那契數(shù)列問(wèn)題第六十九頁(yè)，共八十二頁(yè)，2022年，8月28日解遞推關(guān)系Fn＝Fn－1＋Fn－2的特征方程為x2―x―1＝0，其解為：x1＝，x2＝。于是遞推關(guān)系的通解為Fn＝C1＋C2。將F0＝1，F(xiàn)1＝1代入得C1＋C2＝1C1＋C2＝1解上述式子得：C1＝，C2＝－。于是Fn＝。第七十頁(yè)，共八十二頁(yè)，2022年，8月28日3.常系數(shù)線性非齊次遞推關(guān)系的解法我們把形如H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝f(n)(其中H(n)、H(n－1)、…、H(n－k)是n的函數(shù)，f(n)是n的多項(xiàng)式或an)的遞推關(guān)系式稱為常系數(shù)線性非齊次遞推關(guān)系。這類遞推關(guān)系的求解可通過(guò)將非齊次遞推關(guān)系歸約為齊次遞推關(guān)系的方法來(lái)求解。下面我們通過(guò)一個(gè)例子來(lái)說(shuō)明。例7漢諾塔問(wèn)題解遞推關(guān)系Hn＝2Hn－1＋1對(duì)應(yīng)的齊次方程的通解為Hn＝C2n。利用常系數(shù)變易法作代換Hn＝an2n可得an＝an－1＋，從而an＝a0＋＋＋…＋＝a0＋1－，Hn＝an2n＝(1＋a0)2n－1。由H1＝1得a0＝1。因此，Hn＝2n－1。第七十一頁(yè)，共八十二頁(yè)，2022年，8月28日3.8集合論在命題邏輯中的應(yīng)用3.8.1命題邏輯中的集合表示首先引入以下幾個(gè)符號(hào)：

(A)：命題公式A的主析取范式中所有小項(xiàng)mi的下標(biāo)組成的集合。［A］：命題公式A的主合取范式中所有大項(xiàng)Mi的下標(biāo)組成的集合。令U＝{0，1，2，…，2n－1}，則U為n個(gè)命題變?cè)M成的所有小項(xiàng)(或大項(xiàng))對(duì)應(yīng)的下標(biāo)組成的集合。下面，我們先通過(guò)一個(gè)例子來(lái)說(shuō)明命題公式的主范式可以用集合來(lái)表示，然后證明命題公式的主范式和推理都可通過(guò)集合運(yùn)算而得到。第七十二頁(yè)，共八十二頁(yè)，2022年，8月28日例1

求命題公式P∧Q與P∨Q的主析取范式。解命題公式P∧Q與P∨Q的真值表如表3-1所示：表3-1于是(P∧Q)＝{3}，(P∨Q)＝{1，2，3}。將上述例子推廣到含有n個(gè)命題變?cè)拿}公式中，則有以下的重要結(jié)論。第七十三頁(yè)，共八十二頁(yè)，2022年，8月28日定理3.25設(shè)V＝{P1，P2，…，Pn}，A是命題公式，其包含的命題變?cè)诩蟅中，則[A]＝U－(A)