发布时间 : 星期一 文章离散数学习题集（十五套）- 副本更新完毕开始阅读6a8c3fb669dc5022aaea0079
二、选择 20% （每小题 2分）
题目 答案
三、证明 26%
1、 证：
“?” ?a,b,c?X 若
R
对称性知
1 C D 2 B、C 3 C 4 A 5 D 6 C 7 A 8 D 9 B 10 A
“?” 若
?a,b?C?1，有
f(a)?g(a),f(b)?g(b)?1，又
f(b?1)?f(b),g(b?1)?g?1(b)?f(b?1)?f?1(b)?g?1(b)?g(b?1)
?f(a★b?1)?f(a)*f(b)?g(a)*g(b?1)?g(a★b?1)
?a★b?1?C ?< C , ★> 是 < G1 , ★>的子群。
3、 证：
r①设G有r个面，则
2e??d(Fi)?rki?1，即
r?2ek。而 v?e?r?2故
2?v?e?r?v?e?2ek(v?2)e?k即得 k?2。（8分）
e?k(v?2)k?2不成立，
②彼得森图为k?5,e?15,v?10，这样
所以彼得森图非平面图。（3分）
一、 逻辑推演 16% 1、 证明：
①A P（附加前提） ②A?B
T①I ③A?B?C?D P ④C?D T②③I ⑤D T④I ⑥D?E T⑤I ⑦D?E?F P ⑧F T⑥⑦I ⑨A?F CP
2、证明 ①?xP(x) P（附加前提） ②P(c)
US① ③?x(P(x)?Q(x)) P ④P(c)?Q(c) US③ ⑤Q(c) T②④I ⑥?xQ(x)
UG⑤ ⑦?xP(x)??xQ(x)
CP
二、 计算 18% 1、 解：
??0100??M?1010???1R???0001?M?0R2?MR?MR????0000???0? ， ??0??0101?M?1R3?MR2?M010??R???0000???0000?????1010?M?M?0101??R4?MR3R???0000???0000???010?101??000?000???
，
Mt(R)?MR?MR2?MR3?MR4?1??1??0??0?111??111?001??000??
? t (R)={ , , < a , c> , , , < b ,b > , < b , c . > ,
< b , d > , < c , d > }
2、 解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：
树权C(T)=23+1+4+9+3+17=57即为总造价。
试卷二试题与答案
一、填空 20% （每小题2分）
1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为
；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P
P (1,1) T P (1,2) T P (2,1) F P (2,2) F 则公式?x?yP(y,x)真值为 。 2、 设S={a1 ，a2 ，?，a8}，Bi是S的子集，则由B31所表达的子集是 。
}，则R= 3、 设A={2，3，4，5，6}上的二元关系R?{?x,y?|x?y?x是质数
（列举法）。
R的关系矩阵MR=
。
5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系
R= ；A上既是对称的又是反对称的关系R= 。
6、设代数系统
* a b c a b c a b c b b c c c b
则幺元是 ；是否有幂等 性 ；是否有对称性 。
7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。
9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。 10、公式(P?(?P?Q))?((?P?Q)??R的根树表示为
。
二、选择 20% （每小题2分）
1、在下述公式中是重言式为（ ）
A．(P?Q)?(P?Q)；B．(P?Q)?((P?Q)?(Q?P))； C．?(P?Q)?Q； D．P?(P?Q)。
2、命题公式 (?P?Q)?(?Q?P) 中极小项的个数为（ ），成真赋值的个数为（ ）。
A．0； B．1； C．2； D．3 。
S3、设S?{?,{1},{1,2}}，则 2 有（ ）个元素。
A．3； B．6； C．7； D．8 。 4、 设S?{ 1, 2, 3 }，定义S?S上的等价关系
R?{??a,b?,?c,d? | ?a,b??S?S,?c,d??S?S,a?d?b?c}则由 R产 生
的S?S上一个划分共有（ ）个分块。