离散数学(本)2017年3月份试题

离散数学（本）2017年1月份试题

一、单项选择题（每小题3分，本题共15分） 1．若集合A＝{1,2,3}，则下列表述不正确的是 ( )． A．2?A B．{1, 2}?A

C．{1, 2}?A D．??A

2．设A={1, 2, 3｝，B ={1, 2, 3, 4}，A到B的关系R ={ | x大于y｝，则R = ( )． A．{<1, 1>, <2, 1>} B．{<1, 1>, <1, 2>, <1, 3>, <1, 4>} C．{<2, 1>, <3, 1>, <3, 2 >} D．{<1, 2>, <2, 3>} 3．无向图G的结点的度数之和是20，则图G的边数为（ ）． A．20 B．10 C．21 D．19

4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．r + v - e =2 B．v + e - r=4 C．v + e - r=2 D．v + e – r = – 4

5．设个体域D是实数集合，则命题(?x)(?y)(x?y = y)的真值是（ ）． A．不确定 B． F C．由y的取值确定 D．T

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

6．设集合A={a, b, c}，B={b, c}，C={c, d}，则A–(B?C)等于 ． 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．结点数相等与边数相等是两个图同构的 条件． 9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为4，则在G -S中的连通分支数不超过 ．

10．设个体域D＝{a, b, c}，则谓词公式(?x)P(x)消去量词后的等值式为 ．

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

11．将语句“小李前天去工厂劳动，昨天休息．”翻译成命题公式． 12．将语句“如果他去开会，则我去开会．”翻译成命题公式．

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

13．集合的元素可以是集合．

14．(?x)(P(x)→Q(y)∧R(z))中的约束变元为y．

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

15．设A={1，2，3}，R={|x?A，y?A且x +y >4}，S={|x?A，y?A且x

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

1

(b, d), (b, e), (c, e), (d, e) }，对应边的权值依次为1、1、3、2、3、6、1及5，请画出G的图形、写出G的邻接矩阵并求出G权最小的生成树及其权值．

17．画一棵带权为2, 2, 2, 3, 4的最优二叉树, 并计算该最优二叉树的权．

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

18．试证明：P→Q ? P→(P∧Q) ．

2

离散数学（本）2017年3月份试题解答

(供参考)

一、单项选择题（每小题3分，本题共15分） 1．D 2．C 3．B 4．A 5．D 二、填空题（每小题3分，本题共15分） 6．{ a, b } 7．{2，3} 8．必要 9．4

10．P(a ) ∨P(b) ∨ P(c)

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

11．设P：小李前天去工厂劳动，Q：小李昨天休息． 则命题公式为： P∧Q． 12．设P：他去开会， Q：我去开会． 则命题公式为：P→Q． 四、判断说明题（每小题7分，本题共14分）

13．正确． 例：集合{{1}}中的元素{1}是集合． 说明：举出符合条件的例均给分．

14．错误． (?x)(P(x)→Q(y)∧R(z))中的y是自由变元，约束变元为x． 五．计算题（每小题12分，本题共36分） 15．

R={<2, 3>, <3, 2>, <3, 3>} S={<1, 2>, <1, 3>, <2, 3>} R-1={<2, 3>, <3, 2>, <3, 3>} s(S)={ <1, 2>, <1, 3>, <2, 3>, <2, 1>, <3, 1>, <3, 2>} 说明：对于每一个求解项，如果基本求出了解，可以给对应1分． 16．解：G的图形表示为：

邻接矩阵：

3

（2分） （6分）

（2分）

（6分） （3分）

（7分）

（3分） （7分） 3分） 6分） 9分）

12分） （3分） （ （ （ （

（6分）

粗线表示最小的生成树：

17．

（9分）

权为6 （12分）

（10分）

权为2?3+2?3+2?2+3?2+4?2=30 （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 （7分） （5）P→(P∧Q) CP规则 （8分）

说明：1．因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分． 说明：2．另证如下：

设P→(P∧Q)为F， （1分） 则P为T，P∧Q为F． （3分） 所以P为T，Q为F ， （5分） 从而P→Q也为F． （7分） 所以P→Q?P→(P∧Q)． （8分） 说明3：可以用真值表验证．

4

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学(本)2017年3月份试题在线全文阅读。