一、单选题（20小题，每小题2分，共40分） 1、B 2、C 3、D 4、C 5、C 6、C 7、D 8、C 9、B 10、C 11、C 12、C 13、B 14、B 15、A 16、C 17、B 18、D 19、B 20、D
二、填空题（20小题，每空1分，共20分） 1、0 2、图G连通 3、无
4、{{?,{?}},?,{?,{?}},{?}} 5、2,3 6、8 7、P??Q
8、｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝ 9、1
第 1 页 共 4 页
10、?P(x) 11、5
12、?Q??P 13、不存在 14、b 15、a
16、{?, {?}, {{?}}, {?, {?}}} 17、半群
18、M01或P?? Q 19、无
20、4，5，6
三、简答题（4小题，每小题6分，共24分） 1、答：
子 集 上 确 界 下 确 界 {a,b,c} a d {c,d,e} c 无 A a 无
2、解：邻接矩阵A及A2，A3，A4如下：（2分）
??01000?0100?A??1??01000?? ?00001????00010??
??10100??000??200?02000??0220240??200000?A2????10100??3?000?4? A4???20240???00010? A?????02001??0??00???00010?
?0001???00010????00001??a(3)12=2，所以v1到v2长度为3的路有2条，它们分别是：v1v2v1v2和v1v2v3v2。第 2 页 共 4 页
1分）
（
(2)a13=1，所以v1到v3长度为2的路有1条：v1v2v3。
（1分） （1分）
(3)a22=0，v2到自身无长度为3的回路。
(4)a22=4，v2到自身有4条长度为4的回路，它们分别是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和
v2v1v2v3v2。
（1分）
3、解：该问题相当于求上图的最小生成树。按下图架起八个城市间直接通讯线路的造价最小．最小造价为：
W（T）=180+240+200+280+120+90+220=1330 （2分）
（4分）
4、解：(1)．〈A，／〉是偏序集。 其哈斯图为：
（3分）
(2)．〈A，／〉构成格。因为其任意两个元素都有上确界和下确界。 （1分） (3)．〈A，／〉构成布尔代数。因为它是有界分配格，且其任意元素都有唯一补元素。
（2分）
四、证明题（2小题，每小题8分，共16分） 1、证明： ①
?x??a,b?有唯一x?a??0,1??f是映射 b?a② ?y??0,1?,有(b?a)y?a??a,b??f是满射 ③ ?x1,x2??a,b?,且
x1?ax?a??0,1?,2??0,1? b?ab?ax1?ax2?a?,?f是入射 b?ab?a根据①②③知f是双射
f?1:?0,1???a,b?。 f?1(x)?F(y)?a?(b?a)y
第 3 页 共 4 页
?f?1?a?(b?a)x,其中f?1：?0,1???a,b?
2、（1）该证明的错误在于: (1)、 (2) 与 (3)、 (4) 的顺序颠倒了，应该先指定存在后指定全
称。 （2分）
（2）正确的证明是：（6分）
(1) ?x(Q(x)?Z(x)) P (6) Z(a) T(2) I (2) Q(a)?Z(a) ES (1) (7) R(a) T(4),(5) I (3) ?x(Q(x)?R(x)) P (4) Q(a)?R(a) US (3) (5) Q(a) T(2) I
(8) R(a)?Z(a) T(6),(7) I (9) ?x(R(x)?Z(x)) EG(8) 第 4 页 共 4 页
2014 ～ 2015学年1学期离散数学期末考试试卷(1_A)20141223152003答案
