2012年《离散数学》期末试题A

…… …… …… …… …… …… …… …… …… …… …… …… ：……期……日……核……审…… …… …… …… …… …… …… …… …… …线 …… ：…：……名……签……人……核……审…… … 订 … …… …… …… …… …… …… ：……期……日…装卷……制…… …… …… …… …… …… …… …… …… …… …… ……：……名……签……人……卷……制…… …… …… …… … …

湘潭大学2012年下学期20 10 级《离散数学》课程考试试卷 （A卷） 适用年级专业 信息与科学计算 考试方式 闭卷 考试时间 120 分钟 学院 专业 班级 学号 姓名 题 号 一 二 三 四 五 六 七 总分 阅卷 教师 得 分 ……………………………………………………………………………………………………………… 得 一、填空与选择题（每空 4分，共24分） 分 1．构造一个与 6 个英文字母对应的前缀码为＿＿＿＿＿＿＿＿＿＿＿＿＿ . 2．一颗树有2个度数为4的顶点，3个度数为3的顶点，其余的都是叶点，则该树有 ＿＿＿＿＿＿＿＿＿＿个叶点. 3．?xF(x,y)??yG(y) 的前束范式为＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿. 4．3个元素的集合上可定义 ＿＿＿＿＿＿＿个不同的二元关系，可以定义＿＿＿＿＿＿＿＿个不同的等价关系. 5．连通图 G 是 E 图的充要条件是 ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿. A. 无奇回路， B. 无奇点， C. 至多存在一个偶点， D. 是 H 图. 6． 下列公式中，等值的是＿＿＿＿＿＿. A. ?xF(x)??xG(x) 与 ?x(F(x)?G(x))， B. ?xF(x)??xG(x) 与 ?x(F(x)?G(x)), C. ?x?yF(x,y)与?y?xF(x,y), D. ??xF(x)与?x(?F(x)). 二、（16分）1. 证明R是集合A上的传递关系，当且仅当R2?R； 2. 设R1 和R2 是集合A 上的二元关系，证明S(R1?R2)?S(R1)?S(R2).

（第 1 页 共 4 页）

三、（18分）1. 设G(p,q)是简单图，若G 连通，证明q?p?1; 2. 设p?11,证明 p 阶简单图 G 与其补图 G 中，至少有一个是不可平面图. 四．（8分）求公式P?Q?R?P 的主析取范式和主合取范式.

（第 2 页 共 4 页）

五、（14分）1. 构造下面推理的证明: R,S?T,前提:P?Q,P?唵 S?R,?T, 结论:Q; 2. 在一阶逻辑中，将下列命题符号化：有些人喜欢所有的花. 六、（10分）设Sn?{x|x?Z?,且x|n}（n为正整数） 1. 画出?S30,1? 的 Hasse 图;

（第 3 页 共 4 页）

2. 判断?S45,1?是否为有余格，分配格. 七、（10分） 三元对称群 S3 的非平凡子群是否都是循环群？ 请说明理由并构造 S3 的一个三阶子群.

（第 4 页 共 4 页）

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