离散数学关系部分经典练习及答案

1离散数学关系部分综合练习一、单项选择题1．设集合A={1,a}，则A的幂集P(A)=()．A．{{1},{a}}B．{,{1},{a}}C．{,{1},{a},{1,a}}D．{{1},{a},{1,a}}2．若集合A的元素个数为10，则其幂集的元素个数为（）．A．1024B．10C．100D．17．集合A={1,2,3,4,5,6,7,8}上的关系R={x，y|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．310．设集合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、无、2C．6、2、6、2D．8、1、6、113．设A={a,b}，B={1,2}，R1，R2，R3是A到B的二元关系，且R1={a，2,b，2}，R2={a，1,a，2,b，1}，R3={a，1,b，2}，则（）不是从A到B的函数．A．R1和R2B．R2C．R3D．R1和R324135图一2二、填空题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的二元关系，},,{BAyxByAxyxR且且则R的有序对集合为．4．设集合A={0,1,2}，B={0,2,4},R是A到B的二元关系，},,{BAyxByAxyxR且且则R的关系矩阵MR＝．5．设集合A={a,b,c}，A上的二元关系R={a,b,c.a}，S={a,a,a,b,c,c}则(RS)－1=．6．设集合A=｛a,b,c｝，A上的二元关系R={a,b,b,a,b,c,c,d}，则二元关系R具有的性质是．7．若A={1,2}，R={x,y|xA,yA,x+y=10}，则R的自反闭包为．8．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为．三、判断说明题（判断下列各题，并说明理由．）2．如果R1和R2是A上的自反关系，判断结论：“R-11、R1∪R2、R1R2是自反的”是否成立？并说明理由．3．若偏序集A，R的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．4．若偏序集A，R的哈斯图如图二所示，则集合A的最大元为a，最小元不存在．四、计算题4．设A={0，1，2，3，4}，R={x，y|xA，yA且x+y0}，S={x，y|xA，yA且x+y3}，试求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的最大元、最小元．图一图二adbc图三36．设集合A＝{a,b,c,d}上的二元关系R的关系图如图三所示．（1）写出R的表达式；（2）写出R的关系矩阵；（3）求出R2．7．设集合A={1，2，3，4}，R={x,y|x,yA；|xy|=1或xy=0}，试（1）写出R的有序对表示；（2）画出R的关系图；（3）说明R满足自反性，不满足传递性．五、证明题3．设R是集合A上的对称关系和传递关系，试证明：若对任意aA，存在bA，使得a,bR，则R是等价关系．4．若非空集合A上的二元关系R和S是偏序关系，试证明：SR也是A上的偏序关系．参考解答一、单项选择题1．A2．A7．B8．B9．B10．C11．C12．B13．B二、填空题1．2n2．{,{a,b},{a},{b}}3．{2,2，2,3，3,2}，3,34．0110000115．{a.c,b,c}6．反自反的7．{1,1,2,2}8．8三、判断说明题（判断下列各题，并说明理由．）2．解：成立．因为R1和R2是A上的自反关系，即IAR1，IAR2。由逆关系定义和IAR1，得IAR1-1；由IAR1，IAR2，得IAR1∪R2，IAR1R2。4所以，R1-1、R1∪R2、R1R2是自反的。3．解：正确．对于集合A的任意元素x，均有x,aR（或xRa），所以a是集合A中的最大元．按照最小元的定义，在集合A中不存在最小元．4．解：错误．集合A的最大元不存在，a是极大元．四、计算题4．解：R=,S={0,0,0,1,0,2,0,3,1,0,1,1,1,2,2,0,2,1,3,0}RS=，R-1=，S-1=S，r(R)=IA．5．解：（1）R=I{1,2,1,3,…,1,12,2,4,2,6,2,8,2,10,2,12,3,6,3,9,3,12,4,8,4,12,5,10,6,12}（2）关系R的哈斯图如图四（3）集合B没有最大元，最小元是：26．解：R＝{a,a,a,c,b,c,d,d}1000000001000101RMR2={a,a,a,c,b,c,d,d}{a,a,a,c,b,c,d,d}={a,a,a,c,d,d}7．解：（1）R={1,1,2,2,3,3,4,4,1,2,2,1,2,3,3,2,3,4,4,3}（2）关系图如图五（3）因为1,1,2,2,3,3,4,4均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。因有2,3与3,4属于R，但2,4不属于R，所以R在A上不是传递的。五、证明题3．设R是集合A上的对称关系和传递关系，试证明：若对任意aA，存在bA，使得a,bR，则R是等价关系．证明：已知R是对称关系和传递关系，只需证明R是自反关系．123469578101112图四：关系R的哈斯图1234图五5aA，bA，使得a,bR，因为R是对称的，故b,aR；又R是传递的，即当a,bR，b,aRa,aR；由元素a的任意性，知R是自反的．所以，R是等价关系．4．若非空集合A上的二元关系R和S是偏序关系，试证明：SR也是A上的偏序关系．证明：.①SRxxSxxRxxAx,,,,,，所以SR有自反性；②,,Ayx因为R，S是反对称的，yxxyyxSxySyxRxyRyxSxyRxySyxRyxSRxySRyx),,(),,(),,(),,(,,所以，RS有反对称性．③Azyx,,，因为R，S是传递的，SRzySRyx,,SzyRzySyxRyx,,,,SzySyxRzyRyx,,,,SRzxSzxRzx,,,所以，SR有传递性．总之，R是偏序关系．