《复旦大学计算机科学与工程系 吴永辉 离散数学 集合论经典习题》由会员分享，可在线阅读，更多相关《复旦大学计算机科学与工程系 吴永辉 离散数学 集合论经典习题（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同 时成立，这可能吗？ 可能
2、A=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)
3、 ABAB=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=BAB=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
4、） AB=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=
5、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， 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。 （
6、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)(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
8、, 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。其逆命题也成立吗？证明思想： 证明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，所以(
9、a, b)RR；则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） /*证明
10、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)自反的；(ii)对称的；(iii)传递的； 证明： 1）RS是A上的等价关系RS=SR：如
11、果(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，如果(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)
12、R，所以(a, f)RS；RS是对称的，则(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)，存在
13、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自反、对称和传递*/四、概念综合练习 一、选择题（北京理工大学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) 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-
