《离散数学网上作业题》由会员分享，可在线阅读，更多相关《离散数学网上作业题（16页珍藏版）》请在金锄头文库上搜索。
1、东北农业大学网络教育学院离散数学复习题复习题一一、证明1、对任意两个集合，证明 2、构造下面命题推理的证明如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。二 、计算1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。(2)画一个有一条欧拉回路但没有汉密顿回路的图(3)画一个没有欧拉回路但有一条汉密顿回路的图2、设，求公式：的真值。3、一棵树有个结点度数为2 ，个结点度数为3， ，个结点度数为k ，问它有几个度数为1的结点。4、设集合上的关系 ，求出它的自反闭包，对称闭包和传递闭包。三、设上的整除关系，是否为上的
2、偏序关系？若是，则：1、画出的哈斯图；2、求。四、用推导法求公式的主析取范式和主合取范式。五、设实数集上的关系，证明：是上的等价关系。六、设分别是实数集和正实数集，和分别是普通加法和乘法，定义函数为，证明的同构映射。七、设是实数集合，在上定义二元运算为：，试证明是一个群。是否阿贝尔群？复习题二一、设 上的整除关系 完成下列各小题。1、 证明是上的偏序关系。2、 画出偏序集的哈斯图。3、 在上定义两个二元运算和：对任意，。请填空（在横线上填是或不是）：代数系统 格。 代数系统 有界格。代数系统 有补格。 代数系统 分配格。二、求布尔函数的析取范式和合取范式设是布尔代数上的一个布尔表达式。试写出的
3、析取范式和合取范式（用推导法或列函数表的方法均可）。三、画出满足下列要求的图有一条欧拉回路和一条汉密尔顿回路。有一条欧拉回路但没有汉密尔顿回路。没有欧拉回路但有汉密尔顿回路。既没有欧拉回路也没有汉密尔顿回路。四、证明在完全二叉树中，边的总数等于2(n-1)，这里n是叶子数。五、计算求带权2、3、5、7、11、13的最优二叉树。六、证明在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。试证七、证明设是有限字母表，给定代数系统，其中是串的连接运算。对于任一串，建立到的映射，。证明是到的一个满同态，且当时，是同构映射。八、应用 给定有限状态机，它的状态图如附图所示。1、 求状态的01
4、1010的后继以及可接受状态序列。2、 求对于激励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在上定义两个二元运算和：对任意，。请填空（在横线上填是或不是并回答为什么）：代数系统 格，因为 。代数系统 有界格，因为 。代数系统 有补格
5、，因为 。代数系统 分配格，因为 。代数系统 布尔代数，因为 。二、计算设是布尔代数上的一个布尔表达式。试写出的析取范式和合取范式（用列函数表的方法）。三、回答问题完全图是否是欧拉图？是否是哈密尔顿图？为什么？ 四、画图对于下图，利用克鲁斯克尔算法求一棵最小生成树。五、计算一棵树有两个结点度数为2 ，1个结点度数为3，3个结点度数为4 ，其余结点度数为1。问该树有几个度数为1的结点。六、证明是无向简单图，其中，证明：。证明 因为是简单图，所以图中没有环和平行边，任意两结点间最多有一条边，故。七、证明已知求证 八、设计设计一台有限状态机，它的输出是已经输入符号数的模3数（即设计模3计数器）。九、
6、计算给定码C=00000,10001,01100,10101，求码C中任两个码字的海明距和。复习题四一、填空1、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系，有 个从A到B的函数，其中当mn时有 个入射，当m=n时，有 个双射。2、集合 （是/不是）可数的。二、计算1、用推导法求下列公式的主合取范式和主析取范式：2设上二元关系，求其自反闭包、对称闭包、传递闭包。三、证明1、设是三个集合，证明：2证明等价式：四、将下列命题推理符号化并给出形式证明：已知张三或李四的彩票中奖了；如果张三的彩票中奖了，那么你是知道的；如果李四的彩票中奖了，那么王五的彩票也中奖了；现在你不知道张三的
7、彩票中奖。所以李四和王五的彩票都中奖了。五、设复数集合，定义：当且仅当，证明：为等价关系。六、证明：若。七、设集合，是普通乘法，证明：是一个群。八、设实数集合R，+和x是普通加法和乘法，定义映射，证明的单一同态。复习题五一、填空1、实数集合R （是/不是）可数的。2、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系，有 个从A到B的函数，其中当mn时有 个入射，当m=n时，有 个双射。二、计算1、用推导法求下列公式的主合取范式和主析取范式：2设上二元关系，求其自反闭包、对称闭包、传递闭包。三、证明1、设是三个集合，证明：2证明等价式：四、将下列命题推理符号化并给出形式证明：已知
8、今天下雨或刮风；如果今天下雨，那么我在家看书；如果今天刮风，那么我去放风筝；今天我没有在家看书。所以今天刮风并且我去放风筝了。五、设正整数集合上的二元关系，证明：为等价关系。六、证明：若。七、设集合，是普通乘法，证明：是一个群。八、设正实数集合R+和实数集合R，+和x是普通加法和乘法，定义映射，证明的同构。复习题六一、 求公式q(pq)的析取范式、合取范式及主析取范式、主合取范式。二、用推理规则证明： 前提 ($x)(F(x)S(x)(y)(M(y) W(y)，($y)(M(y)W(y)结论 (x)(F(x)S(x)三、计算题1.证明逻辑等价式A(AB)AB成立。2.对任意集合A，B，C，证明
9、：（A - B） B = A B3.设二元关系R=, 求：(1) dom R(2) ran R(3) RR4.求集合A=|p,q都是整数的势。5. 在20名青年中有10名是公司职员，12名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。四、假设给定了正整数的序偶集合A，在A上定义二元关系R如下：,R,当且仅当xv=yu，证明R为等价关系。五、给出偏序集上偏序关系R的关系图（如下图所示）。（1）求偏序集的哈斯图。（2）指出A的最大、最小元（如果有的话），极大、极小元。六、设为群。若在G上定义二元运算,使得对任何元素x，yG，有xy = y*x。证明也是群七、设为群,a为G中给定
10、元素。定义函数f：GG，使得对每一xG有f(x)=a*x*a-1证明：f是到的自同构。复习题七一、证明1、对任意两个集合，证明 2、构造下面命题推理的证明如果我学习，那么我数学不会不及格；如果我不热衷于玩游戏机，那么我将学习；但我数学不及格，因此我热衷与玩游戏机。二 、计算1、 画一个有一条欧拉回路和一条汉密顿回路的图。2、设，求公式：的真值。3一棵树有个结点度数为2 ，个结点度数为3， ，个结点度数为k ，问它有几个度数为1的结点。4设集合上的关系 ，求出它的自反闭包，对称闭包和传递闭包。三、设上的整除关系，是否为上的偏序关系？若是，则：1、画出的哈斯图；2、求的极大值和的极小值。四、用推导
11、法求公式的主析取范式和主合取范式。五、设自然数集上的关系定义为：，证明：是上的等价关系。六、设分别是实数集和正实数集，和分别是普通加法和乘法，定义函数为，证明的同构映射。七、设是整数集合，是普通加法，试证明是一个群。是否循环群？复习题八一、 求公式(pq)(pq)的析取范式、合取范式及主析取范式、主合取范式。二、用推理规则证明： 前提 ($x)P(x)(x)(P(x)Q(x)R(x)，($x)P(x)，($x)Q(x)结论 ($x)($y)(R(x)R(y)三、计算题1.证明逻辑等价式AB (AB)(AB)成立。2.设AB，求证ACBC。3.设集合A=a，b，c，d，A上的关系R=,，求R的自
12、反闭包、对称闭包。4.求下列集合的基数。（1）T=x|x是单词“BASEBALL”中的字母（2）B=x|xRx2=92x=8（3）C=，A=1,3,7,115. 求从1到500的整数中，能被3或5除尽的数的个数。四、设R，S为A上的两个等价关系，且R S。定义A/R上的关系R/S： R/S当且仅当S证明：R/S为A/R上的等价关系。五、设上的整除关系，是否为上的偏序关系？若是，则：1、画出的哈斯图；2、 求。六、设为一群。证明：（1）若对任意aG有a2 =e，e为幺元，则G为阿贝尔群。（2）若对任意a，bG有(a*b)2 =a2*b2 ，则G为阿贝尔群。七、设N4 =0，1，2, 3，f：N4N4定义如下： 令F = f0,f1,f2,f3，其中f0为N4上恒等函数。给定一代数结构，且（这里为函数合成运算，+4为模4加运算）。试证与同构。复习题九一单项选择题1命题公式为（ ）。A重言式 B可满足式 C矛盾式 D等值式2设集合A = 1，a，则P(A) =（ ）。A1，a B，1，a C，1，a，1，a D1，a，1，a3下列命题中正确的结论是：（ ）A集合上的关系如果不是自反的，就一定是反自反的；B若关系都是反自反的，那么必也为
