|
|
东北农业大学网络教育学院
离散数学复习题
复习题一
一、证明
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：
<[x],[y]>(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．在整数集合上定义如下的乘法运算“”：，那么构成一个什么样的代数结构？试证明你的结论。
|
|
|手机版|小黑屋|网站地图|无忧答案网
( 冀ICP备18010495号-1 )
发表于 2017-7-3 11:28:58