《离散数学(本科)》2018期末试题及答案

PAGEPAGE4《离散数学(本科)》2018期末试题及答案一、单项选择题（每小题3分，本题共15分）1．若集合A={1，{2}，{1，2}}，则下列表述正确的( A．2A B．{1}AC．1A D．2A2．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．A．6 B．4 C．3 3G的邻接矩阵为则G的边数( )．

0 11 01 01 11

1 1 10 1 10 0 00 0 10 1 0A．1 B．7 C．6 4．设集合A={a}，则A的幂集( )．A．{{a}} B．{a，{a}}C．{，{a}} D．{，a}下列公式中( 为永真式．A．ABAB B．AB(AB)C．ABAB D．AB(AB)二、填空题（315分）命题公式PP的真值．若无向树T有5个结点，则T的边数．设正则m叉树的树叶数为t，分支数为则(m-1)i= ．9．设集合A={1，2}上的关系R＝{<1,1>,<1,2>}，则在R 中仅需加一个素 ，就可使新得到的关系为对称的．10．(x)(A(x)→B(x，z)∨C(y))中的自由变元．三、逻辑公式翻译（每小题6分，本题共12分）将语句“今天上课．”翻译成命题公式．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．四、判断说明题（714分判断下列各题正误，并说明理由．13A={1，2}，B={3，4}ABf={<1,3>}fAB的函数．G410G为平面图．五．计算题（每小题12分，本题共36分）试求出的析取范式．16．设A={{1},1,2}，B={1,{2}}，试计算（1）（A∩B） （2）（A∪B） （3）A （A∩B）．17．图G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}，对应边的权值依次为1、2、3、1、4及5，试G的图形；G的邻接矩阵；G权最小的生成树及其权值．六、证明题（本题共8分）18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．试题解答一、单项选择题（每小题3分，本题共15分）1．B 2．D 3．B 4．C 二、填空题（315分）6．假（或0）7．48．t-19．<2,1>10．z，y三、逻辑公式翻译（每小题6分，本题共12分）11．设P：今天上课，（2分）则命题公式为：P．（6分）12．设P：他去操场锻炼，Q：他有时间，（2分）则命题公式为：PQ．（6分）四、判断说明题（每小题7分，本题共14分）13．错误．（3分）因为A中元素2没有B中元素与之对应，故f不是A到B的函数．（7分）14．错误．（3分）不满足“设G是一个有v个结点e条边的连通简单平面图，若≥，则≤-（7分）五．计算题（每小题12分，本题共36分）15P）→∨┐PQ∨RQ） （4分）(┐P∧┐Q)∨（R∨Q） （8分）(┐P∧┐Q)∨R∨Q（析取范式） （12分）（4分）（2）（A∪B）={1,2,{1},{2}} （8分）（3）1,2} （12分）17．（1）G的图形表示如图一所示：a 3 d2 41 5 b 1 c图一 （3分）

0 10101 111

1 11 1 （6分）0 1001 最小的生成树如图二中的粗线所示：a 3 d2 41 51

（10