《离散数学习题.doc》由会员分享，可在线阅读，更多相关《离散数学习题.doc（9页珍藏版）》请在金锄头文库上搜索。
1、一、填空题1. 只有两个命题真值均为真时，复合命题真值才为真的联结词称为析取。2. 只有两个命题真值均为假时，复合命题真值才为假的联结词称为合取。3. 命题公式在它的各种指派情况下，其取值均为真，称该公式为永真式。4. 命题公式在它的各种指派情况下，其取值均为假，称该公式为永假式。5. 析取范式的每一项都是合取式。6. 合取范式的每一分量都是析取式。7. 一个命题公式的等价公式仅于小项的析取组成，称该等价公式为原式的主合取范式。8. 一个命题公式的等价公式仅于大项的合取组成，称该等价公式为原式的主析取范式。9. 由一个集合的所有子集构成的集合称为该集合的幂集。10. 一个元素个数为n的集合，它
2、的幂集的元素个数是2n。11. 集合A中的任意元素均在集合B中出现，称集合A是集合B的子集。12. 集合A中的任意元素均在集合B中出现，集合B中最少有一个元素不集合A中出现，称集合A是集合B的真子集。13. 在集合A上的关系R满足，则关系满足自反性质。14. 在集合A上的关系R满足，则关系满足对称性质。15. 偏序集中，任一两个元素都有最小上界和最大下界，称该偏序集为偏序格。16. 偏序集中，任一两个元素都是可比的，称该偏序集为全序。17. 任意两顶点之间均存在边的无向图，称该图为完全无向图。18. 任意两顶点之间均存在路的无向图，称该图为_。19. 所有顶点的度都相同的无向图，称该图为_。2
3、0. n个顶点的连通图无向图，该图最少有n-1_条边。二、单项选择题21. 下列各公式中不是重言式的是（ C ）。 22. 下列各公式中不是重言式的是（ ）。 23. 集合的幂集是（ B ）。24. 集合的幂集是（ C ）。25. 下面关系满足传递性的是（B）。26. 下面关系满足传递性的是（ B ）。27. 下面哈斯图表示的偏序集是格的是（ B ）。28. 下面图为偶图的是（ ）。29. 设集合A=1,2,3,4,5,6,7,8,9,10，下面定义的运算不封闭的是（ ）。30. 设集合Z+是正整数集，下面的运算封闭的是（ ）。三、多项选择题31. 下列句子构成命题的有（ ）。a. 今天下雨；
4、 b. 他个子很高； c. 3x 8；d. 只要认真学习，就能取得好成绩； e. 5 8。32. 下列句子构成命题的有（ ）。a. 今天天气很好； b. 他个子很高； c. 3=8；d. 只要认真学习，才能取得好成绩； e. x2+y2=1。33. 个体域是整数集，下面公式中，命题是真的有（BD ）。34. 个体域是整数集，下面公式中，命题是真的有（ BC ）。 35. P,Q,R,S是原子命题，下面公式是析取范式的有（ A ）。36. 下面定义在实数集上的函数，是一一对应的有（ D ）。37. 一个关系用下面有向图表示，对应的矩阵表示是（ A ）。38. 下列关系中，不是等价关系有（ A B
5、CDE ）。a. 正整数集合上的整除关系； b. 家庭兄弟关系； c. 职务的上级与下级关系； d. 实数集合上的关系； e. 集合的包含关系。39. 下列关系满足偏序关系的有（ ABCDE ）。a. 整数集合上的整除关系； b. 家庭兄弟关系； c. 职务上的上下级关系；d. 实数集合上的关系； e. 集合的包含关系。40. 下列关系不满足全序关系的有（ ACDE ）。a. 正整数集合上的整除关系； b. 家庭兄弟关系； c. 职务上的上下级关系； d. 实数集合上的关系； e. 集合的包含关系。41. 下列代数系统中是独异点的有（ ABCDE ）。a. 整数集合上的加法； b. 集合的并运
6、算； c. 整数集合上的乘法； d. 字符串的联结运算； e. 矩阵的加法运算。42. 下列代数系统中是群的有（ABE）。a. 整数集合上的加法； b. 集合的并运算； c. 整数集合上的乘法；d. 字符串的联结运算； e. 矩阵的加法运算。43. 设A=1,2,3,4,5,6,7,8，下列集合是A的划分的有（ ）。a. 1,2,3,4,5,6,7,8； b. 1,2,3,4,5,6,7,8； c. 1,2,3,4,5,6,7,8；d. 1,2,3,4,5,6,7,7,8；e. 1,2,3,4,5,6,7,8。44. 设A=1,2,3,4，下列关系中能对应A的一个划分的有（ ）。a. (1,1
7、),(2,2,),(3,3),(4,4) b. (1,2),(2,1),(3,4),(4,3,)c. (1,1),(2,2,), (3,3),(4,4) ,(3,4),(4,3,) d. (1,2),(2,3),(3,4),(4,1)e 1,1,(2,2,), (3,3),(4,4) ,(3,4),(4,3,) ,(1,2),(2,1),(2,3),(3,2)45. 下列代数系统中是格的有（ ）。a. 整数集合上的加法和乘法；b. 集合的并和交运算；c. 矩阵的加法和乘法运算；d. 正整数的指数和对数运算；e. 正整数的最大公约数和最小公倍数运算。46. 下列图中是欧拉图的有（ ）。47. 下
8、列图中存在欧拉通路的有（ ）。48. 下列图中是汉密尔顿图的有（ ）。49. 下列图中是平面图的有（ ）。50. 下列图中是正则图的有（ ）。四、叙述题51. 将下列命题符号化。a. 小张既聪明又能干；b. 今天不下雨就去锻炼。52. 用谓词和量词表达下列命题。a. 一个学生，学习期满，德、智、体、美考核合格即可毕业；b. 没有最大实数。53. 用自然语言描述下面公式。 54. 描述集合A上的等价关系R的定义。55. 写出只有两个元素的群二元运算定义。56. 将下列命题符号化。c. 明知山有虎，偏向虎山行；d. 没有共产党，就没有新中国。57. 用谓词和量词表达下列命题。c. 圆心在原点，半径
9、等于1的单位圆；d. 一个整数除以2的余数为0，该整数是偶数。58. 用自然语言描述下面公式。 59. 描述集合A上的相容关系R的定义。60. 写出只有三个元素的一个循环群的二元运算的定义。五、计算题61. 设集合A=a, b, c，A上的关系R=(a，b)，(b，c)，（c，a）。计算R的自反闭包、对称闭包和传递闭包。62. 设集合A=a, b, c，d，A上的关系R=(a，b)，(b，a)，（a，c），(c，a)，(b，c)，（c，b），(a，a)，(b，b)，（c，c）(d，d)。计算该关系对应的划分。63. 已知A=1，2，3，4，R=(1,2),(2,3),(3,4),S=(4,3)
10、,(3,2),(2,1),计算RS 和 R2。64. 设A=a,b,c,d,B=x,y,z,w,确定下列关系是否为从A到B函数，如果是函数确定它的定义域和值域。如果存在逆函数，写出用有序对集合描述的逆函数。a. (a,y),(b,w),(c,x),(d,z)b. (a,x),(b,x),(c,z),(d,z)65. 设集合A=a, b, c，A上的关系R=(a，b)，(b，c)，（a，c）。计算R的自反闭包、对称闭包和传递闭包。66. 设A=1,2,3,4,5,6，R为A上的整除关系，试求：a. A的极大元、极小元、最大元、最小元； b. 子集2,3,6的上界、下界、最小上界、最大下界。67. 设A=1,2,3,4,5,6，R为A上的整除关系，试求：a. A的极大元、极小元、最大元、最小元； b. 子集2,3,6的上界、下界、最小上界、最大下界。a.六、证明题68. 证明下列公式是重言式。69. 设R是集合X上的自反关系，求证R是对称和传递的，当且仅当（a,b）,(a,c)在R中，且有(b,c)在R中。70. 设代数系统（R,*），R是实数集合，二元运算定义为：a*b=a+b+ab，证明：（R,*）是独异点。71. 连通图G有n个节点，e条边，证明e(n-1)。离散数学试卷（B） 第9页(共6页)
