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

2、月17.08.2022由集合的概念可知，集合中的元素具有確定性、互異性、無(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)抽象性是指：集合中的元素是抽象的，甚至可以是集合。如A1，2，1，2，其中1，2是集合A的元素。第三張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022集合是多種多樣的，我們可以根據(jù)集合中元素的個(gè)數(shù)對(duì)其

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

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

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

6、十二頁(yè)，創(chuàng)作于2022年6月17.08.2022定理3.2 設(shè)A、B和C是三個(gè)集合，則：(1)AA。(2)ABBCAC。證明 (1)由定義顯然成立。(2)ABBCx(xAxB)x(xBxC)x(xAxB)(xBxC)x(xAxC)AC。定義3.2 設(shè)A和B是兩個(gè)集合，若AB且B中至少有一個(gè)元素b使得bA，則稱A是B的真子集，也稱A真包含于B或B真包含A，記作AB。否則，記作AB。B真包含A的符號(hào)化表示：第八張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022ABx(xAxB)x(xBxA)。若兩個(gè)集合A和B沒(méi)有公共元素，我們說(shuō)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是三個(gè)集合，則(1)(AA)。 (2)AB(BA)。(3)ABBCAC。第九張，PPT共八十二頁(yè)，創(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共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.1.4 空集、集族、冪集和全集定義3.3 沒(méi)有任何元素的集合稱為空集，記作。以集合為元素的集合稱為集族。例如，x|xx是空集；xx是某大學(xué)的學(xué)生社團(tuán)是集族。定理3.4 空集是任何集合的子集。證明 任給集合A，則Ax(xxA)。由于x是假的，所以x(xxA)為真，于是有A為真。推論 空集是惟一的。對(duì)于任一集合A，我們稱空集和其自身A為A的平凡子集。第十一張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022特別要注意與的區(qū)別，是不

9、含任何元素的集合，是任意集合的子集，而是含有一個(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。第十二張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022定理3.5 若|A|n，則|P(A)|2n。證明 因?yàn)锳的m個(gè)元素的子集的個(gè)數(shù)為Cnm，所以|P(A)|Cn0Cn1Cnn2n。定理3.6 設(shè)A和B是兩個(gè)集合，則：(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共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022定義3.5 所要討論的集合都是某個(gè)集合的子集，稱這個(gè)集合為全集，記作U或E。全集是一個(gè)相對(duì)的概念。由于所研究的問(wèn)題不同，所取的全集也不同。例如，在研究整數(shù)間的問(wèn)題時(shí)，可把整數(shù)集Z取作全集。在研究平面幾何的問(wèn)題時(shí)，可把整個(gè)坐標(biāo)平面取作全集。第十四張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.1.5 有限冪集元素的編碼表示 為便于在計(jì)算機(jī)中表示有限集，可對(duì)集合中的元素規(guī)定一種次序，在集合和二進(jìn)制之間建立對(duì)應(yīng)關(guān)系。設(shè)Ua1，a2，an，對(duì)U的任意

11、子集A，A與一個(gè)n位二進(jìn)制數(shù)b1b2bn對(duì)應(yīng)，其中bi1當(dāng)且僅當(dāng)aiA。對(duì)于一個(gè)n位二進(jìn)制數(shù)b1b2bn，使之對(duì)應(yīng)一個(gè)集合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共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.2 集合的運(yùn)算與性質(zhì) 3.2.1 集合的交、并、補(bǔ) 定義3.6 設(shè)A和B為兩個(gè)集合，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個(gè)集合的情況，即A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn第十六張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022例1 設(shè)A和B為兩個(gè)集合，且AB，則ACBC。證明 對(duì)任意的xAC，則有xA且xC。而AB，由xA得xB，則xB且xC，從而xBC。所以，ACBC。例2 設(shè)A和B為兩個(gè)集合，則ABABBABA。證明 對(duì)任意的xAB，則xA或xB。又AB，所以xB，于是ABB。又顯然有BAB，故ABB。反之，若ABB，因AAB，所以AB。同理可

13、證ABABA。第十七張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022定義3.7 設(shè)A和B為兩個(gè)集合，所有屬于A而不屬于B的元素組成的集合稱為B對(duì)于A的補(bǔ)集，或相對(duì)補(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的絕對(duì)補(bǔ)或余集，記為( 或A或Ac)。即 x|xU且xA。例3 設(shè)A和B為兩個(gè)集合，則ABA 。證明 因?yàn)閤ABxAxBxAx xA ，所以ABA 。第十八張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022定理3.7 對(duì)于任意3個(gè)集合A、B和C，其交、

14、并、補(bǔ)滿足下面10個(gè)定律：(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共八十二頁(yè)，創(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以上等式的證明主要用到命題演算的等價(jià)式，即欲證集合AB，只需證明xAxB。也可利用已有的公式證明。第二十張，P

15、PT共八十二頁(yè)，創(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)。證明 因?yàn)閤A(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。第二十一張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022例5 證明 。證明 因?yàn)閤 xABxAxBx x x ，所以 。例6 證明A(BC)(AB)(AC)。證明

16、因?yàn)閤A(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。第二十二張，PPT共八十二頁(yè)，創(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共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.2.2 集合的對(duì)稱差 定義3.9 集合A和B的對(duì)稱差定義為AB(

17、AB)(BA)。例如，若A0，0，則P(A)A(P(A)A)(AP(A)，0，0，0，0。 定理3.9 設(shè)A、B和C為三個(gè)集合，則： (1)ABBA。 (2)(AB)CA(BC)。 (3)A(BC)(AB)(AC)。第二十四張，PPT共八十二頁(yè)，創(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共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.2.3 廣義并、廣義交運(yùn)算 定義3.10 集合A的所有元

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

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

20、解步驟的題目中，我們可以使用文氏圖求解，但它不能用于題目的證明。 在文氏圖中，用矩形表示全集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)算得到的。第二十九張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022第三十張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.3 集合的劃分與覆蓋 在集合的研究中，除了進(jìn)行集合之間的比較外，還要對(duì)集合的元素進(jìn)行分類。這一節(jié)將討論集合的劃分問(wèn)題。定義3.12 設(shè)SA1，A2，An是集合A的某些非空子集

21、組成的集合，若 A，則稱S為集合A的一個(gè)覆蓋。定義3.13 設(shè)A1，A2，An是集合A的某些非空子集組成的集合，若 A，且AiAj(ij)，則稱為A的一個(gè)劃分，稱中的元素為A的劃分塊。第三十一張，PPT共八十二頁(yè)，創(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的一個(gè)劃分。解 由題設(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的一個(gè)劃分。第三十二張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022例2 求集合Aa，b，c的所有不同的劃分。解 其不同的劃分共有5個(gè)：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組成的集合為原來(lái)兩劃分的交叉劃分

23、。第三十三張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022定義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(mén)，對(duì)于T中任意元素AiBj必有AiBjAi和AiBjBj，故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è)劃分。

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

25、本的原理。 加法原理 若事件的有限集合SS1S2Sn，且S1、S2、Sn兩兩不相交，則|S|S1|S2|Sn| 乘法原理 若事件的有限集合S是依次取自有限集合S1、S2、Sn中事件的序列的集合，則|S|S1|S2|Sn|第三十六張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022例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ù)總共有53525155個(gè)。第

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

27、，順序選取r個(gè)元素共有的不同選取方法數(shù)為：P(n，r)n(n1)(n2)(nr1)。第三十八張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022例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ù)共有987504種方法。定義3.17 r無(wú)重復(fù)排列可以看作是將選出的r個(gè)元素排列在一條直線上的排列，這時(shí)也稱為r線狀排列。如果把這r個(gè)元素排列在一個(gè)圓周上，則這種排列稱為S的r圓排列。對(duì)兩個(gè)圓排列，若其

28、中一個(gè)圓排列可以由另一個(gè)圓排列通過(guò)旋轉(zhuǎn)而得到，則認(rèn)為這兩個(gè)圓排列在本質(zhì)上是同一個(gè)圓排列。于是有下面的結(jié)論成立。第三十九張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022定理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，又一日三餐，故

29、他們一起能共餐8!/(83)1680天。第四十張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20222.組合定義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.16 n個(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(

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

31、 1.排列的生成 排列的生成算法有詞典順序法、逆序法和遞歸排序法等。在這里僅介紹詞典順序法。 設(shè)S1，2，n，(a1，a2，an)和(b1，b2，bn)是S的兩個(gè)排列，若存在i1，2，n，使得對(duì)一切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)的下一個(gè)排列。第四

32、十三張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022定理3.17 對(duì)S的兩個(gè)排列，(b1，b2，bn)是(a1，a2，an)的下一個(gè)排列的充要條件是：(1)存在m1，2，n，使得對(duì)一切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共八十二頁(yè)

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

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

35、2，ar)(a1，a2，ai1，bi，bi1，br)，然后返回步2。步2.2：若ainri，則當(dāng)i1時(shí)，置ii1，返回步2.1。當(dāng)i1時(shí)，算法終止。例6 S1，2，3，4，5，6，求其所有4元素子集。解 123412351236124512461256134513461356145623452346235624563456。第四十七張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.5 歸納原理 3.5.1 結(jié)構(gòu)歸納原理 設(shè)集合A是歸納定義的集合，現(xiàn)欲證A中所有元素具有性質(zhì)P，即證：對(duì)于任意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共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022由于A僅由(1)和(2)條款所確定的元素組成，因此當(dāng)上述證明過(guò)程完成時(shí)，“A中所有元素具有性質(zhì)P”得證。這種推理原理稱為歸納原理，應(yīng)用這一原理進(jìn)行證明的方法稱為歸納法。為區(qū)別通常所說(shuō)的數(shù)學(xué)歸納法，它又稱為“結(jié)構(gòu)歸納法”。數(shù)學(xué)歸納法是其一種特例。第四十九張

37、，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.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(k1)真。 (3)結(jié)論：所有自然數(shù)具有性質(zhì)P。第五十張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022例1 用歸納法證明：對(duì)任意的自然數(shù)n，有(012n)2031323n3。證明 當(dāng)n0時(shí)，n203。假設(shè)nk時(shí)，(

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

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

40、在以后甲乙的搏奕中乙必勝。因此全局也是乙必勝。第五十三張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.6 容斥原理和抽屜原理 3.6.1 容斥原理 設(shè)集合A是歸納定義的集合，現(xiàn)欲證A中所有元素具有性質(zhì)P，即證：對(duì)于任意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共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022集合的運(yùn)算，可用于有限個(gè)元素的計(jì)數(shù)問(wèn)題。在有限集的元素計(jì)數(shù)問(wèn)題中，容斥原理有著廣泛的應(yīng)用。定理3.19(容斥原理) 對(duì)有限集合A和B，有|AB|A|B|AB|。證明 因?yàn)锳BB(AB)且B(AB)，所以|AB|B|AB|。又因?yàn)锳(AB)(AB)且(AB)(AB)，所以|A|AB|AB|。故|AB|A|B|AB| 。定理3.20 推廣到n個(gè)集合A1，A2，An的情形，有：|A1A2An|i|Ai|ij|AiAj|ijk|AiAjAk|(1)n1|A1A2An|。第五十五張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.

42、2022例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|AB|)，從而|AB| 50|A|B|1750262114。所以，兩次考試都得95分的有14人。例2 從1，2，3，4，5，6，7，8，9中取7個(gè)不同的數(shù)字構(gòu)成7位數(shù)，如不允許5和6相鄰，總共有多少種方法？第五十六張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022解 任取7個(gè)不同的數(shù)字

43、構(gòu)成7位數(shù)的個(gè)數(shù)為 9!/2，5和6相鄰的個(gè)數(shù)為6！(2！ )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é)生集合。則：第五十七張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022|A|12，|B|6，|C|14，|AC|6， |BC|=5,|ABC|2，|(AC)B|6。因?yàn)閨(AC)B|(AB)(BC)|(AB)|(BC)|ABC|(AB

44、)|526，所以|(AB)|3。于是|ABC|12614653220， 25205。故，不會(huì)打這三種球的共5人。在不要求嚴(yán)格步驟的情況下，以上各題也可通過(guò)文氏圖的方法來(lái)求解。下面以例3加以說(shuō)明：設(shè)A、B、C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。該問(wèn)題的文氏圖如圖3-2所示。由題意可得：第五十八張，PPT共八十二頁(yè)，創(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共八十二頁(yè)，創(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。 故，不會(huì)打這三種球的共5人。第六十張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.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è)元素的集合

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

47、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。第六十二張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.20223.7 遞推關(guān)系 3.7.1 遞推關(guān)系的概念 有些計(jì)數(shù)問(wèn)題往往與求一個(gè)數(shù)列的通項(xiàng)有關(guān)。但在一些復(fù)雜的特定條件下要直接求出這個(gè)數(shù)列的通項(xiàng)公式，有時(shí)十分困難。而在同樣的條件下，寫(xiě)出該數(shù)列相鄰項(xiàng)之間的關(guān)系，再利用一定的方法和技巧，卻往往能很容易的得到所要的結(jié)論。 例1 斐波那契數(shù)列

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

49、立柱A移到立柱B，可先將n1個(gè)圓盤(pán)從立柱A移到立柱C，留下最大的圓盤(pán)，移動(dòng)的次數(shù)為Hn1；然后再將最大的圓盤(pán)移動(dòng)到立柱B，移動(dòng)1次；最后將n1個(gè)圓盤(pán)從立柱C移到立柱B，移動(dòng)次數(shù)為Hn1。第六十四張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022于是有Hn2Hn11，n2，其中H11。以上的例子有一個(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)系的幾種解法。第六十五張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2

50、0221.遞推關(guān)系的生成函數(shù)解法設(shè)a0，a1，an，為一個(gè)無(wú)窮數(shù)列，我們稱f(t)a0a1tantn為該數(shù)列的生成函數(shù)。例3 數(shù)列1，1，1，的生成函數(shù)為 1ttn。將遞推關(guān)系代入數(shù)列的生成函數(shù)的系數(shù)中去，通過(guò)計(jì)算可以得到生成函數(shù)的顯式，然后再將它展開(kāi)成冪級(jí)數(shù)就可求得數(shù)列的通項(xiàng)。例4 斐波那契數(shù)列問(wèn)題解 設(shè)F(x) 為斐波那契數(shù)列的生成函數(shù)，則有第六十六張，PPT共八十二頁(yè)，創(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共八十二頁(yè)，創(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)系時(shí)要用到下面三個(gè)定理，其證明參見(jiàn)相關(guān)文獻(xiàn)。定理3.22 設(shè)q為非零的實(shí)數(shù)或復(fù)數(shù)，則H(n)qn是遞推關(guān)系式H(n)b1H(n1)b2H(n2)bkH(nk)0(kn，bk0)的解當(dāng)且僅當(dāng)q是它的一個(gè)特征根。第六十八張，PPT共八十二頁(yè)，創(chuàng)作于2022年6月17.08.2022定理3.23 設(shè)q

52、1、q2、qk為非零的實(shí)數(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個(gè)不同的特征根。定理3.24 設(shè)q1、q2、qk為非零的實(shí)數(shù)或復(fù)數(shù)，它們是遞推關(guān)系式H(n)b1H(n1)b2H(n2)bkH(nk)0(kn，bk0)的特征方程的t(tk)個(gè)不同的特征根，各有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、列問(wèn)題第六十九張，PPT共八十二頁(yè)，創(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共八十二頁(yè)，創(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的多項(xiàng)式或an)的遞推關(guān)系式稱為常系數(shù)線性非齊次遞推關(guān)系。這類遞推關(guān)系的求解可通過(guò)將非齊次

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

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