离散数学（本）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分） （ （
?0?1?（2）邻接矩阵： ?1??1??01110?0110??1011? （6分）
?1101?0110??（3）粗线表示的图是最小生成树，
（10分）
权值为11 （12分） 17．解： 18 ?
7
? 11 ?
3 ? ? ? ? 6 4 5 ? ? （10分）
1 2
权为1?3+2?3+4?2+5?2+6?2=39． （12分）
六、证明题（本题共8分） 18．证明：
（1）P→Q P （1分） （2）P P（附加前提） （3分） （3）Q T（1）（2）I （5分） （4）P∧Q T（2）（3）I （6分） （5）? (?P∨?Q) T（4）E （7分） （6）P→? (?P∨?Q) CP规则 （8分） 另证：
设P→（? (?P∨?Q)）为F， （1分） 则P为T，? (?P∨?Q)为F， （3分） 即P∧Q为F． （4分） 所以P为T，Q为F ， （5分） 从而P→Q也为F． （6分） 所以P→Q?P→(? (?P∨?Q))． （8分）
说明：1、因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分。
另，可以用真值表验证。
4
离散数学（本）2016年7月份试题
一、单项选择题（每小题3分，本题共15分）
1．若集合A＝{1,2,3,4}，B＝{1,3,5}，则下列表述正确的是 ( )． A．A＝B B．B ?A
C．B ?A D．B ? A
2．设A＝｛1,2,3｝，B={2,4,6}，A到B的关系R＝｛〈x, y〉| 2x=y｝，则R= ( )． A. {<1,3>,<2,4>,<3,5>} B. {<2,1 >,<4,3>,<6,5>} C. {<1,1>,<2,2>,<3,3>} D. {<1,2>,<2,4>,<3,6>} 3．无向图G是棵树，边数是10，则G的结点度数之和是（ ）． A. 20 B. 9 C. 10 D. 11
4．下面的推理正确的是（ ）．
A．(1) （?x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）． B．(1) （?x）F（x）→G（x） 前提引入
(2) F（y）→G（y） US（1）．
C．(1) （?x）(F（x）→G（x）） 前提引入 (2) F（y）→G（x） ES（1）．
D．(1) （?x）（F（x）→G（x）） 前提引入 (2) F（y）→ G（y） US（1）．
5．设个体域为整数集，则公式?x?y(x+y=2)的解释可为 ( )．
A. 任一整数x，对任意整数y满足x+y=2 B. 对任一整数x，存在整数y满足x+y=2 C. 存在一整数x，对任意整数y满足x+y=2 D. 存在一整数x，有整数y满足x+y=2
二、填空题（每小题3分，本题共15分）
6．设集合A={1, 2, 3}，B={2, 3, 4}，C={3, 4, 5}，则B∪(A–C)等于 ． 7．设A={1, 2}，B={2, 3}，C={3，4}，从A到B的函数f ={<1, 2>, <2, 3>}，从B到C的函数g={<2, 3>, <3, 4>}，则Ran(g? f)等于 ．
8．两个图同构的必要条件包括结点数相等、边数相等与 ． 9．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，v值为5，e值为4则r的值为 ．
10．设个体域D＝{1, 2, 3, 4}，则谓词公式(?x)A(x)消去量词后的等值式为 ．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“昨天下雨，今天仍然下雨．”翻译成命题公式． 12．将语句“若不下雨，我们就去参加比赛．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．若图G是一个欧拉图，则图G中存在欧拉路．
5
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学(本)2016年10月份试题在线全文阅读。
相关推荐：