中央电大离散数学2012年1月期末考试试卷及答案

1、试卷代号:1009座位号E口 中央广播电视大学2011-2012学年度第一学期开放本科期末考试(半开卷) 离散数学(本)试题 2012年1月 |题号|一|二|三l四|五|六|总分| |分数IIIIIIII i得分|评卷入| 题每小题3分，本题共15分) III 1.若集合A的元素个数为10，则其幕集的元素个数为( A.10B. 100 C.1024D. 1 2.设A=a，的，B=1，2，凡，凡，R3是A到B的二元关系，且R1=, Rz=， ，凡=，则()是从A到B的函数. A.R1和Rz C.R3 B.Rz D.R1和R3 3.设A=1，2，3，4，5，6，7，8，R是A上的整除关系，B=2

2、，4，6，则集合B的最大元、 最小元、上界、下界依次为(). A.8、2，8、2a元、2、元、2 C.6、2、6、2U8、1、6、1 4.若完全图G中有n个结点三2)，m条边，则当()时，图G中存在欧拉回路. A.n为奇数B.n为偶数 C.m为奇数D.m为偶数 67 5.已知图G的邻接矩阵为 00011 o0001 00011 10101 11110 则G有(). A.6点，8边 C.5点，8边 |得分|评卷人| III B.6点，6边 D.5点，6边 二、填空题(每小题3分，本题共15分 6.设集合A=叫，那么集合A的事集是 7.若乱和凡是A上的对称关系，则RlURz,Rln凡，Rl一儿，凡

3、-Rl中对称关系有 个. 8.设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去条边后 使之变成树. 9.设连通平面图G的结点数为5，边数为6，则 面数为 10.设个体域D=a，肘，则 谓 词公式(Vx)(A(x)八B(x)捎去 量词 后的等值式为 得分|评卷人 三、逻辑公式翻译(每小题6分，本题共12分) 11.将语句今天有联欢活动，明天有文艺晚会翻译成命题公式. 12.将语句如果小王来，则小李去翻译成命题公式. 68 |得分|评卷人| III 四、判断说明题每小题7分，本题共14分) 判断下列各题正误，并说明理由. 13.若偏序集的晗斯图如图一所示，则集合A的最大元为a，极小元

4、不存在. /气od 14.-,P A(P-，Q)VP为永假式. |得分|评卷人| III 五、计算题每小题12分，本题共36分 15.设集合A=l，2，3，的，R=1工，yA川x-yl=1或x-y=O，试 (1)写出R的有序对表示; (2)画出R的关系图; (3)说明R满足自反性，不满足传递性. 16.设图G=，V=t勺，吨，屿，叭，Vs,E= (VIVz),(VIV3 ),(吨，V4)(叫，Vs), (叭，Vs)，试 (1)画出G的图形表示s (2)写出其邻接矩阵; (3)求出每个结点的度数; (4)画出图G的补图的图形. 17.求PQ八R的合取范式与主析取范式. |得分|评卷人| III

5、六、证明题本题共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.4 8.1 9.3 10.(A(a)八B(b八(A(a)八B(b 三、逻辑公式翻译每小题6分，本题共12分 11.设P:今天有联欢活动，Q:明天有文艺晚会， P八Q. 12

6、.设P:小王来，Q:小李去 PQ. (2分 (6分 (2分 (6分 四、判断说明题每小题7分，本题共14分 13.错误.(3分 对于集合A的任意元素工，均有 R(或xRa)，所以a是集合A中的最大元.(5分) 但按照极小元的定义，在集合A中b，c，d均是极小元.(7分) 14.错误.(3分) PA(PQ)VP是由PA(PQ)与P组成的析取式， 如果P的值为真，则.，p八(PQ)VP为真，(5分) 如果P的值为假，则.，p与PQ为真，即.，p八(PQ)为真， 70 也即PA(PQ)VP为真.(7分 所以PA(PQ) VP是永真式. 另种说明z PA(PQ)VP是由PA(PQ)与P组成的析取式，

7、只要其中一项为真，则整个公式为真.(5分) 可以看到，不论P的值为真或为假PA(PQ)与P总有一个为真， 所以.，p八(PQ)VP是永真式.(7分) 或用等价演算PA(PQ)VP件T 五、计算题每小题12分，本题共36分) 15.(l)R =. . (2)关系 图如图二: (3分) 图二二(6分) (3)因为.均属于R.即A的每个元素构成的有序对均 在R中，故R在A上是自反的.(9分 因有与属于R，但不属于R.所以R在A上不是传递的.(12分) 16.(1)关系图如图三z V2 (2)邻接短阵 图三 V4 Vs (3分) 71 O11OO 1OO1O 1OOO1(6分 O1OO1 LO O11

8、O (3)deg(VI) = 2 deg(V2)=2 deg(叫)=2 deg(叫)=2(9分 deg(V5)=2 (4)补图如图四 V2、 主二hvs 图四(1 2分 (4分 (6分) (7分) 估分 (9分) (10分) (合取范式) 件(-，P八-，Q)V(-,P八Q)V(R1Q) 件-,P1-,Q)1(-,RVRV(-,P八Q)V(R八Q) 件(-，p八-，Q八-，R)V(-,P八-，Q八R)V(-，P八Q)V(R八Q) 件(-，p八-，QI-，R)V(-，PI-，Q八R)V-,P八Q)1 (-,RVRV(R八Q) 件(-,P1-,Q1-,R) V(-,P1-,Q1R) V(-,P1Q

9、1-,R) V(-,P1Q八R)V(RAQ) 17.P(R八Q) 件-，PV(R八Q) 件(-，PVQ)八(-，PVR) P(R八Q) 件-，PV(R八Q) 件(-,P1 (-,QVQV(R八Q) 件(-PA-，Q八-，R)V(-,P八-，Q1R)V(-,P1Q八-，R)V 72 (-,P八Q八R)V(-,P VP)1(R八Q 件(-,P1-,Q1-,R)V (-,P1-,Q八R)V (-,P八QI-,R) V (-PIQ八R)V(P八R1Q)(主析取范式)(12分) 说明z此题解法步骤多样，若能按正确步骤求得结果，均可给分. 六、证明题(本题共8分 18.证明:可利用数列可图化及握手定理解答 顶