资源描述：
《电大历年离散数学试题汇总》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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∧
