离散数学（本）2016年10月份试题

离散数学（本）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=，其中V={ a, b, c, d }，E={ (a, b), (a, d), (b, c), (b, d)}，则该图中的割边为 ．

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={|x?A，y?A且x+y=4}，S={|x?A，y?A且x=y}，试求R，S，R-1，r(S)．

16．图G=，其中V={ a, b, c, d, e }，E={ (a, b), (a, c) , (a, d), (b, c) , (b, d) , (c, d) , (c,

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

本文来源：https://www.bwwdw.com/article/zjt2.html