离散数学试题与答案试卷.doc

《离散数学试题与答案试卷.doc》由会员分享，可在线阅读，更多相关《离散数学试题与答案试卷.doc（27页珍藏版）》请在三一文库上搜索。

1、离散数学试题与答案试卷一一、填空 20% （每小题2分）1设 （N：自然数集，E+ 正偶数） 则 。2A，B，C表示三个集合，文图中阴影部分的集合表达式为 A B C 。3设P，Q 的真值为0，R，S的真值为1，则的真值= 。4公式的主合取范式为 。5若解释I的论域D仅包含一个元素，则 在I下真值为 。6设A=1，2，3，4，A上关系图为则 R2 = 。7设A=a，b，c，d，其上偏序关系R的哈斯图为则 R= 。8图的补图为 。9设A=a，b，c，d ，A上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是 ，有逆元的元素为 ，它

2、们的逆元分别为 。10下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分）1、下列是真命题的有（）A ； B；C ； D 。2、下列集合中相等的有（ ） A4，3；B，3，4；C4，3，3；D 3，4。3、设A=1，2，3，则A上的二元关系有（ ）个。 A 23 ； B 32 ； C ； D 。4、设R，S是集合A上的关系，则下列说法正确的是（ ） A若R，S 是自反的， 则是自反的； B若R，S 是反自反的， 则是反自反的； C若R，S 是对称的， 则是对称的； D若R，S 是传递的， 则是传递的。5、设A=1，2，3，4，P（A）（A的幂集）上规定二元系如下则P（A）/ R

3、 ）AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、设A=，1，1，3，1，2，3则A上包含关系“”的哈斯图为（ ）7、下列函数是双射的为（ ）Af : IE , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x | 。（注：I整数集，E偶数集， N自然数集，R实数集）8、图 中 从v1到v3长度为3 的通路有（ ）条。A 0；B 1；C 2；D 3。9、下图中既不是Eular图，也不是Hamilton图的图是（ ）10、在一棵树中有7片树叶，

4、3个3度结点，其余都是4度结点则该树有（ ）个4度结点。A1；B2；C3；D4 。三、证明 26%、 R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 和在R中有在R中。（8分）、 f和g都是群到的同态映射，证明是的一个子群。其中C= (8分)、 G= (|V| = v，|E|=e ) 是每一个面至少由k（k3）条边围成的连通平面图，则， 由此证明彼得森图（Peterson）图是非平面图。（11分）四、逻辑推演 16%用CP规则证明下题（每小题 8分）1、2、五、计算 18%1、设集合A=a，b，c，d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。 （9分）2、如

5、下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（分）试卷二试题与答案一、填空 20% （每小题2分）1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。2、论域D=1，2，指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式真值为 。2、 设S=a1 ，a2 ，a8，Bi是S的子集，则由B31所表达的子集是 。3、 设A=2，3，4，5，6上的二元关系，则R= （列举法）。R的关系矩阵MR= 。5、设A=1，2，3，则A上既

6、不是对称的又不是反对称的关系R= ；A上既是对称的又是反对称的关系R= 。*a b cabca b cb b cc c b6、设代数系统，其中A=a，b，c,则幺元是 ；是否有幂等 性 ；是否有对称性 。7、4阶群必是 群或 群。8、下面偏序格是分配格的是 。9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。10、公式的根树表示为 。二、选择 20% （每小题2分）1、在下述公式中是重言式为（ ）A；B；C； D。2、命题公式 中极小项的个数为（ ），成真赋值的个数为（ ）。A0； B1； C2； D3 。3、设，则 有（ ）个元素。A3； B6； C7； D8 。4、 设，定义上

7、的等价关系则由 R产 生的上一个划分共有（ ）个分块。A4； B5； C6； D9 。5、设，S上关系R的关系图为则R具有（ ）性质。A自反性、对称性、传递性； B反自反性、反对称性；C反自反性、反对称性、传递性； D自反性 。6、设 为普通加法和乘法，则（ ）是域。A BC D= N 。7、下面偏序集（ ）能构成格。8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。A1； B2； C3； D4 。9、在如下各图中（ ）欧拉图。10、设R是实数集合，“”为普通乘法，则代数系统 是（ ）。A群； B独异点； C半群 。三、证明 46%1、 设R是A上一个二元关系，试证明若R是A上一个

8、等价关系，则S也是A上的一个等价关系。（9分）2、 用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）3、 若是从A到B的函数，定义一个函数对任意有，证明：若f是A到B的满射，则g是从B到 的单射。（10分）4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）5、 设G是具有n个结点的无向简单图，其边数，则G是Hamilton图（8分）四、计算 14%1、 设是一个群，这里+6是模6加法，Z6=0 ，1，2，3，4，5，试求出的所有子群及其相应左陪集。（7分）2、 权数1，4，9，16，25，36，49，64，81，100构造一棵

9、最优二叉树。（7分）试卷三试题与答案一、 填空 20% （每空 2分）1、 设 f，g是自然数集N上的函数，则 。2、 设A=a，b，c，A上二元关系R= , , , 则s（R）= 。3、 A=1，2，3，4，5，6，A上二元关系，则用列举法 T= ；T的关系图为 ；T具有 性质。4、 集合的幂集= 。5、 P，Q真值为0 ；R，S真值为1。则的真值为 。6、 的主合取范式为 。7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词的自然语言是 。8、 谓词的前束范式为 。二、 选择 20% （每小题 2分）1、 下述命题公式中，是重言式

10、的为（ ）。A、； B、；C、； D、。2、 的主析取范式中含极小项的个数为（ ）。A 、2； B、 3； C、5； D、0； E、 8 。3、 给定推理PUSPESTIUG推理过程中错在（ ）。A、-; B、-; C、-; D、-; E、-4、 设S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在条件下X与（ ）集合相等。A、 X=S2或S5 ； B、X=S4或S5；C、X=S1，S2或S4； D、X与S1，S5中任何集合都不等。5、 设R和S是P上的关系，P是所有人的集合，则表示关系 （ ）。A、；B、；C、 ； D、。6、 下面函数（

11、 ）是单射而非满射。A、；B、；C、；D、。其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。7、 设S=1，2，3，R为S上的关系，其关系图为 则R具有（ ）的性质。A、 自反、对称、传递； B、什么性质也没有；C、反自反、反对称、传递； D、自反、对称、反对称、传递。8、 设，则有（ ）。A、1,2 ；B、1,2 ； C、1 ； D、2 。9、 设A=1 ,2 ,3 ，则A上有（ ）个二元关系。A、23 ； B、32 ； C、； D、。10、全体小项合取式为（ ）。A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。三、 用CP规则证明 16% （每小题 8

12、分）1、2、四、（14%） 集合X=, , , ，R=,|x1+y2 = x2+y1 。1、 证明R是X上的等价关系。 （10分）2、 求出X关于R的商集。（4分）五、（10%）设集合A= a ,b , c , d 上关系R= , , , 要求 1、写出R的关系矩阵和关系图。（4分） 2、用矩阵运算求出R的传递闭包。（6分）六、（20%）1、（10分）设f和g是函数，证明也是函数。2、（10分）设函数，证明 有一左逆函数当且仅当f是入射函数。卷号：4 湖北师范学院期末考试试卷离散数学本题得分一、选择题（选择真确答案，并将其代号写在题干后面的括号里，本题共6小题,每小题3分，共18分)1 命题“

13、小李和小王学习努力”的否定是：（ ）(A)小李或小王学习不努力； (B)小李和小王学习都不努力；(C)小李学习努力和小王学习不努力；(D)小李和小王至少有一人学习努力。2 设个体域，公式在中消去量词后应为: ( )(A) ； (B) ；(C) ； (D) 。3 A=1，2，3，A上的如下二元关系中，( )是函数。(A)R1=，,；(B)R2=，；(C)R3=，； (D)R4=，,，。4下列代数系统，哪个是群？ （ ）(A) 是模7加法； (B)（有理数集合），是一般乘法；(C) (整数集合)，是一般减法； (D) 是模11乘法。5下面集合（ ）关于整除关系构成格。(A)2，3，6，12，24，

14、36 ； (B)1，2，3，4，6，8，12 ；(C)1，2，3，5，6，15，30 ； (D)3，6，9，12。6 ，则有向图是（ ）。(A)强连通的 ； (B)单侧连通的 ； (C)弱连通的 ； (D)不连通的。本题得分二、填空题（请将正确答案填入空格内，每小题3分，共18分）1 设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为 _。2 设A=1，2，P(A)表示A的幂集，,则P(A) A =_。3设考虑下列子集：，则A的覆盖有 ，A的划分有 。4 设是分配格，若对任意的，如果有成立，则有 。5 若连通平面图共有r

15、个面，其中，则它满足的Euler公式为 。 6 5个结点可以构成 棵非同构得无向树。本题得分三、判断题（请在你认为正确的题后括号内打“”，错误的打“”，本题共6小题，每小题1分，共6分）1设P，Q是两个命题，当且仅当P，Q的真值均为T时，的值为T。（ ）2且。（ ）3 集合上的关系是传递的。（ ）4任何循环群必定是阿贝尔群，反之亦真。（ ）5设G为无向图，若G中恰好n个结点，n-1条边，则G必为一棵树。（ ）6平面图一定是连通图。( )本题得分四、计算题（本题共4小题,每小题6分，共24 分）1求下式的主析取范式和主合取范式：。2设集合A= 1,2,3,4上的二元关系R1与R2定义如下：R1=

16、R2=,，（1）写出的关系矩阵，并判断具有哪些性质？（2）求出。3 设S = R -1（R为实数集），。 （1）说明是否构成群； （2）在中解方程。4 一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。问T中有几个结点?本题得分五、应用题（本题共1小题,每小题10分，共10分）下图给出的赋权图表示六个城市及架起城市间直接通讯线路的预测造价。给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。本题得分六、证明题（本题共3小题,每小题8分，共24分）1设，在上定义关系当且仅当，证明是上的等价关系，并求出.2设是群，是G的子群，证明：是的子群。3将下列命题形式化，并证

17、明结论的有效性：所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。离散数学试题五一、判断题（每题1分，共10分）1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是惟一的。 （ ）2. 011是公式的成真赋值 ( )3. ( )4. （ ）5.三种重要的二元关系是等价关系、偏序关系和函数关系，它们的共同特点是都具有自反性 。 ( )6. 设F,R都是二元关系,则(FR)-1=F-1R-1。( )7.设n是任意一个正整数,则一定存在阶是n的群. ( )8. 布尔代数是有界格,也是分配格. ( )9.无向完全图（n2）一定是哈密顿图 ( )10.阶数至少是2 树的每一条边都是桥

18、因而它的边连通度是1. （ ）二、空题（每小题分，共分） 1. 谓词公式x(P(x,y) tQ(t,z)R(x,y,t)中量词的辖域是_。2.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_ _。 3.从公式分类角度来看，它为_式。 4.设R=,，则R的对称闭包是 。 5.设A,B是集合，6.，是模6加群， 则它的生成元是 。24= 7整数加群是循环群，其生成元是和。8.设是偏序集,如果_ _, 则称是(偏序)格。9.一棵二叉树先序遍历得ABDECF，中序遍历得DBEACF,则后序遍历的结果是_。 10. r=5,当s= 时，完全二部图才可能

19、存在完美匹配。 。 三、计算题（1-4题每题8分；5-6题每题10分，共52分）1.R1=,R2=,求：(1) R1-1 (2) R1R2 (3)R22 (4)t(R1)(传递闭包)2设G=，G上的运算是矩阵乘法。已知G构成群。（1）指出个元素的阶；（2）找出G的全部子群；（3）在同构的意义下G是4阶循环群还是Klein四元群？3.(1)在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中应该有几片树叶？(2)画出两棵非同构的满足上述条件的无向树。4.设为一个偏序集，其中，A=1，2，3，4，6，9，24，54,R是A上的整除关系。（1）画出的哈斯图； （2）求A的极大元和极小元；

20、3）求B=4,6的上确界和下确界。5.求公式的主和取范式(化成M1M2M3的形式)。画一棵带权为2，2，2，3，3，4，5，8的最优二叉树T，并计算它的权W（T）。四、证明题（每小题6分，共18分）1.前提： 结论: 2.定理（子群判别法1)设H是群的非空子集，则HG当且仅当(1)a，bH， abH；(2)aH，a1H。利用上述定理证明：设H是群的非空有限子集。若H关于封闭，则H是G的子群。3.用数学归纳法证明n阶无向树T有n-1边。离散数学试题六一、判断题（每题1分，共10分）1.任何命题公式都存在惟一的析取范式。 （ ） 2. 封闭的公式在任何解释下都变成命题。 ( )3. 的层数是3

21、 ）4. ( )5. 设A,B,C是三集合，已知ABAC，则一定有BC. ( )6.矩阵的等价、相似、合同都是等价关系。 ( )7.已知a是群集的二阶元，则=a,a2. ( )8.有界格中某元的的补元不止一个，则它不是分配格。 ( )9.有向图是强连通的，则它一定是单向连通的，也弱连通的。 ( )10.二部图是欧拉图也是哈密顿图。 ( )二、填空题（每小题2分，共20分） 1.从公式的类型看，它属于式。2. _。3.设F(x):x是人，H(x):x呼吸，在一阶逻辑中，命题“凡人都呼吸”的符号化形式为_ _。 4.6阶循环群有 个子群。 5. A=a,b,则A的幂集P(A)到自身的双射有_ _

22、个。6. A=1,2,3，S是A上所有置换构成的集合，构成群，则单位元是 ，的逆元是 ，该元是 阶元。7.一个3阶有向图的度序列是2，2，4，入度序列是2，0，2，出度序列是 。8.一无向图存在生成树的充分必要条件是 。9.最优二叉树有n片树叶，则它有 分支点。 10. 下图的点连通度等于 ，边连通度等于_。三、计算题（每小题10分，共50分）1.设A=a,b,c,B=b,c,d,C=d,e,f,R1=,R2=, 求(1) (2) AB (3) R1-1 (4) R1R2 (5) R1在A上的限制。2.其中，A=1，2，3，4，R=,R是A上的二元关系。（1）画出的R的关系图； （2）求R的自

23、反、对称、传递闭包； 3.S=QQ,其中Q为有理数集合，定义S上的二元运算*，,S，*=, (1)求*.(2)已知*=,求a,b.(3)*是可交换的吗？是可结合的吗？4.在一个无向图中有6条边，3度顶点和5度顶点各1个，其余顶点都是2度点，该图有几个顶点？5.在下图中，用克鲁斯卡尔算法构造最小生成树，写出边添加到生成树的边序列，并画出生成树。 四、证明题（共20分）1.前提：结论:2.已知(即整数集上2阶方阵构成的集合关于矩阵的加法)构成群,H=(1) 的单位元是什么? 的逆元是什么?(2)证明: H是的子群.3.叙述并证明关于连通平面图的欧拉公式。离散数学试题七一、选择题（每小题 2 分，共

24、 20 分）1、使命题公式p(pq)为假的赋值是()A.10B.01 C. 00D.112、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）A. pq BpqC.pq Dpq 3、设B不含有x，下列一阶逻辑等值式不正确的是()A.B. C. D. 4、 设X，Y，Z是集合，下列结论不正确的是（ ）A若XY,则XY=X B(X-Y)-Z=X-(YZ)C D5、设R是集合A上的二元关系，IA是上的恒等关系，IAR下面四个命题为真的是()A.R是自反的B.R是传递的C.R是对称的D.R是反对称的6、设函数f：NN（N 为自然数集），f(n)=n+1，下面四个命题为真的

25、是()A. f是单射B.f是满射 C. f是双射的 D.f非单射非满射7、集合A=1，2，3，4，则对A 的元素进行分类正确的是（ ）A. ,1,2,3,4 B. 1,2,3,3,4C. 1,3,4 D. 1,2,3,48、无向完全图有( )条边A. nB. n2 C.n(n-1)D. n(n-1)/29、 设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）A2 B3 C4 D5 10、一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则 根结点的右子树有（ ）结点。A1 B2 C3 D4二、填空题（每题2分，共10分）1、量词否定等值式 _。2、设R是A=1，2，

26、3，4上的二元关系,R=,则R的对称闭包是 。3、A=1，2，是群，是集合的对称差运算。该群的单位元是 ，1的逆元是 。4、图G是平面图的充分必要条件是没有收缩到_或 的子图。 5、无向图G=,V=a,b,c,d,E=(a,b),(a,c),(a,d),(b,c),则它的邻接矩阵为 ，该图的补图有 条边。三、计算题（每题8分，共 48分）1、求公式的主和取范式(化成M1M2M3的形式)。2、R1=, R2=, (1) 求 R1-1 (2) 求 (3)R1是函数吗？3、(1)叙述等价关系的定义；(2)设A=1，2，3，4,R=,是A上的等价关系吗？如果是,给出R确定的对A的分类；如果不是,请说明

27、理由。4、已知(即实数集上2阶方阵构成的集合关于矩阵的加法和乘法)构成的环。(1)的零位元是什么?单位元是什么?(2)说明 不是无零因子环；(3)举例说明不满足消去律。5、求A到其余顶点的最短路径。6、求下PERT图中各顶点的最早完成时间TE(vi)和最迟完成时间TL(vi)，并求出关键路径。得分阅卷人四、证明题（ 22分）1、前提： 结论: 2、设是可交换群，H=aGkN(正整数集)，使ak=e，证明H是G的子群。3、用数学归纳法证明，含有n片树叶的最优二叉树有n-1个分支点.离散数学试卷 八得分阅卷人一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内）题号12345 678

28、910答案1、从集合分类的角度看,命题公式可分为() A.永真式、矛盾式 B. 永真式、可满足式、矛盾式C. 可满足式、矛盾式 D. 永真式、可满足式2、设B不含有x，等值于()A. B. C. D.3、设S,T,M是集合，下列结论正确的是（ ）A如果ST=SM，则T=M B如果S-T=，则S=TC D4、设R是集合A上的偏序关系，则R不一定是()A.自反的 B. 对称的 C. 反对称的 D. 传递的5 设R为实数集，定义R上4个二元运算，不满足结合律的是（ ）。A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy D. f4(x,y)=maxx,y 6、设

29、是一个格，则它不满足()A.交换律 B. 结合律 C. 吸收律 D. 消去律7、设A=1,2,则群的单位元和零元是()A. 与AB. A与 C. 1与 D. 1与A8、下列编码是前缀码的是( ).A.1,11,101 B.1,001,0011 C.1,01,001,000D.0,00,0009、下图中既是欧拉图又是哈密顿图的是（ ） A B C D 10、下图所示的二叉树中序遍历的结果是（ ）Aabcde Bedcba Cbdeca Dbadce得分阅卷人二、填空题（每题3分，共24分）1、含3个命题变项的命题公式的主合取范式为,则它的主析取范式为 。()2、，模4加群， 则3是 阶元，33=

30、 ，3的逆元是 。 3、设V=,其中“+”是普通加法。，令1(x)=x, 2(x)=-x,3(x)=x+5, 4(x)=2x，其中有 个自同构.4、设是集合A=1，2，3，4,5,6上的一个置换，则把它表示成不相交的轮换的积是 。4、已知n阶无向简单图G有m条边，则G的补图有 条边。5、一个有向图是强连通的充分必要条件是 。7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m，则m= .8、在下图中从A点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是 （ ）。得分阅卷人三、计算题（每题9分，共 36分）1、已知命题公式，(1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。2、R1=, R2=,求： (1) （） () 求 、设为一个偏序集，其中，A=1，2，3，4，6，9，12，24,R是A上的整除关系。（1）画R出的哈斯图； （2）求A的极大元和极小元； （3）求B=4,6的上确界和下确界。、画一棵带权为1，1，1，3，3，5，8的最优二叉树T，并计算它的权W（T）。得分阅卷人四、证明题（共 20分）1、（7分）前提： 结论: 2、（7分）A=(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1),R=| (a,b),(c,d)A且a+b=c+d