离散数学

《离散数学》综合复习资料

一、判断题

1．如果有限集合A有n个元素，则其幂集p(A)有2n个元素。

2．R1，R2是集合A上的二元关系，若R1和R2都是反自反的，则R1R2也是反自反的。

3．“这朵玫瑰花多美丽呀！”是一个命题。

4．A、B、C是任意集合，如果A?B及B?C，则A?C。 5．“中国有四大发明”是一个命题。 6．对任意集合A，A

。

7．集合A的一个划分确定A的元素间的一个等价关系。 8．含有幺元的半群为独异点。

9．每个图中，边数等于结点度数总和两倍。 二、基本题

1. 将下列命题符号化： （1）4是偶数和合数。

（2）如果天不下雨，王荣就去图书馆。 （3）所有人都是要死的。

2. 求命题公式P?(P?Q)的主合取范式。 3. 举出A={a,b,c}上的二元关系R和S满足： （1）R是自反的、对称的； （2）S是对称的、传递的。

4. 已知图G的邻接矩阵M如下，结点集为{v1,v2,v3,v4,v5}，试画出该图，并求V2的入度d-(V2)和出度d+(V2)。

0 1 0 0 0

0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0

M=

5. 将下列命题符号化：

（1）如果张三和李四都不去，她就去。 （2）今天要么是晴天，要么是雨天。

（3）每一个有理数都是实数。 6. 求命题公式?(P?Q)的主析取范式。 7. 举出A={a,b,c}上的二元关系R和S满足： （1）R既不是自反的又不是反自反的； （2）S既不是对称的又不是反对称的。

8. 已知图G的邻接矩阵M如下，结点集为{v1,v2,v3,v4,v5}，试画出该图，并求V2的入度d-(V2)和出度d+(V2)。

0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0

M=

9. 举出A={a,b,c}上的二元关系R和S满足： （1）R是自反的、传递的； （2）S是反自反的、传递的。

10. 设集合为A ={1，3，4，12，24}，其上的偏序关系为整除，试列出相应的关系并画出哈斯图。

11. 二元运算a*b=a+b-ab在实数集R上是否满足交换律和结合律?

12. 设集合为A ={1，2，5，10，20}，其上的偏序关系为整除，试列出相应的关系并画出哈斯图。

13. 二元运算a*b=a+b-3在实数集R上是否满足交换律和结合律? 三、证明题

1. 试证明：A?B, ?(BC) ? ?A

2. 设R,S是A上的等价关系，证明R?S也是A上的等价关系。

3. 设?G,*?是一群，x?G。定义：a?b?a*x*b，?a,b?G。证明?G,??也是一群。 4. 试证明：A?(B?C), ?DA, B ? D?C

5. 在任何有向图中，所有结点的入度之和等于所有结点的出度之和。 6. 试证明：?AB, C??B?A??C

7. 设R，S是A上的相容关系，证明R?S也是A上的相容关系。 8. 设G=有11个结点，m条边，证明G或者其补图G’是非平面图。

9. 设f是从A到B的一个函数，定义A上的关系R：aRb当且仅当f(a)=f(b)，证明R是A上的等价关系。

10. 试证明代数系统为群，已知*运算满足结合律，运算表如下表所示。

* a b c d a a b c d b b a d c c c d a b d d c b a 11. 在有6个结点12条边的连通简单平面图中，每个面由3条边围成。

《离散数学》综合复习资料参考答案

一、判断题 题目 答案 1 错误 2 正确 3 错误 4 正确 5 正确 6 错误 7 正确 8 正确 9 错误 二、基本题 1. 答案： （1）（p∧q） （2）（p→q）

（3（(?x)(R(x)?Q(x))） 2. 答案：

解：原式?P?(?P?Q) ?(P? (?Q?Q)) ? ( ?P?Q) ?(P??Q)?(P?Q)?(?P?Q) 3. 答案：

解：此题答案不唯一

（1）R = {,,,,} （2）S={,,} 4. 答案：

解：该矩阵不对称，所以G是有向图，如右图。d-(V2)=2，d+(V2)=1 5. 答案：

（1）（（?P??Q）?R） （2）（PQ）

（3） ((?x)(R(x)?Q(x))) 6. 答案： 解：?(P?Q)