试卷代号：1009 座位号■ 中央广播电视大学2007一2008学年度第二学期“开放本科”期末考试（半开卷） 离散数学（本）试题 2008年7月 题 号 二 三 四 五 六 总分 分 数 得分 评卷人 一、单项选择题（每小题3分，本题共15分】 1.设A={a,b),B={1,2},R,R2,R是A到B的二元关系，且R1={,}, R2={,,},R,={,},则( )不是从A到B的函数. A.R1和R2 B.R2 C.R3 D.R1和R3 2.设A={1,2,3,4,5,6,7,8},R是A上的整除关系，B={2,4,6},则集合B的最 大元、最小元、上界，下界依次为(). A.8、2、8、2 B.无、2、无、2 C.6、2、6、2 D.8、1、6、1 3.若集合A的元素个数为10，则其幂集的元素个数为( A.1024 B.10 C.100 D.1 4.设完全图K.有n个结点(n≥2)，m条边，当( )时，K。中存在欧拉回路 A.m为奇数 B.n为偶数 C.n为奇数 D.m为偶数 64
试卷代号:1009 座位号巨口 中央广播电视大学2007-2008学年度第二学期“开放本科”期末考试(半开卷) 离散数学(本) 试题 2008年 7月 题 号 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题《每小题3分。本题共 15分) 1.设 A={a,b},B=(1,2),R,,RZ,R3是 A到 B的二元关系，且 R,“{ , ) RZ ={ ， , },R3“{，}，则( )不是从 A 到B的函数. A. R;和 RZ B. R, C. R3 D. R;和 R3 2.设 A={1, 2, 3, 4, 5, 6, 7, 8},R是A 上的整除关系，B}i2, 4, 6}，则集合 B的最 大元 、最小元、上界、下界依次为( A. 8,2,8,2 B.无 、2、无 、2 C. 6,2,6,2 D.8,1,6、1 3.若集合A的元素个数为 10，则其幂集的元素个数为( ) A. 1024 C. 100 B. 10 D. 1 4.设完全图 K，有 n个结点(n)2),m条边，当( )时，K，中存在欧拉回路. B. D. A. m为奇数 C. n为奇数 n为偶数 m 为偶数
0101 1 1000 1 5.已知图G的邻接矩阵为 00011, 则G有(). 1 010 1 11110 A.5点，8边 B.6点，7边 C.6点，8边 D.5点，7边 得分 评卷人 二、填空题（每小题3分，本题共15分） 6.设集合A={a,b},那么集合A的幂集是 7.如果R和R2是A上的自反关系，则RUR,R∩R2,R一R,中自反关系有个 8.设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之 变成树. 9.设连通平面图G的结点数为5，边数为6，则面数为一· 10.设个体域D={a,b},则谓词公式(Hx)A(x)∧(3x)B(x)消去量词后的等值式为 得分 评卷人 三、逻辑公式翻译（每小题4分，本题共12分） 11.将语句“如果所有人今天都去参加活动，则明天的会议取消.”翻译成谓词公式. 12.将语句“今天没有人来.”翻译成命题公式. 13.将语句“有人去上课.”翻译成谓词公式. 65
则 G有 ( ). 、一 一 夕 1 子 .. 土 ，.工 ， 土 、 以 1 0 1 0 0 0 5.已知图G的邻接矩阵为 0 0 1 0 1 0 1 1 1 n ︸ 1 1 ︸U l.1 1 1 2 ‘ .l es l l ..es .十 几. t、 .5点，8边 6点 ，8边 B. 6点，7边 D. 5点 ，7边 得 分 评卷人 二、填空题(每小题 3分，本题共 15分) 6.设集合 A= {a, b}，那么集合 A的幂集是 7.如果 R,和 凡 是 A上的自反关系，则 R, UR,,R, nRZ,R,-RZ中自反关系有 个. 8.设图G是有 6个结点的连通图，结点的总度数为 18，则可从G中删去 条边后使之 变成树. 9.设连通平面图 G的结点数为 5，边数为 6，则 面数为 10.设个体域 D={a, b}，则谓词公式(Vx)A(x) A (3x)B(x)消去量词后的等值式为 得 分 评卷人 三、逻辑公式翻译 (每小题 4分 ，本题共 12分) 11.将语句“如果所有人今天都去参加活动，则明天的会议取消.”翻译成谓词公式. 12.将语句“今天没有人来.”翻译成命题公式. 13.将语句“有人去上课.”翻译成谓词公式
得分 评卷人 四、判断说明题（每小题7分，本题共14分】 判断下列各题正误，并说明理由. 14.P(P→Q)VP为永真式. 15.若编序集的哈斯图如图一所示，则集合A的最大元为a,最小元不存在. 图一 得分评卷人 五、计算题（每小题12分，本题共36分）】 G.设樊会A-={1.23,4},R={x,y∈A;|x-y川=1或x-y=0},试 (1)写出P的有序对表示； 2)画出R的关系图： (3,说明R满足自反性，不满足传递性. 1?.求P*QVR的析取范式，合取范式、主析琅范式，主合取范式. 18.设图行=,V={,,,4,5},E={(,2),(,),(2,h). (),(g,),(u,v3),(4,5）},试 (1)画出G的图形表示： (2冫写出其邻接矩阵： (3)求出每个结点的度数： （4,画出蜜G的补图的图形 得 分 评卷人 六、证明题（本题共8分） I9.证明(3x)(P()ARx))=(3x)P(x)∧(3x)R(x) 66
到 · 、 ··说明·(·小·7一“分’ 判断下列各题正误，并说明理由. 14，I'八(尸一‘一，Q) V P为永真式. 15若偏序集的哈斯图如图一所示，则集合 A的最大元为a，最小元不存在. ,0/ :d If “h 图 一 rw万‘爪 二飞 犷一二二二」 五、计“题‘“小“12“ ，本题“36”’ _‘.1_'} S一``:，、二·(1.? 3,4},E==( ix, yEA; Ix-川`1或 X--Y=O，试 〔协写出P.的有序对表示、 _韵画出 R的关系图; .3?说明尺满足 t反4.,不满足传递性. 1, .求产，QV尺的析取范式，合取范式、主析取范式，主合取范式. 18设图 存二，V二 {。:，二:，vg、v,，v5}，E_ {(vi，'v2)，(v;，Z03 )，(。。:，二:，) (:，:、二:) , (}'=}3，二;)，(。、，。;)，(℃;，、，。)}，试 (工)画 七G的 V形表示 : (2l写出I`邻接矩阵; (3)求出辱个结点的度数- t4)画出!1 G约补图的图形 二二 」 六、证明题‘本题”8 5t ) 18.试证明(日:)(rj (;一)八R(二))二、(日二)P(二)八(〕x)R(二) 一得 ︷
试卷代号：1009 中失广播电视大学2007一2008学年度第二学期“开放本科”期未考试（半开卷） 离散数学（本） 试题答案及评分标准 (供参考） 2008年7月 ~、单项是择题（每小题3分，本题共15分） 1.3 2.B 3.A 4.C i.) ”、填空题（每小题3分，本题共15分） 6.{,(a},{b},{a,b}} 7.2 8.4 9.3 i0.(A (u)AA (B))A(B(a)VB(b)) 三、逻辑公式翻译（每小题4分，本题共12分） 11.设P:所有人今天都去参加活动，Q:明天的会议取消， (1分) P-*Q. (4分 2.设P:今天有人来， (1分) P (4分 13.设P(x):x是人，Q(x):x去上课， (分 (3x)(P(x)AQ(x). (4分 四、判断说明题（每小题7分，本题共14分） 14.正确. (2分)》 一PA(P+Q)VP是由一P∧(P→一Q)与P组成的析取式， 如果P的值为真，则P∧(P→Q)VP为真， 5分) 如果P的值为假，则一P与P+一Q为真，即一P∧(P+Q)为其， 也即PA(P+Q)VP为真， 所以PA(P→Q)VP是永真式. (”分) 67
试卷代号:0009 中央广播电视大学2007--2008学年度第二学期“开放本科”期末考试(半开卷) 离散数学(本) 试题答案及评分标准 (供参考) `x_008年 7月 一、单项笼封罪题 (每小题 3分 ，本题共 15分 ) 1. 13 2. 13 3. A 二、填空题(每小题 3分，本题共 15分) 6.{必 ，了a}，{b}，{a,b}} 7.2 8.4 9.3 1 0. (A (a) A A (b))n (B(a) V B(b)) 三、逻辑公式翻译(每小题 4分，本题共 12分) 且.设P.所有人今天都去参加活动，Q:明天的会议取消， 尸一‘Q. 几2.设尸:今天有人来， ，尸. 13.设 P(x):x是人 ，Q(x):x去上课， (3 .x) (P(x) n Q(x)). 四、判断说明题 (每小题 7分，本题共 14分) 14.正确. ，尸八(尸~ ，Q)V尸是由，尸八(尸~ ，Q)与 P组成的析取式， 如果 尸的值为真 ，则 ，尸八(尸~ ，Q)VP为真， 如果 P的值为假 ，则 ，P与 P -. -, Q为真，即 ，PA (1，一，一Q)为真 ， 也 即，尸八(尸一，，Q)V尸为真， 所以一、1'八(I'-}。Q)VP是永真式. (了分、 (4分 (1分) (4分 (‘分 (4分_ (忿分) 分 ) (’分)
另种说明： 一PA(P→一Q)VP是由PA(P+Q)与P组成的析取式， 只要其中一项为真，则整个公式为真. (5分) 可以看到，不论P的值为真或为假，一P∧(P→一Q)与P总有一个为真， 所以P∧(P→一Q)VP是永真式. (7分) 或用等值演算一PA(P→一Q)VP台T 15.正确 (3分) 对于集合A的任意元素x,均有∈R(或xRa),所以a是集合A中的最大元. (5分) 按照最小元的定义，在集合A中不存在最小元。 (7分) 五、计算题（每小题12分，本题共36分） 16.(1)R={,,,,,,, ,,} (3分) (2)关系图为 (6分) (3)因为，，，均属于R,即A的每个元素构成的有序对均 在R中，故R在A上是自反的， (9分) 因有与属于R,但不属于R,所以R在A上不是传递的.(12分) 17.P+(RVQ) 台PV(RVQ) 台一PVQVR(析取、合取、主合取范式) (9分) =(PA-QA-R)V(P∧Q∧R)V(PAQ∧R)V(PAQ∧R)V(PA QAR)V(PAQ∧一R)V(PAQR)(主析取范式) (12分) 18.(1)关系图 (3分) 68
另种说明 : ，尸八(尸、 ，Q)V尸是由，尸八(尸~ 二Q)与 P组成的析取式， 只要其中一项为真，则整个公式为真. (5分) 可以看到，不论 尸的值为真或为假，，尸八(尸~ ，Q)与尸总有一个为真， 所以 ，尸八(P.-.. -,Q)VP是永真式. (7分) 或用等值演算，P A (P-;， Q) V Pt#T 15.正确. (3分) 对于集合 A的任意元素x，均有ER(或 xRa)，所以a是集合A 中的最大元. (5分) 按照最小元的定义，在集合 A中不存在最小元. (7分) 五 、计算题(每小题 12分，本题共 36分 ) 16.(1)R={ ， ， ， ， ，， ， ，， } (3分) (2)关系图为 (6分) (3)因为,,,均属于R，即A的每个元素构成的有序对均 在R中，故R在A上是自反的. (9分) 因有与属于R，但不属于 R，所以R在 A上不是传递的.(12分) 17.P--> (R V Q) 拱 ，PV (RVQ) 娜，尸VQV尺(析取、合取、主合取范式) (9分) a (，P八 ，Q八 ，R) V(，P八 ，QAR) V(，P八Q八R) V (PA ，Q八 -QAR) V (P八Q八，R) V (PAQAR)(主析取范式) 18.0)关系图 二R)V(P八 (12分 ) (只朴
(2)邻接矩阵 r0110 0>》 1 011 0 11011 (6分) 01101 00110 (3)deg(y)=2 deg(2)=3 deg(v3)=4 deg(v)=3 g()=2 (9分) (任图 (12分) 六、证明题（本题共8分）】 19.证明： (1)(3x)(P(x)∧R(x)) (2)P(a)AR(a) ES(1) (2分) (3)P(a) T(2)I (4)(3x)P(x) EG(3) (4分) (5)R(a) T(2)1 (6)(3x)R(x) EG(5) (6分) (7)(3x)P(x)∧(3x)R(x) T(5)(6)1 (8分) 69
(2)邻接矩阵 (6分) (3)deg(v,)=2 deg(VZ)=3 deg(v,)=4 deg(v,)=3 j、9(、、二2 (:;宇象多 (9分) (12分) 六、证明题(本题共8分) 19.证明: (1)(3 x) (P (x) n R(x)) (2) P(a)八R(a) M P(a) (4)(丑x)P(x) (5)R(a) (6)(日x)R(x) (7)(」x)P(x) n(3 x)R(x) ES (1) (2分) T(2 )I EG(3) (4分 ) T(2)1 EG(5) T(5)(6)1 (6分 ) (8分) 69