离散数学11-12A(信管、电商)试题及答案.doc

装 订 线
装 订 线 内 不 要 答 题
学 号

姓 名

班 级

东 北 大 学 秦 皇 岛 分 校

课程名称： 离散数学（答案） 试卷： (A) 考试形式：闭卷
授课专业： 信管、电商 考试日期：2011年12月2日 试卷共3页

题号
一
二
三
四
总分
得分

阅卷人

一、 填空题：（每小题4分，共20分）
1、设，则 。
2、设的真值为1，的真值为0，则命题公式
的真值为 0 。
3、设是正整数集合，表示求两个数的最小公倍数的运算，则对于运算的幺元是 1 。
4、设为12阶循环群，则的4阶子群为。
5、设有向简单图的度数序列为，其中入度列为，则的出度列为。
二、选择题：（每小题4分，共20分）
1、 设是正整数集合，且，则为（ A ）。

2、 设，其中是整数集，为普通加法，则下列映射中（ C ）不是的自同态映射。

3、 完全二部图中，边数等于（ B ）。

4、设一棵树中有哥顶点的度数为，其余的顶点均为树叶，则该树有（ D ）片树叶。

5、语句“情况并非如此，如果他不来，那么我也不去” 可化简为（ C ）

二、 解答题（共28分）
1、（8分）考虑解释：
（1）个体域；
（2）上的特定谓词：
在此解释下，求下列公式的真值（要求解题过程）。
（1）
（2）
装 订 线
装 订 线 内 不 要 答 题
学 号

姓 名

班 级

解： （1）
公式为真 ------4分
（2）

公式为真 -----8分
2、（6分）设，有一个划分，试求由划分诱导的上的等价关系。
解

----3分
故所求的等价关系为

-------6分
3、（8分）设是代数系统，其中，对，有
（1）列出的运算表；
（2）运算是否有零元和幺元，并讨论所有元素的逆元。
解：（1）运算表为

------4分
（2）无逆。 -----8分
4、（6分）求公式的主析取范式
解

------6分（也可用真值表求解）
四、作图或证明题（共32分）
1、（5分）画出一个5个顶点6条边的无向欧拉图，但不是哈密顿图。
解： --------5分
2、（6分）画出的所有含4条边的非同构生成子图。
解：
-------6分
3、（9分）画出带权为的最优二元树，计算其树权和树高，并给出每个数字相对应的前缀码。
解：
装 订 线
装 订 线 内 不 要 答 题
学 号

姓 名

班 级

8
7
5
3
2
5
10
15
25
------4分

树高为3 -------7分
对应的前缀码为 ------9分
4、（6分）利用推理规则，证明
证 （1）　　　　　　　　　（附加前提）
（2）　　　　　　
（3）　　　　　　　　　（1）（2）
（4）　　　　　
（5）　　　　　 （4）
（6） （5）
（7） （矛盾） （3），（6） ------6分
5、（6分）设是群的子群，在中定义二元关系，证明是上的一个等价关系。
证：由，有，故是自反的；
若，即，因是群，有，则，故是对称的；
若，即，因是群，满足结合律，有，则，故是传递的。因此是上的一个等价关系。 ---------------6分

- 3 -