2014河科大离散数学考研真题试题
河南科技大学
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. 3. P 真值为1，Q 的真值为0 4. (⌝P ∨S ∨R ) ∧(⌝P ∨⌝S ∨R )
{Φ, {{Φ, 2}},{{2}},{{Φ, 2},{2}}}7. 8. 9. 2(n t -1) 10. v -e +r =2
三、计算题(本大题共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分)
3．设G =是模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，则Z 12的子群有： 1 1
=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分)
=={0,1,2,3,4,5,6,7,8,9,10,11} 12阶子群 (1分)
1 1
1 1
4．求下图的邻接矩阵和可达矩阵。
解：(1) 求邻接矩阵 (4分)
⎛0 1
A (G ) = 1
0 0⎝
0000⎫
⎪
0110⎪0000⎪
⎪
0100⎪0000⎪⎭
0000⎫⎛0
⎪
0100⎪ 1
A 3(G ) = 00000⎪
⎪
0000⎪ 0
00000⎪⎭ (1分) ⎝
0000⎫
⎪
0000⎪0000⎪
⎪
0000⎪0000⎪⎭ (1分)
(2) 求可达矩阵
⎛0
1
A 2(G ) = 0
1 0⎝
A 4(G ) =O 5⨯5 (1分)
所以可达矩阵
⎛0 1
P =A ∨A 2∨A 3∨A 4= 1
1 0⎝
0000⎫
⎪
0110⎪0000⎪
⎪
0100⎪0000⎪⎭ (1分)
5. 如下图所示的赋权图表示某七个城市v 1, v 2, , v 7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算其总造价。
解：(1) 用Kruskal 算法求产生的最优树。算法为：
w (v 1, v 7) =1w (v 7, v 2) =4w (v 7, v 3) =9w (v 3, v 4) =3w (v 4, v 5) =17w (v 1, v 6) =23
结果如图：
选e 1=v 1v 7选e 2=v 7v 2选e 3=v 7v 3选e =v 3v 4选e =v 4v 5选e =v 1v 6
(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分) (3分) (3分)
(1分)
c ∈A , 有∈R 且∈R )} 2．设R 是A 上一个二元关系，S ={|(a , b ∈A ) ∧(对于某一个
试证明：若R 是A 上一个等价关系，则S 也是A 上的一个等价关系。
证明：
（1） S 自反的 (3分)
∀a ∈A ，由R 自反，∴(∈R ) ∧(∈R ) ，∴∈S
（2） S 对称的 (3分)
∀a , b ∈A
∈S ⇒(∈R ) ∧(∈R )
⇒((∈R R ) ) Λ⇒∧((∈>∈R R ) )
⇒∈S
（3） S 传递的 (3分)
S 定义 R 对称 R 传递
∀a , b , c ∈A
∈S ∧∈S
⇒(∈R ) ∧(∈R ) ∧(∈R ) ∧(∈R ) ⇒(∈R ) ∧(∈R ) ⇒∈S
3. 设是一代数系统，*是R 上二元运算，∀a , b ∈R ，a *b =a +b +a ⋅b ，则0是幺元且是独异点。 证明：
[幺] ∀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 ⋅c a *(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分)
(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 ={ , , , }，请写出R 的关系矩阵M R 和关系图G R ，并用矩阵运算求出R 的传递闭包t (R ) 。
0000⎪ ⎝0000⎪⎪⎭ (1分) ⎛ 1010⎫M M 0
0⎪⎪⎭ (1分) ⎛ 1111⎫M = 1111⎪ ⎪t (R ) =M R +M R 2+M R 3+M R 4
所以，t (R)={ , , , , , , , , }
分) (3