资源描述：
《东北农业大学(2014版)《离散数学》网上作业题及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、东北农业大学网络教育学院离散数学复习题复习题一一、证明1、对任意两个集合，证明答：证明：2、构造下面命题推理的证明如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。答：符号化为：证明：(1)P(2)T(1)I(3)T(1)I(4)P(5)T(2)(4)I(6)P(7)T(3)(6)I(8)T(5)(7)I55二、计算1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。(2)画一个有一条欧拉回路但没有汉密顿回路的图(3)画一个没有欧拉回路但有一条汉密顿回路的图答：
2、三种图如下：2、设，求公式：的真值。答：3、一棵树有个结点度数为2，个结点度数为3，…，个结点度数为k，问它有几个度数为1的结点。答：设它有个度数为1的结点，则：1*＋2*＋3*＋…＋k*=2*（+++…+-1）得：=＋2*＋…＋(k-2)*+24、设集合上的关系，求出它的自反闭包，对称闭包和传递闭包。答：55三、设上的整除关系，是否为上的偏序关系？若是，则：1、画出的哈斯图；答：是上的偏序关系。的哈斯图：2、求。答：。四、用推导法求公式的主析取范式和主合取范式。答：五、设实数集上的关系，证明：是上的等价关系。55答：证明：因此是自反的因此是
3、对称的因此是传递的。综上：是上的等价关系。六、设分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数为，证明的同构映射。答：证明：因此。，所以的同构映射。七、设是实数集合，，在上定义二元运算为：，试证明是一个群。是否阿贝尔群？答：证明：因此，运算是封闭的55综上：是一个群。不是阿贝尔群。复习题二一、设上的整除关系完成下列各小题。1、证明是上的偏序关系。答：证明。55综上，是上的偏序关系。1、画出偏序集的哈斯图。答：偏序集的哈斯图如右图所示。2、在上定义两个二元运算和：对任意，，。请填空（在横线上填是或不是）：①代数系统是格。②代数系统
4、是有界格。③代数系统是有补格。④代数系统不是分配格。二、求布尔函数的析取范式和合取范式设是布尔代数上的一个布尔表达式。试写出的析取范式和合取范式（用推导法或列函数表的方法均可）。答：方法1推导法析取范式为：55合取范式为：方法2列函数表法布尔表达式对应的函数表为：<0,0,0><0,0,1><0,1,0><0,1,1><1,0,0><1,0,1><1,1,0><1,1,1>01010111析取范式为：合取范式为：三、画出满足下列要求的图①有一条欧拉回路和一条汉密尔顿回路。②有一条欧拉回路但没有汉密尔顿回路。55③没有欧拉回路但有汉密尔顿回路。
5、④既没有欧拉回路也没有汉密尔顿回路。四、证明在完全二叉树中，边的总数等于2(n-1)，这里n是叶子数。答：证明设分枝点数为i。因为在完全m叉树中，有(m-1)i=n-1，所以，当m=2时有i=n-1。又因为在完全二叉树中，每个分枝点射出两条边，所以边的总数是2i，即边的总数是2(n-1)。五、计算求带权2、3、5、7、11、13的最优二叉树。答：解23571113所求最优二叉树为55711131071113171113172441六、证明在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。试证答：在一个连通平面图中，若它有n个结
6、点，m条边，且每个面由k条边围成。试证55证明设此平面图有r个面。又，从而有。将其代入欧拉公式得整理得七、证明设是有限字母表，给定代数系统，其中是串的连接运算。对于任一串，建立到的映射，。证明是到的一个满同态，且当时，是同构映射。答：证明对于中任意两字符串和，因为，所以，对于任一正整数，取，则，所以，，是到的一个满同态。当时，设，，，是双射，因此，是一个同构映射。55八、应用给定有限状态机，它的状态图如附图所示。1、求状态的011010的后继以及可接受状态序列。答：因为所以状态的011010的后继状态是，可接受状态序列是。2、求对于激励010
7、110的响应。答：对于激励010110的响应是。3、构造一台与相似的转换赋值机，画出的状态图。答：与相似的转换赋值机，其中：55的状态图为：九、证明考察一个（8，4）码C，它的校验位a5，a6，a7，a8满足下列方程a5=a1+a2+a4a6=a1+a3+a4a7=a1+a2+a355a8=a2+a3+a4其中a1，a2，a3，a4为信息位。求出这个码的一致校验矩阵。证明。答：证明一致校验矩阵为：矩阵中无零列向量，且任意两个、三个列向量之和不等于零向量。而第一、二、六、八列向量之和为零向量，所以，复习题三一、设集合完成下列各小题。1求的幂集。
8、答：2证明是偏序集。答：。55综上，是偏序集。3画出偏序集的哈斯图。答：偏序集的哈斯图如图1。4在上定义两个二元运算和：对任意，，。请填空（在横线上填是或不是并回答
