离散数学复习题1

一、逻辑1、给出的真值表2、证明()()pqpq为永真式二、谓词量词和推理1、使用量词和谓词表达0lim()xxfx不存在这一事实2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门考试蕴含结论“通过考试的某个人没有读过书”三、集合、函数、数列与求和1、全集为12345678910，，，，，，，，，，求集合A=13579，，，，的位串？它的补集的位串是什么？写出集合A=13579，，，，的所有子集，写出集合AA2、从集合abcd，，，到集合能定义多少个函数？下面给出的函数其定义为：()4,()3,()1,()3fafbfcfd该函数是双射吗？是满射吗？该函数是否存在逆函数？如果存在请给出其逆函数。四、计数1、计算机系统的美国用户有一个6～8个字符构成的密码，其中每个字符是一个大写字母或数字，且每个密码必须至少包含一个数字，问总共有多少个合适的密码？2、在30天的一个月里，某棒球队一天至少打一场比赛，但最多打45场。证明一定有连续的若干天内这个球队恰好打了14场比赛3、证明n个元素的集合中允许重复的r组合数等于(1,)(1,1)CnrrCnrn4、按照字典顺序生成整数1，2，3的所有排列（不允许重复），在362541后面按照字典顺序的下一个最大排列是什么？找出在1000100111后面的下一个最大的二进制串。五、关系1、求下面给出关系R的自反闭包、对称闭包和传递闭包的0-1关系矩阵，其中101010110RM2、S是所有比特串的集合，,sStS关系3R定义为3sRt当s=t或者s和t的长度至少是3，且前3个比特相同时具有关系3R，例如013R01，001113R00101，但01R3010，01011R301110。证明3R是S上的等价关系，由3R产生的S的等价类是那些集合？3、偏序集（{2,4,5,10,12,20,25},|）的那些元素是极大的，那些元素是极小的？六、图与树1、在下图所示的图中，从a到d的长度为4的通路有几条？该图是否是Euler图，是否是Hamilton图，该图的度序列是什么？该图是否可平面，如果是请给出平面画图，该图的点色数和边色数等于多少？给出该图的一个生成树，2、求下面赋权图从a到z的最短距离是多少？最短路径是什么？（画图给出标号过程）()()pqpq1234，，，3、用哈夫曼编码方法来编码下列符号，这些符号具有下列频率：A:0.08，B:0.10，C:0.12，D:0.15，E:0.20，F:0.35,该编码方法编码一个字符的平均位数是多少？4、下面树的高度是多少？那些节点是内部节点，那些节点是叶子节点，该树是否是3元正则树？分别给出该树节点的前序、中序、后序遍历的节点访问次序