离散数学10年7月份试题_离散数学1月份试题

离散数学10年7月份试题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学1月份试题”。

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，{2}，{1，2}}，则下列表述正确的是(B)．

A．2AB．{1}AC．1AD．2  A

2．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为

(D)．A．6B．4C．3D．5

3．设无向图G的邻接矩阵为则G的边数为(B)．, A．1B．7C．6D．14 0111

11111 0011000010011010

4．设集合A={a}，则A的幂集为(C)． A．{{a}}B．{a，{a}}C．{，{a}}D．{，a} 5．下列公式中(B)为永真式． A．AB  ABB．AB  (AB)C．AB  ABD．AB  (AB)

二、填空题（每小题3分，本题共15分）

6．命题公式PP的真值是假（或F，或0）．7．若无向树T有5个结点，则T的边数为

8．设正则m叉树的树叶数为t，分支数为i，则(m-1)it

9．设集合A={1，2}上的关系R＝{,}，则在R中仅需加一个元素，就可使新得到的关系为对称的．10．(x)(A(x)→B(x，z)∨C(y))中的自由变元有z，y．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“今天上课．”翻译成命题公式．

设P：今天上课，则命题公式为：P．

12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．

设 P：他去操场锻炼，Q：他有时间，则命题公式为：P Q．

四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．

13．设集合A={1，2}，B={3，4}，从A到B的关系为f={}，则f是A到B的函数．

错误． 因为A中元素2没有B中元素与之对应，故f不是A到B的函数．

14．设G是一个有4个结点10条边的连通图，则G为平面图．

错误．不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．

五．计算题（每小题12分，本题共36分）

15．试求出（P∨Q）→（R∨Q）的析取范式．

（P∨Q）→（R∨Q） ┐(P∨Q)∨（R∨Q）

(┐P∧┐Q)∨（R∨Q）

(┐P∧┐Q)∨R∨Q（析取范式）

16．设A={{1}, 1, 2}，B={ 1, {2}}，试计算

（1）A∩B（2）A∪B（3）A （A∩B）．

（1）A∩B={1}（2）A∪B={1, 2, {1}, {2}}（3）A（A∩B）={{1}, 1, 2}

17．图G=，其中V={ a, b, c, d }，E={(a, b),(a, c),(a, d),(b, c),(b, d),(c, d)}，对应边的权值依次为1、2、3、1、4及5，试

（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值． 3（1）G的图形表示如图一所示：ad

01111011110111 5 11 51 b c1 0b c 图二 a 3d（2）邻接矩阵：图一

（3）最小的生成树如图二中的粗线所示：权为：1+1+3=5

六、证明题（本题共8分）

18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．

证明：设xA，因为R自反，所以x R x，即R；

又因为S自反，所以x R x，即S．

即R∩S

故R∩S自反．