離散數(shù)學(xué)（第3版）課件ch3(1) 集合與關(guān)系 3.1-3.2 2021-5-13

1在SharpEL-506S計(jì)算器上，230的值為1073741820。如果這個(gè)值是正確的，那么228=230/4的最后一位一定是5。但是，2的冪不可能是奇數(shù)，所以230的最后一位一定是錯(cuò)誤的。230的最后一位數(shù)字是什么？2“國(guó)際標(biāo)準(zhǔn)書號(hào)”(InternationalStandardBookNumber，ISBN)RobCallan所著《ArtificialIntelligence》ISBN是0-333-80136-9。校驗(yàn)位9是如何計(jì)算的？校驗(yàn)位有11個(gè)可能的值：0、1、2、3、4、5、6、7、8、9或X(X代表10)。校驗(yàn)位是按下列方法計(jì)算出來(lái)的：分別用10、9、8、7、6、5、4、3和2乘以ISBN的前9位，并將這9個(gè)乘積相加得到y(tǒng)，校驗(yàn)位d是滿足y＋d≡0(mod11)的數(shù)字。3證明對(duì)任意整數(shù)N，存在N的一個(gè)倍數(shù)，此倍數(shù)只含有數(shù)字0和7。證明在n+2個(gè)正整數(shù)中，必存在兩個(gè)數(shù)a,b滿足a+b或a-b是2n的倍數(shù)。4T.JenkynsandB.Stephenson,FundamentalsofDiscreteMathforComputerScience:AProblem-SolvingPrimer,UndergraduateTopicsinComputerScience,DOI10.1007/978-1-4471-4069-6_6,#Springer-VerlagLondon

2013《離散數(shù)學(xué)解題指導(dǎo)（第2版）》，清華大學(xué)出版社，2016賁可榮等5集合與關(guān)系第3章集合與關(guān)系3.1集合的概念和表示法3.2集合的運(yùn)算3.12包含排斥原理第5章組合計(jì)數(shù)5.6鴿籠原理第3章6

十九世紀(jì)數(shù)學(xué)最偉大成就之一集合論體系:

樸素(naive)集合論公理(axiomatic)集合論創(chuàng)始人康托(Cantor)1845~1918

德國(guó)數(shù)學(xué)家,集合論創(chuàng)始人.3.1集合的概念和表示法7什么是集合(set)？集合：不能精確定義。一些對(duì)象的整體就構(gòu)成集合，這些對(duì)象稱為元素(element)

用大寫英文字母A,B,C,…表示集合用小寫英文字母a,b,c,…表示元素

a∈A：表示a是A的元素，讀作“a屬于A”aA：表示a不是A的元素，讀作“a不屬于A”一、集合的表示Asetisawell-definedcollectionofobjectscalleditselements8Asetisawell-definedcollectionofobjectscalleditselements//By“well-defined”,wemeanthatforanyobjectthatmightpossiblybeintheset,//thereisawayofdecidingwhetheritisinthesetornot.//We’veleft“collection”and“object”asprimitive(thatis,undefined)terms//(butwehope“youknowwhatImean”).9集合有哪些表示方法？枚舉法:描述法:圖示法:列出集合的所有元素，元素之間用逗號(hào)隔開，并把它們用花括號(hào)括起來(lái)。把屬于集合中元素所具有的屬性描述出來(lái)，寫在花括號(hào)里。集合與集合之間的關(guān)系以及一些運(yùn)算結(jié)果可用文氏圖給予直觀表示。文氏(JohnVenn,1834~

1923)圖:平面上的n個(gè)圓(或橢圓),使得任何可能的相交部分,都是非空的和連通的。

一、集合的表示10全體整數(shù)的集合，表示為Z全體自然數(shù)的集合，表示為N全體有理數(shù)的集合，表示為Q全體實(shí)數(shù)的集合，表示為R全體復(fù)數(shù)的集合，表示為C常用的數(shù)集有哪些？11子集、集合的包含與相等空集冪集二、基本概念12

設(shè)A，B是兩個(gè)集合，如果A的每一元素都是B的元素，那么就說(shuō)Ａ是Ｂ的子集，記作（讀作Ａ包含于Ｂ），或記作（讀作Ｂ包含Ａ）。思考：若A，B都是集合，則A能同時(shí)既是B的元素又是B的子集嗎？定理：設(shè)A，B為任意集合，則稱A與B相等的充分必要條件是A

B且B

A。符號(hào)化表示為A＝B

A

B∧B

A。

子集、集合的包含和相等基本概念13包含的性質(zhì)A

A若A

B，且A≠B，則BA若A

B，且B

C，則A

C集合之間的關(guān)系14空集空集:沒有任何元素的集合是空集，記作

。例如,{x∈R|x2+1=0}定理1:對(duì)任意集合A,

A證明:

A

x(x∈

→x∈A)

x(F→x∈A)

T.試證明空集是唯一的。15定義：集合A的所有子集的全體稱為A的冪集，記為P（A）（powerset）冪集設(shè)A是具有n個(gè)元素的有限集合，則A的冪集P(A)有2n個(gè)元素。試判斷下列命題是否為真：P(A)∩P(B)＝P(A∩B)P(A)∪P(B)＝P(A∪B)16ItissaidthatwhenBertrandRussell(1872–1970)wasastudent,hereadadescriptionofsettheoryasabasisforthefoundationsofmathematicsbyGottlobFrege(1848–1925)muchlikethelastfewpageshereandwonderedaboutthesetK={x:xx},thesetofallsetsthatarenotelementsofthemselves.17ThissetisparadoxicalbecauseifK∈K;then(KmustsatisfytheconditionformembershipinKso)KK;butifKK;then(KdoessatisfytheconditionformembershipinKso)K∈K:Russell’sParadoxmayberemovedbyconstructingamuchmore“sophisticated”settheory(Zermelo-Fraenkelsettheory)thatassignstypestotheobjects,classes,andsetsorthatrestrictsobjectstoafixed“universeofdiscourse”.Butlet’sjustnotworryabouttheparadoxhopingitwillnevercauseusproblemslike.18Zermelo-Fraenkel公理集合論的部分公理：(1)子集公理：對(duì)于任何一個(gè)集合A和集合A的每一種性質(zhì)P，存在一個(gè)集合B，B的元素恰好是A中具有性質(zhì)P的元素。(2)外延公理：集合A和B相等，等價(jià)于x∈Ax∈B。(3)空集公理：不包含任何元素的集合是存在的。(4)冪集公理：對(duì)于任何集合A，存在唯一集合B，

B恰以A中所有子集為其元集。(5)基礎(chǔ)公理：對(duì)于任何集合A，只要A非空，就存在x∈A

，使得x和A沒有任何相同元素。

19集合與關(guān)系第3章集合與關(guān)系3.1集合的概念和表示法3.2集合的運(yùn)算3.12包含排斥原理第5章組合計(jì)數(shù)5.6鴿籠原理第3章20一、集合的基本運(yùn)算并運(yùn)算(union)

由A的一切元素和B的一切元素所成的集合叫做A與B的并集，記作A∪B交運(yùn)算(intersection)

由集合A與B的公共元素所組成的集合叫做A與B的交集記作A∩B設(shè)A，B是兩個(gè)集合，A與B有如下運(yùn)算：差運(yùn)算(setdifference)是由一切屬于A但不屬于B的元素所組成的，稱為A與B的差。對(duì)稱差運(yùn)算A⊕B=(A-B)∪(B-A)=(A∪B)-(A∩B)21二、有窮計(jì)數(shù)集

每一條性質(zhì)決定一個(gè)集合。任何兩個(gè)集合都畫成相交的，將已知集合的元素?cái)?shù)填入表示該集合的區(qū)域內(nèi)。通常從n個(gè)集合的交集填起，根據(jù)計(jì)算的結(jié)果將數(shù)字逐步填入所有的空白區(qū)域。如果交集的數(shù)字是未知的，可以設(shè)為x。根據(jù)題目中的條件，列出一次方程或方程組，就可以求得所需要的結(jié)果。文氏圖22

設(shè)A為集合，A的元素的元素構(gòu)成的集合稱為A的廣義并，記為∪A?！華＝{x|

z(z

A∧xz)}。

設(shè)A為非空集合，A的所有元素的公共元素構(gòu)成的集合稱為A的廣義交，記為∩A?！葾＝{x|

z(z

A→x

z)}三、廣義并和廣義交23例1

(1)A={{a,b},{c,d},{d,e,f}}，求∩A和∪A

。

(2)A={{1,2,3},{1,a,b},{1,6,7}}，求∩A和∪A

。例2

A1={a,b,{c,d}},A2={{a,b}},A3={a},A4={,{}},A5=a,A6=

，求A1—A6的廣義并與廣義交。24例1

(1)A={{a,b},{c,d},{d,e,f}}，求∩A和∪A

。

(2)A={{1,2,3},{1,a,b},{1,6,7}}，求∩A和∪A

。答（1）∩A=

∪A={a,b,c,d,e,f}（2）∩A={1}∪A={1,2,3,6,7,a,b}25例2

A1={a,b,{c,d}},A2={{a,b}},A3={a},A4={,{}},A5=a,A6=

，求A1—A6的廣義并與廣義交。A1∩A1=

∪A1=a∪b∪{c,d}A2∩A2={a,b}∪A2={a,b}A3∩A3=a∪A3=a(如a是非空集合)A4∩A4無(wú)

∪A4={

}A5∩A5無(wú)

∪A5無(wú)

A6∩A6無(wú)

∪A6無(wú)

26

設(shè)A，B，C為任意集合，下列各式成立。（l）等冪律A∪A=A

A∩A=A（2）交換律A∪B=B∪AA∩B＝B∩A（3）結(jié)合律(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)（4）分配律A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)集合的運(yùn)算的性質(zhì)27（5）吸收律A∩(A∪B)=AA∪(A∩B)=A（6）德摩根律A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)集合的運(yùn)算的性質(zhì)(續(xù))28集合與關(guān)系第3章集合與關(guān)系3.1集合的概念和表示法3.2集合的運(yùn)算3.12包含排斥原理第5章組合計(jì)數(shù)與離散概率5.6鴿籠原理第3章29例3一個(gè)班50人中，有16人期中得優(yōu)，21人期末得優(yōu)，17人兩次均沒得優(yōu)，問有多少人兩次均得優(yōu)？定理(包含排斥原理

)對(duì)有限集合A和B，有|A∪B|＝|A|＋|B|－|A∩B|包含排斥原理

解:設(shè)A為期中得優(yōu)的人的集合，B為期末得優(yōu)的人的集合，E為全集。則根據(jù)題設(shè)有|A|＝16，|B|＝21，|E|＝50，|(A∪B)|＝50-17，兩次均得優(yōu)的人數(shù)為|A∩B|，|A∩B|＝|A|＋|B|－|(A∪B)|＝16＋21－(50－17)＝430例4

學(xué)英、法、德語(yǔ)的同學(xué)分別為100,30,35人,其中同時(shí)學(xué)英語(yǔ)和法語(yǔ)的同學(xué)15人，同時(shí)學(xué)英語(yǔ)和德語(yǔ)的同學(xué)20人，同時(shí)學(xué)法語(yǔ)和德語(yǔ)的同學(xué)15人，同時(shí)學(xué)三種語(yǔ)言的同學(xué)5人，問只學(xué)一種語(yǔ)言的同學(xué)有多少人？包含排斥原理

包含排斥原理可以擴(kuò)充到三個(gè)集合的情況。|A∪B∪C

|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|

－|C∩B|+|A∩

B∩

C

|31例5

對(duì)24名會(huì)外語(yǔ)的科技人員進(jìn)行掌握外語(yǔ)情況的調(diào)查。其統(tǒng)計(jì)結(jié)果如下：會(huì)英、日、德和法語(yǔ)的人分別為13，5，10和9人，其中同時(shí)會(huì)英語(yǔ)和日語(yǔ)的有2人，會(huì)英、德和法語(yǔ)中任兩種語(yǔ)言的都是4人。已知會(huì)日語(yǔ)的人既不懂法語(yǔ)也不懂德語(yǔ)，分別求只會(huì)一種語(yǔ)言(英、德、法、日)的人數(shù)和會(huì)三種語(yǔ)言的人數(shù)。英德法日32集合與關(guān)系第3章集合與關(guān)系3.1集合的概念和表示法3.2集合的運(yùn)算3.12包含排斥原理第5章組合計(jì)數(shù)

5.6鴿籠原理第3章33

有一個(gè)晚上，宿舍停電了，伸手不見五指。突然緊急集合，于是你就摸床底下的襪子。你有三雙分別為紅、白、黑顏色的襪子?？墒悄闫綍r(shí)做事隨便，一脫襪子就丟，在黑暗中不知道哪一雙是同色的。于是，你想拿最少數(shù)目的襪子出去，到走廊上配成一對(duì)。這最少數(shù)目應(yīng)該是多少？思考題

34鴿巢原理(PigeonholePrinciple)定理鴿巢原理（第一種形式）

n只鴿子飛入k個(gè)鴿巢，k<n，則必存在某個(gè)鴿巢包含至少兩只鴿子。

例6

任選8個(gè)人，至少有2個(gè)人是在一星期的同一天出生的。證明:采用反證法。假設(shè)結(jié)論不成立，即每個(gè)鴿巢至多有一只鴿子，則k個(gè)鴿巢中最多有k只鴿子，與鴿子總為n>k矛盾。故結(jié)論成立。35鴿巢原理

鴿巢原理最先是由德國(guó)數(shù)學(xué)家狄利克雷運(yùn)用于解決數(shù)學(xué)問題的，所以也叫“狄利克雷原理”。又稱為“抽屜原理”。它是數(shù)學(xué)中證明存在性的一種方法。鴿巢原理的表述雖然比較簡(jiǎn)單，很容易理解，但其變化多，應(yīng)用廣。36例7

在1~8的整數(shù)中任取5個(gè)，一定有兩個(gè)數(shù)之和為9。例8

從集合{1,2,3,…,20}中任選11個(gè)數(shù)，則必有一個(gè)數(shù)是另一個(gè)數(shù)

的倍數(shù)。例9

在邊長(zhǎng)為1的正方形內(nèi)，任意給定5個(gè)點(diǎn)，則其中必有兩點(diǎn)之間的距離不大于(21/2)/2。鴿巢原理定理鴿巢原理（第一種形式）

n只鴿子飛入k個(gè)鴿巢，k<n，則必存在某個(gè)鴿巢包含至少兩只鴿子。

37鴿籠原理（第二種形式）定理如果有n只鴿子，m只籠子，且m<n，則有一只籠子里面至少有[（n-1）/m]+1只鴿子。證明：（反證）如果每個(gè)籠子包含的鴿子數(shù)≤[（n-1）/m]，則最多有鴿子m×[（n-1）/m]≤m×（n-1）/m=n-1，矛盾。因此，其中一只籠子必須至少包含[（n-1）/m]+1只鴿子。鴿巢原理38鴿籠原理（第二種形式）定理

如果有n只鴿子，m只籠子，且m<n，則有一只籠子里面至少有[（n-1）/m]+1只鴿子。例10

任選30個(gè)人，至少有5個(gè)人是在一星期的同一天出生的。例11

若