离散数学复习资料
一、填空
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 = ，
～?= 。
5，6},B?{2，3，4},C?{1，3，4}，则A-B= ，A?B = ，A×C = 。 9. 设A={2，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具有 性质。
1
14. 偏序集?A,R??的哈斯图为，则R?= 。
15. 设A?{x|x?2n,n?N}，定义A上的二元运算为普通乘法、除法和加法，则代数系统
中运算*关于 运算具有封闭性。 16. A，B，C表示三个集合，文图中阴影部分的集合表达式为 。
A B C ?0??117. 设图G = < V，E >，V?{v1,v2,v3,v4}的邻接矩阵A??1??1?101001001??1?，则v1的入度 ?0?0???deg(v1)= ，v4的出度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={α，β，γ，δ}上的二元运算*为
* α β γ δ α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ 那么，代数系统
2
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>}
D= {<1,1>,<2 , 2 >,<1 , 2 >,<2,1>,<1 ,3 >,<3,1>,<3 , 3 >,<2 , 3 >,<3,2>}
?3,3?}，26. 设X?{1,2,3,4},R?{?1,2?,?2,4?，则r (R)= ；s (R)= ；t (R) = 。
27. 设G是n阶完全图，则G的边数m= 。
28. 设A={a，b，c，d}，其上偏序关系R的哈斯图如右图所示：则
R= 。
29. n阶完全图Kn的边数为 。
30. 结点数n（n?3）的简单连通平面图的边数为m，则m与n的关系为 。
31. 图的补图为 。
3
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))
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 ，+ >的一个子群。
4
三、按要求解答
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?1,2,3,?)的并与交。 n?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)。
5