同济大学博士研究生入学考试离散数学试题
同济大学2006年博士研究生入学考试离散数学试题 9Z rn(D
一、给出下列定义，简要叙述其作用。（15分） cDTDim1F
（1）关系；（2）合取范式；（3）格 &U
'Ds!
二、证明下列命题(50分) QW2% Gv :
1. 集合A的幂集 m@c2'*&Y
中元素个数为 。 FpRK^MEkG
2. 一有向图 ，其基本回路长度不大于 ，V是结点集。 t%dPj8~
3. 代数系统 ，运算“ ”若存在单位元素，则必惟一。 _ve7Is`/
4. 。 hcaH
5. 设 是格，任意 ，且满足 （注： 为偏序关系符号），证明 。 jA]xpf6}
三、综合题(35分，第1题15分，第2题20分) /|DQ_<*
1． 有集合 ，其上面的偏序关系为整除，画出集合的偏序关系图，并指出哪个是全序关系。 2． 有一农村集市平时每天开放，遇雨天则三天开放一次，用有限状态机实现该模型。 t1~*q)!Mo
离散 sU}e78m h
1． 函数、映射和关系的定义及其它们间的不同。 W4YC5ZH{l
2． 根据所给出的条件构造一个自动机，并转换成另一种自动机形式。 =q"3a9 pb7
3． 证明谓词关系式两边等价。 WD )[Ac[
4． 有关群、子群的相关证明。 Y|lMa?\E
5． 证明某偏序关系是否是格。 ):[[Ch_
6． 有关左陪集和右陪集的一个证明。 |F=^Cu,
!{3pp
|