华南农业大学期末考试试卷（
2011-2012学年第
一学期
A卷）
考试科目：离散结构考试时间：
120
分
考试类型：（闭卷）考试钟
学号姓名年级专业
题号得分评阅人
一二三四五总分
□林旭东□黄华伟□朱梅阶□黄沛杰
考试注意事项：
①本试题分为试卷与答卷
2部分。试卷有五大题，共
4页。
②所有解答必须写在答卷上，写在试卷上不得分。
得分
一、选择题（本大题共10 小题，每小题
）
2 分，共20 分）
1、重言式的否定是（A、重言式有可能
2、A(x)：x在北京工作，
B、矛盾式
C、可满足式D、A-C均
B(x)：x是北京人；则命题“在北京工
作的人都是北京人。”可表示为______。A、B、
xA(x)x(A(x)
B(x)B(x))
C、D、
xA(x)x(A(x)
B(x)B(x))
3、设p:天冷, q:小王穿羽绒服，下列命题中，和命题“只要天冷，小王就穿羽绒服。”一样符号化为
p?q 的是______。
A、如果天不冷，则小王不穿羽绒服。B、小王穿羽绒服仅当天冷的时候。C、除非小王穿羽绒服，否则天不冷。D、只有天冷，小王才穿羽绒服4、下列哪个表达式错误_____。
A、B、C、D、5、设
A
x(A(x)x(A(x)x(P(x)x(P(x){1,2,3,...,10}
B)B)Q(x))Q(x))
xA(x)xA(x)
BB
xQ(x)xQ(x)
R{
x,y|x,y
S
x
y
10}
xP(x)xP(x)
，定义A上的关系，
则R具有的性质为______。
A、自反的传递的
6、设V=
乘法，下面函数中是V 的自同态的是______。A、f(x)=2xB、f(x)= -xC、f(x)=1/xD、f(x)=x+1
1 / 11
B、对称的
C、传递的，对称的
D、
7、设V=
A、-8
B、8
C、-6
D、6______。
D、
-3
8、给定下列各序列，可以构成无向简单图的度数序列为
A、1,1,2,2,3 1,3,4,4,5
9、具有6 个顶点，12条边的连通简单平面图中，______个。
A、5
B、6
C、7
D、8
B、1,1,2,3,3
C、0,1,1,3,3
次数为3的面有
10、在下面所示的4个图中，______不是单向连通图。
A、B、C、D、
得分
二、填空题（本大题共15 空，每空2 分，共30 分）
1、p→q 的主合取范式是____________________。2、表达式
xyA(x,y)
中谓词的个体域是
D
{a,b}，将其中的量词
消去，写成与之等价的命题公式为3、若明天是星期一或星期三，
__________________。
我就有课。若有课，今天必备课。
将命题
我今天下午备课。所以，明天不是星期一和星期三。
中的4个简单命题依次符号化为，p：明天是星期一，q：明
天是星期三，r：我有课，s：我备课。则推理的形式结构为：前提：______________________________；结论：_____________________。4、
x(yF(x,y)
yG(x,y))的前束范式为：
A
{1,2,3,4}
____________________。
5、设R，S是集合
R
{1,1,
1
上的两个关系，其中
2,2,
2,3,3,2,
4,4}
2,2,2,3,4,4}
，
S{1,1,
,
则(RS)
____________________。
A,
6、设偏序集
B
{3,4,5}
的哈斯图如右所示，若
A的子集
，则B的最大下界为_____。
，
x,y
Z
7、在整数集Z上定义二元运算
x
y
x
y
2，则关于运算
有
的幺元是______。
3
8、设a是12阶群的生成元，则a是阶元素
9、若连通平面图G有4个结点，3个面，则G有条边。10、在右边的PERT图中，关键路径为______。11、一颗带权为2,3,5,7,8,9的最优2元树，其权为______。
12、1400 的不同的正因子个数为______。13、满足等式
x1
x2
x3
x4
8的非负整数解的个数有
______。
14、n阶无向树至少有______片树叶。（n>=2）
得分
3 / 11
三、计算题：（6+4+6+6，共22 分）1、设A={1, 2, 3, 4}，R={
A，y
A且x+y<5}R的关系图。
（1）写出R的集合表达式和关系矩阵，画出
（2）画出关系R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)的关系图。2、分别画出下面无向图
A的关联矩阵和有向图
B的邻接矩阵。
e1 e2
v1
ee4 5 e3
V3 v2
图A
V4
v1 e1 v2
ee2 3
图B
v4 e4 e5
v3
3、求下面带权图中v1到其它顶点的最短路径及对应的权。
3
v2
6
103
v4
2
2
v1
4
2
4
v6
v3
4、设有5个城市
v5
v1,v2,v3,v4,v5，任意两城市之间的铁路造价如
下（以百万元为单位）：W(v1, v2)=4, W(v1, v3)=7, W(v1, v4)=16, W(v1, v5)=10, W(v2,v3)=13, W(v2, v4)=8, v5)=17, W(v3, v4 )=3,
W(v2,
W(v3 ,v5)=10，W(v4, v5)=12。试求
出连接5个城市的且造价最低的铁路网。四、证明题：（本大题共4 个小题，每题1、用等值演算法证明下面的等值式
((P
Q)
(P
R))
(P
(Q
R))
6 分，共24 分）
2、设A为整数集合，在A′A上定义二元关系R：
华南农业大学离散数学期末考试试卷及答案
