离散复习题

离散数学复习资料

一、填空

1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，L(x,y):x?y则命题的逻辑谓

词公式为 。

2. 设p：王大力是100米冠军，q：王大力是500米冠军，在命题逻辑中，命题“王大力不但是100米冠军，

而且是500米冠军”的符号化形式为 。命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。 3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= 。 4. 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词

?x(P(x)??y(O(y)?N(y,x))) 的自然语言是 。

5. 设个体域是{a,b}，谓词公式(?x)?P(x)?(?x)P(x)写成不含量词的形式是 。 6. 谓词?x?y(?z(P(x,z)?P(y,z))??uQ(x,y,u))的前束范式为 。

7. 命题公式A?P?(?P?(Q?(?Q?R)))的主合取范式为 ，其编码表示为 。 8. 设E为全集， ，称为A的绝对补，记作～A，且～（～A）= ，～E = ，

～?= 。

9. 设A={2，，56},B?{2，，34},C?{1，，34}，则A-B= ，A?B = ，A×C = 。 10. 设A?{a,b,c}考虑下列子集S1?{{a,b},{b,c}}，S2?{{a},{a,b},{a,c}}，

S3?{{a},{b,c}}，S4?{{a,b,c}}，S5?{{a},{b},{c}}，S6?{{a},{a,c}}

则A的覆盖有 ，A的划分有 。

11. 设M?{x1?x?12,x被2整除，x?Z}，N?{x1?x?12,x被3整除，x?Z}，则 M?N? ，

M?N? 。

12. 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},则A?B= ，A?B= 。

13. A={1，2，3，4，5，6}，A上二元关系T?{?x,y?|x?y是素数}，则用列举法 T= ；T的关系图

为 ，T具有 性质。

14. 偏序集?A,R??的哈斯图为

n，则R?= 。

15. 设A?{x|x?2,n?N}，定义A上的二元运算为普通乘法、除法和加法，则代数系统中运算*关

于 运算具有封闭性。

16. A，B，C表示三个集合，文图中阴影部分的集合表达式为 。

1

?0??117. 设图G = < V，E >，V?{v1,v2,v3,v4}的邻接矩阵A??1??1?A B C 101001001??1??，则的入度 deg(v1)= ，v4v1?0?0??的出度deg?(v4)= ，从v2到v4的长度为2的路径有 条。

18. 结点数n（n?3）的简单连通平面图的边数为m，则m与n的关系为 。 19. 设 f，g是自然数集N上的函数?x?N,f(x)?x?1,g(x)?2x，则f?g(x)? 。

20. 设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下： [i]?3[j]?[(i?j)mod3]，

则+3的运算表为 ；是否构成群 。 21. 集合S={α，β，γ，δ}上的二元运算*为

* α β γ δ α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ 那么，代数系统中的幺元是 ，α的逆元是 。 22. 设< {a,b,c}, * >为代数系统，* 运算如下：

* a b c a a b c b b a c c c c c

则它的幺元为 ；零元为 。

23. 设A={a，b，c}，A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} , 则s（R）= 。 24. 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},则A?B= ，A?B= 。 25. 设集合X={1,2,3}，下列关系中 不是等价的。 A= {<1,1>,<2 , 2 >,<3 , 3 >}

B= {<1,1>,<2 , 2 >,<3 , 3 >,<3,2>,<2 ,3 >} C= {<1,1>,<2 , 2 >,<3 , 3 >,<1,4>}

2

D= {<1,1>,<2 , 2 >,<1 , 2 >,<2,1>,<1 ,3 >,<3,1>,<3 , 3 >,<2 , 3 >,<3,2>}

?3,3?}，则r (R)= ；s (R)= ；t (R) = 。 26. 设X?{1,2,3,4},R?{?1,2?,?2,4?，27. 设G是n阶完全图，则G的边数m= 。

28. 设A={a，b，c，d}，其上偏序关系R的哈斯图如右图所示：则 29. n阶完全图Kn的边数为 。

30. 结点数n（n?3）的简单连通平面图的边数为m，则m与n的关

系为 。 R= 。

31. 图的补图为 。

32. 有向图 中从v1到v2长度为2的通路有 条。

33. 设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 个5度结点。

34. n阶完全图结点v的度数d(v) = 。

二、证明

1. 不构造真值表证明蕴涵式

(Q?(P??P))?(R?(R?(P??P)))?R?Q

2. 证明A?B?C?D,D?E?F?A?F 3. 证明(P∧Q)∨(P∧?Q) ? P

4. 证明((P?Q?R))?(P??Q)?R 5. 证明?x(P(x)?Q(x))??xP(x)??xQ(x) 6. 证明?x(P(x)?Q(x))??xP(x)??xQ(x) 7. 用推理规则证明下式：

前提: (?x)P(x)??x((P(x)?Q(x))?R(x)),(?x)P(x),(?x)Q(x) 结论：(?x)(?y)(P(x)?R(y))

3

8. 设论域D={a , b , c}，求证：?xA(x)??xB(x)??x(A(x)?B(x))。 9. 设g?f是复合函数，如果g?f满射，则g也是满射。

10. 假定f:A?B,g:B?C，且g?f是一个满射，g是个入射，则f是满射。 11. 用反证法证明(P?Q)?(P?R)?(Q?S)?S?R。

12. 设< I ，+ >是一个群，设IE={ x|x=2n ，n∈I }，证明< IE ，+ >是< I ，+ >的一个子群。

三、按要求解答

1. 将谓词公式((?x)P(x)?(?y)Q(y))?(?y)R(y)化为前束析取范式与前束合取范式。

2. 用推理规则论证：如果今天是星期六，我们就要到颐和园或圆明园玩，如果颐和园游人太多，我们就不去颐

和园玩。今天是星期六，颐和园游人太多，所以，我们去圆明园玩。

3. 符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。

4. 用推理规则论证：或者逻辑难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑并不难学。因此，

如果许多学生喜欢逻辑，那么数学并不难学。

5. 设有下列情况，用推理规则论证结论是否有效？ （a）或者天晴，或者下雨。（b）如果天晴，我去看电影。

（c）如果我去看电影，我就不看书。结论：如果我在看书则天在下雨。

6. 符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论。 7. 给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：(Q?R)?(P??R)的真值。

8. 将?x(?(?yP(x,y))?(?zQ(z)?R(x)))化为与其等价的前束范式。 9. 把公式??x?P?x????x?Q?x?转化为前束范式 10. 求(Q?P)?(?P?Q)的主合取范式。

11. 求(A?B?C) ?(?A?(?B??C))的主析取范式与主合取范式。 12. 求(P∨Q)?R的主析取范式与主合取范式。

13. 设命题A1，A2的真值为1，A3，A4真值为0，求命题

(A1?(A2?(A3??A1)))?(A2??A4)的真值。

14. 求集合An??x0?x???1??n?(n?1,2,3,?)的并与交。

15. 设X={1,2,3,4,5}，X上的关系R={<1,1> , < 1 , 2 > , <2 , 4 > , < 3 , 5 > , < 4 , 2 > }，求R的传递闭包t (R)。 16. 设集合X?{a，b，c，d}上的关系R???a,b?,?b,a?,?b,c?,?c,c??。求R的传递闭包t(R)。 17. 在实数平面上，画出关系R???x,y?x?y?2?0?x?y?2?0?，并判定关系的特殊性质。

18.设X={ a，b，c，d }，R是X上的二元关系,R={< a ，c >，< a ，d >，< b ，c >，< b ，d >，< c ，

4

d >}

(1) 画出R的关系图。(2) 写出R的关系矩阵。(3) 说明R的性质

19. A={a,b,c,d}，R={,,,}为A上的关系，利用矩阵乘法求R的传递闭包，并画出t（R）的

关系图。 20. 设S={1 , 2 , 3 , 4, 6 , 8 , 12 , 24}，“?”为S上整除关系，问：（1）偏序集?S　,??的哈斯图如何？（2）偏

序集{S　,?}的极小元、最小元、极大元、最大元是什么?

21. 集合A?{2,3,6,12,24,36}上的偏序关系为整除关系。设B?{6,12}，C?{2,3,6}，试画出哈斯

图，并求A，B，C的最大元素、极大元素、下界、上确界。

22. 对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。

可结合性 可交换性 存在幺元 存在零元 Max Min + 23. 设B4={e , a , b , ab }，运算*如下表，

则是一个群（称作Klein四元群）。

24. 设S = R - {-1}（R为实数集），a?b?a?b?ab。

（1）说明?S,??是否构成群； （2）在S中解方程2?x?3?7 。 25. 设X＝{1，，，234}，R是X上的二元关系，

R＝{?1，1?，?3，1?，?1，3?，?3，3?，?3，2?，?4，3?，?4，1?，?4，2?，?1，2?}

* e a b ab e e a b ab a a e ab b b ab ab ab b e a a e b (1) 画出R的关系图。写出R的关系矩阵。说明R是否是自反、反自反、对称、传递的。 26. 设I?是负整数集合，定义二个双射函数f、g，

f:I??I?f?x?? ? x ?{??1,1?，??2,2?,<-3,3>,?}, g?x?? x?1?{?1,0?，?2,1?,<3,2>,?}，

5

g:I??N

求g?f，并说明其是否是双射函数。

27. 设M= {0o,60o,120o,240o,300o,180o}表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算*，对M中

任一元素a,b有a*b=图形旋转(a+b)的角度，并规定当旋转到360o时即为0o。是否是群。

* 0o 60o 120o 180o 240o 300o

0o 0o 60o 120o 180o 240o 300o

60o 60o 120o 180o 240o 300o 0o

120o 120o 180o 240o 300o 0o 60o

180o 180o 240o 300o 0o 60o 120o

240o 240o 300o 0o 60o 120o 180o

300o 300o 0o 60o 120o 180o 240o

28. 求图中的一棵最小生成树。

v1?0?v2?0A?v3?1?v4??129. 已知某有向图的邻接矩阵如下：

001011000??1?1??0?? 试求：v3到v1的长度为4的有向路径的条数。

30. 下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。

31. 求图的可达矩阵，并判断图的连通性。

32. 有向图G如图所示，试求：(1) 求G的邻接矩阵A。(2) 求出A2、A3和A4（3）v1到v4长度为1、2、3和4

的路径有多少？(4) 求出可达矩阵P。

6

V3

33. 画一个有一条欧拉回路和一条汉密尔顿回路的图。画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。

画一个有一条欧拉回路，但有一条汉密尔顿回路的图。 34. 下面两图是否同构，若是给出点集间的同构映射。

35. 已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）。 36. 图给出的赋权图表示五个城市v1，v2，v3，v4，v5

及对应两城镇间公路的长度。试给出一个最优化的设计 方案使得各城市间能够有公路连通。

7

本文来源：https://www.bwwdw.com/article/40v7.html