华南理工大学网络教育学院

2015–2016学年度第一学期期末考试 《 离散数学 》试卷（模拟卷2）

教学中心： 专业层次：

学 号： 姓 名： 座号： 注意事项：1. 本试卷共 三 大题，满分100分，考试时间90分钟，闭卷；

2. 考前请将以上各项信息填写清楚；

3. 所有答案必须做在答题纸上,做在试卷、草稿纸上无效； 4．考试结束，试卷、答题纸、草稿纸一并交回。

一、单项选择题（本大题30分，每小题6分） A CABC 1 A．如果天气好，那么我去散步。 B．天气多好呀！

C．x=3。 D．明天下午有会吗？ 在上面句子中( )是命题

2．设个体域为整数集，下列真值为真的公式是( ) A．?y?x (x – y =2) B．?x?y(x – y =2) C．?x?y(x – y =2) D．?x?y(x – y =2)

3. 设A={0，1}，B={1，2}，则A×{1}×B=( )

A．{<0，1，1 >，<1，1，1 >，<0，1，2 >，<1，1，2 >} B．{<0，1 >，<1，1 >，<0，2 >，<1，2 >}

C．{<1，0， 1 >，<1，1，1 >，<1，0， 2 >，<1，1，2 >} D．{<0，1，1 >，<1，1，1 >，<0，2， 1 >，<1，2，1 >}

4．设A={1，2，3，4，5, 6}，B={a，b，c，d，e}，以下哪个函数是从A到B的满射函数( )

A．F ={<1，b>，<2，a>，<3，c>，<1，d>，<5，e>, <6，e>} B．F={<1，c>，<2，a>，<3，b>，<4，e>，<5，d>, <6，e>} C．F ={<1，b>，<2，a>，<3，d>，<4，a>, <6，e>}

D．F={<1，e>，<2，a>，<3，b>，<4，c>，<5，e>, <6，e>} 5．对于群来说，下列判断错的是（ ）

A．群中除了幺元外，不可能再有等幂元 B．群与其子群共一幺元 C．循环群的生成元是唯一的

D．任何一个循环群必定是阿贝尔群

《 离散数学 》 第 1 页 （共 2 页）

二、 判断题（本大题20分，每小题4分） ×××√×

1、命题公式（P?Q）?（?R?T）是析取范式。 （ ） 2、设c是个体域中某个元素，A是谓词公式，则A(c)? ?xA(x)。 （ ） 3．集合A 的幂集P(A)上的包含关系是偏序关系。 （ ） 4．任何图都有一棵生成树。 （ ） 5．连通无向图的欧拉回路经过图中的每个顶点一次且仅一次。 （ ）

三、解答题（计算或者证明题：本大题50分，每小题10分） 1．设命题公式为（P ?（P? Q））? Q。 （1）求此命题公式的真值表； （2）判断该公式的类型。 解 （1） 真值表如下 P 0 0 1 1 Q P?Q P ?（P? Q） 0 1 0 1 1 0 0 0 0 1 1 1 （2）该公式为重言式 （P ?（P? Q））? Q 1 1 1 1

2．用直接证法证明

前提：P ? (Q ? R)，S ? ? Q，P，S。 结论：R

证 (1)P P (2) P ? (Q ? R) P

(3) Q ? R T(1,2)I (4)S P (5) S ? ? Q P

(6)?Q T(4,5)I (7) R T(3,6)I

3．设R是集合A = {1, 3,4, 5,8,12,24}上的整除关系。

(1) 给出关系R； （2） 给出COV A

（3） 画出关系R的哈斯图；

（4） 给出关系R的极大、极小元、最大、最小元。

《 离散数学 》 第 2 页 （共 2 页）

解 R={<1,3>,<1,4>,<1,5>,<1,8>,<1,12>,<1,24>,<3,12>，<3,24>，<4,8>，<4,12>，<4,24>,<8,24>,<12,24>}∪IA

COV A={<1,3>,<1,4>,<1,5>,<3,12>, <4,8>，<4,12>，,<8,24>,<12,24>} 作哈斯图如右上：

由图看出该偏序集没有最大元，最小元为1；5，24是极大元，1是极小元和最小元。

248415123

4．如图所示带权图，用避圈法(Kruskal算法)求一棵最小生成树并计算它的权值。

解

13245

C?T??1?3?4?5?2?15

5、给定权为1，9，4，7，3；构造一颗最优二叉树。

解 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24

241583497W?T??4?1?4?3?3?4?2?7?1?9?51

41《 离散数学 》 第 3 页 （共 2 页）