离散数学（本）2016年10月份试题
一、单项选择题（每小题3分，本题共15分）
1．若集合A＝{1,2,3,4}，则下列表述不正确的是 ( )． A．1?A B．{1,2,3}?A
C．{1,2,3}?A D．? ?A
2．设A＝｛1, 2, 3｝，B={1, 2, 3, 4}，A到B的关系R＝｛〈x, y〉|x=y｝，则R为 ( ) ． A. {<1, 2>, <2, 3>} B. {<1, 1>, <1, 2>, <1, 3>, <1, 4>, <1, 5>} C. {<1, 1>, <2, 1>} D. {<1, 1>, <2, 2>, <3, 3 >} 3．无向图G的边数是10，则图G的结点度数之和为（ ）． A. 10 B. 20 C. 30 D. 5
4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．r + v - e =2 B．v + e - r=4 C．v + e – r = – 4 D．v + e - r=2
5．设个体域D是整数集合，则命题?x?y (x = y+2)的真值是（ ）． A. 不确定 B. T C. 由y的取值确定 D. F
二、填空题（每小题3分，本题共15分）
6．设集合A={a, b, c}，B={b, c, d }，C={c, d, e}，则(B?C) – A等于 ． 7．设A={2, 3}，B={1, 2}，C={3, 4}，从A到B的函数f={<2, 2>, <3, 1>}，从B到C的函数g={<1，3>, <2，4>}，则Dom(g? f)等于 ．
8．若图G=
9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为6，则在G -S中的连通分支数不超过 ．
10．设个体域D＝{1,2, 3, 4}，A(x)为“x小于10”，则谓词公式(?x)A(x)的真值为 ．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“小明是学生，小张是飞行员．”翻译成命题公式．
12．将语句“当大家都进入教室，则讨论会开始进行．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．空集的幂集是空集．
14．(?x)(P(x)→Q(y)∨R(z))中的约束变元有x与y．
五．计算题（每小题12分，本题共36分）
15．设A={1, 2, 3}，R={
16．图G=
1
e) , (d, e)}，对应边的权值依次为2、3、4、5、6、7，6及2，试
（1）画出G的图形； （2）写出G的邻接矩阵；
（3）求出G权最小的生成树及其权值．
17．试画一棵带权为1, 2, 4, 5, 6的最优二叉树,并计算该最优二叉树的权．
六、证明题（本题共8分）
18．试证明：P→Q ? P→（? (?P∨?Q)）．
2
离散数学（本）2016年10月份试题
参考解答
一、单项选择题（每小题3分，本题共15分） 1．C 2．D 3．B 4．A 5．B
二、填空题（每小题3分，本题共15分） 6．{d} 7．{2，3} 8．(b, c) 9．6
10．真（或T，或1）
三、逻辑公式翻译（每小题6分，本题共12分）
11．设P：小明是学生， Q：小张是飞行员． 则命题公式为： P∧Q． 12．设P：大家都进入教室， Q：讨论会开始进行． 则命题公式为：P→Q．
四、判断说明题（每小题7分，本题共14分）
13．错误． 空集的幂集不为空，为{?} 14．错误． 约束变元仅有x．
五．计算题（每小题12分，本题共36分）
15．解：R={<1,3>,<2,2>,<3,1>} S={<1,1>,<2,2>,<3,3>} R-1={<3,1>,<2,2>,<1,3>} r(S)={ <1,1>,<2,2>,<3,3>} 说明：对于每一个求解项，如果基本求出了解，可以给对应1分．16．解：（1）G的图形表示为：
3
2分） （6分）
（2分）
（6分） （3分）
（7分） （3分） （7分） （3分） （6分） （9分）
12分） （3分） （ （