电大历年离散数学试题汇总

计算机科学与技术专业级第二学期离散数学试题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={a，2,a，1}，R2={a，1,a，2,b，1}，R3={a，1,b，2}，则（）是从A到B的函数．A．R1和R2B．R2C．R3D．R1和R33．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，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-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．将语句“如果小王来，则小李去．”翻译成命题公式．设P：小王来，Q：小李去（2分）P→Q．（6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．若偏序集A，R的哈斯图如图一所示，则集合A的最大元为a，极小元不存在．错误．（3分）对于集合A的任意元素x，均有x,a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的值为真，则┐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={x,y|x,yA；|xy|=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分）abcd图一16．设图G=V，E，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v4)，(v3,v5)，(v4,v5)}，试(1)画出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出图G的补图的图形．16．（1）关系图如图三：（3分）（2）邻接矩阵0110010010100010100100110（6分）（3）deg(v1)=2deg(v2)=2deg(v3)=2deg(v4)=2deg(v5)=2（9分）（4）补图如图四（12分）17．求PQ∧R的合取范式与主析取范式．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∧Q)（9分）(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q)∨(R∧Q)（10分）(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨((┐P∧Q)∧(┐R∨R))∨(R∧Q)(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)∨(R∧Q)(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)∨((┐P∨P)∧(R∧Q))(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨v1v2v3v4图三v5v1v2v3v4图四v5(┐P∧Q∧R)∨(P∧R∧Q)（主析取范式）（12分）说明：此题解法步骤多样，若能按正确步骤求得结果，均可给分．六、证明题（本题共8分）18．设连通无向图G有14条边，3个4度顶点，4个3度顶点，其它顶点的度数均小于3，试说明G中可能有的顶点数．证明：可利用数列可图化及握手定理解答顶点度数和为214=28，（2分）28-（34+43）=4，则知其他顶点度数和为4，（4分）对于有限图，若无零度顶点，则除4度及3度顶点外，可能的顶点情况有：2个2度点；1个2度点和2个1度点；4个1度点，（6分）即对应图的顶点数分别至少为9、10、11．（8分）2011年7月一、单项选择题（每小题3分，本题共15分）1．A2．C3．C4．D5．B1．若集合A={1，{1}，{2}，{1，2}}，则下列表述正确的是()．A．{2}AB．{1，2}AC．1AD．2A2．设G为无向图，则下列结论成立的是()．A．无向图G的结点的度数等于边数的两倍．B．无向图G的结点的度数等于边数．C．无向图G的结点的度数之和等于边数的两倍．D．无向图G的结点的度数之和等于边数．3．图G如图一所示，以下说法正确的是()．A．{(a，b)}是边割集B．{a，c}是点割集C．{d}是点割集D．{(c，d)}是边割集图一4．设集合A={1}，则A的幂集为()．A．{{1}}B．{1，{1}}C．{，1}D．{，{1}}5．设A(x)：x是人，B(x)：x犯错误，则命题“没有不犯错误的人”可符号化为（）．A．┐(x)(A(x)→┐B(x))B．┐(x)(A(x)∧┐B(x))C．┐(x)(A(x)∧B(x))D．(x)(A(x)∧B(x))二、填空题（每小题3分，本题共15分）6．命题公式PP的真值是真（或T，或1）．7．若无向图T是连通的，则T的结点数v与边数e满足关系v=e+1时，T是树．8．无向图G是欧拉图的充分必要条件是G是连通的且结点度数都是偶数．9．设集合A={1，2}上的关系R＝{2,2,1,2}，则在R中仅需加入一个元素1,1，abcdef就可使新得到的关系为自反的．10．(x)(P(x)→R(y)∨S(z))中的约束变元有x．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“雪是黑色的．”翻译成命题公式．设P：雪是黑色的，（2分）则命题公式为：P．（6分）12．将语句“如果明天下雨，则我们就在室内上体育课．”翻译成命题公式．设P：如果明天下雨，Q：我们在室内上体育课，（2分）则命题公式为：PQ．（6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．设集合A={1，2}，B={3，4}，从A到B的关系为f={1,3，1,4}，则f是A到B的函数．错误．（3分）因为A中元素1有B中两个不同的元素与之对应，故f不是A到B的函数．（7分）14．设G是一个连通平面图，有5个结点9条边，则G有6个面．正确．（3分）因G是一个连通平面图，满足欧拉定理，有v-e+r=2，所以r=2-（v-e）=2-（5-9）=6（7分）五．计算题（每小题12分，本题共36分）15．试求出P→（R∧Q）的合取范式．P→（R∧Q）┐P∨（R∧Q）（6分）(┐P∨R)∧（┐P∨Q）（合取范式）（12分）16．设A={{1},{1,2}，1}，B={1,2,{2}}，试计算（1）（A∩B）（2）（A∪B）（3）（A∩B）A．（1）（A∩B）={1}（4分）（2）（A∪B）={1,2,{1},{2},{1,2}}（8分）（3）（A∩B）A=（12分）17．试画一棵带权为2,3,3,4,5,的最优二叉树,并计算该最优二叉树的权．最优二叉树如图二所示．（10分）图二权为23+33+32+42+52=39（12分）六、证明题（本题共8分）18．试证明：若R与S是集合A上的对称关系，则R∩S也是集合A上的对称关系．证明：设x，yA，因为R对称，所以若x,yR，则y,xR．（2分）因为S对称，所以若x,yS，则y,xS．（4分）于是若x,yR∩S则x,yR且x,yS23345510717即y,xR且y,xS（6分）也即y,xR∩S，故R∩S是对称的．（8分）中央广播电视大学2010—2011学年度第一学期“开放本科”期末考试离散数学（本）试题2011年1月一、单项选择题（每小题3分，本题共15分）1．A2．D3．B4．D5．C1．若集合A＝{a，{1}}，则下列表述正确的是()．A．{1}AB．{1}AC．{a}AD．A2．设图G＝V,E，vV，则下列结论成立的是()．A．deg(v)=2EB．deg(v)=EC．EvVv)deg(D．EvVv2)deg(3．如图一所示，以下说法正确的是()．A．(e,c)是割边B．(d,e)是割边C．(b,a)是割边D．(b,c)是割边4．命题公式（P∨Q）的合取范式是()．A．PB．（P∧Q）C．（P∨P）D．（P∨Q）5．下列等价公式成立的为()．A．PQPQB．QPPQC．PPQQD．PPQ二、填空题（每小题3分，本题共15分）6．设集合A={0,1,2}，B={1,2,3,4,}，R是A到B的二元关系，},,{BAyxByAxyxR且且则R的有序对集合为{1,1，1,2，2,1，2,2}．7．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2．8．设G＝V,E是有20个结点，25条边的连通图，则从G中删去6条边，可以确定图G的一棵生成树．9．无向图G存在欧拉回路，当且仅当G所有结点的度数全为偶数且连通．10．设个体域D＝{1,2}，则谓词公式)(xxA消去量词后的等值式为A(1)A(2)．abcd图一e三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“如果小李学习努力，那么他就会取得好成绩．”翻译成命题公式．12．将语句“小张学习努力，小王取得好成绩．”翻译成命题公式．11．设P：小李学习努力，Q：小李会取得好成绩，（2分）PQ．（6分）12．设P：小张学习努力，Q：小王取得好成绩，（2分）PQ．（6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．如果R1和R2是A上的自反关系，则R1R2是自反的．14．