离散数学复习资料
一、填空
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上的二元运算为普通乘法、除法和加法，则代数系统
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的关系为 m<=3n-6 。 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