离散数学2009-2010第一学期期末试卷及参考答案解析

《离散数学2009-2010第一学期期末试卷及参考答案解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：华东交通大学2009—2010学年第一学期考试卷　　　　　　　　　　　　　　　　　　　　试卷编号：　　　　（A）卷离散数学课程课程类别：必修考试日期：月日开卷(范围：可带含课程内容的手写的不超过A4大小的纸一张）题号一二三四五六七八九总分累分人签名题分100得分注意事项：1、本试卷共8页（其中试题4页），总分　100　分，考试时间　120　分钟。2、所有答案必须填在答题纸上，写在试卷上无

2、效；3、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、单项选择题（2分×10=20分）1．下列语句是命题的有[B]。A.；B.2010年的国庆节是晴天；C.青年学生多么朝气蓬勃呀！D.学生不准吸烟!4.与命题pÙ(pÚq)等值的公式是[  A ]。  A.p；  B.q；  C.pÚq；  D.pÙq.5.设M={a,b,c}，M上的等价关系R={,,,,}确定的集合M的划分是[D]。A.{{a},{b},{c}}B.{{a,c},{b,c}}C.{{a,c},{b}}D.{{a},{b,c}}6.设D：全总个体

3、域，F(x)：x是花，M(x)：x是人，H(x,y)：x喜欢y，则命题“每个人都喜欢某种花”的逻辑符号化为[C]。12A.；B.；C.；D..7.下列图中，不是哈密顿图的为[A]。·ABCD8.下列四组数据中，能作为某个4阶无向简单图的度序列的为[ D ]。 A.1,2,3,4 ；     B.2,2,2,3；C.  1,1,2,3；    D.1,1,1,3.10.下列选项中与A∪B=A等价的是_____B_______。A．A∩B=A　B．BÍA　C．A∪B=BD．A－B＝Φ10.设为连通的无向图，若仅有个结点的度数是奇数，则一定具有（）A、欧拉路径；B、欧拉回路；C

4、、哈密尔顿路径；D、哈密尔顿回路。二、填空题（2分×10=20分）2.设p：我努力学习，q：我取得好成绩，命题“除非我努力学习，否则我不能取得好成绩。”的符号化形式为Øp→Øq或q→p。3.设解释I如下，个体域D={1,2}，F(1,1)=(2,2)=0，F(1,2)=F(2,1)=1，在解释I下，$xF(x,2) 的真值为1或真。4.谓词公式$xF(x)∧$xG(x)的前束范式为$x$y(F(x)∧G(y))。1.谓词公式的前束范式是___________。6.等价关系满足自反性、对称性和传递性三个性质。128.无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为偶数

5、。9.设A为集合，且

6、A

7、=3，则A上最多可定义29或512个不同的二元关系。7一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有＿＿2（x2+1）＿＿个度数为1的结点。1.用谓词逻辑把下列命题符号化a)有些实数不是有理数三、综合题（第1、2题每题10分，其余每题8分，共60分）1.构造下面推理的证明：（10分）前提：p→(qÚr)，Øs→Ør，pÙØs；结论：q.证明：①pÙØs前提引入②p①化简③p→(qÚr)前提引入④qÚr②③假言推理⑤Øs→Ør前提引入⑥Øs①化简⑦Ør⑤⑥假言推理⑧q④⑦析取三段论122.求公式(p→q)Ù(q→r)的主析取范式

8、、主合取范式、成真赋值。（10分）解：(p→q)Ù(q→r)Û(ØpÚq)Ù(ØqÚr)Û((ØpÚq)Ú(rÙØr))Ù((pÚØp)(ØqÚr))Û(ØpÚqÚr)Ù(ØpÚqÚØr)Ù(pÚØqÚr)Ù(ØpÚØqÚr)ÛM4ÙM5ÙM2ÙM6Û∏(2,4,5,6)Û∑(0,1,3,7)公式(p→q)Ù(q→r)的主析取范式为：∑(0,1,3,7)主合取范式为：∏(2,4,5,6)公式(p→q)Ù(q→r)的成真赋值为：000，001，011，1113.设集合A={a,b,c,d}，R是A上的二元关系，R={,,,}；(8分)

9、（1）画出R的关系图；（2）求R2；（3）求出R的自反闭包r(R)、对称闭包s(R)。解：（1）关系图如右图：（2）R2={，，，}12（3）r(R)=R∪IA={,,,,,,,}s(R)=R∪R–1={,,,,,}4.设S={1,2,3,4,6,8,12}，“”为S上的整除关系。（8分）问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元