2014河南科技大学离散数学试题答案

2014年硕士研究生入学考试试题

考试科目代码： 652 考试科目名称： 离散数学

（如无特殊注明，所有答案必须写在答题纸上，否则以“0”分计算）

一、 单项选择题(本大题共15小题，每小题2分，共30分) 1．下列语句（ ）不是命题。

A．X=13； B．离散数学是计算机系的一门必修课； C．狗有四条腿； D．太阳系以外的星球上有生物 2．命题公式 (?P?Q)?(?Q?P) 中成真赋值的个数为（ ）。

A．0； B．1； C．2； D．3 3．下列公式中，（ ）是重言式。

A．?(P?Q)； B．(P?Q)?Q； C．?(Q?P)?P； D．(P?Q)?P 4．命题“有的人喜欢所有的花”的逻辑符号化为（ ）。

设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y

A．?x(M(x)??y(F(y)?H(x,y)))； B．?x(M(x)??y(F(y)?H(x,y)))； C．?x(M(x)??y(F(y)?H(x,y)))； D．?x(M(x)??y(F(y)?H(x,y)))。 5．设Φ是一个空集，下列哪一个是真命题（ ）。

A． {a}?{{a}}；

B．{{?}}?{?,{?}}；

河南科技大学

C． ??{{?},?}； D． {?}?{{?}}

6．设A={?，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（ ）

7．设s?{1,2,3}，S上关系R的关系图为

则R具有（ ）性质。

A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性

第1页（共4页）

8．下面偏序集（ ）能构成格。

9．设集合A={1，2，3，4，5}上偏序关系的Hass图为

则子集B={2，3，4}的最大元（ ）；最小元（ ）；极大元（ ）；极小元（ ）；上界（ 上确界（ ）；下界（ ）；下确界（ ）。

A．无；4；2、3；4；1；1；4；4； B．无；4、5；2、3；4、5；1；1；4；4； C．无；4；2、3；4、5；1；1；4；4； D．无；4；2、3；4；1；1；4；无

10．设S={0，1}，*为普通乘法，则< S , * >是（ ）。

A．半群，但不是独异点； B．只是独异点，但不是群； C．群； D．环，但不是群。

11．设是偏序集，“?”定义为：?a,b?A,a?b?a|b，则当A=（ ）时，是格。 A．{1,2,3,4,6,12}； B．{1,2,3,4,6,8,12,14}； C．{1,2,3,?，12}； D．{1, 2, 3, 4} 12．图 中 从v1到v3长度为3 的通路有（ ）条。

A． 0；

B． 1； C． 2； D． 3

13．在一棵树中有7片树叶，3个3度结点，其余都是4度结点，则该树有（ ）个4度结点。 A．1；

B．2；

C．3； D．4

14．在如下图中，属于欧拉图的是（ ）。

15．下面四组数能构成无向图的度数列的是( )。 A．2, 3, 4, 5, 6, 7； B．1, 2, 2, 3, 4； C．2, 1, 1, 1, 2； D．3, 3, 5, 6, 0

第2页（共4页）

； ）

二、填空题(本大题共10小题，每小题2分，共20分)

1．P：你努力，Q：你失败。语句“除非你努力，否则你将失败”符号化为 。 2. 设P、Q 的真值为0，R、S的真值为1，则

?(P?(Q?(R??P)))?(R??S)的真值= 。

3. 若P，Q，为二命题，P?Q真值为0 当且仅当 。 4. 公式(P?R)?(S?R)??P的主合取范式为 。 5. 设A={2，3，4，5，6}上的二元关系R?{?x,y?x?y?x是素数}，则R=

（列举法）。

6. 集合A?{{?,2},{2}}的幂集P(A)= 。 7. 设A={a，b，c，d}，其上偏序关系R的哈斯图为

则 R= 。

8. 集合S={α，β，γ，δ}上的二元运算*为

* α β γ δ α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ 那么，代数系统中的幺元是 , α的逆元是 。 9. 完全二叉树中，叶数为nt，则边数m= 。

10. 若连通平面图G??V,E?共有r个面，其中V?v,E?e，则它满足的Euler公式为 。

三、计算题(本大题共5小题，每小题8分，共40分)

1．利用主析取范式，求公式?(P?Q)?Q?R的类型。(注：重言式、矛盾式或可满足式)

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)的真值。

3．设G??Z12,??是模12的整数加群，求G的生成元和所有子群

第3页（共4页）

4. 求下图的邻接矩阵和可达矩阵。

5．如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算其总造价。

四、证明题 (本大题共3小题，每小题10分，共30分)

1．设论域D={a , b , c}，求证：?xA(x)??xB(x)??x(A(x)?B(x))。

c?A,有?a,c??R且?c,b??R)} 2．设R是A上一个二元关系，S?{?a,b?|(a,b?A)?(对于某一个试证明：若R是A上一个等价关系，则S也是A上的一个等价关系。

3. 设是一代数系统，*是R上二元运算，?a,b?R，a?b?a?b?a?b，则0是幺元且是独异点。

五、综合题(本大题共2小题，每小题15分，共30分)

1．假设英文字母a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。

2．设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >}，请写出R的关系矩阵MR和关系图GR，并用矩阵运算求出R的传递闭包t (R)。

第4页（共4页）

本文来源：https://www.bwwdw.com/article/3c1d.html