2012年各高校离散数学试题答案
一、填空（每题5分共20分）
1、数集A={1,2,3}与运算“min”构成的代数系统的单位元是 3 。
2、一个连通的(n,m)平面图的面数为k，则m，n，k满足的Euler公式为 n-m+k=2 。 3、设T是一棵完全二元树，有n个结点，n0片树叶，则n和n0满足如下的公式 2n0-1。 4、减法“-” 不是 正整数集N上的二元运算。 二、单项选择（每题5分共10分） 1.
??I×I, i1?i2? ︱i1-i2︱≦10,则?是 b 。
(a) 反自反的；(b)对称的；(c)反对称的；(d)传递的。 2. 下列各图是Euler图的是 d 。
（a） （b） （c） （d） 三、设A={1},B={2,3},求A×2(8分)。
B
解：因2B?{?,{2},{3},{2,3}}， 4分 则A?2B?{(1,?),(1,{2}),(1,{3}),(1,{2,3})}。 8分 四、证明：集合论中的德·摩根律：(A∩B)=A∪B(8分)。
证 ?a?(A?B)?,则a?A?B,所以a?A或a?B,即a?A?或a?B?, 2分 因此a?A??B?, 故(A?B)??A??B?. 5分 同理?a?A??B?,则a?A?或a?B?,所以a?A或a?B,因此a?A?B, 7分 即?a?(A?B)?, 故A??B??(A?B)?. 8分 五、设X={1,2,3,4}上的关系R={(1,1)，(2,3)，(3,2)}, 求R的传递闭包t(R)。(10分)。 解法一
///R2?R?R?{(1,1),(2,2),(3,3)， 3分
R3?R2?R?{(1,1)，(2,3)，(3,2)}， 5分 R4?R3?R={(1,1),(2,2),(3,3)， 7分
则t(R)?R?R?R?R?{(1,1),(2,2),(2,3),(3,2),(3,3) 10分 解法二
234?1??0MR??0??0?001001000??10??0??01，(3分)MR2?MR?MR??000????000???00100??0?， (4分) ?0?0??00100??0?(6分) ?0?0??MR3?MR2?1??0?M??0??0?001001000??10??0??01(5分)，MR4?MR3?M??000?????000??则Mt(R)?MR?R2?R3?R4?M?MR2?MR3?MR4
?1??0??0??0?011001100??0?,(7分) ?0?0??因此t(R)?{(1,1),(2,2),(2,3),(3,2),(3,3)。 10分
2六、设集合A={a,b,c,d}上的二元关系为R1={(b,b),(b,c),(c,a)}, R2={(b,a),(c,d),(c,a),(d,c)},求R2R1, R1,R2.(10分)。
~解：R2?R1?{(d,a)}， 4分
R21?{(b,b),(b,c),(b,a)}， 8分 R~2?{(a,b),(a,c),(c,d),(d,c)} 10分
七、设A={1,2,3,4}，能否作一个函数g: A?A使得g≠I3A, 但g=IA? (8分)。
解：能(3分)，例如作g??34??12??2314??(6分)，则g3?IA。 (8分) ?八、用形式证明格式求证：A∨B, A→C,B→D?C∨D. (8分)。
证：(1) A∨B 前提引入
(2) ?A?B (1),蕴涵等价式 2分 (3) B→D 前提引入
(4) ?A?D (2), (3)假言推理 4分 (5) ?D?A (4),否定后件 5分 (6) A→C 前提引入
(7) ?D?C (5) ,(6), 假言推理 6分 (8) D?C (7) ,蕴涵等价式 7分 (9) C?D (8),交换律 8分
九、设有一棵树，它有2个2度结点，1个3度结点，3个4度结点，其余为叶，问它有几片树叶？为什么？（解:设该树有x片树叶,
则其共有2+1+3+x=x+6个结点, 3分 且所有结点度的和为:
2×2+1×3+3×4+x=x+19, 6分 则由握手定理得: x+19=2(x+6-1) 9分 解得:x=9 10分 十、如果
?1=b
?1*a
?1. (8分)。
证明:因为a?b?b?1?a?1?a?(b?b?1)?a?1 2分
?a?e?a?1?a?a?1?e 6分
所以(a*b)
?1=b
?1*a?1 8分
10分）。