离散数学网上作业题讲解
- 格式：doc
- 大小：809.00 KB
- 文档页数：16
1
东北农业大学网络教育学院
离散数学复习题
复习题一
一、证明
1、对任意两个集合BA和，证明 ABABA
2、构造下面命题推理的证明
如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。
二 、计算
1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。
(2)画一个有一条欧拉回路但没有汉密顿回路的图
(3)画一个没有欧拉回路但有一条汉密顿回路的图
2、设212,，，个体域为为，整除为xxQyxyxP，求公式：
xQyxPyx,的真值。
3、一棵树有2n个结点度数为2 ，3n个结点度数为3，„ ，kn个结点度数为k ，问它有几个度数为1的结点。
4、设集合AA,4,3,2,1上的关系 4,3,3,2,1,2,2,1,1,1R，求出它的自反闭包，对称闭包和传递闭包。
三、设45,36,27,15,9,6,5,3,2,1A上的整除关系212121,,,aaAaaaaR整除，
R是否为A上的偏序关系？若是，
则：1、画出R的哈斯图；
2、求9,2glb9,2lub9,2和最大下界的最小上界。
四、用推导法求公式RQP的主析取范式和主合取范式。
五、设实数集2R上的关系cbdaRdcbadcba,,,,,,,2＝，
证明：是2R上的等价关系。
六、设RR和分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数RRf:为rrf2)(，证明 ),(),(RRf到是从的同构映射。
2
七、设R是实数集合，}0{*RR，在RR*上定义二元运算为：dbcacdcba,,,，试证明,*RR是一个群。,*RR是否阿贝尔群？
复习题二
一、设 上的整除关系
完成下列各小题。
1、 证明是L上的偏序关系。
2、 画出偏序集,L的哈斯图。
3、 在L上定义两个二元运算和：对任意,abL，(,)abglbab，(,)ablubab。请填空（在横线上填是或不是）：
①代数系统,,L 格。 ②代数系统,,L 有界格。
③代数系统,,L 有补格。 ④代数系统,,L 分配格。
二、求布尔函数的析取范式和合取范式
设123122323(,,)()()()Exxxxxxxxx是布尔代数{0,1},,,上的一个布尔表达式。试写出123(,,)Exxx的析取范式和合取范式（用推导法或列函数表的方法均可）。
三、画出满足下列要求的图
①有一条欧拉回路和一条汉密尔顿回路。
②有一条欧拉回路但没有汉密尔顿回路。
③没有欧拉回路但有汉密尔顿回路。
④既没有欧拉回路也没有汉密尔顿回路。
四、证明在完全二叉树中，边的总数等于2(n-1)，这里n是叶子数。
五、计算
求带权2、3、5、7、11、13的最优二叉树。
六、证明
在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。
试证
(2)2knmk
七、证明
设V是有限字母表，给定代数系统*,V，其中是串的连接运算。对于任一串*V，建立*V到1,2,3,4,12L121212,,,aaaaLaa整除
3
N的映射f，()||f。证明f是*,V到,N的一个满同态，且当||1V时，f是同构映射。
八、应用
给定有限状态机(,,,,,)sMQSRfhA，它的状态图如附图所示。
1、 求状态A的011010的后继以及可接受状态序列。
2、 求sM对于激励010110的响应。
3、构造一台与sM相似的转换赋值机tM，画出tM的状态图。
九、证明
考察一个（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为信息位。
求出这个码的一致校验矩阵。证明0minxCx()4WX。
复习题三
一、设集合
完成下列各小题。
1求S的幂集()PS。
2证明(),PS是偏序集。
3画出偏序集(),PS的哈斯图。
4在()PS上定义两个二元运算和：对任意,()ABPS，ABAB，ABAB。请填空,,Sabc
4
（在横线上填是或不是并回答为什么）：
①代数系统(),PS 格，因为 。
②代数系统(),PS 有界格，因为 。
③代数系统(),PS 有补格，因为 。
④代数系统(),PS 分配格，因为 。
⑤代数系统(),,,~PS 布尔代数，因为 。
二、计算
设123122323(,,)()()()Exxxxxxxxx是布尔代数{0,1},,,上的一个布尔表达式。试写出123(,,)Exxx的析取范式和合取范式（用列函数表的方法）。
三、回答问题
完全图nK是否是欧拉图？是否是哈密尔顿图？为什么？
四、画图
对于下图，利用克鲁斯克尔算法求一棵最小生成树。
五、计算
一棵树有两个结点度数为2 ，1个结点度数为3，3个结点度数为4 ，其余结点度数为1。问该树有几个度数为1的结点。
六、证明
(,)GVE图是无向简单图，其中||||VnEm，，证明：2)1(nnm。
证明 因为G是简单图，所以图G中没有环和平行边，任意两结点间最多有一条边，故2(1)2nnnmC。
七、证明
已知
(,,,),{,,},{,,},:(1)(2)(3)(4)(5)(6)(7)NTNTGVVPVBCVabcPaBCaBCCBBCaBabbBbbbCbccCcc
5
求证 *nnnabc
八、设计
设计一台有限状态机M，它的输出是已经输入符号数的模3数（即设计模3计数器）。
九、计算
给定码C={00000,10001,01100,10101}，求码C中任两个码字的海明距和min()dC。
复习题四
一、填空
1、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系，有 个从A到B的函数，其中当mn时有 个入射，当m=n时，有 个双射。
2、集合2{|}AnnN （是/不是）可数的。
二、计算
1、用推导法求下列公式的主合取范式和主析取范式：(())PQR
2设AA},4,3,2,1{上二元关系{1,2,2,2,2,4,3,4}R，求其自反闭包、对称闭包、传递闭包。
三、证明
1、设CBA,,是三个集合，证明：()()ABCACB
2证明等价式：()(()())()()()()xAxBxxAxxBx
四、将下列命题推理符号化并给出形式证明：
已知张三或李四的彩票中奖了；如果张三的彩票中奖了，那么你是知道的；如果李四的彩票中奖了，那么王五的彩票也中奖了；现在你不知道张三的彩票中奖。所以李四和王五的彩票都中奖了。
五、设复数集合{|,,0}CabiabRa，定义CR上二元关系：,abicdiR当且仅当0ac，证明：R为等价关系。
六、证明：若ABCDABCD和，则。
七、设集合{23|,}mnGmnI，是普通乘法，证明：,G是一个群。
八、设实数集合R，+和x是普通加法和乘法，定义映射:fRR，,()xxRfxe，证明,,fRR是从到的单一同态。
复习题五
一、填空
1、实数集合R （是/不是）可数的。
2、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系，有 个从A到B的函数，其中当mn时有 个入射，当m=n时，有 个双射。
二、计算
6
1、用推导法求下列公式的主合取范式和主析取范式：(())PQR
2设AA},4,3,2,1{上二元关系{1,1,2,3,2,4,3,2,3,4}R，求其自反闭包、对称闭包、传递闭包。
三、证明
1、设CBA,,是三个集合，证明：()()ABCACB
2证明等价式：()(()())()()()()xAxBxxAxxBx
四、将下列命题推理符号化并给出形式证明：
已知今天下雨或刮风；如果今天下雨，那么我在家看书；如果今天刮风，那么我去放风筝；今天我没有在家看书。所以今天刮风并且我去放风筝了。
五、设正整数集合I上的二元关系{,|,,}2xyRxyxyII，证明：R为等价关系。
六、证明：若ABCDABCD和，则。
七、设集合{5|}nGnI，是普通乘法，证明：,G是一个群。
八、设正实数集合R+和实数集合R，+和x是普通加法和乘法，定义映射:fRR，,()lnxRfxx，证明,,fRR是从到的同构。
复习题六
一、 求公式q∧(p∨┐q)的析取范式、合取范式及主析取范式、主合取范式。
二、用推理规则证明：
前提 (x)(F(x)∧S(x))→(y)(M(y) →W(y))，(y)(M(y)∧┐W(y))
结论 (x)(F(x)→┐S(x))
三、计算题
1.证明逻辑等价式A→(A→B)A→B成立。
2.对任意集合A，B，C，证明：（A - B） B = A B
3.设二元关系R={<{a},b>,, }求：
(1) dom R
(2) ran R
(3) RοR
4.求集合A={|p,q都是整数}的势。
5. 在20名青年中有10名是公司职员，12名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。
四、假设给定了正整数的序偶集合A，在A上定义二元关系R如下：<,>R,当且仅当xv=yu，证明R为等价关系。
