2011级《离散数学I》期末考试试题(A卷)
一、简答题（本大题共20小题，每小题2分，共40分；不必写计算或证明过程） 设A={a,b,c,d,e,f}, A上的一个划分C={{a}{b,c}{d,e,f}}，那么C所对应的等价关系RC的元素个数是多少？
2. 设A={a,b,c}，B={1,2,3}，R、S是A与B上的关系，且R={(a,1),(b,2),(b,3)}，
S={(a,1),(b,1),(c,1)}，那么R和S可定义为A到B内映射吗？
3. 设集合A={1,2,3,4}，则集合A上既是对称又是反对称的关系有多少个？ 4. 请问公式Q?(?Q?P)是恒真？恒假？还是可满足的？ 5. 公式P?? (P?Q)?Q的主析取范式是什么？
6. 设公式G= P→Q，H= (R→P)→Q，则H是否蕴含G?
7. 设个体域D={-2,3,6}，谓词P(x):x≤3，Q(x):x>5，R(x):x≤7。试判断下列公式为
真还是为假？
(1) ?x(P(x) ?Q(x)) (2) ?x(R(x) →P(x)) ?Q(3)
8. 设谓词公式G的Skolem范式为S，若解释I满足G，则I一定满足S吗？G与
S可满足性等价吗？
9. 设图G中有n个点m条边，每个点的度不是k就是k+1,求具有k度点的个数。 10. 判断下面两个邻接矩阵所表示的简单图是否同构？
1.
?0?1??0??11001b00011?1?? , 1??0?5?0?1??1??11001d10011?1?? 1??0?5f711. 确定下面权图中从点a到z的最短路及其长度。
4a3c6e5g2312z4
第 1 页 共 2 页
12. 请指出下面(a)、(b)、(c)三个有向图中哪些是欧拉图。
(a) (b) (c)
13. 欧拉图中每一个点都是根吗？恰有一个根且无回路的有向图一定是有向树吗？ 14. 在完全图K5中最多有多少个不同（非同构）的支撑树？ 15. 一个有11个点的树，其补图有多少条边？
c c 16. 请画出 K 4 K 3 ,请问该图是哈密顿图吗？
17. 任意整数整除0吗？整数集合上的整除关系是部分序关系吗？ 18. 29-1与214-1互质吗？
19. 写出模9的一个完全剩余系。
20. 同余式ax≡1（Mod m）什么情况下有解？什么情况下无解？ 二、解答题（本大题共2小题，每小题10分，共20分）
21. 设命题公式集合S={?P, Q, ? (P?Q), P?Q, P?Q, P?Q, 1, 0 }，“?”为S上蕴含
关系，则(S, ?)为部分序集，请画出(S, ?)的Hasse（哈塞）图，指出其中的最大元、最小元、极大元、极小元；并求B={?P, Q, P?Q }的上界、下界、上确界、下确界。 22. 解同余式126x≡6（Mod 303）
三、证明题（本大题共4小题，每小题10分，共40分） 23. 设R是集合A上的等价关系，证明：R2=R。
24. 用形式演绎法证明{P→(Q?R)，Q→?P，M→?R}?P→?M 25. 证明：?xA(x)→?x B(x) ? ?x(A(x)→B(x))
26. 若有限图G中恰有两个奇数度点，证明这两个奇数度点必然相连。
第 2 页 共 2 页