东农18秋《离散数学》离线作业答案
东北农业大学网络教育学院离散数学复习题
复习题一
一、证明
1、对任意两个集合，证明
2、构造下面命题推理的证明
如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。二 、计算
1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。
(2)画一个有一条欧拉回路但没有汉密顿回路的图
(3)画一个没有欧拉回路但有一条汉密顿回路的图
2、设，求公式：
的真值。
3、一棵树有个结点度数为2 ，个结点度数为3，…，个结点度数为k ，问它有几个度数为1的结点。
4、设集合上的关系 ，求出它的自反闭包，对称闭包和传递闭包。三、设上的整除关系，
是否为上的偏序关系？若是，
则：1、画出的哈斯图；
2、求。
四、用推导法求公式的主析取范式和主合取范式。
五、设实数集上的关系，
证明：是上的等价关系。
六、设分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数为，证明的同构映射。七、设是实数集合，，在上定义二元运算为：，试证明是一个群。是否阿贝尔群？复习题二
一、设 上的整除关系
完成下列各小题。
证明是上的偏序关系。
画出偏序集的哈斯图。
在上定义两个二元运算和：对任意，，。请填空（在横线上填是或不是）：
①代数系统 格。 ②代数系统 有界格。
③代数系统 有补格。 ④代数系统 分配格。
二、求布尔函数的析取范式和合取范式
设是布尔代数上的一个布尔表达式。试写出的析取范式和合取范式（用推导法或列函数表的方法均可）。
三、画出满足下列要求的图
①有一条欧拉回路和一条汉密尔顿回路。
②有一条欧拉回路但没有汉密尔顿回路。
③没有欧拉回路但有汉密尔顿回路。
④既没有欧拉回路也没有汉密尔顿回路。四、证明在完全二叉树中，边的总数等于2(n-1)，这里n是叶子数。
五、计算
求带权2、3、5、7、11、13的最优二叉树。
六、证明
在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。
试证
七、证明
设是有限字母表，给定代数系统，其中是串的连接运算。对于任一串，建立到的映射，。证明是到的一个满同态，且当时，是同构映射。
八、应用
给定有限状态机，它的状态图如附图所示。
求状态的011010的后继以及可接受状态序列。
求对于激励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为信息位。
求出这个码的一致校验矩阵。证明。复习题三
一、设集合 完成下列各小题。
1求的幂集。
2证明是偏序集。
3画出偏序集的哈斯图。
4在上定义两个二元运算和：对任意，，。请填空（在横线上填是或不是并回答为什么）：
①代数系统 格，因为 。
②代数系统 有界格，因为 。
③代数系统 有补格，因为 。
④代数系统 分配格，因为 。
⑤代数系统 布尔代数，因为 。
二、计算
设是布尔代数上的一个布尔表达式。试写出的析取范式和合取范式（用列函数表的方法）。
三、回答问题
完全图是否是欧拉图？是否是哈密尔顿图？为什么？
四、画图
对于下图，利用克鲁斯克尔算法求一棵最小生成树。
五、计算
一棵树有两个结点度数为2 ，1个结点度数为3，3个结点度数为4 ，其余结点度数为1。问该树有几个度数为1的结点。
六、证明
是无向简单图，其中，证明：。
证明因为是简单图，所以图中没有环和平行边，任意两结点间最多有一条边，故。
七、证明
已知
求证
八、设计
设计一台有限状态机，它的输出是已经输入符号数的模3数（即设计模3计数器）。
九、计算
给定码C={00000,10001,01100,10101}，求码C中任两个码字的海明距和。复习题四
一、填空
1、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系，有 个从A到B的函数，其中当m(n时有 个入射，当m=n时，有 个双射。
2、集合 （是/不是）可数的。二、计算
1、用推导法求下列公式的主合取范式和主析取范式：
2设上二元关系，求其自反闭包、对称闭包、传递闭包。
三、证明
1、设是三个集合，证明：
2证明等价式：
四、将下列命题推理符号化并给出形式证明：
已知张三或李四的彩票中奖了；如果张三的彩票中奖了，那么你是知道的；如果李四的彩票中奖了，那么王五的彩票也中奖了；现在你不知道张三的彩票中奖。所以李四和王五的彩票都中奖了。
五、设复数集合，定义：当且仅当，证明：为等价关系。
六、证明：若。
七、设集合，是普通乘法，证明：是一个群。
八、设实数集合R，+和x是普通加法和乘法，定义映射，，证明的单一同态。
复习题五
一、填空
1、实数集合R （是/不是）可数的。
2、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系，有 个从A到B的函数，其中当m(n时有 个入射，当m=n时，有 个双射。二、计算
1、用推导法求下列公式的主合取范式和主析取范式：
2设上二元关系，求其自反闭包、对称闭包、传递闭包。
三、证明
1、设是三个集合，证明：
2证明等价式：
四、将下列命题推理符号化并给出形式证明：
已知今天下雨或刮风；如果今天下雨，那么我在家看书；如果今天刮风，那么我去放风筝；今天我没有在家看书。所以今天刮风并且我去放风筝了。
五、设正整数集合上的二元关系，证明：为等价关系。
六、证明：若。
七、设集合，是普通乘法，证明：是一个群。
八、设正实数集合R+和实数集合R，+和x是普通加法和乘法，定义映射，，证明的同构。
复习题六
求公式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>,<a,b>, <b,c>}求：
(1) dom R
(2) ran R
(3) RοR
4.求集合A={<p,q>|p,q都是整数}的势。
5. 在20名青年中有10名是公司职员，12名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。四、假设给定了正整数的序偶集合A，在A上定义二元关系R如下：<<x,y>,<u,v>>(R,当且仅当xv=yu，证明R为等价关系。
五、给出偏序集<A, R>上偏序关系R的关系图（如下图所示）。
（1）求偏序集<A, R>的哈斯图。
（2）指出A的最大、最小元（如果有的话），极大、极小元。
六、设<G，(>为群。若在G上定义二元运算о,使得对任何元素x，y(G，有
xоy = y(x。
证明<G，о>也是群
七、设<G，(>为群,a为G中给定元素。定义函数f：G→G，使得对每一x(G有f(x)=a(x(a-1
证明：f是<G，(>到<G，(>的自同构。复习题七
一、证明
1、对任意两个集合，证明
2、构造下面命题推理的证明
如果我学习，那么我数学不会不及格；如果我不热衷于玩游戏机，那么我将学习；但我数学不及格，因此我热衷与玩游戏机。
二 、计算
画一个有一条欧拉回路和一条汉密顿回路的图。
2、设，求公式：
的真值。
3一棵树有个结点度数为2 ，个结点度数为3，…，个结点度数为k ，问它有几个度数为1的结点。
4设集合上的关系 ，求出它的自反闭包，对称闭包和传递闭包。
三、设上的整除关系，是否为上的偏序关系？若是，则：
1、画出的哈斯图；2、求的极大值和的极小值。
四、用推导法求公式的主析取范式和主合取范式。
五、设自然数集上的关系定义为：，
证明：是上的等价关系。
六、设分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数为，证明的同构映射。
七、设是整数集合，＋是普通加法，试证明是一个群。是否循环群？复习题八
求公式(┐p∨┐q)→(p(┐q)的析取范式、合取范式及主析取范式、主合取范式。
二、用推理规则证明：
前提 ((x)P(x)→((x)((P(x)∨Q(x))→R(x))，((x)P(x)，((x)Q(x)
结论 ((x)((y)(R(x)∧R(y))
三、计算题
1.证明逻辑等价式A(B( (A∧B)∨(┐A∧┐B)成立。
2.设A(B，求证A∩C(B∩C。
3.设集合A={a，b，c，d}，A上的关系R={<b,b>,<a,b>,<c,b>,<d,c>}，求R的自反闭包、对称闭包。4.求下列集合的基数。
（1）T={x|x是单词“BASEBALL”中的字母}
（2）B={x|x∈R∧x2=9∧2x=8}
（3）C=，A={1,3,7,11}
5. 求从1到500的整数中，能被3或5除尽的数的个数。四、设R，S为A上的两个等价关系，且R ( S。定义A/R上的关系R/S：
<,>(R/S当且仅当<x，y>(S
证明：R/S为A/R上的等价关系。
五、设上的整除关系
，
是否为上的偏序关系？若是，
则：1、画出的哈斯图；
求。
六、设<G，(>为一群。证明：
（1）若对任意a(G有a2 =e，e为幺元，则G为阿贝尔群。
（2）若对任意a，b(G有(a(b)2 =a2(b2 ，则G为阿贝尔群。
七、设N4 =｛0，1，2, 3｝，f：N4→N4定义如下：
令F = {f0,f1,f2,f3}，其中f0为N4上恒等函数。给定一代数结构<F, ο>，且（这里ο为函数合成运算，+4为模4加运算）。
试证<F, ο>与< N4,+4>同构。
复习题九
一 ．单项选择题
1．命题公式为（ ）。
A．重言式 B．可满足式 C．矛盾式 D．等值式
2．设集合A = {1，a}，则P(A) =（ ）。
A．{{1}，{a}} B．{，{1}，{a}}
C．{，{1}，{a}，{1，a}} D．{{1}，{a}，{1，a}}
3．下列命题中正确的结论是：（ ）
A．集合上的关系如果不是自反的，就一定是反自反的；
B．若关系都是反自反的，那么必也为反自反的；
C．若关系都是自反的，那么必也为自反的；
D．每一个全序集必为良序集.
4．下列结论中不正确的结论是：（ ）
A．三个命题变元的布尔小项的编码是；
B．三个命题变元的布尔大项的编码是；
C．任意两个不同的布尔小项的合取式必为永假式；
D．任意两个不同的布尔大项的合取式必为永假式.
5．设集合A和二元运算*，可交换的代数运算是（ ）。
A．设
B．设
C．设，运算是矩阵的乘法
D．设
6．以下命题中不正确的结论是（ ）
A．素数阶群必为循环群； B．Abel群必为循环群；
C．循环群必为Abel群 D．4阶群必为Abel群.
7．设代数系统和，存在映射，如果，都有（ ），称K1与K2同态。
A． B．
C． D．
8．图G有21条边，3个4度结点，其余均为3度结点，则G有（ ）个结点。
A．13 B． 15 C．17 D．19
9．以下命题中正确的结论是（ ）
A．时，完全图必为欧拉图
B．如果一个连通图的奇结点的个数大于2，那么它可能是一个Euler图；
C．一棵树必是连通图，且其中没有回路；
D．图的邻接矩阵必为对称阵.
10．若连通图，其中，则要删去G中（ ）条边，才能确定G的一棵生成树。
A． B． C． D．
二．填空题
11．公式的对偶式为 。
12．子集公理的逻辑表达式为 。
13．设集合A = {a,b,c,d}，A上的二元关系R = {<a,b>,<b,d>,<c,c>,<c,d>}，那么Dom(R) = ，Ran(R) = 。
14．设集合B = {a,b,c}上的二元关系R的关系矩阵，则R具有的性质是 ，且它的对称闭包＝ 。
15．设集合A = {a,b}，B = {1,2}，则从A到B的所有函数是
，其中双射的函数 。
16．完全图是平面图的充要条件是
17．在布尔代数中，有成立，则其对偶式 成立。
18．已知下图，它的点连通度为 ，边连通度为 。
19．给定平面图G，如下图所示，则G的面数为 ，G中面的总次数为 。
20．若二部图为完全二部图，则其边数为
三．计算题(一)
21．符号化下述两个语句，并说明其区别：
（1）如果天不下雨，我们就去旅游；（2）只有不下雨，我们才去旅游。
22．将下命题化为主析取范式和主合取范式： .
23．设，求：⑴ ；⑵ ；
⑶ ；⑷
24．设集合Ａ＝｛１，２，３，４｝，Ａ上的二元关系Ｒ，其中Ｒ＝｛<1,1>,<1,4>,<2,2>,
<2,3>,<3,2>,<3,3>,<4,1>,<4,4>｝，说明Ｒ是否Ａ上的等价关系。
25．分别画下图中的强分图、单向分图。
26．设代数系统,其中Z是整数集，二元运算定义为。,求的逆元.三．计算题(二)
27．设是布尔代数，，化简。
28．求下图D的邻接矩阵，并算出其可达矩阵
四．证明题
29．试证明：┣
30．给定正整数m，令，证明：是一个群，其中+是数的普通加法。复习题十
一 ．单项选择题
1．下列哪个语句是真命题（ ）。
A．我正在说谎 B．如果1+2 = 3，则雪是黑色的
C．如果1+2 = 5，则雪是黑色的 D．上网了吗
2．设L(x)：x是演员，J(x)：x是教师，A(x，y)：x佩服y，命题“所有演员都佩服某些
教师”可符号化为（ ）。
A． B．
C． D．
3．设A，B，C为任意三个集合，下列命题正确的是（ ）。
A．若，则 B．若，则
C．若且，则 D．若，则
4．设集合A = {a，b}上的二元关系R = {<a,a>,<b,b>}，则R（ ）。
A．是等价关系但不是偏序关系 B．是偏序关系但不是等价关系
C．既是等价关系又是偏序关系 D．既不是等价关系也不是偏序关系
5．1．设集合A和二元运算*，可交换的代数运算是（ ）。
A．设
B．设
C．设，运算是矩阵的乘法
D．设
6．设G是6阶循环群，a是生成元。则下列集合能构成G的子群的是（ ）。
A． B． C． D．
7．设代数系统和，存在映射，如果，都有（ ），称K1与K2同态。
A． B．
C． D．
8．图G有21条边，3个4度结点，其余均为3度结点，则G有（ ）个结点。
A．13 B． 15 C．17 D．19
9．若连通图，其中，则要删去G中（ ）条边，才能确定G的一棵生成树。
A． B． C． D．
10．如下图所示各图，其中存在哈密顿回路的图是（ ）。
A B C D
二．填空题
11．任意两个不同极小项的合取为 式，全体极小项的析取式必为 式。
12．命题“任意实数总能比较大小”可符号化为 。
13．由集合运算的吸收律， ， 。
14．设集合A = {a,b,c,d}，A上的二元关系R = {<a,a>,<a,b>,<b,d>}，S = {<a,d>,<b,c>,<b,d>,<c,b>}，则R·S = ，R 2 = 。
15．设集合A = {a,b,c,d}，A上的二元关系R = {<a,b>,<b,d>,<c,c>,<c,d>}，那么Dom(R) = ，Ran(R) = 。
16．设集合B = {a,b,c}上的二元关系R的关系矩阵，则R具有的性质是
17．在布尔代数中，有成立，则其对偶式 成立。
18．已知下图，它的点连通度为 ，边连通度为 。
19．给定平面图G，如下图所示，则G的面数为 ，G中面的总次数为 。
20．二部图G中所有基本圈的长度为 （奇数或偶数）
三．计算题
21．符号化下述两个语句，并说明其区别：
（1）如果天不下雨，我们就去郊游；（2）只有不下雨，我们才去郊游。
22．试求命题公式的主析取范式和主合取范式。
23．设，求：⑴ ；⑵ ；
⑶ ；⑷
24．设集合A = {a，b}，B = {1，2，3}，C = {3，4}，求，，并验证。
25．设集合A = {0,1,2,3,4,5}上的二元关系R = {<0,0>,<1,1>,<1,2>,<1,3>,<2,1>,<2,2>, <2,3>,<3,1>,<3,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>}，试说明R在A上是等价关系。
26．设Z+是正整数集，，（即的最小公倍数）。试问是半群，是含单位元的半群吗？三．计算题（二）
27．设是布尔代数，，化简
。28．求图D的邻接矩阵，计算，并找出到长度为2，3的所有通路。
四证明题
29．试证明：30．在整数集合上定义如下的乘法运算“”：，那么构成一个什么样的代数结构？试证明你的结论。
www.ap5u.com提醒：
答案可以联系qq 761296021
页:
[1]