河南科技大学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. Q P →⌝或Q P ⌝→2. 13. P 真值为1，Q 的真值为04. )()(R S P R S P ∨⌝∨⌝∧∨∨⌝5. R={<2,3>,<2,4>,<2,5>,<2,6>,<3,4>,<3,5>,<3,6>, <5,6>}6. }}}2{},2,{{}},2{{}},2,{{,{ΦΦΦ7. {<a.b>,<a,c>,<a,d>,<b,d>,<c,d>} I A8. β，γ9. )1(2-t n 10. 2=+-r e v三、计算题(本大题共5小题，每小题8分，共40分)1．利用主析取范式，求公式()P Q Q R ⌝→∧∧的类型。

(注：重言式、矛盾式或可满足式)解：F R Q Q P R Q Q P R Q Q P R Q Q P ⇔∧∧⌝∧⇔∧∧⌝∧⇔∧∧∨⌝⌝⇔∧∧→⌝)()()()()( (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分)000)10()01())3,3()3,2(())2,3()2,2(()),3(),2((),(=∨=∧∨∧⇔∧∨∧⇔∧∃⇔∀∃L L L L y L y L y y x xL y(2分) (2分)3．设12,G Z =<⊕>是模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，则12Z 的子群有： 12110{0}== 1阶子群 (1分) 12216{0,6}== 2阶子群 (1分) 12314{0,4,8}== 3阶子群 (1分) 12413{0,3,6,9}== 4阶子群 (1分) 12612{0,2,4,6,8,10}== 6阶子群 (1分)121211{0,1,2,3,4,5,6,7,8,9,10,11}== 12阶子群 (1分)4．求下图的邻接矩阵和可达矩阵。

解：(1) 求邻接矩阵 (4分)⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=0000000100000010110100000)(G A(2) 求可达矩阵⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=0000000001000000010100000)(2G A (1分) ⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=0000000000000000000100000)(3G A (1分)554)(⨯=O G A (1分)所以可达矩阵⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=∨∨∨=0000000101000010110100000432A A A A P (1分)5. 如下图所示的赋权图表示某七个城市721,,,v v v 及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算其总造价。

解：(1) 用Kruskal 算法求产生的最优树。

算法为：61615454434337337272277117123),(17),(3),(9),(4),(1),(v v e v v w v v e v v w v v e v v w v v e v v w v v e v v w v v e v v w ============选选选选选选(3分)结果如图：(3分)(2) 树权C(T)=23+1+4+9+3+17=57即为总造价。

(2分)四、证明题 (本大题共3小题，每小题10分，共30分)1．设论域D ={a , b , c }，求证：))()(()()(x B x A x x xB x xA ∨∀⇒∀∨∀。

证明：))()(()()(())()(())()(())()(())()(())()(())()(())()(())()(())()(())()(())()(()()()(()()()(()()(x B x A x c B c A b B b A a B a A c B c A b B c A a B c A c B b A b B b A a B b A c B a A b B a A a B a A c B b B a B c A b A a A x xB x xA ∨∀⇔∨∧∨∧∨⇒∨∧∨∧∨∧∨∧∨∧∨∧∨∧∨∧∨⇔∧∧∨∧∧⇔∀∨∀(3分) (3分) (3分)(1分)2．设R 是A 上一个二元关系，)},,,(),(|,{R b c R c a A c A b a b a S >∈<>∈<∈∧∈><=且有对于某一个试证明：若R 是A 上一个等价关系，则S 也是A 上的一个等价关系。

证明：（1） S 自反的 (3分)A a ∈∀，由R 自反，),(),(R a a R a a >∈<∧>∈<∴，S a a >∈∴<,（2） S 对称的 (3分)传递对称定义R Sa b R R b c R c a S R b c R c a S b a Ab a >∈⇒<>∈<∧>∈<⇒>∈<∧>∈<⇒>∈<∈∀,)(),(),(),(,,（3） S 传递的 (3分)定义传递S Sc a R R c b R b a R c e R e b R bd R d a Sc b S b a Ac b a >∈⇒<>∈<∧>∈<⇒>∈<∧>∈<∧>∈<∧>∈<⇒>∈<∧>∈<∈∀,),(),(),(),(),(),(,,,,由（1）、（2）、（3）得；S 是等价关系。

(1分)3. 设<R ，*>是一代数系统，*是R 上二元运算，,a b R ∀∈，a b a b a b *=++⋅，则0是幺元且<R , *>是独异点。

证明：[幺] R a ∈∀ ，000*,00*0⋅++==⋅++=a a a a a a a即 为幺元00**0∴==a a a (3分)[乘] R b a ∈∀,，由于+，·在R 封闭。

所以R b a b a b a ∈⋅++=*，即*在R 上封闭。

(3分) [半群] R c b a ∈∀,,)*(**)*()*(*)(*)(*)*(c b a c b a c b a c b c a b a c b a c b a c b a c b c a b a c b a cb a b ac b a b a c b a b a c b a =⋅⋅+⋅+⋅+⋅+++=⋅⋅+⋅+⋅+⋅+++=⋅⋅++++⋅++=⋅++=所以(3分)因此 ，〈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分)(,)(,)c a R b c R ⇒<>∈Λ<>∈(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 的关系矩阵M R 和关系图G R ，并用矩阵运算求出R 的传递闭包t (R )。

解：(1) R 的关系矩阵M R⎪⎪⎪⎪⎪⎭⎫⎝⎛=0000100001010010R M (4分)(2) R 的关系图G R(4分)(3) 用矩阵运算求R 的传递闭包t (R )⎪⎪⎪⎪⎪⎭⎫⎝⎛==00000000101001012R R R M M M (1分) ⎪⎪⎪⎪⎪⎭⎫⎝⎛==000000000101101023R R R M M M (1分) ⎪⎪⎪⎪⎪⎭⎫⎝⎛==00000001010010134R R R M M M (1分) ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+++=0000100011111111432)(R R R R R t M M M M M (1分)所以，t (R)={<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > } (3分)。