离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻铜部分的综合练习， 这3次综合练习基本上是按翻考试的题型安排练习题目。目的是通过缘合练习，使同学自己 检验学习成果，找出掌探的湖弱知识点，重点复习，争取尽快掌规。本次是集合论部分的综 合练习 一、单项选择题 1,若集合卡{月，=《a,k{,》,则(》， A.kB且托B.能品但起B C,k仁B,但AeD.紅B且eB 2.若集合4=2，，{的，}，则下列表述正确的是0. A.(a,{d》eB.dcd C.2)cD.②e4 3.若集合4=[品，{，1,2》，则下列表述正确的是0. A.《,{》6B.2c4 C.(a)cD.4 4.若集合本{a,b,1,21,1,2,则()· A.c4,且所B.所4但血d C.4,但年D.:名且单A 5.设集合+[1，，则风0=0. A.(1,{aB.【O,1l,(ad] C.(②.，(.1，]D.(..l,】 6,若集合4的元素个数为10，则其幂集的元素个数为()， A.1024B.10C.100D.1 7.集合L,2,3,4.5,6,7,8上的关系N《x,Dt=10且xe升，则R的性质为 (). A:白反的B。对称的 C.传递且对称的D.反自反且传递的 8.设集合+1,2,3,4,5,6副上的二元关系P(品eA且+b8},则层 具有的性质为()， A,自反的B,对称的 C.对称和传递的D.反自反和传递的 9.如果品和%是A上的白反美系，则后U品，是门是，是-居中白反关系有()个 A.0B.2.1D.3
1 离散数学集合论部分综合练习 本课程综合练习共分 3 次，分别是集合论部分、图论部分、数理逻辑部分的综合练习， 这 3 次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己 检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综 合练习。 一、单项选择题 1．若集合 A={a，b}，B={a，b，{a，b}}，则（）． A．AB，且 ABB．AB，但 AB C．AB，但 ABD．AB，且 AB 2．若集合 A＝{2，a，{a}，4}，则下列表述正确的是()． A．{a，{a}}AB．{a}A C．{2}AD． A 3．若集合 A＝{a，{a}，{1，2}}，则下列表述正确的是()． A．{a，{a}}AB．{2}A C．{a}AD．A 4．若集合 A={a，b，{1，2}}，B={1，2}，则（）． A．BA，且 BAB．BA，但 BA C．BA，但 BAD．BA，且 BA 5．设集合 A={1,a}，则 P(A)=()． A．{{1},{a}}B．{ ,{1},{a}} C．{ ,{1},{a},{1,a}}D．{{1},{a},{1,a}} 6．若集合 A 的元素个数为 10，则其幂集的元素个数为（）． A．1024B．10C．100D．1 7．集合 A={1,2,3,4,5,6,7,8}上的关系 R={|x+y=10 且 x,y A}，则 R 的性质为 （）． A．自反的 B．对称的 C．传递且对称的 D．反自反且传递的 8．设集合 A={1，2，3，4，5，6}上的二元关系 R={ a,b a,b A,且 a+b=8}，则 R 具有的性质为（）． A．自反的 B．对称的 C．对称和传递的 D．反自反和传递的 9．如果 R1 和 R2 是 A 上的自反关系，则 R1∪R2，R1∩R2，R1-R2 中自反关系有（）个． A．0B．2C．1D．3
10.设集合卡1,23,4}上的二元关系 e[,,,}. =(c1,1>,,,,}, 则5是R的()闭包. A,自反B,传递C,对称D。以上都不对 11.设集合本[1,23,4,5引上的偏序关系 的哈斯图如图一所示，若A的子集作3,4,5引， 则元素3为B的()· A.下界B.最大下界 图 C.最小上界D.以上答案都不对 12.设卡1.2,3,4.5,6,7,8刷，R是A上的整障关系，=2,4.6卧。则集合B的最大元、 最小元、上界、下界依次为0. A.8、2、8、2B.无、2、无、2 C.6、2、6.2D.8、1、6.1 13.设卡{4卧，作1,2，，尾，层是A到B的二元美系，且=(K,2),,(,2D,(a,1,是=，，则(》不是从A到的函数， A,R和B.C,RD.R和R 二、填空题 1,设集合A有n个元素，那么A的幂集合0的元素个数为. 2.设集合一[品，时，那么集合A的幂集是. 应该填写：《O,{a,{d,(] 3,设集合年0,1,23引，=2,34，引，骨是A到B的二元关系. R={Kx,y>KEA且yEB且,yEAn 则？的有序对集合为. 4.设集合+0,1,2,0,2,4).R是A到B的二元关系， R={Kx,y>x∈A且y∈B且x,y∈AAB 烟R的关系矩库（一 5.设集合+a,人d,A上的二元关系 A(Kab》,c,SaD,(D,(g⊙] 则(9-=. 6,设集合年{品AC】,A上的二元关系=《4，®，,<A②，<GD,则二元关系 R具有的性质是
2 10．设集合 A={1,2,3,4}上的二元关系 R={ 1,1 ， 2,2 ， 2,3 ， 4,4 }， S={ 1,1 ， 2,2 ， 2,3 ， 3,2 ， 4,4 }， 则 S 是 R 的（）闭包． A．自反 B．传递 C．对称 D．以上都不对 11．设集合 A={1,2,3,4,5}上的偏序关系 的哈斯图如图一所示，若 A 的子集 B={3,4,5}， 则元素 3 为 B 的（）． A．下界 B．最大下界 C．最小上界 D．以上答案都不对 12．设 A={1,2,3,4,5,6,7,8}，R 是 A 上的整除关系，B={2,4,6}，则集合 B 的最大元、 最小元、上界、下界依次为()． A．8、2、8、2B．无、2、无、2 C．6、2、6、2D．8、1、6、1 13．设 A={a,b}，B={1,2}，R1，R2，R3 是 A 到 B 的二元关系，且 R1={,}， R2={,,}，R3={,}，则（）不是从 A 到 B 的函数． A．R1 和 R2B．R2C．R3D．R1 和 R3 二、填空题 1．设集合 A 有 n 个元素，那么 A 的幂集合 P(A)的元素个数为． 2．设集合 A＝{a，b}，那么集合 A 的幂集是． 应该填写：{,{a,b},{a},{b}} 3．设集合 A={0,1,2,3}，B={2,3,4,5}，R 是 A 到 B 的二元关系， R ={ x, y x A且y B且x, y A B} 则 R 的有序对集合为． 4．设集合 A={0,1,2}，B={0,2,4},R 是 A 到 B 的二元关系， R ={ x, y x A且yB且x, y A B} 则 R 的关系矩阵 MR＝ ． 5．设集合 A={a,b,c}，A 上的二元关系 R={,}，S={,,} 则(R•S) －1 =． 6．设集合 A=｛a,b,c｝，A 上的二元关系 R={,,,}，则二元关系 R 具有的性质是． 2 4 1 3 5 图一
7,若卡1,2到，杂《x,少6AEA+=10阴，则R的自反闭色为 8.设集合十山，2)，历（品卧，那么集合A到B的双射函数是 9.设(a,c,一1,2，作64一品则不同的函数个数为. 三、判断说明愿（列断下列各题。并说明理由，） 1.设A尽C为任意的三个集合，如果U一UCG,判断结论小C是否成立？并说明 理由， 2.如果成和尾是A上的白反美系，判断 结论：“、是U晨、屈⌒品是自反的”是否 成立？并说明理由. 3.若偏序集e4JeA且 t3,试求RS,原3，，S,扇. 5.设1,23,4.56,7,8,9,1011,12}，R是A上的整豫关系，压(2.4,6卧. 《1)写出关系R的表示式：(2)画出关系骨的哈斯图： 《3)求出集合B的最大元、最小元. 6.设集合A=[品G,函上的二元关系”的关系图 图三所示。 (1)写出的表达式： (2)写出？的关系矩库： 图三 (3)求出票. 7,设集合卡1.2,3.4}，作k>|xe布一川=1成←=0)，试
3 7．若 A={1,2}，R={|xA,yA,x+y=10}，则 R 的自反闭包为． 8．设集合 A={1,2}，B={a,b}，那么集合 A 到 B 的双射函数是 ． 9．设 A={a，b，c}，B={1，2}，作 f：A→B，则不同的函数个数为． 三、判断说明题（判断下列各题，并说明理由．） 1．设 A、B、C 为任意的三个集合，如果 A∪B=A∪C，判断结论 B=C 是否成立？并说明 理由． 2．如果 R1 和 R2 是 A 上的自反关系，判断 结论：“R -1 1、R1∪R2、R1R2 是自反的”是否 成立？并说明理由． 3．若偏序集的哈斯图如图一所示， 则集合 A 的最大元为 a，最小元不存在． 4．若偏序集的哈斯图如图二所示， 则集合 A 的最大元为 a，最小元不存在． 5．设 N、R 分别为自然数集与实数集，f：N →R，f(x)=x+6，则 f 是单射． 四、计算题 1．设集合 A＝{a,b,c}，B={b,d,e}，求 （1）BA；（2）AB；（3）A－B；（4）BA． 2．设 A={{a,b},1,2}，B={a,b,{1},1}，试计算 （1）（A−B）（2）（A∪B）（3）（A∪B）−（A∩B）． 3．设集合 A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）（A−B）；（2）（A∩B）；（3）A×B． 4．设 A={0，1，2，3，4}，R={|xA，yA 且 x+y|xA，yA 且 x+y3}，试求 R，S，R•S，R -1，S -1，r(R)． 5．设 A={1,2,3,4,5,6,7,8,9,10,11,12}，R 是 A 上的整除关系，B={2,4,6}． （1）写出关系 R 的表示式；（2）画出关系 R 的哈斯图； （3）求出集合 B 的最大元、最小元． 6．设集合 A＝{a,b,c,d}上的二元关系 R 的关系图 如图三所示． （1）写出 R 的表达式； （2）写出 R 的关系矩阵； （3）求出 R 2． 7．设集合 A={1，2，3，4}，R={|x,yA；|x−y|=1 或 x−y=0}，试 图一 图二 a d b c 图三
(1)写出爱的有序对表不：(2)画出R的关系图： (3)说明层调足自反性，不滑足传递性。 五、证明愿 1,试证明集合等式：AU(O=(U0⌒(O. 2.试证明集合等式h(U0=(hu(h0. 3,设R是集合A上的对称关系和传递关系，试证明：若对任意aeA存在beA,使得 《品的eR则R是等价关系 4,若非空集合A上的二元关系和S是偏序关系。试证明：R⌒S也是A上的偏序关 系 参考解容 一、单项选择题 1.2.B3.C4.5.06.A7.8.B 9,B10C11,C12.B13.B 二、填空愿 1.2g 2.(@.a,{a,] 3.(22D,2.3》,3,2>,3.3> 「110 4.000 110 5.(aA) 6.反自反的 7.(1.1D,22D 8.(1.D,2.,1,⊙，2> 9.8 三、判断说明题（判断下列各愿，并说明理由。） 1.解：错 设卡1,2》，=(1)，2，则AU=AUC但eG 2.解：成立 因为是和居是A上的自反关系，即I品，IC尼： 由逆关系定义和ICR,得J仁R: 由CR,IC&,得ICRU,ICRn品 所以，R、U尾、RAR是自反的： 3解：正确
4 （1）写出 R 的有序对表示；（2）画出 R 的关系图； （3）说明 R 满足自反性，不满足传递性． 五、证明题 1．试证明集合等式：A(BC)=(AB)(AC)． 2．试证明集合等式 A(BC)=(AB)(AC)． 3．设 R 是集合 A 上的对称关系和传递关系，试证明：若对任意 aA，存在 bA，使得 R，则 R 是等价关系． 4．若非空集合 A 上的二元关系 R 和 S 是偏序关系，试证明： RS 也是 A 上的偏序关 系． 参考解答 一、单项选择题 1．A2．B3．C4．B5．C6．A7．B8．B 9．B10．C11．C12．B13．B 二、填空题 1．2 n 2．{,{a,b},{a},{b}} 3．{，，}， 4． 1 1 0 0 0 0 1 1 0 5．{,} 6．反自反的 7．{,} 8．{,}，{,} 9．8 三、判断说明题（判断下列各题，并说明理由．） 1．解：错． 设 A={1,2}，B={1}，C={2}，则 A∪B=A∪C，但 BC． 2．解：成立． 因为 R1 和 R2 是 A 上的自反关系，即 IAR1，IAR2。 由逆关系定义和 IAR1，得 IAR1 -1； 由 IAR1，IAR2，得 IAR1∪R2，IAR1R2。 所以，R1 -1、R1∪R2、R1R2 是自反的。 3．解：正确．
对于集合A的任意元素，均有《，心E是 (暖)，所以：是集合A中的最大元， 按属最小元的定义，在集合A中不存在最 小元 4,解：错误 集合A的最大元不存在，：是极大元 5,解：正确. 授，居为自然数且居，则有八x)-x64居6f风x,故f为单射 四、计算愿 1.解：(1)+（品五dn点dd-(同 (2)Au={aau么d={aG4 (3)4-=(4Ac-{6d={acd (4)eUB-+a,点&dd-{卧-aGd到 2.解：(1)(+0-（品，2到 (2)(4U)=(品4,1,2盛点} (3)(AU酚-(An=({4M,2品A1] 3.解：(1)4=41,29] (2)An作1,20 (3)A×=.,([13.{1,2>,(21.1>。. ,21,22D 2,1,2到月 4.解：0， 华{,0,2D,0,3>,.,,2,0>,21>,30>} A2, W'-☑， 5= 12 9 (M=. 5.解(1)U1.2,1.3,“,4,12> 2,4.2,6>.28>.210>.2,12>.3,6》.8,9. 3,12>,(4,8>.(4,12.(5,10>,6,121 (2)关系R的哈斯图如图四 图四：关系R的哈 (3)集合B没有最大元，最小元是：2 6.解：-Ka,,《a,cD,<6,c,《db
5 对于集合 A 的任意元素 x，均有R （或 xRa），所以 a 是集合 A 中的最大元． 按照最小元的定义，在集合 A 中不存在最 小元． 4．解：错误． 集合 A 的最大元不存在，a 是极大元． 5．解：正确． 设 x1，x2 为自然数且 x1x2，则有 f(x1)=x1+6x2+6=f(x2)，故 f 为单射． 四、计算题 1．解：（1）BA={a,b,c}{b,d,e}={b} （2）AB={a,b,c}{b,d,e}={a,b,c,d,e} （3）A－B={a,b,c}－{b,d,e}={a,c} （4）BA=AB－BA={a,b,c,d,e}－{b}={a,c,d,e} 2．解：（1）（A−B）={{a,b},2} （2）（A∪B）={{a,b},1,2,a,b,{1}} （3）（A∪B）−（A∩B）={{a,b},2,a,b,{1}} 3．解：（1）A−B={{1},{2}} （2）A∩B={1,2} （3）A×B={，，，，， ，，，，，, } 4．解：R=, S={,,,,,,,,,} R•S=， R -1 =， S -1 =S， r(R)=IA． 5．解：（1）R=I{,,…,, ,,,,,,, ,,,,} （2）关系 R 的哈斯图如图四 （3）集合 B 没有最大元，最小元是：2 6．解：R＝{,,,} 1 2 3 4 6 9 5 7 8 10 11 12 图四：关系 R 的哈 斯图
f1010] 0010 1g= 0000 0001 =ka,ac>,Ac,db}K品D,(mc,(6c2,《d -Ka.(a,o.(d. 7.解1(1)朵(，2,2D,3,30,(4.4> 《1,2,21>.23》.3,2>,34D,4.3 (2)关系图如图五 (3)因为1,1>，2,2D,3,3>,4,4>均属于R 即A的每个元素构成的有序对均在层中，故？在 A上是自反的： 因有属于R但2,4》不属于尼 所以R在A上不是传递的， 五、证明题 1.证明：设，若xeAU(O,则eA或reG 即xEA或xeB且xEA或x∈C, 即xeAB且x@AUG 即xE=(AU0n(AUO: 所以AU(Qc(AU动n(AUO. 反之，若xe(AU扇n(AUO,则IEAB且rEAC 即x后A或xEB且xEA或xeG 即x∈A或xehG 即xEAU(O, 所以(AU周n(OCU(0. 因此.AU(Q=(AUn(UO. 2.证明：设÷4n(U0,户(MnMU(AnO,若xeS,则∈A且reUG即xeA 且xB或xeA且xeG 也即eAnB或eA门G即eT,所以冬无 反之，若x∈元则eAnB或x∈AnG 即xEA且x∈B戚xEA且x∈C 也即EA且∈UC,即∈S所以S 因此严 3,设R是集合A上的对称关系和传递关系，试证明：若对任意eA存在eA,使得
6 = 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 MR R 2 ={,,,}•{,,,} ={,,} 7．解：（1）R={,,,, ,,,,,} （2）关系图如图五 （3）因为,,,均属于 R， 即 A 的每个元素构成的有序对均在 R 中，故 R 在 A 上是自反的。 因有与属于 R，但不属于 R， 所以 R 在 A 上不是传递的。 五、证明题 1．证明：设，若 x∈A(BC)，则 x∈A 或 x∈BC， 即 x∈A 或 x∈B 且 x∈A 或 x∈C． 即 x∈AB 且 x∈AC， 即 x∈T=(AB)(AC)， 所以 A(BC)(AB)(AC)． 反之，若 x∈(AB)(AC)，则 x∈AB 且 x∈AC， 即 x∈A 或 x∈B 且 x∈A 或 x∈C， 即 x∈A 或 x∈BC， 即 x∈A(BC)， 所以(AB)(AC)A(BC)． 因此．A(BC)=(AB)(AC)． 2．证明：设 S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若 x∈S，则 x∈A 且 x∈B∪C，即 x∈A 且 x∈B 或 x∈A 且 x∈C， 也即 x∈A∩B 或 x∈A∩C，即 x∈T，所以 ST． 反之，若 x∈T，则 x∈A∩B 或 x∈A∩C， 即 x∈A 且 x∈B 或 x∈A 且 x∈C 也即 x∈A 且 x∈B∪C，即 x∈S，所以 TS． 因此 T=S． 3．设 R 是集合 A 上的对称关系和传递关系，试证明：若对任意 aA，存在 bA，使得 1 2 3 4 图五
(品》cR则R是等价关系 证明：已知R是对称美系和传递关系，只需证明”是白反美氛 YaG小，3eA,使得ERE眉 由元素云的任意性，知R是白反的， 所以，R是等价关系， 4,若非空集合A上的二元关系R和S是偏序关系。试证明！R⌒S也是A上的偏序关 系 证明：.①：CAeS→×xx>eR⌒S，所以RnS有自反性： ②x,y@A,因为层，S是反对称的， cx.y>RnSARnS(CX.y>ERACI.Y>ES)A(CY.I>ERACY.X>ES) (ERAER)A(ESAES)ex=yAy=xex=y 所以，S有反对称性， 图x,y,:eA,因为层5是传遥的， ERnSAeRnS 白ERAESAERAES ×x,y>eRAeRAeSAeS ERAESEERnS 所以，RnS有传通性 总之，月是偏序关系
7 R，则 R 是等价关系． 证明：已知 R 是对称关系和传递关系，只需证明 R 是自反关系． aA，bA，使得R，因为 R 是对称的，故R； 又 R 是传递的，即当R，RR； 由元素 a 的任意性，知 R 是自反的． 所以，R 是等价关系． 4．若非空集合 A 上的二元关系 R 和 S 是偏序关系，试证明： RS 也是 A 上的偏序关 系． 证明：.① xA, x, x R, x, x S x, x R S ，所以 R S 有自反性； ② x, y A, 因为 R，S 是反对称的， x y R y x R x y S y x S x y y x x y x y R S y x R S x y R x y S y x R y x S = = = ( , , ) ( , , ) , , ( , , ) ( , , ) 所以，RS 有反对称性． ③ x, y,z A ，因为 R，S 是传递的， x, y R S y,z R S x, y R x, y S y,z R y,z S x, y R y,z R x, y S y,z S x,z R x,z S x,z R S 所以， R S 有传递性． 总之，R 是偏序关系．