河南科技大学
2014年硕士研究生入学考试试题答案及评分标准
考试科目代码： 652 考试科目名称： 离散数学
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1-5：A D B D C 6-10：C D B A B 11-15：A D A B B
二、填空题(本大题共10小题，每小题2分，共20分)
1. ?P?Q或?Q?P 2. 1 3. P真值为1，Q的真值为0 4. (?P?S?R)?(?P??S?R)
5. R={<2,3>,<2,4>,<2,5>,<2,6>,<3,4>,<3,5>,<3,6>, <5,6>} 6. {?,{{?,2}},{{2}},{{?,2},{2}}} 7. {,,,
三、计算题(本大题共5小题，每小题8分，共40分)
1．利用主析取范式，求公式?(P?Q)?Q?R的类型。(注：重言式、矛盾式或可满足式)
解：
?(P?Q)?Q?R??(?P?Q)?(Q?R)?(P??Q)?(Q?R)?P??Q?Q?R?F (6分)
它无成真赋值，所以为矛盾式。(2分)
2． 给定解释I： D={2，3}，L（x, y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0，求在解释I下?y?xL(x,y)的真值。 解：
(2分) (2分)
?y?xL(x,y)??y(L(2,y)?L(3,y))?(L(2,2)?L(3,2))?(L(2,3)?L(3,3)) ?(1?0)?(0?1)?0?0?0
(2分) (2分)
第1页（共6页）
3．设G??Z12,??是模12的整数加群，求G的生成元和所有子群
解：(1) ?(12)?4，小于12且与12互质的数是1,5,7,11；所以，G的生成元是1,5,7,11 (2分) (2) 12的正因子有1,2,3,4,6,12，则Z12的子群有： 1 1121?0?{0} 1阶子群 (1分) ?6?{0,6} 2阶子群 (1分) ?4?{0,4,8} 3阶子群 (1分) ?3?{0,3,6,9} 4阶子群 (1分) ?2?{0,2,4,6,8,10} 6阶子群 (1分)
?1?{0,1,2,3,4,5,6,7,8,9,10,11} 12阶子群 (1分)
122 1 1123124 1 1
1261212 4．求下图的邻接矩阵和可达矩阵。
解：(1) 求邻接矩阵 (4分)
?0??1A(G)??1??0?0?0000??0110?0000??0100?0000??
0000??0??0100??1A3(G)??00000???0000??0?00000?? (1分) ?0000??0000?0000??0000?0000?? (1分)
(2) 求可达矩阵
?0??1A2(G)??0??1?0?A4(G)?O5?5 (1分)
所以可达矩阵
?0??1P?A?A2?A3?A4??1??1?0?0000??0110?0000??0100?0000?? (1分)
第2页（共6页）
5. 如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算其总造价。
解：(1) 用Kruskal算法求产生的最优树。算法为：
w(v1,v7)?1w(v7,v2)?4w(v7,v3)?9w(v3,v4)?3w(v4,v5)?17w(v1,v6)?23结果如图：
选e1?v1v7选e2?v7v2选e3?v7v3选e?v3v4选e?v4v5选e?v1v6
(3分)
(3分)
(2) 树权C(T)=23+1+4+9+3+17=57即为总造价。 (2分)
四、证明题 (本大题共3小题，每小题10分，共30分)
1．设论域D={a , b , c}，求证：?xA(x)??xB(x)??x(A(x)?B(x))。 证明：
?xA(x)??xB(x)?(A(a)?A(b)?A(c)?(B(a)?B(b)?B(c)?(A(a)?B(a))?(A(a)?B(b))?(A(a)?B(c))?(A(b)?B(a))?(A(b)?B(b))?(A(b)?B(c))?(A(c)?B(a))?(A(c)?B(b))?(A(c)?B(c))?(A(a)?B(a))?(A(b)?B(b))?(A(c)?B(c)??x(A(x)?B(x))
第3页（共6页）
(3分) (3分) (3分)
(1分)
c?A,有?a,c??R且?c,b??R)} 2．设R是A上一个二元关系，S?{?a,b?|(a,b?A)?(对于某一个试证明：若R是A上一个等价关系，则S也是A上的一个等价关系。
证明：
（1） S自反的 (3分)
?a?A，由R自反，?(?a,a??R)?(?a,a??R)，??a,a??S
（2） S对称的 (3分)
?a,b?A?a,b??S?(?a,c??R)?(?c,b??R)?((??ac,,ca????RR))???((??bc,cb????RR))??b,a??S（3） S传递的 (3分)
?S定义?R对称?R传递
?a,b,c?A?a,b??S??b,c??S?(?a,d??R)?(?d,b??R)?(?b,e??R)?(?e,c??R)?(?a,b??R)?(?b,c??R)??a,c??S
3. 设
[幺] ?a?R ，0*a?0?a?0?a?a,a*0?a?0?a?0
即 0*a?a*0?a?0为幺元 (3分)
[乘] ?a,b?R，由于+，·在R封闭。所以a*b?a?b?a?b?R，即*在R上封闭。(3分) [半群] ?a,b,c?R
?R传递?S定义
由（1）、（2）、（3）得；S是等价关系。 (1分)
(a*b)*c?(a?b?a?b)*c?a?b?a?b?c?(a?b?a?b)?c?a?b?c?a?b?a?c?b?c?a?b?ca*(b*c)?a?b?c?a?b?a?c?b?c?a?b?c所以(a*b)*c?a*(b*c)因此 ，〈R，*〉是独异点。 (1分)
五、应用题(本大题共2小题，每小题15分，共30分)
1．假设英文字母a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。
解： (1) 根据权数构造最优二叉树： (5分)
(3分)
第4页（共6页）
(2) 传输它们的最佳前缀码如上图所示， (5分) a—011；e—111；h—10；n—110；p—0101； r—000；w—0100；y—001
(3) happy new year的编码信息为： (5分)
10 011 0101 0101 001 110 111 0100 001 111 011 000
附：最优二叉树求解过程如下：
2．设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >}，请写出R的关系矩阵MR和关系图GR，并用矩阵运算求出R的传递闭包t (R)。
解：(1) R的关系矩阵MR
?0??1MR??0??0?
100001000??0?1??0?? (4分)
第5页（共6页）
(2) R的关系图GR
(4分)
(3) 用矩阵运算求R的传递闭包t (R)
??1010?M101??R2?M?0R?MR???0000???0000??? (1分) ??0101?M?M?1010??R3?MR2R???0000???0000??? (1分) ??1010?M?M?0101??R4?MR3R???0000???0000??? (1分) ??1111?M??1111???t(R)?MR?MR2?MR3?MR4?0001???0000??? (1分)
所以，t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }
第6页（共6页）
分) (3