集合論-第一二章習(xí)題課

1、第一章第一章 集合及其運(yùn)算（集合及其運(yùn)算（1 1）例例1 1 設(shè)設(shè)A,B,CA,B,C是三個(gè)任意集合，則是三個(gè)任意集合，則(1)(1)若若A AB B則則A A可能嗎可能嗎? ? A A常真嗎常真嗎? ?舉例說明。舉例說明。(2)(2)設(shè)設(shè)A,BA,B是任意兩個(gè)集合是任意兩個(gè)集合,A,AB B與與A A B B同時(shí)成立同時(shí)成立 這可能嗎這可能嗎? ?證明你的斷言。證明你的斷言。 例例2 2 設(shè)設(shè)A,B,CA,B,C是任意三個(gè)集合，則是任意三個(gè)集合，則(1)(1)若若A AA A，則有，則有B=CB=C嗎？嗎？(2)(2)若若A AA A則有則有B=CB=C嗎？嗎？(3)(3)若若A AA A且

2、且A AA A，則有，則有B=CB=C嗎？嗎？例例3 3若若A,B,CA,B,C是三個(gè)任意集合是三個(gè)任意集合, ,當(dāng)當(dāng)A AA A且且A AC CA AC C， 是否有是否有B=CB=C？例例4 4 設(shè)設(shè)A,BA,B是兩個(gè)任意集合，證明是兩個(gè)任意集合，證明: :(1)A(1)AB BA A2 2B BA AB BA A=2=2B BA=BA=B2 2A A2 2B BA A；2 2A A2 2B BA A ；(5)(5)A A=2=2A A2 2B B。 (3) (3) 例例6 6設(shè)設(shè)A,B,CA,B,C是集合是集合, ,求下列各式成立的充分必要條件求下列各式成立的充分必要條件: : (1)

3、(1)(AB)(AB)AC)=AAC)=A；(2)(AB)(2)(AB)AC)=AC)= (3)(AB)(3)(AB)AC)=AC)=(4)(AB)(4)(AB)AC)=AC)=例例7 7 設(shè)設(shè)A,BA,B是任意集合，則是任意集合，則(1)(1)若若AB=BAB=B，則，則A A與與B B有何關(guān)系？有何關(guān)系？(2)(2)若若AB=BAAB=BA，則，則A A與與B B又有何關(guān)系。又有何關(guān)系。例例8 8 設(shè)設(shè)A,B,CA,B,C是三個(gè)任意的集合，則是三個(gè)任意的集合，則 (1)(1)證明證明:(:(AB)CAB)CA(A( ； (2)(2)舉例說明舉例說明( (AB)CAB)CA(A(。例例9 9

4、設(shè)設(shè)A,BA,B是集合，證明是集合，證明: : (1)A= (1)A=； (2)(AB)(2)(AB) S,T,WS,T,W 習(xí)題課（習(xí)題課（2 2）例例1 1在在10001000名大學(xué)生的調(diào)查中名大學(xué)生的調(diào)查中, ,有有804804人掌握了英語人掌握了英語,205,205人掌握了日語人掌握了日語,190,190人掌握了俄語人掌握了俄語,125,125人既掌握了英語人既掌握了英語又掌握了日語又掌握了日語,57,57人既掌握了日語又掌握了俄語人既掌握了日語又掌握了俄語,85,85人人既掌握了英語又掌握了俄語。試求這既掌握了英語又掌握了俄語。試求這10001000名大學(xué)生中名大學(xué)生中, ,英語、日

5、語、俄語全掌握的有多少人？英語、日語、俄語全掌握的有多少人？(23(23人人) )例例2 2 某班某班3030名學(xué)生中學(xué)英語有名學(xué)生中學(xué)英語有7 7人，學(xué)日語有人，學(xué)日語有5 5人，這人，這兩科都選有兩科都選有3 3人，問兩科都不選的有多少人？人，問兩科都不選的有多少人？ (|A(|AC CB BC C|+|AB|=30, |A|+|AB|=30, |AC CB BC C|=21|=21人人) )例例3 3 某校學(xué)生數(shù)學(xué)、物理、英語三科競賽，某班某校學(xué)生數(shù)學(xué)、物理、英語三科競賽，某班3030人，人，學(xué)生中有學(xué)生中有1515人參加了數(shù)學(xué)競賽，人參加了數(shù)學(xué)競賽，8 8人參加了物理競賽，人參加了物理

6、競賽，6 6人參加了英語競賽，并且其中人參加了英語競賽，并且其中3 3人三科競賽都參加了，人三科競賽都參加了，問至少有多少人一科競賽都沒有參加。問至少有多少人一科競賽都沒有參加。(7(7人人) )例例4 4 甲每甲每5 5秒放一個(gè)爆竹，乙每秒放一個(gè)爆竹，乙每6 6秒放一個(gè)，丙每秒放一個(gè)，丙每7 7秒秒放一個(gè)，每人都放放一個(gè)，每人都放2121個(gè)爆竹，共能聽見多少聲響。個(gè)爆竹，共能聽見多少聲響。(54(54響響) )習(xí)題課（習(xí)題課（3 3）例例1 1 設(shè)設(shè)A,B,CA,B,C是三個(gè)任意集合，證明是三個(gè)任意集合，證明: :A A (B(B C)=C)=( (A A B)B) C C。 左邊左邊=(A

7、=(AB BC CC CC C)(B)(BC CC CC C)(C)(CB BC CA AC C)(A)(AB BC)C) 例例2 2設(shè)設(shè)A,B,CA,B,C是三個(gè)任意集合，化簡是三個(gè)任意集合，化簡例例3 3設(shè)設(shè)A,BA,B是兩個(gè)集合是兩個(gè)集合,B,B , ,試證試證: :若若A AB=BB=BB,B,則則A=BA=B。例例4 4設(shè)設(shè)A,BA,B為集合，試證：為集合，試證：A AB BB BA A的充要條件是下列的充要條件是下列三個(gè)條件至少有一個(gè)成立：三個(gè)條件至少有一個(gè)成立：(1)A=(1)A= ；(2)B=(2)B=3)A=B3)A=B。()()()()()()()CCCCCCCCCABCA

8、BCABCABCABCABCABC例例5 5 馬大哈寫馬大哈寫n n封信，封信，n n個(gè)信封，把個(gè)信封，把n n封信放入到封信放入到n n個(gè)信個(gè)信封中，求全部裝錯(cuò)的概率是多少？封中，求全部裝錯(cuò)的概率是多少？n n個(gè)人，個(gè)人，n n頂帽子，全部戴錯(cuò)的概率是多少？頂帽子，全部戴錯(cuò)的概率是多少？ 當(dāng)當(dāng)n10n10時(shí)時(shí), ,概率都近似等于概率都近似等于0.36790.3679例例6 6 畢業(yè)舞會(huì)上，小伙子與姑娘跳舞，已知每個(gè)小伙畢業(yè)舞會(huì)上，小伙子與姑娘跳舞，已知每個(gè)小伙子至少與一個(gè)姑娘跳過舞，但未能與所有姑娘跳過子至少與一個(gè)姑娘跳過舞，但未能與所有姑娘跳過舞舞。同樣地，每個(gè)姑娘也至少與一個(gè)小伙子跳舞，

9、但也未同樣地，每個(gè)姑娘也至少與一個(gè)小伙子跳舞，但也未能與所有的小伙子跳過舞。證明：在所有參加舞會(huì)的能與所有的小伙子跳過舞。證明：在所有參加舞會(huì)的小伙子與姑娘中，必可找到兩個(gè)小伙子和兩個(gè)姑娘，小伙子與姑娘中，必可找到兩個(gè)小伙子和兩個(gè)姑娘，這兩個(gè)小伙子中的每一個(gè)只與這兩個(gè)姑娘中的一個(gè)跳這兩個(gè)小伙子中的每一個(gè)只與這兩個(gè)姑娘中的一個(gè)跳過舞，而這兩個(gè)姑娘中的每一個(gè)也只與這兩個(gè)小伙中過舞，而這兩個(gè)姑娘中的每一個(gè)也只與這兩個(gè)小伙中的一個(gè)跳過舞。的一個(gè)跳過舞。例例7 7 設(shè)設(shè)M M1 1,M,M2 2, ,和和N N1 1,N,N2 2, ,是集合是集合S S的子集的兩個(gè)序列，的子集的兩個(gè)序列，對(duì)對(duì)ijij，

10、i,j=1,2,i,j=1,2,，有，有N Ni i N Nj j= = 。 令令試證：試證：1111,() ,2,3,nCnnkkQM QMMn 1()nnniiiNQNM第二章第二章 映射習(xí)題映射習(xí)題(1)(1)討論下列映射的性質(zhì)討論下列映射的性質(zhì)例例1 1 X=1,2,3,4,Y=X=1,2,3,4,Y=a,b,c,d,ea,b,c,d,e,f(1)=,f(1)=a,fa,f(2)=a,(2)=a, f(3)= f(3)=c,fc,f(4)=d(4)=d。例例2 2 令令N=1,2,3,N=1,2,3, ，S:NS:NN N，則，則(1)(1) n nS S(n)=n+1,(n)=n+1

11、,稱為自然數(shù)集稱為自然數(shù)集N N上的后繼函數(shù)。上的后繼函數(shù)。(2)S(1)=1,(2)S(1)=1, n nS(n)=n-1,nS(n)=n-1,n2,2,稱為自然數(shù)集稱為自然數(shù)集N N 上的前仆函數(shù)。上的前仆函數(shù)。例例3 3 令為全體偶自然數(shù)之集，令為全體偶自然數(shù)之集，f:Ef:EN N， 2m2m f(2m)=mf(2m)=m。例例4 4設(shè)為整數(shù)的有限集，定義集合設(shè)為整數(shù)的有限集，定義集合X-X=x-X-X=x-x x|x,x|x,x 。試證：若。試證：若A,BA,B且且|A|A|B|B|2n-1,2n-1,n1n1，則，則(A-A)(A-A)(B-B)(B-B)中有一個(gè)正整數(shù)。中有一個(gè)正

12、整數(shù)。第二章映射第二章映射2 2 抽屜原理抽屜原理例例1 1(1)(1)一年一年365365天，今有天，今有366366個(gè)人，則至少有兩個(gè)人生個(gè)人，則至少有兩個(gè)人生日相同。日相同。 (2)(2)抽屜里有抽屜里有1010雙手套，從中取雙手套，從中取1111只出來，則其中只出來，則其中至少有兩只是完整配對(duì)的。至少有兩只是完整配對(duì)的。 (3) (3) 某次會(huì)議有某次會(huì)議有n n位代表參加，每一位代表至少認(rèn)位代表參加，每一位代表至少認(rèn)識(shí)其余識(shí)其余n-1n-1位中的一位，則在這位中的一位，則在這n n位代表中，至少有兩位代表中，至少有兩位認(rèn)識(shí)的人數(shù)相等。位認(rèn)識(shí)的人數(shù)相等。例例2 2 在一個(gè)邊為在一個(gè)邊為

13、1 1的正方形內(nèi)（包括邊界），任意地畫的正方形內(nèi)（包括邊界），任意地畫七個(gè)點(diǎn)，則其中必有三個(gè)點(diǎn)，以它們?yōu)轫旤c(diǎn)所組成的七個(gè)點(diǎn)，則其中必有三個(gè)點(diǎn)，以它們?yōu)轫旤c(diǎn)所組成的三角形面積小于三角形面積小于1/61/6。例例3 3 證明，從證明，從1,2,2n1,2,2n中，任選中，任選n+1n+1個(gè)數(shù)，則在這個(gè)數(shù)，則在這n+1n+1個(gè)數(shù)中必有兩個(gè)數(shù)，使得其中一個(gè)能整除另一個(gè)。個(gè)數(shù)中必有兩個(gè)數(shù)，使得其中一個(gè)能整除另一個(gè)。例例4 4 坐標(biāo)上有五個(gè)整數(shù)點(diǎn)，則存在有兩個(gè)點(diǎn)的連線坐標(biāo)上有五個(gè)整數(shù)點(diǎn)，則存在有兩個(gè)點(diǎn)的連線的中點(diǎn)一定是整數(shù)點(diǎn)。的中點(diǎn)一定是整數(shù)點(diǎn)。例例5 5 證明：在證明：在5252個(gè)正整數(shù)中，必有兩個(gè)整數(shù)

14、，使得個(gè)正整數(shù)中，必有兩個(gè)整數(shù)，使得這兩個(gè)整數(shù)之和或差能被這兩個(gè)整數(shù)之和或差能被100100整除。整除。 抽屜原理抽屜原理也稱為鴿巢原理、重疊原理。這個(gè)原也稱為鴿巢原理、重疊原理。這個(gè)原理十分簡單，但若用得好卻會(huì)得到意想不到的有趣理十分簡單，但若用得好卻會(huì)得到意想不到的有趣結(jié)論。結(jié)論。 但也應(yīng)當(dāng)注意，但也應(yīng)當(dāng)注意，抽屜原理抽屜原理并未告訴我們?cè)鯓訉?shí)并未告訴我們?cè)鯓訉?shí)際地去尋找含有兩個(gè)或更多個(gè)物體的那個(gè)抽屜，而際地去尋找含有兩個(gè)或更多個(gè)物體的那個(gè)抽屜，而只是肯定了確有這樣的抽屜。只是肯定了確有這樣的抽屜。例例6 6 已知已知m m個(gè)整數(shù)個(gè)整數(shù)a a1 1，a a2 2，a am m，試證：存在兩

15、個(gè)整，試證：存在兩個(gè)整數(shù)數(shù)k,l,0k,l,0 k k j j m m，使得使得a ak+1k+1+a+ak+2k+2+ +a+al l能被能被m m整除。整除。例例7 7證明：對(duì)任意正整數(shù)證明：對(duì)任意正整數(shù)N N，存在，存在N N的一個(gè)倍數(shù)，使得的一個(gè)倍數(shù)，使得它僅由數(shù)字它僅由數(shù)字0 0和和7 7組成。（例如組成。（例如N N3,3,有有2592593 3777777；N N4,4,有有192519254 477007700；N N5,5,有有14145 57070；N N6,6,有有129512956 677707770等）。等）。例例8 8 證明：在任意個(gè)人中，或有證明：在任意個(gè)人中，或

16、有3 3個(gè)人相互認(rèn)識(shí)，個(gè)人相互認(rèn)識(shí)，或有或有3 3個(gè)人相互不認(rèn)識(shí)。個(gè)人相互不認(rèn)識(shí)。例例9 9 5 5個(gè)整數(shù)中必有個(gè)整數(shù)中必有3 3個(gè)整數(shù)其和能被個(gè)整數(shù)其和能被3 3整除。整除。例例1010 設(shè)設(shè)a a1 1,a,a2 2, ,a,an n為為1 1，2 2，3 3，n n的任一排列的任一排列, ,若若n n是奇數(shù)且是奇數(shù)且(a(a1 1-1)(a-1)(a2 2-2)-2)(a(an n-n)-n) 0 0，則乘積為偶數(shù)。則乘積為偶數(shù)。 上面的上面的例例2 2、例、例8 8使用的使用的鴿巢原理鴿巢原理實(shí)際上是鴿巢原實(shí)際上是鴿巢原理的一種推廣形式，稱為理的一種推廣形式，稱為“平均值原理平均值原理

17、”，即即 若把若把m m只物體放到只物體放到n n個(gè)抽屜里，則一定存在某一個(gè)個(gè)抽屜里，則一定存在某一個(gè)抽屜，它里面至少有抽屜，它里面至少有(m-1)/n+1(m-1)/n+1個(gè)物體。個(gè)物體。 這里這里xx表示不大于表示不大于x x的最大整數(shù)。的最大整數(shù)。2.2 2.2 抽屜原理強(qiáng)形式抽屜原理強(qiáng)形式抽屜原理強(qiáng)形式抽屜原理強(qiáng)形式: :設(shè)設(shè)m m1 1,m,m2 2,m,mn n都是正整數(shù)都是正整數(shù), ,若把若把m m1 1+m+m2 2+m+mn n-n+1-n+1個(gè)物體放到個(gè)物體放到n n個(gè)抽屜里個(gè)抽屜里, ,則或第一個(gè)抽則或第一個(gè)抽屜里至少有屜里至少有m m1 1個(gè)物體個(gè)物體, ,或第二個(gè)抽屜

18、里至少有或第二個(gè)抽屜里至少有m m2 2個(gè)物個(gè)物體體,或第或第n n個(gè)抽屜里至少有個(gè)抽屜里至少有m mn n個(gè)物體。個(gè)物體。說明說明: :當(dāng)當(dāng)m m1 1=m=m2 2=m=mn n=2=2時(shí)，時(shí)，m m1 1+m+m2 2+m+mn n-n+1=n+1-n+1=n+1。抽屜。抽屜原理是強(qiáng)形式的一種特殊情況。原理是強(qiáng)形式的一種特殊情況。推論推論1 1 若有若有m m個(gè)物體放到個(gè)物體放到n n個(gè)抽屜里，則一定存在某個(gè)抽屜里，則一定存在某一個(gè)抽屜，它里面至少有一個(gè)抽屜，它里面至少有(m-1)/n+1(m-1)/n+1個(gè)物體。個(gè)物體。推論推論2 2 若把若把n(m-1)+1n(m-1)+1個(gè)物體放進(jìn)

19、個(gè)物體放進(jìn)n n個(gè)抽屜里，則一定個(gè)抽屜里，則一定存在某一個(gè)抽屜，它里面至少有存在某一個(gè)抽屜，它里面至少有m m個(gè)物體。個(gè)物體。 此推論是強(qiáng)形式中，當(dāng)此推論是強(qiáng)形式中，當(dāng)m m1 1=m=m2 2=m=mn n=m =m 時(shí)的特殊時(shí)的特殊情況。情況。推 論推 論 3 3 若若 m m1 1, m, m2 2, , m, , mn n是是 n n 個(gè) 正 整 數(shù) ， 且個(gè) 正 整 數(shù) ， 且(m(m1 1+m+m2 2+m+mn n)/nr-1)/nr-1，則，則m m1 1,m,m2 2,m,mn n中至少有一個(gè)中至少有一個(gè)大于或等于大于或等于 r r 。 鴿巢原理強(qiáng)形式例題鴿巢原理強(qiáng)形式例題例

20、例1 1 一個(gè)人步行了十小時(shí)，共走一個(gè)人步行了十小時(shí)，共走4545公里，已知他第公里，已知他第一個(gè)小時(shí)走了一個(gè)小時(shí)走了6 6公里，而最后一小時(shí)只走了公里，而最后一小時(shí)只走了3 3公里，公里，證明一定存在連續(xù)的兩個(gè)小時(shí)，在這兩個(gè)小時(shí)之內(nèi)證明一定存在連續(xù)的兩個(gè)小時(shí)，在這兩個(gè)小時(shí)之內(nèi)至少走了至少走了9 9公里。公里。例例2 2 一個(gè)園環(huán)等分一個(gè)園環(huán)等分3636段，將段，將3636個(gè)數(shù)字個(gè)數(shù)字1,2,361,2,36任任意地寫在每一段上，使每一段上恰有一個(gè)數(shù)字，證意地寫在每一段上，使每一段上恰有一個(gè)數(shù)字，證明：一定存在連續(xù)的三段，在這三段上的數(shù)字之和明：一定存在連續(xù)的三段，在這三段上的數(shù)字之和至少為至

21、少為5656。 S,T,WS,T,W 例例3 3設(shè)設(shè)A,B,CA,B,C是三個(gè)任意集合，化簡是三個(gè)任意集合，化簡例例4 4設(shè)設(shè)A,BA,B是兩個(gè)集合是兩個(gè)集合,B,B , ,試證試證: :若若A AB=BB=BB,B,則則A=BA=B。例例5 5設(shè)為整數(shù)的有限集，定義集合設(shè)為整數(shù)的有限集，定義集合 X-X=x- X-X=x-x|x,xx|x,x。試證：若。試證：若A,BA,B且且|A|A|B|B|2n-1,n12n-1,n1，則，則(A-A)(A-A)(B-B)(B-B)中有一個(gè)正整數(shù)。中有一個(gè)正整數(shù)。() () () ()() () ()CCCCCCCCCA B CAB CA BCA B C

22、ABCA BCAB C 第二章第二章 映射習(xí)題課（映射習(xí)題課（2 2）例例1 1 令令X=xX=x1 1,x,x2 2, , ,x xm m,Y=y,Y=y1 1,y,y2 2, , ,y yn n,問：問：(1)(1)有多少個(gè)不同的由有多少個(gè)不同的由X X到到Y(jié) Y的關(guān)系？的關(guān)系？(2)(2)有多少個(gè)不同的由有多少個(gè)不同的由X X到到Y(jié) Y的映射？的映射？(3)(3)有多少個(gè)不同的由有多少個(gè)不同的由X X到到Y(jié) Y的雙射？的雙射？(4)(4)有多少個(gè)不同的從有多少個(gè)不同的從X X到到Y(jié) Y的單射？的單射？例例2 2 設(shè)設(shè)f:Xf:XY Y，A,BA,BX,X,證明證明: :(1)f(A(1)

23、f(AB)=f(A)B)=f(A)f(B); (2)f(Af(B); (2)f(AB)B)f(A)f(A)f(B);f(B);(3)f(A)f(B)(3)f(A)f(B)f(AB);(4)f(A)f(AB);(4)f(A) f(B)f(B)f(Af(A B)B)。例例3 3設(shè)設(shè)X X是一個(gè)有限集合，從是一個(gè)有限集合，從X X到到X X的部分映射有的部分映射有多少？多少？例例4 4 設(shè)設(shè)u u1,1,u u2,2,u umn+1mn+1是一個(gè)兩兩不相同的整數(shù)構(gòu)是一個(gè)兩兩不相同的整數(shù)構(gòu)成的數(shù)列，則必有長至少為成的數(shù)列，則必有長至少為n n1 1的遞增子序列的遞增子序列或有長至少為或有長至少為m m

24、1 1的遞減子序列。的遞減子序列。例例5 5設(shè)設(shè)N=1,2,3,N=1,2,3,試構(gòu)造兩個(gè)映射試構(gòu)造兩個(gè)映射f,g:Nf,g:N，使得使得fgfg=I=IN N，但，但gfgf I IN N。例例6 6設(shè)設(shè)N=1,2,3,N=1,2,3,試構(gòu)造兩個(gè)映射試構(gòu)造兩個(gè)映射f,g:Nf,g:N，使得使得gfgf=I=IN N，但，但fgfg I IN N。例例9 9 設(shè)設(shè)，證明：，證明：(1)f(1)f是單射是單射 F F 2 2X X，f f1 1(f(f(F(F)=F)=F；(2)f(2)f是滿射是滿射 E E 2 2Y Y，f(ff(f1 1(E)=E(E)=E。例例1010 設(shè)設(shè)， X X =

25、m=m， Y Y =n=n，則則(1)(1)若若f f是左可逆的，則是左可逆的，則f f有多少個(gè)左逆映射？有多少個(gè)左逆映射？(2)(2)若若f f是右可逆的，則是右可逆的，則f f有多少個(gè)右逆映射？有多少個(gè)右逆映射？例例1111 設(shè)設(shè)，則，則(1)(1)若存在唯一的一個(gè)映射若存在唯一的一個(gè)映射g g, ,使得使得gfgf=I=IX X, ,則則f f是可是可逆的嗎？逆的嗎？(2)(2)若存在唯一的一個(gè)映射若存在唯一的一個(gè)映射g g, ,使得使得fgfg=I=IY Y, ,則則f f是可是可逆的嗎？逆的嗎？習(xí)題（習(xí)題（2 2）例例1 1 設(shè)設(shè)f:Xf:XY Y，A AX X，B BY Y，證明：，證明：f(ff(f-1-1(B)(B)A)=BA)=Bf(A)f(A)。例例2 2 設(shè)設(shè)f:Af:AB,B,證明證明: : T T例例3 3 設(shè)設(shè)，證明：，證明： (1)f(1)f是單射是單射 F F 2 2X X，f f1 1(f(F)=F(f(F)=F； (2)f(2)f是滿射是滿射 E E 2 2Y Y，f(ff(f1 1(E)=E(E)=E。例例4 4 設(shè)有映射設(shè)有映射f:Af:AB B,HA，令，令H HC C是是H H對(duì)對(duì)A A中