离散数学201207试题

1试卷代号：1009座位号中央广播电视大学学年度第学期期末考试计算机科学与技术专业级第二学期离散数学试题2012年7月题号一二三四五六总分得分一、单项选择题（每小题3分，本题共15分）1．若集合A＝{{a}}，则下列表述正确的是()．A．{a}AB．{a}AC．aAD．A2．若a是图G的割点，则以下说法正确的是()．A．{a}不是点割集B．删除a点，G仍连通C．{a,b}可以是点割集D．删除a点，则G不连通3．无向树T有5条边，则T的结点数为()．A．4B．5C．6D．74．命题公式P的合取范式是()A．PB．（P∧P）∨（P∨P）C．P∧PD．（P∧P）5．下列公式成立的为()．A．P∧QP∨QB．PQPQC．PPD．P∧(P∨Q)Q二、填空题（每小题3分，本题共15分）6．设集合A={1,2,3}，B={2,3,4,5,6}，R是A到B的二元关系，},{yxByAxyxR且且则R的有序对集合为．7．如果R是非空集合A上的等价关系，aA，bA，a,bR，则可推知R中至少包含等元素．8．设G＝V,E是有6个结点，9条边的无向连通图，则从G中删去条边，可以确定图G的一棵生成树．9．设G是具有n个结点m条边k个面的连通平面图，则m等于．10．设个体域D＝{1,2}，A(x)为“x大于2”，则谓词公式()()xAx的真值为．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“如果今天天晴，则后天上课．”翻译成命题公式．212．将语句“41次列车下午五点开或者六点开．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．若a为偏序集A，R的最大元，则a一定不为偏序集A，R的最小元．14．如果图G是无向连通图，则图G是欧拉图．五．计算题（每小题12分，本题共36分）15．设集合A={{1},1}，B={{1}}，试计算（1）（AB）；（2）（A∩B）；（3）A×B．16．设G=V，E，V={v1，v2，v3，v4}，E={(v1,v3)，(v2,v3)，(v3,v4)}，试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形．17．设谓词公式),,()(),()(zyxQzyxPx，试（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元．六、证明题（本题共8分）18．设A，B是任意集合，试证明：若A=B，则AA=BB．3中央广播电视大学学年度第学期期末考试计算机科学与技术专业级第二学期离散数学试题解答(供参考)一、单项选择题（每小题3分，本题共15分）1．B2．D3．C4．A5．C二、填空题（每小题3分，本题共15分）6．{2,2，3,3}7．a,a，b,b，a,b，b,a8．49．n+k210．假（或F，或0）三、逻辑公式翻译（每小题6分，本题共12分）11．设P：今天天晴，Q：后天上课．（2分）则命题公式为：PQ．（6分）12．设P：41次列车下午五点开，Q：41次列车下午六点开，（2分）则命题公式为：（P∧Q）∨（P∧Q）．(或PQ)（6分）四、判断说明题（每小题7分，本题共14分）13．错误．（3分）a可以既为偏序集A，R的最大元，也为最小元，如图一：（7分）14．错误．（3分）当图G结点度数有为奇数时，图G不是欧拉图．（7分）五．计算题（每小题12分，本题共36分）15．（1）AB={1}（4分）（2）A∩B={{1}}（8分）（3）A×B={{1},{1}，1,{1}}（12分）16．（1）G的图形表示为(如图二)：（3分）a图一v1v2v3v4图二4（2）邻接矩阵：0010001011010010（6分）（3）v1，v2，v3，v4结点的度数依次为1，1，3，1（9分）（4）补图如图三所示：（12分）17．（1）x量词的辖域为),(yxP，（3分）z量词的辖域为),,(zyxQ,（6分）（2）自由变元为公式中的y与),,(zyxQ中的x，（9分）约束变元为),(yxP的x与),,(zyxQz．（12分）六、证明题（本题共8分）18．证明：设x，yAA，则xA，yA（1分）因为A=B，则有xB，yB，（3分）所以x，yBB，即有AABB．（5分）设x，yBB，则xB，yB，（6分）因为A=B，故xA，yA，（7分）所以x，yAA，即有BBAA．故得AA=BB．（8分）v1v2v3v4图三