《复旦大学计算机科学与工程系_吴永辉_离散数学_集合论经典习题》由会员分享，可在线阅读，更多相关《复旦大学计算机科学与工程系_吴永辉_离散数学_集合论经典习题（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, 1 AC不常真 A=1, B=1, C=1,2 设A, B是任意2个集合， A B与 AB同时成立，这可能吗？,可能 A=
2、1, B=1, 1.,3 设A, B, C是集合，判断下列命题真假，如果为真，给出证明；如果为假，给出反例： 1) AB, 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=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) ABAB=B; 2) ABAB=A; 3) ABAB=A; 4) ABA
3、B=B; 5) ABA(B-A)=B; 6) BA(A-B)B=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，不成立；,1.2 集合运算,5 设A, B, C是任意3个集合， （1）AB=AC，则B=C吗？ （2）AB=AC，则B=C吗？ （3） A
4、B=AC且AB=AC，则B=C吗？,（1）假 A=1, 2, B=1, C=2 （2）假 A=1, B=1, 2, C=1, 3 （3）真 /*基本法、反证法证明*/ 设xB，假设xC。因为xB，所以xAB；因为AB=AC，所以xAC；因为xC，所以xA；又因为xB，所以x AB；因为AB=AC ，所以xAC；则xC，这与xC矛盾。所以B=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=
5、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，xA，则xA-B 或 xA-C；则有,2）：设ABC=，对任意的x，xA，则xB或xC，则有,对任意的x，x(A-B)(A-C)，则xA-B或 xA-C，则有,（2） (A-B)(A-C)= (A-B)=或(A-C)= AB并且AC ABC 所以，充要条件为ABC。,（3） 1) 设(
6、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)(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,/*利用基本法证明集合的包含关系*
7、/ 证明： (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上的关系 （1）R是自反的，则RR是自反的； （2）R是对称的，则RR是对称的； （3）R是反自反和传递的，则R是反对称的；,/*证明思想：根据定义给出的性质证明*/ 证明： （1）证明思想与（2）和（3）相同 （2）设(a, b)RR, 则存在c, (a, c)R, (c, b)R; 因
8、为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。 其逆命题也成立吗？ 证明思想： 证明RR=R，1）证明RRR； 2） 证明RRR：,证明： 1）证明RRR： 设(a, b)RR，存在cA, 使得(a, c)R, (c, b)R，因为R是传递的，所以(a, b)R；则RRR； 2） 证明RRR： 设(a, b)R，R是自反的，(b, b)R，所以(a, b)RR；则
9、RRR。 所以RR=R。,自反不成立 传递成立,特殊关系,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 (a, b)，即R是对称的。 3） /*证明R是传递的；*/ 如果(
10、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)自反的；(ii)对称的；(iii)传递的；,证明： 1）RS是A上的等价关系RS=SR： 如果(a, b)RS, 因为R
11、S是对称的，所以(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，如果(a, b)RS, (b, c)RS，因为RS=SR，则有(b, c)SR，即存在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)RS；RS是对称
12、的，则(f, a)RS；因为R是对称的，(f, c)R，则(c, f)R。 因为(f, a)RS，则存在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)RS。因为已经证明，RS是对称的，所以(a, c)RS。,函数,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),/*基本法证明*/ 证明：（1）对任意的yf(AB)，存在x，x AB，使得y=f(x)。因为xA，
13、所以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自反、对称和传递*/,四、概念综合练习,一、选择题（北京理工大学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
14、) ABB B) AB=B C) AB=A D) ABB2,4 R是集合A上的自反关系，则（ ） A) R R B) RR R C) RR-1=IA D) R R-1=IA,5 集合A中有n个元素，则A上共有（ ）个既对称又反对称的关系。 A) 0 B) 2n C) n2 D) 2n,6 R是可传递的二元关系，则在RR-1,RR-1, R-R-1, R-1-R中，有（ ）个一定是可传递的。 A) 1 B) 2 C) 3 D) 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) 4 B) 8 C) 16 D) 64,二、选择题（北京理工大学1999） 1 已知AB=1, 2, 3，AC=2, 3, 4 ，若2B，则 。 A) 1C B) 2C C) 3C D) 4C,2 对任何二元关系R，在RR-1, RR-1, RR-1, RR-1中有 个一定是对称关系。 A) 1 B) 2 C) 3 D) 4,
