吉林大学2011级离散数学I(A卷)

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 页

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4