《2017东北农业大学网络教育学院离散数学复习题附答案》由会员分享，可在线阅读，更多相关《2017东北农业大学网络教育学院离散数学复习题附答案（42页珍藏版）》请在金锄头文库上搜索。
1、1东北农业大学网络教育学院东北农业大学网络教育学院离散数学复习题离散数学复习题复习题一复习题一一、证明一、证明1、对任意两个集合，证明 BA和 ABABA答：证明： AEABBABABABABA2、构造下面命题推理的证明 如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天 是星期三且数学老师有事，所以我有一次英语测验。答：符号化为：QSPRSRQP,证明：(1) PSP (2) T(1)IP(3) T(1)IS(4) PRQP(5) T(2)(4)IRQ(6) PRS(7) T(3)(6)I,R(8) T(5)(7)IQ二二 、计算、计算 1、(1)画一个有
2、一条欧拉回路和一条汉密顿回路的图。 (2)画一个有一条欧拉回路但没有汉密顿回路的图 (3)画一个没有欧拉回路但有一条汉密顿回路的图 答：三种图如下：2、设，求公式： 212,，个体域为为，整除为xxQyxyxP的真值。 xQyxPyx,2答： TTTFTTTFTFFTTTTQPQPQPQPxQxPxQxPxxQyxPyx22 , 221 , 212 , 111 , 12 ,1 ,3、一棵树有个结点度数为 2 ，个结点度数为 3， ，个结点度数为 k ，问它有几个度数为 12n3nkn的结点。答：设它有个度数为 1 的结点，则：1n1*2*3* k*=2*（+-1）1n2n3nkn1n2n3nk
3、n得：=2* (k-2)*+21n3n4nkn4、设集合上的关系 ，求出它的自反闭包，对称闭包和AA,4 , 3 , 2 , 14 , 3,3 , 2,1 , 2,2 , 1,1 , 1R传递闭包。答：4 , 4,3 , 3,2 , 2,4 , 3,3 , 2,1 , 2,2 , 1,1 , 1)(Rr3 , 4,2 , 3,4 , 3,3 , 2,1 , 2,2 , 1,1 , 1)(Rs4 , 1,4 , 2,2 , 2,3 , 1,4 , 3,3 , 2,1 , 2,2 , 1,1 , 1)(Rt三、三、设上的整除关系，45,36,27,15, 9 , 6 , 5 , 3 , 2 , 1
4、A212121,aaAaaaaR整除是否为上的偏序关系？若是，RA 则：1、画出的哈斯图；R 答：是上的偏序关系。RA 的哈斯图：R2、求。 9 , 2glb9 , 2lub9 , 2和最大下界的最小上界答：。 19 , 2glb,369 , 2lub9 , 2最大下界的最小上界四、四、用推导法求公式的主析取范式和主合取范式。RQP3答： RQPRQPRQPRQPRQPRQPRQPRQPRQPPRQQPRQRPRQPRQPRQP五、五、设实数集上的关系，2RcbdaRdcbadcba,2证明：是上的等价关系。2R答：证明：yxyxxyyxRyx,2所以有因此是自反的badcadbccbdadc
5、ba,所以即有因此是对称的febaebfafebadcedfccbdafedcdcba,所以得即有因此是传递的。综上：是上的等价关系。2R六、六、设分别是实数集和正实数集，和分别是普通加法和乘法，定义函数为RR和 RRf :，证明的同构映射。rrf2)( ),(),(RRf到是从答：证明：是入射所以有且fyxRyxyx,22,是满射所以即使fzrzRrRzr,log,2,2因此。是双射f，所以的同构映射。 yfxfyxfRyxyxyx222,有 ),(),(RRf到是从七、七、设是实数集合，在上定义二元运算 为：，试R0* RRRR * dbcacdcba,证明是一个群。是否阿贝尔群？ ,*R
6、R ,*RR答：证明：因此，运算是封 RRdbcacdcbaRdbcacRaccaRdcbaRRdcba*, 0, 0, 0,所以且则：且有闭的4 运算是可结合的因此所以,*fedcbafedcbafdebceacefdecebafedcbafdebceacefedbcacfedcbaRRfedcba 是幺元因此且有0 , 10 , 1, a0 , 10 , 1,*RRbabbaRRba abbaRRabbab abbaRRba,a1,a1,0 , 1, a,a1,a1,*逆元为有逆元因此且有综上：是一个群。 ,*RR不是阿贝尔群。 ,*RR复习题二复习题二一、设一、设 上的整除关系上的整除关
7、系 完成下列各小题。完成下列各小题。 1、 证明是上的偏序关系。L答：证明 。,aLaaa a 因为整除所以，因此是自反的122112,a aa aaa1221设有，即a整除a，a整除a，则，因此是反对称的。122313,a aa aaa1223设有，即a整除a，a整除a，则整除，13,a a即,因此是传递的。综上，是上的偏序关系。L2、 画出偏序集的哈斯图。,L答：偏序集的哈斯图如右图所示。,L3、 在上定义两个二元运算和：对任意，。请填空L, a bL( , )abglb a b( , )ablub a b1,2,3,4,12L 121212,a aa aL aa整除5（在横线上填是或不是
8、）：代数系统 是 格。 代数系统 是 有界格。, ,L , ,L 代数系统 是 有补格。 代数系统 不是 分配格。, ,L , ,L 二、求布尔函数的析取范式和合取范式二、求布尔函数的析取范式和合取范式设是布尔代数上的一个布尔表达式。: 123122323( ,)()()()E x x xxxxxxx0,1, , , 试写出的析取范式和合取范式（用推导法或列函数表的方法均可） 。123( ,)E x x x答：方法 1 推导法 析取范式为：: 123122323( ,)()()()E x x xxxxxxx:123323112311123123123123()()()()()()()()()(
9、)xxxxxxxxxxxxxxxxxxxxxxxx:123123123123123123123()()()()()()()xxxxxxxxxxxxxxxxxxxxx合取范式为：: 123123123123( ,)()()()E x x xxxxxxxxxx方法 2 列函数表法 布尔表达式对应的函数表为：f0 1 0 1 0 1 1 1析取范式为：合取范式为：: 123123123123123123( ,)()()()()()E x x xxxxxxxxxxxxxxxx: 123123123123( ,)()()()E x x xxxxxxxxxx三、画出满足下列要求的图三、画出满足下列要求的图
10、 有一条欧拉回路和一条汉密尔顿回路。6有一条欧拉回路但没有汉密尔顿回路。 没有欧拉回路但有汉密尔顿回路。 既没有欧拉回路也没有汉密尔顿回路。四、证明在完全二叉树中，边的总数等于四、证明在完全二叉树中，边的总数等于 2(n-1)2(n-1)，这里，这里 n 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
11、 所求最优二叉树为5 5 7 11 13 10 7 11 13 17 11 13 17 24 41 六、证明六、证明 在一个连通平面图中，若它有 n 个结点，m 条边，且每个面由 k 条边围成。 试证 (2) 2k nmk 答：在一个连通平面图中，若它有 n 个结点，m 条边，且每个面由 k 条边围成。 试证(2) 2k nmk证明 设此平面图有 r 个面。deg( )deg( )iirkrkr又deg( )irk，从而有。将其代入欧拉公式2krm2mrk得 整理得 2nmr22mnmk(2) 2k nmk七、证明七、证明7设是有限字母表，给定代数系统，其中 是串的连接运算。对于任一串，建立V
12、*,V*V到的映射，。证明是到的一个满同态，且当时，是同*VNf( ) |ff*,V,N | 1V f构映射。答：证明 对于中任意两字符串和，因为，所以*V| |() |( )( )fff，对于任一正整数，取，则，所以，是( )0fnNaV|n aaan ()n f aaan f到的一个满同态。*,V,N 当时，设，是双射，因此，是一个同构映射。| 1V Va()n f aaan ( )0fff八、应用八、应用给定有限状态机，它的状态图如附图所示。( , , , , )sMQ S R f h A1、 求状态的 011010 的后继以及可接受状态序列。A答：因为011010AECAECD 所以状态的 011010 的后继状态是，可接受状态序列是。ADAECAECD2、 求对于激励 010110 的响应。sM答：对于激励 010110 的响应是。sMecdcae3、 构造一台与相似的转换赋值机，画出的状态图。sMtMtM答：与相似的转换赋值机，其中：sM( , , , ,)tI
