资源描述:
《电大历年离散数学试题汇总》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、计算机科学与技术专业级第二学期离散数学试题2012年1月一、单项选择题(每小题3分,本题共15分)1.C2.C3.B4.A5.D1.若集合A的元素个数为10,则其幂集的元素个数为().A.10B.100C.1024D.12.设A={a,b},B={1,2},R1,R2,R3是A到B的二元关系,且R1={,},R2={,,},R3={,},则()是从A到B的函数.A.R1和R2B.R2C.R3D.R1和R33.设A={1,2,3,4,5,6,7,8},R是A
2、上的整除关系,B={2,4,6},则集合B的最大元、最小元、上界、下界依次为().A.8、2、8、2B.无、2、无、2C.6、2、6、2D.8、1、6、14.若完全图G中有n个结点(n≥2),m条边,则当()时,图G中存在欧拉回路.A.n为奇数B.n为偶数C.m为奇数D.m为偶数5.已知图G的邻接矩阵为则G有().A.6点,8边B.6点,6边C.5点,8边D.5点,6边二、填空题(每小题3分,本题共15分)6.设集合A={a},那么集合A的幂集是{Æ,{a}}.7.若R1和R2是A上的对称关系,则R1∪R2,R1∩R2,R1
3、-R2,R2-R1中对称关系有4个.8.设图G是有5个结点的连通图,结点度数总和为10,则可从G中删去1条边后使之变成树.9.设连通平面图G的结点数为5,边数为6,则面数为3.10.设个体域D={a,b},则谓词公式("x)(A(x)∧B(x))消去量词后的等值式为(A(a)∧B(b))∧(A(a)∧B(b)).三、逻辑公式翻译(每小题6分,本题共12分)11.将语句“今天有联欢活动,明天有文艺晚会.”翻译成命题公式.设P:今天有联欢活动,Q:明天有文艺晚会,(2分)P∧Q.(6分)12.将语句“如果小王来,则小李去.”翻译
4、成命题公式.设P:小王来,Q:小李去(2分)P→Q.(6分)四、判断说明题(每小题7分,本题共14分)ooooabcd图一判断下列各题正误,并说明理由.13.若偏序集的哈斯图如图一所示,则集合A的最大元为a,极小元不存在.错误.(3分)对于集合A的任意元素x,均有ÎR(或xRa),所以a是集合A中的最大元.(5分)但按照极小元的定义,在集合A中b,c,d均是极小元.(7分)14.┐P∧(P→┐Q)∨P为永假式.错误.(3分)┐P∧(P→┐Q)∨P是由┐P∧(P→┐Q)与P组成的析取式,如果P的值为真,则┐
5、P∧(P→┐Q)∨P为真,(5分)如果P的值为假,则┐P与P→┐Q为真,即┐P∧(P→┐Q)为真,也即┐P∧(P→┐Q)∨P为真,所以┐P∧(P→┐Q)∨P是永真式.(7分)另种说明:┐P∧(P→┐Q)∨P是由┐P∧(P→┐Q)与P组成的析取式,只要其中一项为真,则整个公式为真.(5分)可以看到,不论P的值为真或为假,┐P∧(P→┐Q)与P总有一个为真,所以┐P∧(P→┐Q)∨P是永真式.(7分)或用等价演算┐P∧(P→┐Q)∨PÛT五.计算题(每小题12分,本题共36分)15.设集合A={1,2,3,4},R={
6、
7、x,yÎA;
8、x-y
9、=1或x-y=0},试(1)写出R的有序对表示;(2)画出R的关系图;(3)说明R满足自反性,不满足传递性.15.(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}(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分)
10、16.设图G=,V={v1,v2,v3,v4,v5},E={(v1,v2),(v1,v3),(v2,v4),(v3,v5),(v4,v5)},试(1)画出G的图形表示;(2)写出其邻接矩阵;oooov1v2v3v4图三v5o(3)求出每个结点的度数;(4)画出图G的补图的图形.16.(1)关系图如图三:(3分)(2)邻接矩阵(6分)(3)deg(v1)=2deg(v2)=2deg(v3)=2deg(v4)=2oooov1v2v3v4图四v5odeg(v5)=2(9分)(4)补图如图四(12分)17.求P®Q∧R的合
11、取范式与主析取范式.P→(R∧Q)Û┐P∨(R∧Q)(4分)Û(┐P∨Q)∧(┐P∨R)(合取范式)(6分)P→(R∧Q)Û┐P∨(R∧Q)Û(┐P∧(┐Q∨Q))∨(R∧Q)(7分)Û(┐P∧┐Q)∨(┐P∧Q)∨(R∧Q)(8分)Û((┐P∧┐Q)∧(┐R∨R))∨(┐P∧Q)∨(R∧