1、
装 订 线
装 订 线 内 不 要 答 题
学 号
姓 名
班 级
东 北 大 学 秦 皇 岛 分 校
课程名称： 离散数学（答案） 试卷： (A) 考试形式：闭卷
授课专业： 信管、电商 考试日期：2011年12月2日 试卷共3页
题号
一
二
三
四
总分
得分
阅卷人
一、 填空题：（每小题4分，共20分）
1、设，则 。
2、设的真值为1，的真值为0，则命题公式
的真值为 0 。
3、设是正整数集合，表示求两个数
2、的最小公倍数的运算，则对于运算的幺元是 1 。
4、设为12阶循环群，则的4阶子群为。
5、设有向简单图的度数序列为，其中入度列为，则的出度列为。
二、选择题：（每小题4分，共20分）
1、 设是正整数集合，且，则为（ A ）。
2、 设，其中是整数集，为普通加法，则下列映射中（ C ）不是的自同态映射。
3、 完全二部图中，边数等于（ B ）。
4、设一棵树中有哥顶点的度数为，其余的顶点均为树叶，则该树有（ D ）片树叶。
5、语句“情况并非如此，如果他不来，那么我也不去” 可化简为（ C ）
二、 解答题（共28分）
1、（8分）考虑解释：
3、 （1）个体域；
（2）上的特定谓词：
在此解释下，求下列公式的真值（要求解题过程）。
（1）
（2）
装 订 线
装 订 线 内 不 要 答 题
学 号
姓 名
班 级
解： （1）
公式为真 ------4分
（2）
公式为真 -----8分
2、（6分）设，有一个划分，试求由划分诱导的上的等价关系。
解
----3分
故所求
4、的等价关系为
-------6分
3、（8分）设是代数系统，其中，对，有
（1）列出的运算表；
（2）运算是否有零元和幺元，并讨论所有元素的逆元。
解：（1）运算表为
------4分
（2）无逆。 -----8分
4、（6分）求公式的主析取范式
解
------6分（也可用真值表求解）
四、作图或证明题（共32分）
1、（5分）画出一个5个顶点6条边的无向欧拉图，但不是哈密顿图。
解： --------5分
2、（6分）画出的所有含
5、4条边的非同构生成子图。
解：
-------6分
3、（9分）画出带权为的最优二元树，计算其树权和树高，并给出每个数字相对应的前缀码。
解：
装 订 线
装 订 线 内 不 要 答 题
学 号
姓 名
班 级
8
7
5
3
2
5
10
15
25
------4分
树高为3 -------7分
对应的前缀码为 ------9分
4、（6分）利用推理规则
6、证明
证 （1） （附加前提）
（2）
（3） （1）（2）
（4）
（5） （4）
（6） （5）
（7） （矛盾） （3），（6） ------6分
5、（6分）设是群的子群，在中定义二元关系，证明是上的一个等价关系。
证：由，有，故是自反的；
若，即，因是群，有，则，故是对称的；
若，即，因是群，满足结合律，有，则，故是传递的。因此是上的一个等价关系。 ---------------6分
- 3 -
浙ICP备2021020529号-1 | 浙B2-20240490 
