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

《同济大学2006-2009年离散数学考博真题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、同济大学考博离散数学试题2006年试题（330）一、给出下列定义，简要叙述其作用。（15分）（1）关系；（2）合取范式；（3）格二、证明下列命题(50分)n1.集合A的幂集P()Α中元素个数为2。(答案参见《离散数学理论·分析·题解》第148页3—66)2.一有向图G=(V,E)，其基本回路长度不大于

2、V

3、，V是结点集。(答案可借鉴《离散数学》第280页定理7-2.1证明，此时有结点vj=vk，j=k)3.代数系统，运算“”若存在单位元素，则必惟一。o(答案参见《离散数学》p181定理5-2.1证明，零元证明参

4、见《离散数学理论·分析·题解》p2685—6)4.（P→Q）→R⇔（P∨R）∧（¬Q∨R）。5.设是格，任意a,b,cA∈，且满足a≤b≤c（注：≤为偏序关系符号），证明()abbcabac∧∨∧=∨∧∨()()()。(答案参见《离散数学理论·分析·题解》第326页6—10)三、综合题(35分，第1题15分，第2题20分)1．有集合{3,5,15,1,2,3,6,12,3,9,27,54}{}{}，其上面的偏序关系为整除，画出集合的偏序关系图，并指出哪个是全序关系。(答案参见《离散数学理论·分析·题解》第184

5、页3—136)2．有一农村集市平时每天开放，遇雨天则三天开放一次，用有限状态机实现该模型。离散1．函数、映射和关系的定义及其它们间的不同。2．根据所给出的条件构造一个自动机，并转换成另一种自动机形式。3．证明谓词关系式两边等价。4．有关群、子群的相关证明。5．证明某偏序关系是否是格。6．有关左陪集和右陪集的一个证明。同济大学考博离散数学试题2007年试题（330）一、写出定义（15分）（1）格；（2）置换；（3）图。二、证明下列命题(50分)1.不记得2.等价式证明题。3.下列合取范式是否为可满足的：E＝（X1∨¯X2）

6、∧（¯X1∨X2）∧¯X3(答案：可满足解为（1,1,0）或(0,0,0)，可能用真值表法求解比较好)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分）

7、1．格2.关系3.代数系统二、证明下列命题（50分）1．R为等价关系，则必有等价类2．一个图是欧拉图的充要条件是图中各点的度为偶数3．证明两条件命题等价，例如：A→⇔¬∨BAB4．半群中单位元e唯一5．格中abcd≤≤≤，类似证明()abcb∨∧=三、综合题（35分）1．给定两个图，说明其同构2．画{abcd,,,}的幂集对应的哈斯图3．设计一个有限状态机M，接收a、b字符，a的个数为偶数，b的个数为3的倍数。同济大学考博离散数学试题2009年试题（330）一、名词解释并说明其作用（15分）1．函数2.群3.代数系统二、

8、证明下列命题（50分）1．集合A的幂集中元素个数为2．一个图是欧拉图的充要条件是图中各点的度为偶数3．证明两条件命题等价？（此题不确定）4．半群中单位元e唯一5．给出一个偏序集，证明它是格。（具体的记不清了）三、综合题（35分）1．给定两个图，说明其同构2．有集合，其上面的偏序关系为整除，画出集合的偏序关系图，并指出哪个是全序关系。3．有一农村集市平时每天开放，遇雨天则三天开放一次，用有限状态机实现该模型。