离散数学试卷第 1 页 共 5 页试题编号： 2012-2013学年第一学期离散数学试卷（期末） （A 卷） （闭卷）题 号 一 二 三 四 五 六 七 八 九 十 总 分得 分评卷人一、用等值演算法求命题公式 的主析取范式，并根据主析()()pqr取范式写出相应的主合取范式。 （10 分）二、在命题逻辑自然推理系统 P 中构造下面推理的证明。 （10 分）前提: 。,pqrsr结论: 。s离散数学试卷第 2 页 共 5 页三、(14 分)设 A=a,b,c,d,e,f ,R 是 A 上的关系，R=, 。（1）画出 R 的关系图；（2）讨论 R 是否具有自反，反自反，对称，反对称和传递等性质；（3）写出 r(R)、s（R） 、t(R)。四、画出偏序集的哈斯图.并写出极大极小元。(10 分)离散数学试卷第 3 页 共 5 页五、在一阶逻辑自然推理系统 F 中构造下面推理的证明。(10 分)不存在不能表示成分数的有理数。无理数都不能表示成分数.所以,无理数都不是有理数。六、设 R 是 A 上的等价关系,且 A/R=1,2,3,4,5,6,7,试求(1)A; (2)R 。(10 分)七、1. 画出以（2，2，2，2，2，2）为度序列的不同构简单图 2 个。 (4分)离散数学试卷第 4 页 共 5 页2.设无向树 T 有 3 个 3 度、2 个 2 度顶点,其余顶点都是树叶,求 T 的树叶数。(5 分)八.在通信中要传输字母 a，b，c，d，e，f，g，它们出现的频率如下表 1。 表 1字母 a b c d e f g频率 30% 20% 15% 10% 10% 9% 6%请利用最优二叉树设计一个传输上述字母的前缀码，并求传输 10000 个按上述频率出现的字母所需二进制字个数。(10 分)九、 （1）画一个奇数个顶点奇数条边的简单欧拉图（既是简单图又是欧拉图）(6 分)(2) 画一个 n（n3）阶简单哈密尔顿图，使得对任意不相邻的顶点离散数学试卷第 5 页 共 5 页的度数都满足 . (6 分),ijv()ijdvn+表 2* a b c da a b c db b c b dc c a b cd d a c c(1)求出*运算的单位元和零元；(2)求出所有可逆元素的逆元。