（推荐）离散数学作业册

《（推荐）离散数学作业册》由会员分享，可在线阅读，更多相关《（推荐）离散数学作业册（44页珍藏版）》请在装配图网上搜索。

1、如果您需要使用本文档，请点击下载按钮下载!第一章 命题逻辑1.1 命题与逻辑联结词1. 判断下列语句是否是命题，不是划“”，是划“”，且指出它的真值.(1)所有的素数都是奇数. ( ) 其真值( )(2)明天有离散数学课吗？ ( ) 其真值( )(3) ( ) 其真值( )(4)实践出真知. ( ) 其真值( )(5)这朵花真好看呀！ ( ) 其真值( )(6) ( ) 其真值( )(7)太阳系外有宇宙人 ( ) 其真值( )2. 将下列命题符号化(1)如果天下雨，那么我不去图书馆. (2)若地球上没有水和空气，则人类无法生存.(3)我们不能既划船又跑步(4)大雁北回，春天来了.3.将下列复合

2、命题分解成若干个原子命题，并找出适当的联结词.(1)天下雨，那么我不去图书馆.(2)若地球上没有水和空气，则人类无法生存.如果您需要使用本文档，请点击下载按钮下载!1.2 命题公式1. 判断下列各式是否是命题公式，不是的划“”，是的划“”(1)(QRS). ( )(2)(R(QR)(PQ). ( )(3) (PQR)S. ( )(4)(PQ)(QP). ( )2写出五个常用命题联结词的真值表.如果您需要使用本文档，请点击下载按钮下载!1.3 真值表与等价公式1.指出下列命题的成真赋值与成假赋值(1)(PQ).(2)P(QP).2.构造真值表，判断下列公式的类型(1)(PQ)(PQ).(2) P

3、(PQ)R.3.用等值演算法验证下列各等价式(1) (PQ)(QR)(PR)T.(2)P(QR)(PQ)(PR).(3)(PQ)(PQ)P如果您需要使用本文档，请点击下载按钮下载!1.4 蕴涵式及其他联结词1.试证明下列各式为重言式(1) (PQ)(QR)(PR)(2) (PQ)QPQ(3) (PQ)PQ2.将下列公式化成与之等价且仅含，中联结词的公式(1) (PQ)P(2) (P(QR)(PQ)3.证明，是最小全功能联结词组.4.设A、B、C为任意的三个命题公式，试问下面的结论是否正确？(1)若ACBC，则AB(2)若AB，则AB(3)若ACBC，则AB如果您需要使用本文档，请点击下载按钮下

4、载!1.6 对偶与范式1.试给出下列命题公式的对偶式(1)T(PQ)(2)(PQ)(PQ)2.试求下列各公式的主析取范式和主合取范式(1) (P(QR)(P(QR)(2)(PQ)Q)R(3)(P(QR)(P(QR).3.试用将公式化为主范式的方法，证明下列各等价式(1) (PQ)(PR)P(QR)(2) (PQ)(PQ)(PQ)如果您需要使用本文档，请点击下载按钮下载!1.7 推理理论1.试用推理规则，论证下列各式(1) (PQ),QR,RP(2) PQ,QR,PS,SR(PQ)(3) PQ,QR,RSPS(4) PQ,PR,QSRS如果您需要使用本文档，请点击下载按钮下载!第二章 谓词逻辑2

5、.1 词的概念与表示1.用谓词表达写出下列命题(1) 高斯是数学家，但不是文学家.(2)小王既是运动员也是大学生.(3)张宁和李强都是三好学生.(4)若是奇数，则2不是奇数.2.2 命题函数与量词1.用谓词表达式写出下列命题(1) 每个计算机系的学生都学离散数学.(2)直线A平行于直线B当且仅当直线A不相交于直线B.(3)不存在既是奇数又是偶数的自然数.(4)没有运动员不是强壮的.(5)有些有理数是实数但不是整数.(6)所有学生都钦佩某些教师.如果您需要使用本文档，请点击下载按钮下载!2.3 谓词公式与变元的约束1.利用谓词公式翻译下列命题(1)没有一个奇数是偶数.(2)一个整数是奇数，如果它

6、的平方是奇数.2. 设个体域为自然数集N，令P(x)：x是素数；E(x)：x是偶数；O(x)：x是奇数；D(x，y)：x整除y将下列各式译成汉语(1)$x(E(x)D(x，6)(2)x(O(x)y(P(x)D(x，y) 3.指出下列表达示中的自由变元和约束变元，并指明量词的辖域(1)(2)x(P(x，y)Q(z)$y(R(x，y) zQ(z)4.设个体域为Aa，b，c，消去公式xP(x)$xQ(x)中的量词如果您需要使用本文档，请点击下载按钮下载!2.4 谓词演算的等价式与蕴含式1.试证下列等价式或蕴涵式,其中A(x),B(x)表示含x自由变量的公式,A,B表示不含变量x（不论是自由的还是约束

7、的）的公式.(1)（x A(x)B）(x(A(x)B)(2)（x A(x)B）x(A(x)B)2.试将下列公式化成等价的前束范式(1)x（yP(x,y)）(zQ(z)R(x)）(2)x(F(x)G(x)($xF(x)$xG(x)如果您需要使用本文档，请点击下载按钮下载!2.5 谓词演算的推理理论1.证明下列推理(1)所有有理数都是实数，某些有理数是整数。因此，某些实数是整数.(2)每个大学生不是文科生就是理科生，有些大学生是优等生，小张不是理科生，但他是优等生.因而，如果小张是大学生，他就是文科学生.2.将下列的命题符号化，并证明之.已知每一个大学生都是诚实的，而小李是不诚实的，证明小李不是大

8、学生.如果您需要使用本文档，请点击下载按钮下载!第三章 集合代数1.在1到200的整数中(1和200包含在内)分别求满足以下条件的整数个数(1)可以被3整除,但不能被5或7整除(2)可以被3或5整除，但不能被7整除2.化简下列集合表达式(1)(A-(BC)(ABC)(2)(AB)-(C-(AB)3.计算幂集(1)(2)如果您需要使用本文档，请点击下载按钮下载!第四章 二元关系4.序偶与笛卡儿积1.设Aa，b，求集合P(A)A2.设A、B、C和D为任意集合，判断下列命题是否正确？(1)ABACBC(2)(AB)C(AC)(BC)(3)存在集合A使得AAA如果您需要使用本文档，请点击下载按钮下载!

9、4.二元关系1.写出下列关系R的序偶集合(1)A=, xRyA(2)A=, xRyA2. 设，从A到B的关系，试给出R的关系图和关系矩阵.3设A=1，2，3，4，A上关系R的关系的图为写出R的表达式如果您需要使用本文档，请点击下载按钮下载!4.3 关系的运算1.Aa，b，c，d，R1和R2是A上关系，R1，R2，求:(1) R1R2、R2R1、R1和 R2(2)给出R1的关系矩阵和关系图(3) R12.设R和S均为A上的二元关系，证明(1)(RS)=RS(2)(RS)=SR3.设A=1,2,3,试给出A上的两个不同的关系R1和R2，使R1= R1，R2= R2如果您需要使用本文档，请点击下载按

10、钮下载!4.4 关系的性质 1.设X1，2，3，4，R是X上的二元关系，R，(1)画出R的关系图.(2)写出R的关系矩阵.(3)说明R是否是自反、反自反、对称、传递的.2.设R和S是A上的任意关系，下列命题是否成立？若成立予以证明，否则举例证明其不成立.(1)若R具有传递性和反自反性，则R具有反对称性.(2)若R和S是传递的，则RS是传递的.3.在整数集合Z上的空关系，全关系ZZ，D(整除)，是否具有自反、反自反、对称、反对称、传递属性？4.若集合A上的二元关系R和S具有对称性，证明 RS对称当且仅当RSSR如果您需要使用本文档，请点击下载按钮下载!4.关系的闭包运算1.设Aa，b，c，d，R

11、是A上的二元关系，且R，b，c，求r(R)、s(R)和t(R)2.试举例说明st(R)ts(R).3设集合A=a，b，c，d上的关系R=,用矩阵运算求出R的传递闭包t(R)如果您需要使用本文档，请点击下载按钮下载!4.等价关系与划分1集合，C*上定义关系，则R是C*上的一个等价关系2.设R是集合A上的关系，如果对任意aA;都有aRa 若aRb,aRc,则bRc;试证R是等价关系.3集合S=1，2，3，4，5，找出S上的等价关系，此关系能产生划分1，2，3，4，5，并画出关系图 如果您需要使用本文档，请点击下载按钮下载!4.7 偏序关系1.设A=,A上的关系R的关系矩阵为.求R的哈斯图2.设P是

12、集合A上的偏序关系，BA. 试证明P(BB)是B上的偏序关系.3. 画出下列集合1，2，3，4，5，8，12，24上整除关系的哈斯图，并指出它们的最大元、极大元、最小元、极小元.如果您需要使用本文档，请点击下载按钮下载!第五章 函数5.2 函数复合1.设f: AB,定义A上的关系R为.证明 R是等价关系.2.设A=，置换P=.求最小正整数k，使.3.设f: AB, g: BC, 且fg: AC是双射. 证明 (1) f: AB是单射；(2) g: BC是满射.如果您需要使用本文档，请点击下载按钮下载!第六章 代数结构6. 二元运算及其性质1 设，问下面定义的二元运算*是否为S上的二元运算？（1

13、）与的最大公约数（2）大于等于的最小整数2设，其中的运算表分别给定如下*abcaabCbabccabc讨论*运算的可交换性、幂等性，是否含有单位元以及S中的元素是否含有逆元.3设.其中表示函数的合成，试给出的运算表，并求出的幺元和所有可逆元的逆元如果您需要使用本文档，请点击下载按钮下载!6. 代数系统1.填空题(1)设集合N为正整数集合，下列定义的二元运算不封闭的是（ ）.( A ) x*y= x. ( B ) x*y=2. ( C ) x*y=GCD(x,y),GCD(x,y)是x与y的最大公约数. ( D ) x*y=x+y-xy(2)对任一代数系统，下列说法正确的是（ ）.( A )单位

14、元和零元总不相等. ( B ) 单位元总有逆元 .( C ) 任一元素的左逆元必等于右逆元 . ( D ) 幂等元必唯一.2.求解与证明题(1)下面各集合都是N的子集,它们能否构成代数系统的子代数?A=,B=(需说明理由).(2)定义在上的两个二元运算*和分别为a*b=,ab=ab, a,bN.试证明 *对是不可分配的.(3)给定代数系统，且*是可结合的，若对A中任意元a和b，有a*bb*aab，试证 *满足幂等律如果您需要使用本文档，请点击下载按钮下载!6.3 半 群1.在实数集R上定义二元运算*为：a*babab，试判断下列论断是否正确？为什么？(1)是一个代数系统.(2)是一个半群.(3

15、)是一个独异点.2.设是半群，对A中任意元a和b，如ab必有a*bb*a，证明 (1)对A中每个元a，有a*aa(2)对A中任意元a和b，有a*b*aa(3)对A中任意元a、b和c，有a*b*ca*c3设S=a,b,构造半群的运算表如果您需要使用本文档，请点击下载按钮下载!6.4 群1.下列代数系统中不是群的是( ).( A ),*是R上的二元运算,a,bR,a*b=a+b-3.( B ),F为n次实系数多项式的集合,“”为多项式乘法.( C ). ( D ).2.求解与证明题(1) 设是一独异点,H是S中所有可逆元素的集合，试证明 是一个群.(2) 设Z是整数集合，在Z上定义二元运算*为：x

16、*yxy2，那么Z和*是否构成群？为什么？.(3)设G=，且是群，试构造群的运算表.如果您需要使用本文档，请点击下载按钮下载!65 子群1.设是群，对任G，令H=.试证明是的子群.2.试求群的所有子群.3.设，均为群的子群,且H,K互不包含,试证明HKG.如果您需要使用本文档，请点击下载按钮下载!6.6 陪集 拉格朗日定理1.设为群的子群，H=，试求子群H的不同左陪集.2.求证 若H在G中的指数为2，则H必是G的不变子群.3.设G为一个群，S是G的一个子群,令N(S)=，证明N(S)为G的不变子群.如果您需要使用本文档，请点击下载按钮下载!6.7 群的同态与同构1.下列映射中为同构映射的是（

17、）.(A)设和为群，取固定的aG,f: ZG, f(n)=.(B)设和为群，f: ZG, f(n)=n.(C)设加群到乘群的映射f,且f(x)=5,.(D)设H=,f: NH,f(n)=dn.2.证明:循环群的子群与同态像是循环群.3.设f为从群到群的同态映射，则f为单同态当且仅当Kerf=e,其中e是G的单位元.如果您需要使用本文档，请点击下载按钮下载!6.8 环与域1.设A=,验证是否构成域.（其中+，为普通的加法和乘法.2.设是一个环,且对于,都有aa=a,证明(1)a+a=,其中为加法单位元.(2)是可换环.3.证明 当n不为素数时，必定含有零因子，并对于找出其零因子如果您需要使用本文

18、档，请点击下载按钮下载!第七章 格与布尔代数 7.2 分配格与有补格1.判断下面关于格的命题的真假性.(1)设是格,则和均为交换半群. ( )(2)设是格,a,bL,那么,ab=a和ab=b至少有一个成立. ( )(3)设是格,aL,若a有余元素,那么该余元素是惟一的. ( )(4)设N为正整数集合,/为其上的整除关系,则为有余分配格. ( )2.试证 若一个有界格含有不只一个元素,则该有界格中任何一个元素的余元素必不是它自身.3.设有界分配格,试证 L中拥有余元素的各元素构成一个代数子格.如果您需要使用本文档，请点击下载按钮下载!7.3 布尔代数1.给定代数结构,其中S=a,b,c,d,证明

19、该代数结构是布尔代数.2.给定布尔代数,且a,b,cL.证明 (1)a(ab)=ab(2)(ab)(ab)=a3.设是布尔代数,如果在上定义一个二元运算为. 证明 是阿贝群.如果您需要使用本文档，请点击下载按钮下载! 第八章 图论8.1 图的基本概念1.设阶无向简单图G中，问应为多少？2.设无向图中有6条边，3度与5度顶点各1个，其余的都是2度顶点，问该图中共有几个顶点？3.一个简单无向图如果同构于它的补，则该图称为自补图.(1)给出一个五个结点的自补图.(2)给出一个五个结点的自补图.(3)是否存在三个结点、五个结点的自补图？(4)证明一个n阶自补图G, 其所包含的结点数n=4k或n = 4

20、k+1,其中k是正整数.如果您需要使用本文档，请点击下载按钮下载!8.2 路径与回路1. 给定无向图G如图所示，试求(1)从a到d的所有简单路(2)长度分别是最小和最大的简单回路(3)从a到d的距离(4)d(G)、D(G)分别是多少？2. 证明 若图G是不连通的，则G的补图是连通的.3.设e为图G中的一条边，w(G)为G的连通分支数，证明 w(G)w(Ge)w(G)1.如果您需要使用本文档，请点击下载按钮下载!8.3 图的矩阵表示1.求出图G(下图所示)的邻接矩阵A(G),找出从到长度为2和4的路径, 用计算来验证这一结论. 2.给定一个简单有向图D=(V,E), 用A(D)表示D的邻接矩阵,

21、可把图的距离矩阵定义成 .(1)求出右图的距离矩阵.(2)如何从一个距离矩阵求可达性矩阵.(3)说明若一个图G的距离矩阵的元素除 主对角线元素外都不是零且不是,那么图G是强连通的.如果您需要使用本文档，请点击下载按钮下载!8.4 欧拉图与哈密尔顿图1.试构造一个欧拉图，使其结点数n和边数m 满足以下条件,如果不可能, 请说明原因.(1)m 和 n 的奇偶性相同； (2)m 和 n 的奇偶性相反.2.今有n个人,已知他们中的任何二人合起来认识其余的n-2个人.证明: 当n3时, 这n个人能排成一列,使得中间的任何人都认识两旁的人,而两旁的人认识左边(或右边)的人. 当n4时, 这n个人能排成一个

22、圆圈,使得每个人都认识两旁的人.3. 5阶完全带权图(下图所示),求图中最短的哈密尔顿回路.如果您需要使用本文档，请点击下载按钮下载!8.5 二部图1.证明：如果G是二部图，它有n个顶点，m条边，则mn2/4. 2. 甲、乙、丙、丁四位教师，分配他们教数学、物理，电工和计算机原理四门课。甲能教物理和电工，乙能教数学和计算机原理，丙能教数学、物理和电工，丁只能教电工，对他们的工作怎样分配？3.画出完全二部图.如果您需要使用本文档，请点击下载按钮下载!8.6 平面图1.证明 在n3的简单平面图中,面数r2n-4.2证明 (1) 对于K5 的任意边e, K5 - e 是平面图. (2) 对于K3,3

23、的任意一条边e, K3,3 - e 是平面图.3.求下图的点着色数.如果您需要使用本文档，请点击下载按钮下载!8.7 树1.一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点？2.对于下图，利用克鲁斯克尔(Kruskal)算法求一棵最小生成树.3.给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100.(1)构造一棵最优二叉树.(2)构造一棵最优三叉树.(3)说明如何构造一棵最优t叉树.如果您需要使用本文档，请点击下载按钮下载!离散数学模拟试题(一)一、求公式(pq)(pq)的析取范式、合取范式及主析取范式、主合取范式。（本大题共8分）二、

24、用推理规则证明：（本大题共12分）前提 ($x)P(x)(x)(P(x)Q(x)R(x)，($x)P(x)，($x)Q(x)结论 ($x)($y)(R(x)R(y)三、计算题（本大题共15分，每小题3分，共5小题）1.证明逻辑等价式AB (AB)(AB)成立。2.设AB，求证ACBC。3.设集合A=a，b，c，d，A上的关系R=,，求R的自反闭包、对称闭包。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。定

25、义A/R上的关系R/S： R/S当且仅当S证明：R/S为A/R上的等价关系。（本大题共8分）五、设上的整除关系，是否为上的偏序关系？若是，则：1、画出的哈斯图；2、求。（本大题共7分）六、设为一群。证明：（1）若对任意aG有a2 =e，e为幺元，则G为阿贝尔群。如果您需要使用本文档，请点击下载按钮下载!（2）若对任意a，bG有(a*b)2 =a2*b2 ，则G为阿贝尔群。（本大题共10分）七、设N4 =0，1，2, 3，f：N4N4定义如下： 令F = f0,f1,f2,f3，其中f0为N4上恒等函数。给定一代数结构，且（这里为函数合成运算，+4为模4加运算）。试证与同构。（本大题共10分）如

26、果您需要使用本文档，请点击下载按钮下载!离散数学模拟试题(二)一、填空（本大题共5个空，每空2分，总计10分）1、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系，有 个从A到B的函数，其中当mn时有 个单射，当m=n时，有 个双射。2、集合 （是/不是）可数的。二、计算（本大题共2小题，每小题10分，总计20分）1、用推导法求下列公式的主合取范式和主析取范式：2、设上二元关系，求其自反闭包、对称闭包、传递闭包。三、证明（本大题共2小题，第1小题5分，第2小题10分，总计15分）1、设是三个集合，证明：2、证明等价式：四、（本大题共15分）将下列命题推理符号化并给出形式证明：

27、已知张三或李四的彩票中奖了；如果张三的彩票中奖了，那么你是知道的；如果李四的彩票中奖了，那么王五的彩票也中奖了；现在你不知道张三的彩票中奖。所以李四和王五的彩票都中奖了。五、（本大题共10分）设复数集合，定义：当且仅当，证明：为等价关系。六、（本大题15分）设集合，是普通乘法，证明：是一个群。七、（本大题15分）设实数集合R，+和x是普通加法和乘法，定义映射，证明的单一同态。如果您需要使用本文档，请点击下载按钮下载!离散数学模拟试题(三)一、单项选择题（每小题1分，本大题共15分）1设A=1，2，3，4，5，下面（ ）集合等于A A、1，2，3，4，5，6； B、；C、； D、2设A=1，2，

28、3，4，5，6，7，8，下列各式中（ ）是错的。A、； B、6，7，8A；C、4，5A； D、1，2，3A 3六阶群的子群的阶数可以是（ ）A、1，2，5； B、2，4； C、3，6，7； D、2，3 。4设，下列各式中（ ）是正确的A、 domSB ； B、domSA； C、ranSA； D、domS ranS = S5设集合，则空关系不具备的性质是（ ）A、自反性； B、反自反性； C、对称性； D、传递性6下列函数中，（ ）是入射函数A、世界上每个人与其年龄的序偶集； B、世界上每个人与其性别的序偶集；B、 一个作者的专著与其作者的序偶集； D、每个国家与其国旗的序偶集7是群，则对*（

29、）A、满足结合律、交换律； B、有单位元，可结合； C、有单位元、可交换； D、每元有逆元，有零元。8下面（ ）哈斯图所描述的偏序关系构成分配格如果您需要使用本文档，请点击下载按钮下载!9下列（ ）中的运算符都是可交换的A、； B、； C、； D、 10设G是n个结点、m条边和r个面的连通平面图，则m等于（ ）A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2 。11n个结点的无向完全图的边数为（ ）A、 ； B、 ； C、 ； D、。12下列图中（ ）是根树A、 ；B、 ；C、 ；D、 。13设P：22=5，Q：雪是黑的，R：24=8，S：太阳从东方升起，下列（ ）命

30、题的真值为真 A、； B、； C、； D、14下面（ ）命题公式是重言式 A、 ； B、； C、； D、15设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为（ ）A、； B、；C、； D、。如果您需要使用本文档，请点击下载按钮下载!二、填空题：（每空1分，本大题共15分）1设， 则 ， 。2在一个有n个元素的集合上，可以有 种不同的关系，有 种不同的函数。3若关系R是反对称的，当且仅当关系矩阵中 ，在关系图上 4设是一个复合函数，若和都是满射，则为 ，若和都是入射，则是 5三阶群有 个（不同构），其运算表为 6设图G = ，的邻接矩阵

31、，则的入度= ，的出度= ，从到的长度为2的路有 条。7命题公式的主合取范式为 8在半群、独异点、群中 满足消去律。三、判断改正题：判断下列各题是否正确，正确的划“”，错误的划“”，并加以改正。（每小题2分，本大题共20分）1A，B，C为任意集合，若，则B = C 。 （ ）如果您需要使用本文档，请点击下载按钮下载!2设R是实数集，R上的关系，R是相容关系。（ ）3设是偏序集，则B的极大元且唯一。 （ ）4谓词公式的前束范式是。（ ）5在代数系统 中，若一个元素的逆元是唯一的，其运算*必是可结合的。 （ ）6每一个有限整环一定是域，反之也对。 （ ）7有割点的连通图可能是哈密尔顿图。 （）8。

32、 （ ）9无多重边的图是简单图。 （ ）10设是布尔代数，则一定为有补分配格。 （ ）四、简答题：（每小题5分，本大题共20分）1设和是A上的任意二元关系，如果和是自反的，是否也是自反的，为什么？如果和是对称的，是对称的吗？2如图给出的赋权图表示六个城市及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。如果您需要使用本文档，请点击下载按钮下载!3设S = R - -1（R为实数集），。 （1）说明是否构成群； （2）在中解方程 。4将公式划为只含有联结词的等价公式。五、证明题：（共30分）1设，在上定义关系当且仅当，证明是上的等价关系，2设A=1，2，A上所有函数的集合记为AA, 是函数的复合运算，试给出AA上运算的运算表，并指出AA中是否有幺元，哪些元素有逆元。3将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。4证明：若T是有n个结点的完全二叉树，则T有片叶子。 （注：可编辑下载，若有不当之处，请指正，谢谢!）