同济大学2006-2009年离散数学考博真题 .pdfVIP

同济大学考博离散数学试题 2006 年试题（330） 一、 给出下列定义，简要叙述其作用。（15 分）（1）关系；（2 ）合取范式；（3 ）格 二、 证明下列命题(50 分) ( ) 2n 1. 集合 A 的幂集P Α 中元素个数为 。 (答案参见《离散数学 理论·分析·题解》第 148 页 3—66) 2. 一有向图G=(V, E) ，其基本回路长度不大于|V| ，V 是结点集。 (答案可借鉴《离散数学》第280 页定理 7-2.1 证明，此时有结点v =v ，j=k) j k 3. 代数系统S, o o ，运算“ ”若存在单位元素，则必惟一。 (答案参见 《离散数学》p181 定理 5-2.1 证明，零元证明参见 《离散数学理论·分析·题 解》p268 5—6) （P →Q ）→R ⇔（P ∨R ）∧（¬Q ∨R ） 4. 。 A, ° a,b,c ∈A a ≤b ≤c ≤ 5. 设 是格，任意 ，且满足 （注： 为偏序关系符号）， 证明 (a ∧b) ∨(b ∧c) =(a ∨b) ∧(a ∨c) 。 (答案参见《离散数学 理论·分析·题解》第 326 页 6—10) 三、 综合题(35 分，第 1 题 15 分，第 2 题 20 分) { }{ }{ } 1． 有集合 3,5,15 , 1,2,3,6,12 , 3,9, 27,54 ，其上面的偏序关系为整除，画出集 合的偏序关系图，并指出哪个是全序关系。(答案参见《离散数学 理论·分析·题解》第 184 页 3—136) 2 ． 有一农村集市平时每天开放，遇雨天则三天开放一次，用有限状态机实现该模型。 离散 1． 函数、映射和关系的定义及其它们间的不同。 2 ． 根据所给出的条件构造一个 自动机，并转换成另一种自动机形式。 3 ． 证明谓词关系式两边等价。 4 ． 有关群、子群的相关证明。 5 ． 证明某偏序关系是否是格。 6 ． 有关左陪集和右陪集的一个证明。 同济大学考博离散数学试题 2007 年试题（330） 一、 写出定义（15 分） （1）格； （2 ）置换； （3 ）图。 二、 证明下列命题(50 分) 1. 不记得 2. 等价式证明题。 3.下列合取范式是否为可满足的： E ＝（X ∨¯X ）∧（¯X ∨X ）∧¯X (答案：可满足解为（1,1,0）或(0,0,0)，可能用 1 2 1 2 3 真值表法求解比较好) 4. 不记得 5. 证明图的边数与图的度数的关系，即图的度数为 2n，n 为边数。 (答案见《离散数学》第 274 页定义 7-1.2 证明) 三、综合题(35 分，第 1 题 15 分，第 2 题 20 分) 1． 不记得 2 ．找一种9 个 a，9 个 b ，9 个 c 的圆形排列，使由字母｛a,b,c ｝组成的长度为3 的 27 个字的每个字仅出现一次。 (答案参见《离散数学 理论·分析·题解》第 387 页 7— 同济大学考博离散数学试题 2008 年试题（330） 一、 名词解释并说明其作用（15 分） 1．格 2.关系 3.代数系统 二、 证明下列命题（50 分） 1． R 为等价关系，则必有等价类 2 ． 一个图是欧拉图的充要条件是图中各点的度为偶数 3 ． 证