复旦大学计算机科学与工程系-吴永辉-离散数学-集合论经典习题省公开课金奖全国赛课一等奖微课获奖PPT

集合论习题解析

——经典习题与考研习题经典习题一、集合基础二、二元关系三、函数四、概念综合练习考研习题北京大学、中科院计算所、中科院软件所、中科院自动化所、北京师范大学、中科院成都计算所、上海交通大学、西安交通大学、西南交通大学、北京航空航天大学、复旦大学等1/126一、集合基础1.1与1.2集合运算1.3幂集2/1261.1与1设A,B,C是任意3个集合，假如AB,BC,则AC可能吗？AC常真吗？举例说明。3/126AC可能A={1},B={{1}},C={{1},{{1}}}AC不常真A={1},B={{1}},C={{{1}}}4/1262设A,B是任意2个集合，A

B与

AB同时成立，这可能吗？5/126可能A={1},B={{1},1}.6/1263设A,B,C是集合，判断以下命题真假，假如为真，给出证实；假如为假，给出反例：1)AB,BCAC;2)

AB,BCAC;3)

AB,BCAC;4)

AB,BCAC;5)aA,AB

aB.7/1261）假A={1},B={2},C={{2}}

2）假A={1},B={2},C={{1}}3）假A={1},B={{1}},C={{1},1}8/1264）假A={1},B={{1},1}，C={{1},2}5）真子集定义9/1264设A,B,C是U子集，判断以下命题真假，假如为真，给出证实；假如为假，给出反例：1)ABAB=B;2)ABAB=A;3)ABAB=A;4)ABAB=B;5)ABA(B-A)=B;6)BA(A-B)B=A;10/1261）假，A=B时不成立/*

与

不一样*/分析：I)ABAB=B：因为BAB；对于任意xAB，假如xA,因为AB,所以xB,则对任意xAB，xB成立。所以AB=B。II)A=B

AB=B，但AB不成立。11/1262）假，A={1}，B={1，2}，不成立；3）假，A=B时不成立；4）假，A={1}，B={1，2}，不成立；5）假，A=B时不成立6）假，A={1，2}，B={1}，不成立；12/1261.2集合运算5设A,B,C是任意3个集合，（1）AB=AC，则B=C吗？（2）AB=AC，则B=C吗？（3）AB=AC且AB=AC，则B=C吗？13/126（1）假A={1,2},B={1},C={2}（2）假A={1},B={1,2},C={1,3}（3）真/*基本法、反证法证实*/设xB，假设xC。因为xB，所以x

AB；因为AB=AC，所以xAC；因为xC，所以x

A；又因为xB，所以xAB；因为AB=AC，所以xAC；则xC，这与xC矛盾。所以B=C。14/1266设A,B是任意2个集合，（1）若A-B=B，则A与B有何关系？（2）若A-B=B-A，则A与B有何关系？（3）若A

B=A

B，则A与B有何关系？（4）若AB=A，则A与B有何关系？/*用文氏图辅助*/15/126证实：(1)由A-B=B，可得出A=B=

。16/126(2)由A-B=B-A，可导出A=B。17/126(3)A=B18/126(4)B=

19/1267给出以下命题成立充分必要条件（1）(A-B)(A-C)=A（2）(A-B)(A-C)=（3）(A-B)(A-C)=（4）(A-B)(A-C)=/*等式推导*/20/126解：(1)1)：设(A-B)(A-C)=A，对任意x，xA，则xA-B或xA-C；则有21/1262）：设A

BC=，对任意x，xA，则xB或xC，则有22/126对任意x，x(A-B)(A-C)，则xA-B或

xA-C，则有23/126（2）

(A-B)(A-C)=(A-B)=或(A-C)=

AB而且ACABC所以，充要条件为ABC。24/126（3）1)设(A-B)(A-C)=，对任意x，xA，x(A-B)而且x(A-C)；所以xB-A或xC-A；则有xB或xC；得xBC。所以ABC。2)ABCAB或AC；所以A-B=或A-C=。得(A-B)(A-C)=。从而，(A-B)(A-C)=ABC。25/126（4）(A-B)(A-C)=((A-B)-(A-C))((A-C)-(A-B))=

(A-B)(A-C)而且(A-C)(A-B)

(A-B)=(A-C)26/1261.3幂集7设A,B是任意2个集合，证实：（1）ABP(A)P(B)（2）P(A)P(B)A

B（3）P(A)=P(B)A=B27/126/*利用基本法证实集合包含关系*/证实：(1)对任意xP(A),有xA,又因为AB，所以xB,即xP(B)；所以P(A)P(B)。(2)/*证实方法同(1)；*/对任意xA,则{x}P(A)，又因为P(A)P(B)，所以{x}P(B)，即xB；所以A

B。(3)由(1)和(2)证实导出。28/126二、二元关系1设R是集合A上关系（1）R是自反，则RR是自反；（2）R是对称，则RR是对称；（3）R是反自反和传递，则R是反对称；29/126/*证实思想：依据定义给出性质证实*/证实：（1）证实思想与（2）和（3）相同（2）设(a,b)

RR,则存在c,(a,c)

R,(c,b)

R;因为R是对称，所以(b,c)

R,(c,a)

R;所以(b,a)

RR。则RR是对称。（3）假设(a,b)

R,(b,a)R。因为R是传递，所以(a,a)R，(b,b)R；因为R是反自反，所以造成矛盾。30/1262设R是A上关系，若R是自反和传递，则R

R=R。其逆命题也成立吗？证实思想：证实R

R=R，1）证实R

R

R；2）证实R

R

R：31/126证实：1）证实R

R

R：设(a,b)

R

R，存在cA,使得(a,c)

R,(c,b)

R，因为R是传递，所以(a,b)

R；则R

R

R；2）证实R

R

R：设(a,b)

R，R是自反，(b,b)

R，所以(a,b)

R

R；则R

R

R。所以R

R=R。32/126自反不成立传递成立33/126特殊关系3设S={1,2,3,4}，并设A=SS，在A上定义关系R为：（a,b）R（c,d）当且仅当a+b=c+d。（1）证实R是等价关系；（2）计算出A/R。34/126（1）证实：/*依据等价关系定义证实*/1）/*证实R是自反；*/对于任意(a,b)SS，因为a+b=a+b，所以(a,b)R(a,b)，即R是自反。2）/*证实R是对称；*/假如(a,b)R(c,d)，则a+b=c+d，那么有c+d=a+b；所以(c,d)R(a,b)，即R是对称。3）/*证实R是传递；*/假如(a,b)R(c,d)，(c,d)R(e,f)，则a+b=c+d，c+d=e+f；所以a+b=e+f，得(a,b)R(e,f)，即R是传递。35/126（2）假如(a,b)R(c,d)，则a+b=c+d，所以依据和数来划分。36/1264设R,S是A上等价关系，证实：R

S是A上等价关系

R

S=S

R。37/126证实思想：1）R

S是A上等价关系

R

S=S

R；证实(i)R

S

S

R；(ii)S

R

R

S；2）R

S=S

R

R

S是A上等价关系；证实R

S是(i)自反；(ii)对称；(iii)传递；38/126证实：1）R

S是A上等价关系

R

S=S

R：假如(a,b)

R

S,因为R

S是对称，所以(b,a)

R

S,所以存在cA,使得(b,c)

R,(c,a)

S；因为R和S是对称，所以(c,b)

R,(a,c)

S；则(a,b)

S

R；同理，S

R

R

S；39/1262）R

S=S

R

R

S是A上等价关系：/*证实R

S是自反、对称比较轻易*/40/126传递性证实：对任意a,b,cA，假如(a,b)

R

S,(b,c)

R

S，因为R

S=S

R，则有(b,c)

S

R，即存在e,fA，使(a,e)

R，(e,b)

S，(b,f)

S，(f,c)

R。因为S是传递，(e,b)

S，(b,f)

S，所以(e,f)

S；因为(a,e)

R，所以(a,f)

R

S；R

S是对称，则(f,a)

R

S；因为R是对称，(f,c)

R，则(c,f)

R。因为(f,a)

R

S，则存在gA，使得(f,g)

R，(g,a)

S；因为R是传递，由(c,f)

R，(f,g)

R，则(c,g)

R；因为(c,g)

R，(g,a)

S，所以(c,a)

R

S。因为已经证实，R

S是对称，所以(a,c)

R

S。41/126函数12设f:XY是函数，A,B是X子集，证实：（1）f(AB)f(A)f(B)（2）f(AB)=f(A)f(B)（3）f(A)-f(B)f(A-B)42/126/*基本法证实*/证实：（1）对任意yf(AB)，存在x，xAB，使得y=f(x)。因为xA，所以yf(A)；因为xB，所以yf(B)。所以yf(A)f(B)。则f(AB)f(A)f(B)。43/12613设R是A上一个二元关系，S={(a,b)|a,b

A而且对于某个c

A，有(a,c)

R且(c,b)

R}。证实：若R是A上等价关系，则S是A上等价关系。/*证实是S自反、对称和传递*/44/126四、概念综合练习一、选择题（北京理工大学考研）1以下集合运算中（）对满足分配律。A)B)C)¯D)

45/1262A、B是集合，P(A)、P(B)为其幂集，且AB=，则P(A)P(B)=（）A)

B){}C){{}}D){,{}}46/1263A、B是集合，以下各式除（）之外，均与A

B等价。A)A

B

BB)AB=BC)AB=AD)ABB247/1264R是集合A上自反关系，则（）A)RоRB)R

RоRC)R

R-1=IAD)Rо

R-1=IA48/1265集合A中有n个元素，则A上共有（）个既对称又反对称关系。A)0B)2nC)n2D)2n49/1266R是可传递二元关系，则在RR-1,RR-1,R-R-1,R-1-R中，有（）个一定是可传递。A)1B)2C)3D)450/1267函数f:R

R，其中R为实数集合，以下四个命题中（）为真。A)f(x)=5是内射B)f(x)=5是满射C)f(x)=5是双射D)A),B),C)都不真51/1268集合A到B共有64个不一样函数，则B中元素不可能是（）个。A)4B)8C)16D)6452/126二、选择题（北京理工大学1999）1已知A

B={1,2,3}，AC={2,3,4}，若2B，则

。A)1CB)2CC)3CD)4C53/1262对任何二元关系R，在RR-1,RR-1,RR-1,RR-1中有

个一定是对称关系。A)1B)2C)3D)454/1263R={(1,4),(2,3),(3,1),(4,3)},则

t(R)。A)(1,1)B)(1,2)C)(1,3)D)(1,4)55/126集合论——考研习题考研习题一、集合基础二、二元关系三、函数56/126一、集合基础1.1集合运算——容斥原理1.2集合运算——证实1.3幂集1.4相类似练习题目57/1261.1集合运算——容斥原理中国科学院自动化所1997120个学生参加考试，考试有A、B和C3道题，考试结果以下：12个学生3道题都做对了，20个学生做对A和B，16个学生做对A和C，28个学生做对B和C，做对A有48个学生，做对B有56个学生，有16个学生一道也没有做对。试求做对了C学生有多少个？直接使用容斥原理58/126解：设做对A题学生集合为PA，做对B题学生集合为PB，做对C题学生集合为PC。/*依据容斥原理，列出计算式*/|PAPBPC|=12,|PAPB|=20,|PAPC|=16,|PBPC|=28,|PA|=48,|PB|=56,

59/126/*依据容斥原理，进行计算*/|PAPBPC|=120-16,|PAPBPC|=|PA|+|PB|+|PC|-|PAPB|-|PAPC|-|PBPC|+|PAPBPC|,所以|PC|=20+16+28+104-12-48-56=52，做对C题学生为52人。60/126容斥原了解题总结使用容斥原理时，首先搞清论域，划定全集；其次对全集进行分类，列出计算式；最终依据容斥原理公式进行计算。61/126北京师范大学证实容斥原理：设A1,A2,……,An都是有限集，则|A1A2……An|=其中：{i1,i2,…in}是遍历{1,2,…,n}全部k元子集。/*证实思想：数学归纳法*/62/126证实：1）归纳基础：当k=2时，集合A1和A2公共元素个数为|A1A2|，这些元素中每一个在|A1|+|A2|里计算了两次，但在|A1A2|中是作为一个元素计算。所以有|A1A2|=|A1|+|A2|-|A1A2|。所以，当n=2时，命题成立。63/1262）归纳步骤：64/126当k=n时，|A1A2……An|=|(A1A2……An-1)An|=|(A1A2……An-1)|+|An|-|(A1A2……An-1)An|因为|(A1A2……An-1)An|=|(A1An)(A2An)……(An-1An)|/*n-1个集合并，依据归纳假设展开*/65/126北京师范大学设S为任一集合，证实在S与其幂集P(S)之间不存在1-1对应。66/1261.2集合运算——证实基本法、公式法67/126中国科学院软件所19981对于任意集合A和B，证实:(1)P(A)P(B)P(AB),

(2)P(A)P(B)=P(AB)；并举例说明P(A)P(B)P(AB)。/*幂集定义：P(A)={x|xA}*/68/126（1）/*基本法*/对任意x

P(A)P(B)，有x

P(A)或xP(B)。若x

P(A)，则x

A，所以x

AB，即x

P(AB)；同理，若xP(B)，则xB，所以x

AB，即x

P(AB)。总而言之，P(A)P(B)P(AB)。69/126（2）/*基本法*/对任意xP(A)P(B)，有x

P(A)且xP(B)。即x

A而且xB，则x

AB。所以xP(AB)。故P(A)P(B)P(AB)。对任意xP(AB)，有x

AB，即x

A而且xB，所以x

P(A)且xP(B)。所以P(AB)P(A)P(B)。总而言之，P(A)P(B)=P(AB)。70/126举例说明P(A)P(B)P(AB)。A={1},B={2},AB={1,2};P(A)={,{1}},P(B)={,{2}},P(A)P(B)={,{1},{2}},P(AB)={,{1},{2},{1,2}};所以P(A)P(B)P(AB)。71/126中国科学院计算所19982证实：若(A-B)(B-A)=C，则A(B-C)(C-B)充分必要条件是ABC=。证实思想：（1）充分性，即证实：若ABC=，则A(B-C)(C-B)；基本法证实；（2）必要性，即证实：若A(B-C)(C-B)，则ABC=；反证法证实。72/126证实：（1）对于任意aA，因为ABC=，所以aBC，则a有3种情况：I)aB，但aC，则aC-B，所以a(B-C)(C-B)；II)aB，但aC，则aB-C，所以a(B-C)(C-B)；III)aB且aC，因为aA，所以aA-B，所以a

(A-B)(B-A)，即aC，造成矛盾，所以aB且aC不可能出现。总而言之，对于任意aA，a

(A-B)(B-A)，所以A(B-C)(C-B)。73/126证实：（2）假设ABC，则存在a，a

ABC，即a

A，aB，且aC。所以aB-C，aC-B。则a(B-C)(C-B)。因为A(B-C)(C-B)，a

A，所以造成矛盾。所以ABC=。74/126北京大学19983给出集合表示式(A-C)B=AB成立充要条件.75/126

76/126北京大学1994判断题，为真给出证实，为假给出反例：1）{}{x}-{{x}}2）若AB=AC，则B=C。3）R是A上关系，则R=R2充要条件是R=IA。77/1261.3幂集幂集运算：代数法78/126北京大学19971设A为集合，B=P(A)-{

}-{A}，且B

。求偏序集(B,

)极大元，极小元，最小元。79/126因为B

，所以|A|>1。对任意xA,A-{x}是极大元，{x}是极小元，无最小元。80/126北京大学19992设A={

,{

}}，计算P(A)-{

},

P(A)

A。81/126/*代数法求P(A)*/设x=

,y={

}，A={x,y},P(A)={

,{x},{y},{x,y}};P(A)={

,{

},{{

}},{

,{

}}};P(A)-{

}={

,{{

}},{

,{

}}};P(A)

A={{{

}},{

,{

}}};82/126上海大学19983设A是集合，A元素也是集合，P(A)是A幂集。定义A={x|yA,xy}（1）计算{{a,b,c},{a,d,e},{a,f}}；（2）证实P(A)=A；（3）请问P(A)=A？解题要素：A（广义并）和幂集定义；基本法83/126（1）计算{{a,b,c},{a,d,e},{a,f}}解：

{{a,b,c},{a,d,e},{a,f}}={a,b,c}{a,d,e}{a,f}={a,b,c,d,e,f}84/126（2）证实P(A)=A证实：对任意xP(A)，则存在yP(A)，xy；因为yP(A)，所以yA；所以xy，则有P(A)A；对任意xA，设y={x}，则yA。所以yP(A)。所以xP(A)。所以P(A)=A。85/126（3）请问P(A)=A？不成立。反例：（1）

A={{a,b,c},{a,d,e},{a,f}}A={a,b,c,d,e,f}P(A)A86/126上海交通大学19984C是非空集合族，证实：P(C)={P(X)|XC}证实方法：基本法，集合族概念87/126证实：任取x

P(C)，则xC，所以对于任意ax，有aC；对于任意XC，有aX；那么xX，即x

P(X)。由X任意性，也即x{P(X)|XC}。所以P(C){P(X)|XC}。任取x{P(X)|XC}，则对于任意XC，有xP(X)，即xX。因为XC，对于任意ax，有aX；所以aC。所以xC，即x

P(C)。所以{P(X)|XC}P(C)。所以P(C)={P(X)|XC}。88/126中科院成都计算所5设A是一有限集，A基数为|A|。证实：A幂集P(A)基数|P(A)|=2|A|。89/1261.4相类似题目1A,B是两个集合，给出AB=B充分必要条件是什么，并证实你结论。/*南京理工大学*/90/1262判断以下各式是否成立，假如成立，则证实之，不然举出反例。（1）P(A)P(B)=P(AB),

（2）(AB)C=(AC)(BC)上海交通大学91/1263证实P(A)P(B)P(AB)，并说明等号成立条件。上海交通大学199992/1264设A,B,C,D为4个非空集合，则ABCD充分必要条件是

。/*重庆大学1998*/93/126二、二元关系关系及其性质与运算等价关系与划分序关系94/126关系及其性质与运算95/126北京大学19971设R={(x,y)|x,yN而且x+3y=12}，求R2。解题思绪：将R全部元素列出，求R与它本身复合所得关系96/126解：R={(0,4),(3,3),(6,2),(9,1),(12,0)}R2={(3,3),(12,4)}97/126北京大学19902设R是复数C上二元关系，且满足xRyx-y=a+bi，a和b为非负整数，试确定R性质（自反、反自反、对称、反对称和传递），并证实之。98/126北京大学19943判断题，为真给出证实，为假给出反例：R是A上二元关系，则R=R2

R=IA。99/126武汉大学19994设A={a,b,c}，给出A上一个二元关系R，使其同时不满足自反、反自反、对称、反对称和传递性。100/126武汉大学19985设A={1,2,3}，R是P(A)上二元关系，且R={(a,b)|ab}。则R不满足以下哪些性质？为何？1)自反2)反自反3)对称4)反对称5)传递性101/126等价关系与划分102/126中科院成都计算所1设R是集合A上一个传递和自反关系，T是A上一个关系，使得(a,b)属于T当且仅当(a,b)和(b,a)都属于R。证实：T是一个等价关系。103/126西南交通大学19972设X和Y都是正整数集，xiX,yiY,i=1,2.[1]以下关系是否是等价关系？证实你结论。1)R={((x1,x2),(y1,y2))|x1+y2=x2+y1}2)R={((x1,x2),(y1,y2))|x1+y1=x2+y2}[2]若R是等价关系，定义集合M,M={(0,2),(1,2),(2,4),(3,4),(4,6),(5,6),……}。试给出它等价类。104/126西南交通大学19983设S={1,2,3}，定义SS上关系R为：对任意(a,b),(c,d)SS，有((a,b),(c,d))a+d=b+c，证实：R为SS上等价关系并给出SS/R。105/126上海交通大学4设P是X上等价关系，Q是Y上等价关系，关系R满足((x1,y1),(x2,y2))R当且仅当(x1,