离散数学复习题(全) 下载本文

内容发布更新时间 : 2024/12/23 20:07:28星期一 下面是文章的全部内容请认真阅读。

离散数学复习资料

一、填空

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的关系为 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