集合论习题解析精选文档.ppt

《集合论习题解析精选文档.ppt》由会员分享，可在线阅读，更多相关《集合论习题解析精选文档.ppt（126页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、集合论习题解析集合论习题解析本讲稿第一页，共一百二十六页一、集合基础一、集合基础1.1 与1.2 集合运算1.3 幂集本讲稿第二页，共一百二十六页1.1 与与 1 设A,B,C是任意3个集合，如果AB,B C,则AC可能吗？AC常真吗？举例说明。本讲稿第三页，共一百二十六页AC可能A=1,B=1,C=1,1AC不常真A=1,B=1,C=1本讲稿第四页，共一百二十六页2 设A,B是任意2个集合，A B与 AB同时成立，这可能吗？本讲稿第五页，共一百二十六页可能A=1,B=1,1.本讲稿第六页，共一百二十六页3 设A,B,C是集合，判断下列命题真假，如果为真，给出证明；如果为假，给出反例：1)AB

2、,BC AC;2)AB,BC AC;3)AB,BC AC;4)AB,BC AC;5)aA,AB aB.本讲稿第七页，共一百二十六页1）假A=1,B=2,C=2 2）假A=1,B=2,C=13）假A=1,B=1,C=1,1本讲稿第八页，共一百二十六页4）假A=1,B=1,1，C=1,25）真子集定义本讲稿第九页，共一百二十六页 4 4 设设A,B,CA,B,C是是U U的子集，判断下列命题真假，如果为真，的子集，判断下列命题真假，如果为真，给出证明；如果为假，给出反例：给出证明；如果为假，给出反例：1)1)AA B BA AB=BB=B;2)2)AA B BA AB=AB=A;3)3)A A B

3、 BA AB=AB=A;4)4)AA B BAAB=B;B=B;5)5)A A B BA A(B-A)=B(B-A)=B;6)6)B B A A(A-B)(A-B)B=AB=A;本讲稿第十页，共一百二十六页1）假，A=B时不成立/*与与不同不同*/分析：I)ABAB=B：因为BAB；对于任意xAB，如果xA,因为AB,所以xB,则对任意的xAB，xB成立。所以AB=B。II)A=B AB=B，但AB不成立。本讲稿第十一页，共一百二十六页2）假，A=1，B=1，2，不成立；3）假，A=B时不成立；4）假，A=1，B=1，2，不成立；5）假，A=B时不成立6）假，A=1，2，B=1，不成立；本讲稿

4、第十二页，共一百二十六页1.2 集合运算集合运算5 设A,B,C是任意3个集合，（1）AB=AC，则B=C吗？（2）AB=AC，则B=C吗？（3）AB=AC且AB=AC，则B=C吗？本讲稿第十三页，共一百二十六页（1 1）假）假A=1,2,B=1,C=2A=1,2,B=1,C=2（2 2）假）假A=1,B=1,2,C=1,3A=1,B=1,2,C=1,3（3 3）真）真/*/*基本法、反证法证明基本法、反证法证明基本法、反证法证明基本法、反证法证明*/*/设设x x B B，假设，假设x x C C。因为。因为x x B B，所以，所以x x A AB B；因为；因为A AB=AB=AC C，

5、所以，所以x x A AC C；因为；因为x x C C，所以，所以x x A A；又因为又因为x x B B，所以，所以x x A AB B；因为；因为AAB=AB=AC C ，所以，所以x x AAC C；则；则x x C C，这与，这与x x C C矛盾。所以矛盾。所以B=CB=C。本讲稿第十四页，共一百二十六页6 设A,B是任意2个集合，（1）若A-B=B，则A与B有何关系？（2）若A-B=B-A，则A与B有何关系？（3）若AB=AB，则A与B有何关系？（4）若AB=A，则A与B有何关系？/*用文氏图辅助*/本讲稿第十五页，共一百二十六页证明：(1)由A-B=B，可得出A=B=。本讲稿

6、第十六页，共一百二十六页(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，xA，则xA-B 或 xA-C；则有本讲稿第二十一页，共一百二十六页2）：设ABC=，对任意的x，xA，则xB或xC，则有本讲稿第二十二页，共一百二十六页 对任意的x，x(A-

7、B)(A-C)，则xA-B或 xA-C，则有本讲稿第二十三页，共一百二十六页（2）(A-B)(A-C)=(A-B)=或(A-C)=AB并且ACABC所以，充要条件为ABC。本讲稿第二十四页，共一百二十六页（3）1)设(A-B)(A-C)=，对任意的x，xA，x(A-B)并且x(A-C)；所以xB-A或xC-A；则有xB或xC；得xBC。所以ABC。2)ABC AB或AC；所以A-B=或A-C=。得(A-B)(A-C)=。从而，(A-B)(A-C)=ABC。本讲稿第二十五页，共一百二十六页（4）(A-B)(A-C)=(A-B)-(A-C)(A-C)-(A-B)=(A-B)(A-C)并且(A-C)

8、(A-B)(A-B)=(A-C)本讲稿第二十六页，共一百二十六页1.3 幂集幂集7 设A,B是任意2个集合，证明：（1）ABP(A)P(B)（2）P(A)P(B)A B（3）P(A)=P(B)A=B本讲稿第二十七页，共一百二十六页/*利用基本法证明集合的包含关系*/证明：(1)对任意的xP(A),有xA,又因为AB，所以xB,即xP(B)；所以P(A)P(B)。(2)/*证明方法同(1)；*/对任意的xA,则xP(A)，又因为P(A)P(B)，所以x P(B)，即xB；所以A B。(3)由(1)和(2)的证明导出。本讲稿第二十八页，共一百二十六页二、二元关系二、二元关系1 设R是集合A上的关系

9、（1）R是自反的，则RR是自反的；（2）R是对称的，则RR是对称的；（3）R是反自反和传递的，则R是反对称的；本讲稿第二十九页，共一百二十六页/*证明思想：根据定义给出的性质证明*/证明：（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是反自反的，所以导致矛盾。本讲稿第三十页，共一百二十六页2 设R是A上的关系，若R是自反的和传递的，则RR=R。其逆命题也成立吗？证明思想：

10、证明RR=R，1）证明RRR；2）证明RRR：本讲稿第三十一页，共一百二十六页 证明：证明：1 1）证明）证明R R R R R R：设设(a,b)(a,b)R R R R，存在，存在c c A,A,使得使得(a,c)(a,c)R,(c,b)R,(c,b)R R，因，因为为R R是传递的，所以是传递的，所以(a,b)(a,b)R R；则；则R R R R R R；2 2）证明证明R R R R R R：设设(a,b)(a,b)R R，R R是自反的，是自反的，(b,b)(b,b)R R，所以，所以(a,(a,b)b)R R R R；则；则R R R R R R。所以所以R R R=RR=R。本

11、讲稿第三十二页，共一百二十六页自反不成立传递成立本讲稿第三十三页，共一百二十六页特殊关系特殊关系3 设S=1,2,3,4，并设A=SS，在A上定义关系R为：（a,b）R（c,d）当且仅当a+b=c+d。（1）证明R是等价关系；（2）计算出A/R。本讲稿第三十四页，共一百二十六页（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(

12、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上的等价关系，证明：RS是A上的等价关系RS=SR。本讲稿第三十七页，共一百二十六页证明思想：1）RS是A上的等价关系RS=SR；证明(i)RSSR；(ii)SR RS；2）RS=SR RS是A上的等价关系；证明RS是(i)自反的；(

13、ii)对称的；(iii)传递的；本讲稿第三十八页，共一百二十六页证明：1）RS是A上的等价关系RS=SR：如果(a,b)RS,因为RS是对称的，所以(b,a)RS,所以存在cA,使得(b,c)R,(c,a)S；因为R和S是对称的，所以(c,b)R,(a,c)S；则(a,b)SR；同理，SR RS；本讲稿第三十九页，共一百二十六页2）RS=SR RS是A上的等价关系：/*证明RS是自反的、对称的比较容易*/本讲稿第四十页，共一百二十六页 传递性证明：传递性证明：对任意对任意a,b,ca,b,c A A，如果，如果(a,b)(a,b)R R S,(b,c)S,(b,c)R R S S，因为，因为R

14、 R S=SS=S R R，则有，则有(b,c)(b,c)S S R R，即存在，即存在e,fe,f A A，使，使(a,e)(a,e)R R，(e,b)(e,b)S S，(b,f)(b,f)S S，(f,c)(f,c)R R。因为因为S S是传递的，是传递的，(e,b)(e,b)S S，(b,f)(b,f)S S，所以，所以(e,f)(e,f)S S；因；因为为(a,e)(a,e)R R，所以，所以(a,f)(a,f)R R S S；R R S S是对称的，则是对称的，则(f,(f,a)a)R R S S；因为；因为R R是对称的，是对称的，(f,c)(f,c)R R，则，则(c,f)(c,

15、f)R R。因为因为(f,a)(f,a)R R S S，则存在，则存在g g A A，使得，使得(f,g)(f,g)R R，(g,(g,a)a)S S；因为；因为R R是传递的，由是传递的，由(c,f)(c,f)R R，(f,g)(f,g)R R，则，则(c,(c,g)g)R R；因为；因为(c,g)(c,g)R R，(g,a)(g,a)S S，所以，所以(c,a)(c,a)R R S S。因为已。因为已经证明，经证明，R R S S是对称的，所以是对称的，所以(a,c)(a,c)R R S S。本讲稿第四十一页，共一百二十六页函数函数12 设f:XY是函数，A,B是X的子集，证明：（1）f(

16、AB)f(A)f(B)（2）f(AB)=f(A)f(B)（3）f(A)-f(B)f(A-B)本讲稿第四十二页，共一百二十六页/*基本法证明*/证明：（1）对任意的yf(AB)，存在x，x AB，使得y=f(x)。因为xA，所以yf(A)；因为x B，所以yf(B)。所以yf(A)f(B)。则f(AB)f(A)f(B)。本讲稿第四十三页，共一百二十六页13 设R是A上的一个二元关系，S=(a,b)|a,bA并且对于某个cA，有(a,c)R且(c,b)R。证明：若R是A上的等价关系，则S是A上的等价关系。/*证明是S自反、对称和传递*/本讲稿第四十四页，共一百二十六页四、概念综合练习四、概念综合练

17、习一、选择题（北京理工大学2000考研）1 下列集合运算中（）对满足分配律。A)B)C)D)本讲稿第四十五页，共一百二十六页2 A、B是集合，P(A)、P(B)为其幂集，且AB=，则P(A)P(B)=（）A)B)C)D),本讲稿第四十六页，共一百二十六页3 A、B是集合，以下各式除（）之外，均与AB等价。A)ABBB)AB=BC)AB=AD)ABB2本讲稿第四十七页，共一百二十六页4 R是集合A上的自反关系，则（）A)R RB)RR RC)RR-1=IAD)R R-1=IA本讲稿第四十八页，共一百二十六页5 集合A中有n个元素，则A上共有（）个既对称又反对称的关系。A)0B)2nC)n2D)2

18、n本讲稿第四十九页，共一百二十六页6 R是可传递的二元关系，则在RR-1,RR-1,R-R-1,R-1-R中，有（）个一定是可传递的。A)1B)2C)3D)4本讲稿第五十页，共一百二十六页7 函数f:RR，其中R为实数集合，下列四个命题中（）为真。A)f(x)=5是内射的B)f(x)=5是满射的C)f(x)=5是双射的D)A),B),C)都不真本讲稿第五十一页，共一百二十六页8 集合A到B共有64个不同的函数，则B中元素不可能是（）个。A)4B)8C)16D)64本讲稿第五十二页，共一百二十六页二、选择题（北京理工大学1999）1 已知AB=1,2,3，AC=2,3,4，若2B，则 。A)1C

19、B)2CC)3CD)4C本讲稿第五十三页，共一百二十六页2 对任何二元关系R，在RR-1,RR-1,RR-1,RR-1中有 个一定是对称关系。A)1B)2C)3D)4本讲稿第五十四页，共一百二十六页3 R=(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

20、集合运算集合运算容斥原理容斥原理中国科学院自动化所中国科学院自动化所1997120个学生参加考试，考试有A、B和C3道题，考试结果如下：12个学生3道题都做对了，20个学生做对A和B，16个学生做对A和C，28个学生做对B和C，做对A的有48个学生，做对B 的有56个学生，有16个学生一道也没有做对。试求做对了C的学生有多少个？直接使用容斥原理本讲稿第五十八页，共一百二十六页解：设做对A题的学生集合为PA，做对B题的学生集合为PB，做对C题的学生集合为PC。/*根据容斥原理，列出计算式*/|PAPBPC|=12,|PAPB|=20,|PAPC|=16,|PBPC|=28,|PA|=48,|PB

21、|=56,本讲稿第五十九页，共一百二十六页/*根据容斥原理，进行计算*/|PAPBPC|=120-16,|PAPBPC|=|PA|+|PB|+|PC|-|PAPB|-|PAPC|-|PBPC|+|PAPBPC|,所以|PC|=20+16+28+104-12-48-56=52，做对C题的学生为52人。本讲稿第六十页，共一百二十六页容斥原理解题总结容斥原理解题总结使用容斥原理时，首先搞清论域，划定全集；其次对全集进行分类，列出计算式；最后根据容斥原理的公式进行计算。本讲稿第六十一页，共一百二十六页北京师范大学北京师范大学2001证明容斥原理：设A1,A2,An都是有限集，则|A1A2An|=其中：

22、i1,i2,in是遍历1,2,n的所有k元子集。/*证明思想：数学归纳法*/本讲稿第六十二页，共一百二十六页证明：1）归纳基础归纳基础：当k=2时，集合A1和A2的公共元素个数为|A1A2|，这些元素中的每一个在|A1|+|A2|里计算了两次，但在|A1A2|中是作为一个元素计算的。因此有|A1A2|=|A1|+|A2|-|A1A2|。所以，当n=2时，命题成立。本讲稿第六十三页，共一百二十六页2 2）归纳步骤：）归纳步骤：本讲稿第六十四页，共一百二十六页 当k=n时，|A1A2An|=|(A1A2An-1)An|=|(A1A2An-1)|+|An|-|(A1A2An-1)An|因为|(A1A

23、2An-1)An|=|(A1An)(A2 An)(An-1An)|/*n-1个集合的并，根据归纳假设展开*/本讲稿第六十五页，共一百二十六页北京师范大学北京师范大学2000设S为任一集合，证明在S与其幂集P(S)之间不存在1-1对应。本讲稿第六十六页，共一百二十六页1.2 集合运算集合运算证明证明基本法、公式法本讲稿第六十七页，共一百二十六页中国科学院软件所中国科学院软件所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*/本讲稿第六十八页，共一百二十六页（1）/

24、*基本法*/对任意的xP(A)P(B)，有xP(A)或xP(B)。若xP(A)，则xA，所以xAB，即xP(AB)；同理，若xP(B)，则xB，所以xAB，即xP(AB)。综上所述，P(A)P(B)P(AB)。本讲稿第六十九页，共一百二十六页（2）/*基本法*/对任意的xP(A)P(B)，有xP(A)且xP(B)。即xA并且xB，则xAB。所以xP(AB)。故P(A)P(B)P(AB)。对任意的xP(AB)，有xAB，即xA并且xB，所以xP(A)且xP(B)。因此P(AB)P(A)P(B)。综上所述，P(A)P(B)=P(AB)。本讲稿第七十页，共一百二十六页举例说明P(A)P(B)P(AB

25、)。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)。本讲稿第七十一页，共一百二十六页中国科学院计算所中国科学院计算所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=；反证法证明。本讲稿第七十二页，共一百二十六页证明：（1）对于任意的aA，因为ABC=，所以aBC，则a有3种情况：I)aB，但aC，则aC-B

26、，所以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)。本讲稿第七十三页，共一百二十六页证明：（2）假设ABC，则存在a，a ABC，即aA，aB，且aC。所以a B-C，aC-B。则a(B-C)(C-B)。因为A(B-C)(C-B)，aA，所以导致矛盾。所以ABC=。本讲稿第七十四页，共一百二十六页北京大学北京大学19983 给出集合表达式(A-C)B=AB成立的充要

27、条件.本讲稿第七十五页，共一百二十六页 本讲稿第七十六页，共一百二十六页北京大学北京大学1994判断题，为真给出证明，为假给出反例：1）x-x2）若AB=AC，则B=C。3）R是A上的关系，则R=R2的充要条件是R=IA。本讲稿第七十七页，共一百二十六页1.3 幂集幂集幂集运算：代数法本讲稿第七十八页，共一百二十六页北京大学北京大学19971 设A为集合，B=P(A)-A，且B。求偏序集(B,)的极大元，极小元，最小元。本讲稿第七十九页，共一百二十六页因为B，所以|A|1。对任意xA,A-x是极大元，x是极小元，无最小元。本讲稿第八十页，共一百二十六页北京大学北京大学19992 设A=,，计算

28、P(A)-,P(A)A。本讲稿第八十一页，共一百二十六页/*代数法求P(A)*/设x=,y=，A=x,y,P(A)=,x,y,x,y;P(A)=,;P(A)-=,;P(A)A=,;本讲稿第八十二页，共一百二十六页上海大学上海大学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（广义并）和幂集的定义；基本法本讲稿第八十三页，共一百二十六页（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,

29、e,f本讲稿第八十四页，共一百二十六页（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。本讲稿第八十五页，共一百二十六页（3）请问P(A)=A？不成立。反例：（1）A=a,b,c,a,d,e,a,fA=a,b,c,d,e,fP(A)A本讲稿第八十六页，共一百二十六页上海交通大学上海交通大学1998 4 4 C C是非空集合族，证明：是非空集合族，证明：P(P(C)=C)=P(X)|XP(X)|X CC 证明方法：基本法，集合族的概念证明方法：基

30、本法，集合族的概念本讲稿第八十七页，共一百二十六页 证明：证明：任取任取x x P(P(C)C)，则，则x xC C，所以对于任意的，所以对于任意的a a x x，有，有a aC C；对于任意的；对于任意的X X C C，有，有a a X X；那么；那么x x X X，即，即x x P(XP(X)。由。由X X的任意性，也即的任意性，也即x xP(X)|XP(X)|X CC。所以。所以P(P(C)C)P(X)|XP(X)|X CC。任取任取x xP(X)|XP(X)|X CC，则，则对于任意的对于任意的X X C C，有，有x xP(X)P(X)，即，即x x X X。因为。因为X X C C

31、，对于任意的，对于任意的a a x x，有，有a a X X；因此；因此a aC C。所以。所以x xC C，即，即x x P(P(C)C)。所。所以以P(X)|XP(X)|X C C P(P(C)C)。所以所以P(P(C)=C)=P(X)|XP(X)|X CC。本讲稿第八十八页，共一百二十六页中科院成都计算所中科院成都计算所20005 设A是一有限集，A的基数为|A|。证明：A的幂集P(A)的基数|P(A)|=2|A|。本讲稿第八十九页，共一百二十六页1.4 相类似的题目相类似的题目1 A,B是两个集合，给出AB=B的充分必要条件是什么，并证明你的结论。/*南京理工大学2000*/本讲稿第九

32、十页，共一百二十六页2 判断下列各式是否成立，如果成立，则证明之，否则举出反例。（1）P(A)P(B)=P(AB),（2）(AB)C=(AC)(BC)上海交通大学2001本讲稿第九十一页，共一百二十六页3 证明P(A)P(B)P(AB)，并说明等号成立的条件。上海交通大学1999本讲稿第九十二页，共一百二十六页4 设A,B,C,D为4个非空集合，则AB CD的充分必要条件是 。/*重庆大学1998*/本讲稿第九十三页，共一百二十六页二、二元关系二、二元关系关系及其性质与运算等价关系与划分序关系本讲稿第九十四页，共一百二十六页关系及其性质与运算关系及其性质与运算本讲稿第九十五页，共一百二十六页北

33、京大学北京大学19971 设R=(x,y)|x,yN并且x+3y=12，求R2。解题思路：将R的所有元素列出，求R与它本身复合所得的关系本讲稿第九十六页，共一百二十六页解：R=(0,4),(3,3),(6,2),(9,1),(12,0)R2=(3,3),(12,4)本讲稿第九十七页，共一百二十六页北京大学北京大学19902 设R是复数C上的二元关系，且满足xRyx-y=a+bi，a和b为非负整数，试确定R的性质（自反、反自反、对称、反对称和传递），并证明之。本讲稿第九十八页，共一百二十六页北京大学北京大学19943 判断题，为真给出证明，为假给出反例：R是A上的二元关系，则R=R2R=IA。本

34、讲稿第九十九页，共一百二十六页武汉大学武汉大学19994 设A=a,b,c，给出A上的一个二元关系R，使其同时不满足自反、反自反、对称、反对称和传递性。本讲稿第一百页，共一百二十六页武汉大学武汉大学19985 设A=1,2,3，R是P(A)上的二元关系，且R=(a,b)|ab。则R不满足下列哪些性质？为什么？1)自反2)反自反3)对称4)反对称5)传递性本讲稿第一百零一页，共一百二十六页等价关系与划分等价关系与划分本讲稿第一百零二页，共一百二十六页中科院成都计算所中科院成都计算所20011 设R是集合A上的一个传递的和自反的关系，T是A上的一个关系，使得(a,b)属于T当且仅当(a,b)和(b

35、,a)都属于R。证明：T是一个等价关系。本讲稿第一百零三页，共一百二十六页西南交通大学西南交通大学1997 2 2 设设X X和和Y Y都是正整数集，都是正整数集，x xi i X,yX,yi i Y,i=1,2.Y,i=1,2.11下列关系是否是等价关系？证明你的结论。下列关系是否是等价关系？证明你的结论。1)R=(x1)R=(x1 1,x,x2 2),(y),(y1 1,y,y2 2)|x)|x1 1+y+y2 2=x=x2 2+y+y1 1 2)R=(x2)R=(x1 1,x,x2 2),(y),(y1 1,y,y2 2)|x)|x1 1+y+y1 1=x=x2 2+y+y2 2 22若

36、若R R是等价关系，定义集合是等价关系，定义集合M,M=(0,2),(1,2),(2,M,M=(0,2),(1,2),(2,4),(3,4),(4,6),(5,6),4),(3,4),(4,6),(5,6),。试给出它的等价类。试给出它的等价类。本讲稿第一百零四页，共一百二十六页西南交通大学西南交通大学19983 设S=1,2,3，定义SS上的关系R为：对任意(a,b),(c,d)SS，有(a,b),(c,d)a+d=b+c，证明：R为SS上的等价关系并给出SS/R。本讲稿第一百零五页，共一百二十六页上海交通大学上海交通大学20014 设P是X上的等价关系，Q是Y上的等价关系，关系R满足(x1

37、,y1),(x2,y2)R 当且仅当(x1,x2)P，(y1,y2)Q，证明：R是XY上的等价关系。本讲稿第一百零六页，共一百二十六页南京理工大学南京理工大学20005 R是集合A上等价的二元关系，证明R2也是A上的等价关系。本讲稿第一百零七页，共一百二十六页序关系序关系本讲稿第一百零八页，共一百二十六页西南交通大学西南交通大学19981 集合A上的二元关系R如果是传递和反自反的，则称R是A上的拟序关系，证明：（1）如果R是A上的拟序关系，则r(R)=RIA是偏序关系；（2）如果R是A上的偏序关系，则R-IA是拟序关系。本讲稿第一百零九页，共一百二十六页西南交通大学西南交通大学19992 设R

38、是集合A上的偏序关系，且BA，试证明R=R(BB)是B上的偏序关系。本讲稿第一百一十页，共一百二十六页复旦大学复旦大学19993 判断是否正确，并说明理由。设A是一个集合，R是A的幂集P(A)上的二元关系，对所有S、TP(A)，(S,T)P(A)。当且仅当|S|T|，R是偏序关系。本讲稿第一百一十一页，共一百二十六页华中科技大学华中科技大学20004 设P是集合A上的二元关系，P是传递的和反自反的，证明：r(P)是A上的偏序关系。本讲稿第一百一十二页，共一百二十六页北京师范大学北京师范大学19995 证明整除关系是正整数集合上的偏序关系。本讲稿第一百一十三页，共一百二十六页三、函数三、函数本讲

39、稿第一百一十四页，共一百二十六页西南交通大学西南交通大学19991 假设函数f:AB并定义G:BP(A)，对于bB，G(b)=x|xA,f(x)=b。证明如果f是A到B的满射，则G是内射的；其逆命题成立吗？本讲稿第一百一十五页，共一百二十六页北京大学北京大学19982 设f:NNN,f(x,y)=xy。求f(N1),f-1(0)，并说明是否为满射、内射和双射。本讲稿第一百一十六页，共一百二十六页3 设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)。本讲稿第一百一十七页，共一百二十六页复旦大学复旦

40、大学19994 判断是否正确，并说明理由。设A和B为集合，若存在A到B的满射函数，则|B|A|。本讲稿第一百一十八页，共一百二十六页武汉大学武汉大学19995 设A,B,C,D是任意集合，f是A到B的双射，g是C到D的双射。令h:ACBD且(a,c)AC，h(a,c)=(f(a),g(c)。那么h是双射吗？请证实你的判断。本讲稿第一百一十九页，共一百二十六页中国科学院软件所中国科学院软件所19966 设f:AB,g:BC,h:BC,证明：如果h o o g o o f=IA，f o o h o o g=IB，g o o f o o h=IC，则f、g和h均为双射，并求出f-1，g-1，h-1。本讲稿第一百二十页，共一百二十六页中国科学院计算所中国科学院计算所19987 设R1和R2为X上的两个关系，且R1 o o R2=IX。1）若X为有限集合，证明：存在X上双射f1和f2，使得f1 o o f2=IX且aR1bb=f1(a),cR2dd=f2(c)。2）若X为无限集合，举例说明1）的结论不成立。本讲稿第一百二十一页，共一百二十六页本讲稿第一百二十二页，共一百二十六页本讲稿第一百二十三页，共一百二十六页本讲稿第一百二十四页，共一百二十六页本讲稿第一百二十五页，共一百二十六页本讲稿第一百二十六页，共一百二十六页