东北农业大学网络教育学院
离散数学复习题
复习题一
一、证明
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)I
二 、计算
1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。
(2)画一个有一条欧拉回路但没有汉密顿回路的图
(3)画一个没有欧拉回路但有一条汉密顿回路的图
答：三种图如下：
2、设，求公式：
的真值。
答：
3、一棵树有个结点度数为2 ，个结点度数为二叉树公式3，…  ，个结点度数为k ，问它有几个度数为1的结点。
答：设它有个度数为1的结点，则：
1*＋2*＋3*＋… ＋k*=2*（+++…+-1）
  得：=＋2*＋… ＋(k-2)*+2
4、设集合上的关系 ，求出它的自反闭包，对称闭包和传递闭包。
答：
三、设上的整除关系，
是否为上的偏序关系？若是，
则：1、画出的哈斯图；
答：是上的偏序关系。
的哈斯图：
2、求。
答：。
四、用推导法求公式的主析取范式和主合取范式。
答：
五、设实数集上的关系，
证明：是上的等价关系。
答：证明：
因此是自反的
因此是对称的
因此是传递的。综上：是上的等价关系。
六、设分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数为，证明的同构映射。
答：证明：
因此。
，所以的同构映射。
七、设是实数集合，，在上定义二元运算为：，试证明是一个。是否阿贝尔？
答：证明：
因此，运算是封闭的
综上：是一个。
不是阿贝尔。
复习题二
一、设  上的整除关系   
完成下列各小题。
1、证明是上的偏序关系。
答：证明  。
综上，是上的偏序关系。
2、画出偏序集的哈斯图。
答：偏序集的哈斯图如右图所示。
3、在上定义两个二元运算和：对任意，，。请填空（在横线上填是或不是）：
①代数系统    是  格。        ②代数系统    是  有界格。
③代数系统    是  有补格。    ④代数系统  不是    分配格。
二、求布尔函数的析取范式和合取范式
设是布尔代数上的一个布尔表达式。试写出的析取范式和合取范式（用推导法或列函数表的方法均可）。
答：方法1  推导法
析取范式为：
合取范式为：
方法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>
0
1
0
1
0
1
1
1
析取范式为：
合取范式为：
三、画出满足下列要求的图
①有一条欧拉回路和一条汉密尔顿回路。
②有一条欧拉回路但没有汉密尔顿回路。
③没有欧拉回路但有汉密尔顿回路。
④既没有欧拉回路也没有汉密尔顿回路。
四、证明在完全二叉树中，边的总数等于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的最优二叉树。
答：解  2  3  5  7  11  13                    所求最优二叉树为
          5  5  7  11  13 
            10  7  11  13 
                17  11  13 
                17      24 
                        41
                           
六、证明
在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。
试证
答：在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。
试证
证明  设此平面图有r个面。
又
，从而有。将其代入欧拉公式
得   整理得 
七、证明
设是有限字母表，给定代数系统，其中是串的连接运算。对于任一串，建立到的映射，。证明是到的一个满同态，且当时，是同构映射。
答：证明  对于中任意两字符串和，因为，所以
，对于任一正整数，取，则，所以，，是到的一个满同态。
当时，设，，，是双射，因此，是一个同构映射。
八、应用
    给定有限状态机，它的状态图如附图所示。
1、求状态的011010的后继以及可接受状态序列。
答：因为
所以状态的011010的后继状态是，可接受状态序列是。
2、求对于激励010110的响应。
答：对于激励010110的响应是。
3、构造一台与相似的转换赋值机，画出的状态图。
答：与相似的转换赋值机，其中：
的状态图为：
九、证明
考察一个（8，4）码C，它的校验位a5，a6，a7，a8满足下列方程
a5=a1+ a2+ a4   
a6=a1+ a3+ a4   
a7=a1+ a2+ a3   
a8=a2+ a3+ a4
其中a1，a2，a3，a4为信息位。
    求出这个码的一致校验矩阵。证明。
答：证明  一致校验矩阵为：
矩阵中无零列向量，且任意两个、三个列向量之和不等于零向量。而第一、二、六、八列向量之和为零向量，所以，
                 
复习题三
一、设集合     

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。