试卷代号:1009座位号E口中央广播电视大学2011-2012学年度第一学期\离散数学(本)试题2012年1月|题号|一|二|三l四|五|六|总分|IIIII|分数Ii得分|评卷入|IIIII题{每小题3分，本题共15分)1.若集合A的元素个数为10，则其幕集的元素个数为(A.10B.100D.1={,},C.10242.设A={a，的，B={1，2}，凡，凡，R3是A到B的二元关系，且R1Rz={，，}，凡={，}，则(A.R1和Rz)是从A到B的函数.B.RzD.R1和R3C.R33.设A={1，2，3，4，5，6，7，8}，R是A上的整除关系，B={2，4，6}，则集合B的最大元、最小元、上界、下界依次为(A.8、2，8、2C.6、2、6、2).a元、2、元、2U8、1、6、14.若完全图G中有n个结点\三~2)，m条边，则当(A.n为奇数)时，图G中存在欧拉回路.B.n为偶数C.m为奇数D.m为偶数675.已知图G的邻接矩阵为00011o11则G有(00010001101110110).B.6点，6边A.6点，8边C.5点，8边D.5点，6边I|得分|评卷人|II二、填空题(每小题3分，本题共15分}6.设集合A={叫，那么集合A的事集是7.若乱和凡是A上的对称关系，则Rl个.URz,Rln凡，Rl一儿，凡-Rl中对称关系有8.设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去使之变成树.9.设连通平面图G的结点数为5，边数为6，则面数为条边后10.设个体域D={a，肘，则谓词公式(Vx)(A(x)八B(x))捎去量词后的等值式为得分|评卷人三、逻辑公式翻译(每小题6分，本题共12分)11.将语句\今天有联欢活动，明天有文艺晚会\翻译成命题公式.12.将语句\如果小王来，则小李去\翻译成命题公式.68I|得分|评卷人|II四、判断说明题{每小题7分，本题共14分)判断下列各题正误，并说明理由.13.若偏序集的晗斯图如图一所示，则集合A的最大元为a，极小元不存在./气\\od14.-,PA(P→-，Q)VP为永假式.I|得分|评卷人|II五、计算题{每小题12分，本题共36分}15.设集合A={l，2，3，的，R={1工，yεA川x-yl=1或x-y=O}，试(1)写出R的有序对表示;(2)画出R的关系图;(3)说明R满足自反性，不满足传递性.16.设图G=，V={'t勺，吨，屿，叭，Vs},E={(VI'Vz),(VI'V3),(吨，V4)'(叫，Vs),(叭，Vs)}，试(1)画出G的图形表示s(2)写出其邻接矩阵;(3)求出每个结点的度数;(4)画出图G的补图的图形.17.求P→Q八R的合取范式与主析取范式.I|得分|评卷人|II六、证明题{本题共8分)18.设连通无向图G有14条边，3个4度顶点，4个3度顶点，其它顶点的度数均小于3，试说明G中可能有的顶点数.69试卷代号:1009中央广播电视大学2011一2012学年度第一学期\离散数学(本)试题答案及评分标准(供参考〉2012年1月-、单项选择题{每小题3分，本题共15分}I.C2.C3.B4.A5.0二、填空题{每小题3分.本题共15分}6.{正当，{a}}7.48.19.310.(A(a)八B(b?八(A(a)八B(b?三、逻辑公式翻译{每小题6分，本题共12分}11.设P:今天有联欢活动，Q:明天有文艺晚会，P八Q.(2分〉(6分〉(2分〉12.设P:小王来，Q:小李去P?Q.四、判断说明题{每小题7分，本题共14分}(6分〉13.错误.(3分〉对于集合A的任意元素工，均有εR(或xRa)，所以a是集合A中的最大元.(5分)但按照极小元的定义，在集合A中b，c，d均是极小元.14.错误.(7分)(3分)\(P?\VP是由\(P→\Q)与P组成的析取式，如果P的值为真，则...，p八(P→\Q)VP为真，如果P的值为假，则...，p与P→\Q为真，即...，p八(P→\Q)为真，(5分)70也即\PA(P→\Q)VP为真.所以\PA(P另种说明z\→\是由\→\与P组成的析取式，只要其中一项为真，则整个公式为真.可以看到，不论P的值为真或为假?\(P→\与P总有一个为真，所以...，p八(P→\Q)VP是永真式.(7分〉?\P是永真式.(5分)(7分)或用等价演算\PA(P→\Q)VP件T五、计算题{每小题12分，本题共36分)15.(l)R={<1.1>.<2.2>.<3.3>.<4.4>.<1.2>.<2.1>.<2.3>.<3,2>.(3分)<3.4>.<4.3>}(2)关系图如图二:图二二(6分)(3)因为<1，1>.<2.2>.<3.3>.<4.4>均属于R.即A的每个元素构成的有序对均在R中，故R在A上是自反的.(9分〉因有<2.3>与<3，4>属于R，但<2.4>不属于R.所以R在A上不是传递的.(12分)16.(1)关系图如图三zV2VsV4图三(2)邻接短阵(3分)71
