离散数学复习题(30页).doc

《离散数学复习题(30页).doc》由会员分享，可在线阅读，更多相关《离散数学复习题(30页).doc（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-离散数学复习题-第 28 页离散数学复习题一、 单项选择题1. 下列句子是原子命题的是 （ A ）A. 大熊猫产在我国；B. 2+x=5; C. 小王和小李是学生；D. 别讲话了！2. 设p：天下雨，q：我去新华书店，命题“除非天不下雨，我去新华书店”的符号化形式为 （ D ）Apqqpqp pq3. 以下命题不是重言式的有 （ A ）A. PP B. PP C. (PQ)(QP) D. PPQ4. 以下语句中不是命题的为 （ B ）A明天我要上门去谢你。谢谢你给了我机会。 如果不说，我就不谢你。除非你做了，我才谢你5与($x) M(x) 等价的是 （ D ）A(x) M(x)($x) M(

2、x)(x) M(x)(x) M(x)6. 设P(x)为“x是大学生”，Q(x)为“x满30岁”。命题“所有大学生都不满30岁”写成谓词公式为 （ C ）A. x(P(x)Q(x) B. x(P(x)Q(x) C.x(P(x)Q(x) D. x(P(x)Q(x)7.公式 (x) (P(x)(y)R(x, y)中，x的辖域为 （ B ）AP(x)(P(x)(y)R(x, y) P(x)和R(x, y)P(x)(y)8设S=a, b, c,则S的幂集的元素的个数有 （ C ） A3 6 . 899以下等式中不正确的是： ( A )AA(BC)=(AB)(AC)A(BC)=(AB)(AC) （AB)C

3、=(AC)(AC)(AB)C=A(BC)10设A=1, 2, 3, 4, A上的等价关系R=, , , IA, 则对应于R的A的划分是 ( D )A1,2, 3, 41, 2,3, 4 1,2, 3, 41,2, 3, 411设函数 f：1，21，则f是 ( B ) A入射B满射C双射D非入射非满射 12设Z是负正整数集合，+，*，是普通数的加法、减法和平方运算，则能构成代数系统是 ( B )A 13若 他聪明， 他用功，则“他虽聪明但不用功”，可符号化为 （ B ）A. B. C. D. 14. 若一个代数系统(A，*)满足运算封闭性及结合律，且有幺元，则它是 ( A )A独异点B群C格D布

4、尔代数15设G为无限群，则 ( C ) A G是交换群 G是循环群 G中每个元素都有逆元G中每个元素的阶都是无限的 16在有3个结点的图中，度数是奇数的结点的个数为 ( D )A13. 1或30或217在5阶图G中，若从结点v1到v4存在路，则从v1到v4的路中必存在路，其长度小于等于 ( D )A12. 34 18连通平面图G的面的次数之和为10，则其边数为 ( A )A510. 152019. 在自然数集合上，下列哪种运算不是可交换的 （ D ）A. B. C. D. 20. 设简单图的最大结点度数为，图的结点数为,则与的关系为 ( B )A. B. C. D. 与没关系21下列各项中错误

5、的是（ A ）A B C D22设，下列各式成立的是（ C ）A B C D23连通平面图中，所有面的次数之和是 （ C ）A边数 B边数的一半 C边数的两倍 D边数的一倍24无向图 具有一条欧拉回路，那么图 的所有结点的度数都是（ B ）A奇数 B偶数C素数 D125. 下列集合哪个是最小联结词集 （ D ）A. B. C. D. 26. 设简单图的最大结点度数为，图的结点数为,则与的关系为 （ B ）A. B. C. D. 与没关系27. 设集合A=1,2,3，B=2,3,4,5，C=2,4,8,16,D=1,2,3,4,设“|”是集合上的“整除”关系，则下列偏序集中能构成格的是 （ C

6、）A. ;B. ;C. ;D. ;28设 上的二元关系,则关系具有的性质是哪一个 （ B ）A. 自反性B. 对称性C. 传递性D. 反对称性29判断下列各式中不是合式公式的是哪一个 （ C ）A. B. C. D. 30. 代数系统(S,)中以下断言正确的是 （ C ）A. 单位元与零元总是不相等； B. 可能有二个左单位元和一个右单位元；C. 单位元总有逆元； D. 若SS，则(S,)是(S,)的子代数31. 指出下列语句中哪个是原子命题 （ A ）A. 苏州是中国的首都。B. 王强不但聪明而且用功。C. 明天下午我乘Z86次或K256次列车去北京。D. 如果天不下雨，我就骑车上班。32.

7、 设，则下列哪个集合是从的函数（ C ）A. B. C. D33. 在谓词演算中，下列各式正确的是 （ A ）A. B. C. D. 34. 设（A,+, ）是整环，则以下断言错误的是 （ D ）A. （A,+）是阿贝尔群 B.（A,）是可交换独异点 C. 运算对可分配 D.（A,）有零因子35. 以下格是分配格的是 （ C ）A. 钻石格 B. 五角格 C. 小于5个元素的格 D. 含与钻石格同构的子格的格36. 指出下列语句中哪个是复合命题 ( C )A. 5是奇数 。B. 苏州是中国的首都。C. 如果天不下雨，我就骑车上班。D. 火星上有生物。37前提的结论是 （ A ）A. B.C.

8、D.38谓词公式中变是 （ C ）A.自由变元 B.约束变元C.既是自由变元又是约束变元 D.既不是自由变元又不是约束变元39. 公式(x)(y)(P(x,y) Q(x,y) (x)P(x,y)中(x)的辖域是 （ B ）A. P(x,y) B. P(x,y)Q(x,y) C. Q(x,y) D. (P(x,y) Q(x,y)(x)P(x,y)40. 以下符号串不是合式公式的是 （ B ）A. PPQ B. (PQ)(QP) C. PPS D. P(PQ)Q41公式中 的辖域为 （ C ）A. B. C. D. 42若 今天下雪了； 路滑；则“虽然今天下雪了，但是路不滑”，可符号化为 （ D

9、）A. B. C. D. 43. 设上的二元关系,则等于是(B ）A. B. C. D. 44. 指出下列语句中哪个是命题 （ D ）A. 这本书真好看啊！B. 上课请不要迟到！C. 你吃午饭了吗？D. 李白是唐朝的诗人。45. 设A=1,2,3,4,5,6,7,8,式子为真是 （ C ）A. 1 A; B. 1,2,3 A; C. 4,5 A; D. A.46. 设 A=a,b,c 上的关系如下, 有传递性的为 （ D ）A. A1=, B. A2=, C. A3=, D. A4= 47. 集合A上的等价关系R, 其等价类的集合称为 （ C ）A. A与R的并集, 记作 A R B. A与R

10、的交集, 记作 A R C. A关于R的商集, 记作 A/RD. A与R的差集, 记作 A-R.48设是连通平面图，中有6个顶点8条边，则的面的数目是 （ C ）A2个面B3个面 C4个面D5个面49. 设A = 1,2,3,4 , A上关系R1 = (1,2),(2,3),(3,4),(4,1), R2 = (1,2),(2,3), (3,2), 则中是映射的为 （ B ）A. R1,R2; B. R1; C. R2; D. 没有50. 设N是自然数集，a,bN使(N,*)不是半群的运算是 （ D ）A. a*b=max(a,b) B. a*b=min(a,b)C. a*b=a+b+2 D.

11、 a*b=a+2b51. 由n个点0条边组成的图称为 （ A ）A. 零图 B. 平凡图 C. 完全图 D. 多重图52. 给定下列序列, 哪一个不能构成无向简单图的结点度数序列 （ D ）A. (1,1,2,2,4) B. (1,1,2,2,2,) C . (2,1,3,3,3) D. (1,3,4,4,5)53设是个结点，条边和个面的连通平面图，则等于 （ A ）ABCD54无向图具有一条欧拉回路，那么它们所有结点度数是 （ A ）A偶数B奇数C素数 D155. 设的真值为0，的真值为1，则下列命题公式中真值为1的是 （ D ）A. B. C. D. 56. 下列各式中永真式是 （ A ）

12、A. B. C. D. 57设，雪是黑的，太阳从东方升起，下列命题为真的是 （ A ）A. B. C. D. 58下面集合关于整除关系构成格的是哪一个 （ C ）A.2，3，6，12 B.3，6，9，12C.1，3，5，6，15，30 D.6，12，24，3659个结点的无向完全图的边数为 （ D ）A BC D60设是任意三个集合，下列结论正确的是 （ A ）A若且，则 B若且，则C若且，则 D若且，则61在一个有4个元素的集合上，可以有不同关系的个数为 （ D ）ABCD62设为整数集，下面那个序偶不构成偏序集 （ A ）A（：小于关系）B（：小于等于）C（：等于关系）D：整除关系）63给

13、定上的关系为，则满足的性质是 （ C ）A自反的B对称的C传递的D不可传递的64指出下列语句中哪个不是命题 （ C ）A. 3+2=5。 B. 北京是中国的首都。C. 请勿吸烟！ D. 李白是唐朝的诗人。65. 命题公式A与B是等价的是指 （ D ）A. A与B有相同的原子变元B. A与B是可满足的C. 当A的真值为真时，B的真值也为真D. A与B有相同的真值66下列等值式不正确的是 （ C ）A. B.C. D.67下列各式中，哪个不成立 （ A ）A. B. C. D. 68设是演员，是老师， 钦佩 ，命题“所有演员都钦佩某些老师”符号化为 （ B ）A. B. C. D. 69设为任意集

14、合，则下列等式不成立的是 （ C ）ABCD70下列式子正确的是 （ B ）A B C D71已知集合，上的两个二元关系，则为 （ A ）ABCD72已知集合上关系，则等于 （ B ）AB CD73已知集合，为上的整除关系，则的极小元是 （ A ）A1 B2 C3D4 74设有函数和，且有，则复合函数是 （ B ）A BCD 75含5个结点，4条边的无向连通图（不同构）的个数为 （ B ）A1 B3 C6 D7 二、 填空题1. 设，如果为集合的一个覆盖，要使成为的一个划分，那么必须满足 AiAj = (i,j=1,2,3,m,ij) 。2. 合式公式（x）F(x) G(x,y)中 变元y是_

15、自由_变元.（填自由或约束） 3. 设Mx | (x是整数) (1x12) (x被2整除) ,N=x | ( x是整数) (1x12) (x被3整除) ， 则MN=_6,12_。4. 若集合A有n个元素，则幂集(A）中有_2 n _个元素。5. 若集合中有201个元素，则的子集有 2201 个。6. 一个命题公式如果_若在它的各种指派下，取值均为假_，则称它为矛盾式。7. 不含多重边和 环 的图，称为简单图。8. 任意两个大项的析取为 永真 。9. 在根树中，若每个结点的出度 小于等于m ，则称这棵树为叉树。10. 设集合A=1,2, B=3,4, C=5,6, 则ABC _(1,3,5),(

16、1,3,6),(1,4,5),(1,4,6),(2,3,5),(2,3,6),(2,4,5),(2,4,6)_.11. 为两个命题，当且仅当 P为真，Q为假时 ，为假。12. 是 可满足 式（填永真，永假或可满足）。13. 如果一个独异点满足 A中每个元素存在逆元 ，则为群。J8814. 一个映射，如果对任意，若，则有 f(xi)f(xj) ，则此映射叫从 到的入射。15. 在公式，量词的辖域是。16. 量词与否定联结词之间有以下关系：xQ(x) $xQ(x) 。17. 设A=1，2，B=1，2，则A与B 相等 （相等、不相等）。18. 在数理逻辑中, 规定联结词,的优先次序是 _, ,_.

17、19. 设P,Q是两个命题，德摩根定律可表示为_ (PQ) PQ, (PO) PQ _。20. 设，的幂集。21. 99M=(aij)是无向图G(V,E)的邻接矩阵，V=v1,v2,vn, Mk中的第i行j列的元素值表示_结点vi到vj的长度为k的路径的数目 25.5_。22. 若某连通简单平面图有4个顶点，3 个区域，则有_5_条边。23. 在根树中，如果每一个结点的出度恰好等于 或零，则称这棵树为完全叉树。24. 是 永真 式（填永真，永假或可满足）。25. 一个命题公式称为合取范式，当且仅当它具有型式： A1A2An ，其中A1，A2，An都是由命题变元或其否定所组成的析取式。26. 在

18、公式中，量词的辖域是 。27. 有集合与，则的充分必要条件是 AB 且BA 。28. 若关系是反对称的，当且仅当关系矩阵中以主对角线为对称的元素不能同时为 1 。29. 设为自然数集，若，则是 双 射的。30. 若集合中有101个元素，则的幂集中有 2101 元素。31. 如果一个独异点满足 A中每个元素存在逆元 ，则为群。32. 给定集合上的关系，若是 自反的 、对称的，则称是上的相容关系。33. 若和是满射的，则是 满射 。34. 在一个有个元素的集合上，可以有 种不同的函数。35. 代数系统如果对内的任意元素均有 (a*b)*c=(a*b)*c ，则称此代数系统中的运算“*”对是可结合的

19、。36. 无向图G具有一条欧拉图，当且仅当G是连通的且_有零个或两个奇数度结点_.37. 个结点的无向完全图的边数为。38. 任意两个大项的析取为永真，全体大项的合取为 永假 。39. 命题“如果1+1=0，则明天太阳在东边落下”的真值为T 。40. ( PP) (Q Q ) R ) 是永假 式。41. 设R，Q都是集合A上的等价关系，则s(RQ)=RQ 。42. 设为根树，若每个结点的出度都小于等于，则称为 叉树。43. 设是群，H是G的非空子集，H是G的子群当且仅当a*b-1H 。44. 若是一个偏序集 ，且A中任意两个元素都有最小上界和最大下界，则A是格。45. 8个结点的无向完全图的边

20、数为28 。46. 为两个命题，当且仅当 P、Q同时为真 ，为真。47. 设 则= 2,3,4,5 。48. 存在 欧拉 回路的图，称为欧拉图。49. 在根树中，入度为零的结点称为 根 。三、 名词解释1. 集合的对称差：设A和B为任意两个集合，A和B的对称差是由或者属于A，或者属于B，但不能既属于A又属于B的元素所组成的集合。2. 复合命题：由联结词、标点符号和原子命题复合构成的命题。3. 是集合A上的全序关系：设是集合A上的二元关系，如果对于A中任意两个元素a,bA，必有ab或ba，则称是A上的全序关系。4. 强连通图：在简单有向图G中，任何一对结点的两者之间相互可达，则称G为强连通图。5

21、. 重言式：给定一命题公式，若无论对分量作怎样的指派，其对应的真值永真.6. 阿贝尔群：如果群中的运算*是可交换的，则称该群为阿贝尔群。 7. 自反闭包：设R是一个二元关系，如果存在一个关系满足：是自反的；对于任何自反关系如果有就有。则称为R自反闭包。8. 命题公式A和B是等价的：设P1,P2,Pn为所有出现在A和B中的原子变元, 若给 P1,P2,Pn的任一组指派, A和B的真值都相等, 称A和B是等价的.9. 子群：设是一个群，S是G的非空子群，如果也构成群，则称是的一个子群。10. 半群：是代数系统，*是集合S上的二元运算，若运算*是封闭的，并且*是可结合的，则称是半群。11. 无向图简

22、单图G的邻接矩阵：设无向图G有n个结点v1,v2,vn, 无多重边，定义nn阶矩阵M=(mij)是G的邻接矩阵，其中12. 约束变元的换名：对公式中的约束变元，遵照一定规则更改名称符号，称为约束变元的换名。13. 单侧连通：在简单有向图中,任何一对结点间,至少有一个结点到另一个结点是可达的,则称这个图是单侧连通的。14. 欧拉回路：给定有向图G，通过图中每边一次且一次的一条回路称作欧拉回路。15. 二元关系：设A、B是任意集合，AB的子集R称为从A到B的二元关系，当A=B时，称R为A上的关系。16. 相容关系：给定集合A上的关系R，若R是自反的、对称的，则称R为A上的相容关系。17. 汉密尔顿

23、图：给定图G，若存在一条回路，经过图中的每个结点恰好一次，这条回路称为汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图。18. 集合A上的拟序关系：设R是集合A上的一个关系，若R满足反自反性和传递性.19. 对称关系：设R为X上的关系，对于每一个，每当时，就有，则称R为X上的对称关系。20. 等价关系：一个二元关系若满足自反性，对称性和传递性称为等价关系。21. 对称闭包：设R是一个二元关系，如果存在一个关系满足：是对称的；对于任何对称关系如果有就有。则称为R的对称闭包。22. 图：图是三元组，其中是一个非空的结点集合，是边集合，是从边集合E到结点无序偶（有序偶）集合上的函数。23. 树：连通

24、且无回路的无向图称为树。24. 格：给定偏序集合，若A的任意子集均存在最小上界和最大下界，称为格。25. 命题公式的对偶式：命题公式A中含联结词，将互换，T与F互换所得公式A*称为A的对偶式。四、 解答题1. 已知y(R(y) B(y)，其中R(3)= B(4)=T，R(4)= B(3)=F，且论域是3, 4，求该式的真值。解：y(R(y) B(y) (R(3) B(3) (R(4) B(4) (T F) (FT) T 2. 下列句子中哪些是命题？1 她能歌善舞。2 如果我有时间，我就来看你。3 你喜欢看电影吗？4 小王今年20岁或21岁。5 别讲话了！6 小王和小李是同学。解：是命题分别为1

25、、2、4。3. 试求公式：P(P Q ) 的析取范式和合取范式。解：P(P Q ) P(PQ)合取范式 (PP) (PQ) 析取范式 4. 设A是18的除1以外的正因数组成的集合，“|”为整除关系，画出（A，|）的哈斯图；若存在的话，分别求出其最大元、最小元，极大元，极小元，上确界，下确界，上界和下界。解：（2分）最大元、极大元，上确界和上界为18；极小元为2，3；没有最小元，下确界和下界。5. 求表达式：(a+bc)d-e(f-g)的树形表示。解：6. 在一阶逻辑中，将下面命题符号化，并且要求只能使用全称量词：（1） 没有人长着绿色头发。（2） 有的上海市民没有去过东方明珠塔。解：（1） 设

26、M（x）：x是人，B（x）：x长着绿色头发 则命题（1）可表示为：（2） 设M（x）：x是上海市民，B（x）：x去过东方明珠塔； 则命题（2）可表示为：7. 给定有向图G=如下：试求：（1）各顶点的出、入度； (2) 写出 G 的邻接矩阵 ； （3）利用矩阵计算求出从顶点1到4长度分别为1，2和3的路各有几条。解：（1） 结点 1 2 3 4 结点的出度 2 2 2 1 结点的入度 0 3 1 3 （2）邻接矩阵：（3）因为：所以从顶点1到4长度分别为1，2和3的路分别有1、1、2条。8. 设的关系为：，求以及。解：设则， 故， 有 9. 设G=（a）为6阶循环群。试找出G的所有子群。解： a

27、0=e，（1分）（a）， a0=e , a3， a0=e , a2, a4 10. 求的主析取范式和主合取范式。解：11. 在一阶逻辑中，将下面命题符号化，并且要求只能使用全称量词：（1） 没有人长着绿色头发。（2） 有的上海市民没有去过东方明珠塔。解：（1）设M（x）：x是人，B（x）：x长着绿色头发则命题（1）可表示为：（2）设M（x）：x是上海市民，B（x）：x去过东方明珠塔； 则命题（2）可表示为：4131122412. 设是上的整除关系。 （1） 求出关系；（2） 画出的哈斯图；（3） 求出子集的极大元、最大元、上界、上确界。 解：（1）R=,（2）画出哈斯图得2分。（3）3，4，1

28、2的极大元为12，最大元为12、上界为12，24，上确界为12。13. 求的主析取范式和主合取范式。解法一：（PQ）（PQ）（PQ）(PQ) (PQ) (PQ)(PQ) (PQ) (PQ)(PQ) （主析取范式）(PQ)P) (PQ)Q) (PP )(QP) (PQ )(QQ) T(QP) (PQ )T（1分(PQ) (PQ ) （主合取范式）解法二：PQPQPQ（PQ）（PQ）TTTTTTFTFFFTTFFFFFTT主析取范式：(PQ)(PQ) 主合取范式：(PQ) (PQ )14. 二元运算在实数集上是否满足交换律和结合律？解：（1）因为 所以满足交换律（2）因为所以满足结合律15. 设为

29、任意命题公式。（1）已知，问吗？（2）已知，问吗？解：（1）设有某种指派，使公式的真值为，但的真值为，的真值为，则和的真值为，故成立，但不一定成立。（2）设有某种指派，使公式的真值为，但的真值为，的真值为，则和的真值为，故成立，但不一定成立。16. 画出符合下列条件的图（1） 画一个有一条欧拉回路和一条汉密尔顿回路的图。（2） 画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。（3） 画一个没有一条欧拉回路，但有一条汉密尔顿回路的图。解：（1）（2）（3）17. 设集合X=1,2,3,4, A1=1,2,2,3,4, A2=1,2,3, A3=1,2,3,4.(1). 判别A1, A2, A3

30、分别是否是X的一个覆盖？是否是X的一个划分？(2). 写出X的划分所确定的等价关系。答：(1). A1是X的一个覆盖，但不是X的一个划分；A2不是X的一个覆盖； A3是X的一个划分。(2). 划分A3确定的X上的等价关系R，R=,. 18. 设是上的等价关系，在什么条件下，自然映射是双射？解：因为是等价关系的等价类构成的集合，即是关于的商集，要使自然映射是双射，则商集的元素个数必须和中元素个数一样多，因此，必须是上的恒等关系。19. 设 X=a,b,c 上关系 R=, , 求R的自反闭包 r(R) , 对称闭包 s(R) , 和传递闭包 t(R) 。解：r(R)=,;s(R)=,;t(R)=,. 20. 设R是集合X=1,2,3,5,6,12,上的整除关系，（1）. 列出R的所有元素；(2). 画出(X,R)的哈斯图；(3). 若X有最大、最小元，极大、极小元，请写出。解：(1). R=, , , ,12,