浙江师范大学离散数学期末试卷A.doc

;.浙江师范大学离散数学考试卷（20102011学年第 1 学期）考试形式闭卷使用学生 软件工程、网络工程09 考试时间 120分钟出卷时间 2010 年 12 月 26 日说明：考生应将全部答案都写在答题纸上，否则作无效处理。一选择题（每题2分，共20分）：1. 设P：我平时认真学习，Q：我通过离散数学考试，则如下哪种说法能符号化为PQ：（ ）A除非我平时认真学习，否则我不能通过离散数学考试。B. 若我平时认真学习，则我通过离散数学考试。C. 因为我平时不认真学习，所以我没有通过离散数学考试。D. 我通过离散数学考试仅当我平时认真学习。2命题公式P(PQR) 为（ ）。A重言式 B可满足式 C矛盾式 D等值式3设集合A=c, c，下列命题错误的是（ ）。A. cP(A) B. cP(A) C. cP(A) D. cP(A)4. 设f: NN, f(x)=(x) mod 5, 即x除以5的余数，则函数f （ ）.A. 仅单射 B. 仅满射 C. 双射 D. 既不单设也不满射5下列命题中正确的结论是：（ ）A集合上的关系如果不是自反的，就一定是反自反的；B集合上的关系如果不是对称的，就一定是反对称的；C在任意关系R上，若、R，则必有R；D非空集合A上的恒等关系既是等价关系又是偏序关系6. 设集合A=a, b, c，A上的关系R=, ，则下列结论错误的是：（ ）AR-1 = , ； B. r(R) = R；Cs(R) = , , , ； D. t(R) = R7设集合A和二元运算*，可交换的代数运算是（ ）。A设，运算是矩阵的乘法B设C设D设8以下命题中不正确的结论是（ ）A循环群必为交换群； B交换群必为循环群；C素数阶群必为循环群； D群的运算满足消去率。9. 8阶有限群的任何子群一定不是（ ）的。A. 2阶 B. 3 阶 C. 4 阶 D. 8 阶10以下命题中正确的结论是（ ）An = 2k (k 1)时，完全图Kn必为欧拉图；B如果一个连通图的奇度顶点的个数大于2，那么它可能是一个欧拉图；C无向图中，顶点连通关系 是顶点集V上的等价关系；D顶点度数列(5, 4, 3, 2, 2)可简单图化。二填空题（每题2分，共20分）11. 设p: 张三的祖籍是山东，q：张三的祖籍是浙江，则“张三的祖籍是山东或浙江”可符号化表示为： 。12设个体域为D=a, b，则公式$x (F(x) G(x) )的量词消去后的公式为： 。13. 设A、B为集合，|A|=5, |B|=8, |AB|=3, 则|AB| = 。14设集合A = a, b, c, d，A上的二元关系R = , , , ，则R2= 。15设集合S = a, b, c 上的二元关系R的关系矩阵，则R具有的基本性质为 。16. 设A=1, 3, 5，A上的二元运算*为：a*b=maxa, b，则在独异点中，单位元是 ，零元是 。17. 设a是8阶群G的生成元，则a3是 阶元，a4是 阶元。18设G是有限群且|G| = 6，H是G的子群且|H| = 2，则在中的右陪集个数为 。19无向图G有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点，则G一共有 个顶点。20已知下图，它的点连通度为 ，边连通度为 。三计算题（每小题9分，共45分）21用等值演算方法求出如下两个公式的主析取范式，并由此判定它们是否等值：pqr与p(qr)22设集合A1, 2, 3, 4, A上的二元关系R = , , , IA，通过画出关系图来分析说明R是否为A上的等价关系；若为等价关系，则列出所有的等价类。23设，为整除关系，(1)画出偏序集的哈斯图；（2）找出的极大元、极小元、最大元、最小元；（3）在中求的上界、下界、最小上界、最大下界。24设是18阶循环群，（1）求出的所有生成元；（2）求出的所有子群。25求如下有向图D的邻接矩阵，并求出从顶点v3到顶点v4长度分别为1, 2, 3, 4的通路数。四证明题（第26题5分，第27题10