第1篇預(yù)備知識(shí)ch1集合論ch2計(jì)數(shù)問題

1、 第一章第一章 集合論集合論 第一篇第一篇 預(yù)備知識(shí)預(yù)備知識(shí)1-1 集合的概念和表示集合的概念和表示1-2 集合運(yùn)算集合運(yùn)算第第2章章 計(jì)數(shù)問題計(jì)數(shù)問題2-1 基本原理基本原理2-2 排列與組合排列與組合2-3 鴿籠原理與包含排斥原理（容斥原理）鴿籠原理與包含排斥原理（容斥原理）2-4 離散概率簡(jiǎn)介離散概率簡(jiǎn)介2-5 遞歸關(guān)系遞歸關(guān)系第第1 1章章 集合集合 組成集合的對(duì)象稱為集合的組成集合的對(duì)象稱為集合的member或或（elements）。）。 是是一些確定的、作為一些確定的、作為整體識(shí)別整體識(shí)別的、的、互相區(qū)別互相區(qū)別的的對(duì)象的總體對(duì)象的總體。1-1 1-1 集合的基本概念集合的基本概念

2、 一般用大寫字母表示集合，用小寫字母表示一般用大寫字母表示集合，用小寫字母表示 A A，讀作，讀作“屬于屬于A”A”、“是是A A的元素的元素”、“A A的成員的成員”、 “ “在在A A之中之中”、“A A 包含包含 ”。 如果如果 是是A A的元素，的元素， A A讀作讀作“屬屬于于A ”A ”、或、或“A A中中”。集合的規(guī)定方式有三種：集合的規(guī)定方式有三種：列舉法列舉法 將集合的元素列舉出來(lái)。將集合的元素列舉出來(lái)。 （2）描述法）描述法 利用一項(xiàng)規(guī)則（一個(gè)謂詞公式），描述集合利用一項(xiàng)規(guī)則（一個(gè)謂詞公式），描述集合中的元素的共同性質(zhì)，以便決定某一物體是否中的元素的共同性質(zhì)，以便決定某一物

3、體是否屬于該集合。屬于該集合。 （3）歸納法）歸納法用遞歸方法定義集合。用遞歸方法定義集合。 空集和只含有有限多個(gè)元素的集合稱為空集和只含有有限多個(gè)元素的集合稱為（finite sets），），否則稱為否則稱為（infinite sets）。）。有限集合中元素的個(gè)數(shù)稱為集有限集合中元素的個(gè)數(shù)稱為集合的合的（cardinality）集合集合A的基數(shù)表示為的基數(shù)表示為 A 。 兩個(gè)集合兩個(gè)集合 A和和 B相等相等它們具有相同它們具有相同的元素。即對(duì)任意集合的元素。即對(duì)任意集合A、B, A=B x(x Ax B) 對(duì)任意個(gè)體域，任一謂詞公式都確定一個(gè)以該對(duì)任意個(gè)體域，任一謂詞公式都確定一個(gè)以該域中的

4、對(duì)象為元素的集合。即對(duì)給定個(gè)體域域中的對(duì)象為元素的集合。即對(duì)給定個(gè)體域U，對(duì)，對(duì)任意謂詞公式任意謂詞公式P(x)，存在集合，存在集合S，使得，使得 Sx x UP(x)對(duì)任意謂詞公式對(duì)任意謂詞公式P(x)，均存在集合，均存在集合S，使得，使得 S = x P(x)如果如果A的每的每一個(gè)元素都是一個(gè)元素都是B的元素，則稱的元素，則稱集合集合A是是集合集合B的的（或（或，subsets），或稱），或稱A包含在包含在B內(nèi)，內(nèi)，A B 或稱或稱B包含包含A，B A 。 即即 A B x(x Ax B) 設(shè)設(shè)A，B，C為任意集合，根據(jù)定義，顯然有：為任意集合，根據(jù)定義，顯然有： 包含關(guān)系具有自反性包含關(guān)

5、系具有自反性：A A 包含關(guān)系具有傳遞性：若包含關(guān)系具有傳遞性：若A B且且B C，則，則A C。對(duì)任意集合對(duì)任意集合A，B，AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A B且且B A 。即。即 ABA B B A 。 證明思路：第一步先證充分性：證明思路：第一步先證充分性： AB A B B A 第二步再證必要性：第二步再證必要性： AB A B B A （或（或A B B A AB ） 對(duì)任何集合對(duì)任何集合A， A。即空集是任意集合。即空集是任意集合的子集。的子集。 證明：反證法。證明：反證法。 空集是唯一的空集是唯一的 如果如果 A B且且A B，則稱，則稱集合集合 A是集是集合合 B的真子集，的真子集，“A

6、是是B的真子集的真子集”，記為，記為A B 。 A B x(x Ax B) x(x A x B) A B A B A B不包含任何元素的集合是空集，記為不包含任何元素的集合是空集，記為。U x(x E)恒真恒真 對(duì)任意集合對(duì)任意集合 A，(A)稱為稱為A的的（Power set）定義為）定義為 (A)x | x A 即即A的全體子集構(gòu)成的全體子集構(gòu)成A的冪集。此種運(yùn)算稱為集合的冪集。此種運(yùn)算稱為集合A的求的求冪運(yùn)算。冪運(yùn)算。設(shè)設(shè) A 為一有限集合，為一有限集合，A n，那么，那么 A的的(A)的元素的元素個(gè)數(shù)為個(gè)數(shù)為2n。 證明思路：利用從證明思路：利用從n個(gè)元素中選個(gè)元素中選k個(gè)元素來(lái)組成子

7、集，個(gè)元素來(lái)組成子集，計(jì)算所有可能的選法為計(jì)算所有可能的選法為Cnk種，種， n 子集的總數(shù)是子集的總數(shù)是Cn0 + Cn1 + + Cnn = Cnk k=0 n 根據(jù)二項(xiàng)式定理根據(jù)二項(xiàng)式定理(x+y)n= Cnk xk yn-k k=1 再令再令x=1，y=1，代入上式后定理得證。，代入上式后定理得證。 冪集的元素可以對(duì)子集合的腳標(biāo)用二進(jìn)制編碼來(lái)唯一冪集的元素可以對(duì)子集合的腳標(biāo)用二進(jìn)制編碼來(lái)唯一地確定。地確定。1-2 1-2 集合運(yùn)算集合運(yùn)算ABABE 由由A和和B B的所有的所有共同元素組成的集合共同元素組成的集合S，則稱，則稱集合集合S是是集合集合A和和B的的，AB 。 即即 S= A

8、B = x | (x A) (x B) AB a) AA=A 冪等律冪等律 b) A = 0 0律律 c) AE = A 1 1律律 d) AB = BA 交換交換律律 e) (AB) C= A (BC) 結(jié)合結(jié)合律律 對(duì)對(duì)e)的證明思路：根據(jù)交運(yùn)算的定義，利用謂詞邏輯的證明思路：根據(jù)交運(yùn)算的定義，利用謂詞邏輯中的聯(lián)結(jié)詞中的聯(lián)結(jié)詞“”的結(jié)合律推導(dǎo)，再利用交運(yùn)算的定義，的結(jié)合律推導(dǎo)，再利用交運(yùn)算的定義，轉(zhuǎn)換為集合交運(yùn)算轉(zhuǎn)換為集合交運(yùn)算“”的結(jié)合律。的結(jié)合律。 （證明過程略）。（證明過程略）。 ABABE 由由所有屬于所有屬于A A或或?qū)儆趯儆贐 B的元素組成的集合的元素組成的集合S S，稱集合，

9、稱集合S S是集合是集合A A和和B B的的，AB 。 即即 S= AB = x | (x A) (x B) AB a) AA=A 冪等律冪等律 b) A =A 0 0律律 c) AE =E 1 1律律 d) AB = BA 交換交換律律 e) (AB) C= A (BC) 結(jié)合結(jié)合律律 對(duì)對(duì)e)的證明思路：根據(jù)并運(yùn)算的定義，利用謂詞邏輯的證明思路：根據(jù)并運(yùn)算的定義，利用謂詞邏輯中的聯(lián)結(jié)詞中的聯(lián)結(jié)詞“”的結(jié)合律推導(dǎo)，再利用并運(yùn)算的定義，的結(jié)合律推導(dǎo)，再利用并運(yùn)算的定義，轉(zhuǎn)換為集合并運(yùn)算轉(zhuǎn)換為集合并運(yùn)算“”的結(jié)合律。的結(jié)合律。 設(shè)設(shè) A、B、C 為三個(gè)集合，為三個(gè)集合，則下列分配律成則下列分配律

10、成立：立： a) A (B C)=(A B) (A C) （交對(duì)并分配）（交對(duì)并分配） b) A (B C)=(A B) (A C) （并對(duì)交分配）（并對(duì)交分配）。 證明思路：證明思路：根據(jù)并運(yùn)算和交運(yùn)算的定義，根據(jù)并運(yùn)算和交運(yùn)算的定義， 先證：先證： 等式的左端等式的左端 等式的右端。等式的右端。 對(duì)任意對(duì)任意x 左端左端 x 右端右端 再證：再證： 等式的右端等式的右端 等式的左端。等式的左端。 對(duì)任意對(duì)任意x 右端右端 x 左端左端 設(shè)設(shè) A、B 為任意兩個(gè)集合，為任意兩個(gè)集合，則下列關(guān)系式則下列關(guān)系式（吸收率）成立：（吸收率）成立： a) Aa) A (A(A B B)=A )=A b

11、) A b) A (A(A B)=A B)=A 證明思路：證明思路： 先證先證a) a) ：根據(jù)：根據(jù)1律，將等式左端的第一個(gè)律，將等式左端的第一個(gè)A 換成換成“A E” ，再根據(jù)分配律提出，再根據(jù)分配律提出A，得到，得到A （E B），），再根據(jù)再根據(jù)1律即得右端。律即得右端。 再證再證b) b) ：根據(jù)冪等律，將等式左端的第一個(gè)：根據(jù)冪等律，將等式左端的第一個(gè)A 換成換成“A A”A” ，再根據(jù)分配律提出，再根據(jù)分配律提出A，得到，得到A （A B），），再根據(jù)剛證出的再根據(jù)剛證出的a)a)式式即得右端。即得右端。 A B 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A A B B=B=B或或A A B B=A=A

12、成立。成立。 證明思路：本定理表示成如下兩式：證明思路：本定理表示成如下兩式： a) A B A A B B=B =B b) A B A A B B=A=A a)式的證明步驟：式的證明步驟： 先證先證 A B A A B B=B=B: : 以以“A B”為條件推導(dǎo)出為條件推導(dǎo)出“A A B B=B=B”的的結(jié)論。結(jié)論。 再證再證A A B B=B =B A B : 以以“A A B B=B=B”為條件推導(dǎo)出為條件推導(dǎo)出“A B”的的結(jié)論。結(jié)論。 b)式的證明步驟與式的證明步驟與a)式類似。式類似。 由由所有屬于所有屬于A A而而且不屬于且不屬于B B的元素組成的集合的元素組成的集合S S，稱集

13、合，稱集合S S是集合是集合B B對(duì)于集合對(duì)于集合A A的的，或，或相對(duì)補(bǔ)（相對(duì)補(bǔ)（complement of B with respect to A），A-B ，又稱為又稱為A與與B的差的差（difference） 。 即即 S= A-B = x | (x A) (x B) = x | (x A) (x B) A-BABA-BE稱集合稱集合是集合是集合A A的的絕對(duì)補(bǔ)（絕對(duì)補(bǔ)（complement），A 。 即即 S= E-A = x | (x E) (x A) = x | (x E) (x A) AAAE d) AA （雙重否定律）（雙重否定律） e) E E f) A AE A A g)

14、 (A B)A B (A B)A B 對(duì)任意集合對(duì)任意集合 A，B，C，下式成立，下式成立: a) A - BA B A - BA - (A B) b) A - A A - A A E = c) A - (B C)(A - B) (A - C) A - (B C)(A - B) (A - C）補(bǔ)余律補(bǔ)余律德德摩根律摩根律互否互否律律分配律分配律0-1律律 德德摩根律的證明摩根律的證明: (A B) x | x (A B) x | x (A B) x | (x A ) (x B) x | (x A ) (x B) A B (A B)A B的證明同上。的證明同上。 定理定理1-2.5第第2式式A

15、- BA - (A B)的證明思路的證明思路: 先證先證A - B A - (A B) 從對(duì)于任意的從對(duì)于任意的 x x A - B出發(fā)，推出出發(fā)，推出x x A - (A B) 再證再證A - (A B) A - B 從對(duì)于任意的從對(duì)于任意的x x A - (A B) 出發(fā)，推出出發(fā)，推出x x A - B 對(duì)任意集合對(duì)任意集合A , B ,若若A B,則則 a)a) B A b)b) (B-A)(B-A) A=BA=B 證明思路證明思路: a)a) A B 若若 x x A則則 x x B 若非若非x x B則非則非x x A 若若 x x B則則 x x A B A b)b)先將先將“

16、- ”運(yùn)算轉(zhuǎn)換成運(yùn)算轉(zhuǎn)換成“ ”運(yùn)算，利用運(yùn)算，利用“ 運(yùn)運(yùn)算分配律算分配律”進(jìn)行集合運(yùn)算。進(jìn)行集合運(yùn)算。 對(duì)任意集合對(duì)任意集合A、 B 、C C，下式成立：，下式成立： A (B -C) ( A B ) - ( A C) 證明思路證明思路: 先將先將“ - ”運(yùn)算轉(zhuǎn)換成運(yùn)算轉(zhuǎn)換成“ ”運(yùn)算，利用運(yùn)算，利用“ 運(yùn)算運(yùn)算結(jié)合律結(jié)合律”和和“德德摩根律摩根律”進(jìn)行集合運(yùn)算。進(jìn)行集合運(yùn)算。 設(shè)設(shè)A,BA,B為任意集合為任意集合, A, A B B(A) (A) (B) (B) 。 對(duì)任意集合對(duì)任意集合A，B若它們滿足若它們滿足 （l）A BU （2）A B 那么那么BA A A和和B B的的對(duì)稱對(duì)稱

17、差（差（symmetric differencesymmetric difference）為集合為集合S S，其元素，其元素或?qū)儆诨驅(qū)儆贏 A，或?qū)儆?，或?qū)儆贐 B，但不能即屬于，但不能即屬于A A又屬于又屬于B B，的元素組成，的元素組成的集合的集合S S，AB 。 即即 S= AB =(A-B) (B-A) = x | (x A) (x B) A-BABABE對(duì)任意集合對(duì)任意集合 A，B，C，下式成立，下式成立: a) A B B A 交換交換律律 b) A A c) A A d) A B (A B ) (A B B ） e) (A B) C= A (B C) 結(jié)合結(jié)合律律 （證明過程略）

18、（證明過程略） 若集合若集合C的每個(gè)元素都是集合，則稱的每個(gè)元素都是集合，則稱C為集合族為集合族（collections）。若集合族）。若集合族C可表示為可表示為 C =Sd|d D則稱則稱 D D為集合族的為集合族的（index set）。）。第2章 計(jì)數(shù)問題 2.1基本原理:乘法原理與加法原理(復(fù)習(xí)) 2.2排列與組合(復(fù)習(xí)) 注意環(huán)排問題2.3 2.3 鴿籠原理與容斥原理鴿籠原理與容斥原理 2.3.1鴿籠原理鴿籠原理(Pigeonhole Principle)(Pigeonhole Principle) 定理定理2.3.12.3.1 若有若有n+1n+1只鴿子住進(jìn)只鴿子住進(jìn)n n個(gè)鴿籠，則至少個(gè)鴿籠，則至少有一個(gè)鴿籠至少住進(jìn)有一個(gè)鴿籠至少住進(jìn)2 2只鴿子。只鴿子。 例例1 n+11 n+1個(gè)正整數(shù)中個(gè)正整數(shù)中, ,總有兩個(gè)數(shù)的差能被