集合论习题解析

集合论习题解析——经典习题与考研习题•经典习题一、集合基础二、二元关系三、函数四、概念综合练习•考研习题北京大学、中科院计算所、中科院软件所、中科院自动化所、北京师范大学、中科院成都计算所、上海交通大学、西安交通大学、西南交通大学、北京航空航天大学、复旦大学等一、集合基础•1.1与•1.2集合运算•1.3幂集1.1与•1设A,B,C是任意3个集合，如果AB,BC,则AC可能吗？AC常真吗？举例说明。•AC可能A={1},B={{1}},C={{1},{{1}}}•AC不常真A={1},B={{1}},C={{{1}}}•2设A,B是任意2个集合，AB与AB同时成立，这可能吗？•可能•A={1},B={{1},1}.•3设A,B,C是集合，判断下列命题真假，如果为真，给出证明；如果为假，给出反例：•1)AB,BCAC;•2)AB,BCAC;•3)AB,BCAC;•4)AB,BCAC;•5)aA,ABaB.•1）假A={1},B={2},C={{2}}•2）假A={1},B={2},C={{1}}•3）假A={1},B={{1}},C={{1},1}•4）假A={1},B={{1},1}，C={{1},2}•5）真子集定义•4设A,B,C是U的子集，判断下列命题真假，如果为真，给出证明；如果为假，给出反例：•1)ABAB=B;•2)ABAB=A;•3)ABAB=A;•4)ABAB=B;•5)ABA(B-A)=B;•6)BA(A-B)B=A;•1）假，A=B时不成立•/*与不同*/•分析：•I)ABAB=B：因为BAB；对于任意xAB，如果xA,因为AB,所以xB,则对任意的xAB，xB成立。所以AB=B。•II)A=BAB=B，但AB不成立。•2）假，A={1}，B={1，2}，不成立；•3）假，A=B时不成立；•4）假，A={1}，B={1，2}，不成立；•5）假，A=B时不成立•6）假，A={1，2}，B={1}，不成立；1.2集合运算•5设A,B,C是任意3个集合，•（1）AB=AC，则B=C吗？•（2）AB=AC，则B=C吗？•（3）AB=AC且AB=AC，则B=C吗？•（1）假A={1,2},B={1},C={2}•（2）假A={1},B={1,2},C={1,3}•（3）真/*基本法、反证法证明*/设xB，假设xC。因为xB，所以xAB；因为AB=AC，所以xAC；因为xC，所以xA；又因为xB，所以xAB；因为AB=AC，所以xAC；则xC，这与xC矛盾。所以B=C。•6设A,B是任意2个集合，•（1）若A-B=B，则A与B有何关系？•（2）若A-B=B-A，则A与B有何关系？•（3）若AB=AB，则A与B有何关系？•（4）若AB=A，则A与B有何关系？•/*用文氏图辅助*/•证明：(1)由A-B=B，可得出A=B=。•(2)由A-B=B-A，可导出A=B。•(3)A=B•(4)B=•7给出下列命题成立的充分必要条件•（1）(A-B)(A-C)=A•（2）(A-B)(A-C)=•（3）(A-B)(A-C)=•（4）(A-B)(A-C)=•/*等式推导*/•解：(1)•1)：设(A-B)(A-C)=A，对任意的x，xA，则xA-B或xA-C；则有.xABxACxBxCxBCxBCABC或或所以，•2）：设ABC=，对任意的x，xA，则xB或xC，则有()()()().xABxACxABxACxABACAABAC或或所以，对任意的x，x(A-B)(A-C)，则xA-B或xA-C，则有.()().()().xABxACxAABACAABACAABC或所以，从而，•（2）•(A-B)(A-C)=(A-B)=或(A-C)=AB并且ACABC所以，充要条件为ABC。•（3）1)设(A-B)(A-C)=，对任意的x，xA，x(A-B)并且x(A-C)；所以xB-A或xC-A；则有xB或xC；得xBC。所以ABC。2)ABCAB或AC；所以A-B=或A-C=。得(A-B)(A-C)=。从而，(A-B)(A-C)=ABC。•（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)1.3幂集•7设A,B是任意2个集合，证明：•（1）ABP(A)P(B)•（2）P(A)P(B)AB•（3）P(A)=P(B)A=B•/*利用基本法证明集合的包含关系*/•证明：•(1)对任意的xP(A),有xA,又因为AB，所以xB,即xP(B)；所以P(A)P(B)。•(2)/*证明方法同(1)；*/对任意的xA,则{x}P(A)，又因为P(A)P(B)，所以{x}P(B)，即xB；所以AB。•(3)由(1)和(2)的证明导出。二、二元关系•1设R是集合A上的关系•（1）R是自反的，则RR是自反的；•（2）R是对称的，则RR是对称的；•（3）R是反自反和传递的，则R是反对称的；•/*证明思想：根据定义给出的性质证明*/•证明：•（1）证明思想与（2）和（3）相同•（2）设(a,b)RR,则存在c,(a,c)R,(c,b)R;因为R是对称的，所以(b,c)R,(c,a)R;所以(b,a)RR。则RR是对称的。•（3）假设(a,b)R,(b,a)R。因为R是传递的，所以(a,a)R，(b,b)R；因为R是反自反的，所以导致矛盾。•2设R是A上的关系，若R是自反的和传递的，则RR=R。其逆命题也成立吗？证明思想：证明RR=R，1）证明RRR；2）证明RRR：•证明：•1）证明RRR：设(a,b)RR，存在cA,使得(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。•自反不成立•传递成立特殊关系•3设S={1,2,3,4}，并设A=SS，在A上定义关系R为：（a,b）R（c,d）当且仅当a+b=c+d。•（1）证明R是等价关系；•（2）计算出A/R。•（1）证明：/*根据等价关系的定义证明*/•1）/*证明R是自反的；*/•对于任意的(a,b)SS，因为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是传递的。•（2）如果(a,b)R(c,d)，则a+b=c+d，所以根据和的数来划分。•4设R,S是A上的等价关系，证明：RS是A上的等价关系RS=SR。•证明思想：•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)传递的；•证明：•1）RS是A上的等价关系RS=SR：如果(a,b)RS,因为RS是对称的，所以(b,a)RS,所以存在cA,使得(b,c)R,(c,a)S；因为R和S是对称的，所以(c,b)R,(a,c)S；则(a,b)SR；同理，SRRS；•2）RS=SRRS是A上的等价关系：•/*证明RS是自反的、对称的比较容易*/•传递性证明：•对任意a,b,cA，如果(a,b)RS,(b,c)RS，因为RS=SR，则有(b,c)SR，即存在e,fA，使(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，则存在gA，使得(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。函数•12设f:XY是函数，A,B是X的子集，证明：•（1）f(AB)f(A)f(B)•（2）f(AB)=f(A)f(B)•（3）f(A)-f(B)f(A-B)•/*基本法证明*/•证明：（1）对任意的yf(AB)，存在x，xAB，使得y=f(x)。因为xA，所以yf(A)；因为xB，所以yf(B)。所以yf(A)f(B)。则f(AB)f(A)f(B)。•13设R是A上的一个二元关系，S={(a,b)|a,bA并且对于某个cA，有(a,c)R且(c,b)R}。证明：若R是A上的等价关系，则S是A上的等价关系。•/*证明是S自反、对称和传递*/四、概念综合练习•一、选择题（北京理工大学2000考研）•1下列集合运算中（）对满足分配律。•A)•B)•C)¯•D)•2A、B是集合，P(A)、P(B)为其幂集，且AB=，则P(A)P(B)=（）•A)•B){}•C){{}}•D){,{}}•3A、B是集合，以下各式除（）之外，均与AB等价。•A)ABB•B)AB=B•C)AB=A•D)ABB2•4R是集合A上的自反关系，则（）•A)RоR•B)RRоR•C)RR-1=IA•D)RоR-1=IA•5集合A中有n个元素，则A上共有（）个既对称又反对称的关系。•A)0•B)2n•C)n2•D)2n•6R是可传递的二元关系，则在RR-1,RR-1,R-R-1,R-1-R中，有（）个一定是可传递的。•A)1•B)2•C)3•D)4•7函数f:RR，其中R为实数集合，下列四个命题中（）为真。•A)f(x)=5是内射的•B)f(x)=5是满射的•C)f(x)=5是双射的•D)A),B),C)都不真•8集合A到B共有64个不同的函数，则B中元素不可能是（）个。•A)4•B)8•C)16•D)64•二、选择题（北京理工大学1999）•1已知AB={1,2,3}，AC={2,3,4}，若2B，则。•A)1C•B)2C•C)3C•D)4C•2对任何二元关系R，在RR-1,RR-1,RR-1,RR-1中有个一定是对称关系。•A)1•B)2•C)3•D)4•3R={(1,4),(2,3),(3,1),(4,3)},则t(R)。•A)(1,1)•B)(1,2)•C)(1,3)•D)(1,4)集合论——考研习题•考研习题一、集合基础二、二元关系三、函数一、集合基础•1.1集合运算——容斥原理•1.2集合运算——证明•1.3幂集•1.4相类似的练习题目1.1集合运算——容斥原理•中国科学院自动化所1997•120个学生参加考试，考试有A、B和C3道题，考试结果如下：12个学生3道题都做对了，20个学生做对A和B，16个学生做对A和C，28个学生做对B和C，做对A的有48个学生，做对B的有56个学生，有16个学生一道也没有做对。试求做对了C的学生有多少个？•直接使用容斥原理•解：设做对A题的学生集