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

上传人:坚持 文档编号:3563243 上传时间:2019-06-06 格式:DOC 页数:27 大小:739.50KB
下载 相关 举报
离散数学试题与答案试卷.doc_第1页
第1页 / 共27页
离散数学试题与答案试卷.doc_第2页
第2页 / 共27页
离散数学试题与答案试卷.doc_第3页
第3页 / 共27页
离散数学试题与答案试卷.doc_第4页
第4页 / 共27页
离散数学试题与答案试卷.doc_第5页
第5页 / 共27页
点击查看更多>>
资源描述

1、离散数学试题与答案试卷一一、填空 20% (每小题 2 分)1设 7|),5()(| xExBxNxA且且 (N:自然数集,E + 正偶数) 则 B 。2A,B,C 表示三个集合,文图中阴影部分的集合表达式为 。3设 P,Q 的真值为 0,R ,S 的真值为 1,则 )()( SP的真值= 。4公式 )的主合取范式为。5若解释 I 的论域 D 仅包含一个元素,则 )()(xPx 在 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

2、b c dA BCabcda b c db c d ac d a bd a b c那么代数系统 的幺元是 ,有逆元的元素为 ,它们的逆元分别为 。10下图所示的偏序集中,是格的为 。二、选择 20% (每小题 2 分)1、下列是真命题的有( )A 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 3; D 2。4、设 R,S 是集合 A 上的关系,则下列说法正确的是( )A若 R,S 是自反的, 则 SR是自反的;B若 R,S 是反自反的

3、, 则 是反自反的;C若 R,S 是对称的, 则 是对称的;D若 R,S 是传递的, 则 S是传递的。5、设 A=1,2,3,4,P ( A) (A 的幂集)上规定二元系如下 |(|),|tspts则 P(A)/ R=( )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 : I E , f (x) = 2x ; Bf : NNN, f (n) = ;Cf : R I , f (x) = x ; Df :I N, f (x) = |

4、 x | 。(注:I整数集,E偶数集, N自然数集,R 实数集)8、图 中 从 v1 到 v3 长度为 3 的通路有( )条。A 0; B 1; C 2; D 3。9、下图中既不是 Eular 图,也不是 Hamilton 图的图是( )10、在一棵树中有 7 片树叶,3 个 3 度结点,其余都是 4 度结点则该树有( )个 4度结点。A1; B2; C3; D4 。三、证明 26%、R 是集合 X 上的一个自反关系,求证:R 是对称和传递的,当且仅当和在 R 中有在 R 中。 (8 分)、f 和 g 都是群到的同态映射,证明是的一个子群。其中 C= )(|1xgfx且 (8 分)、G= (|

5、V| = v,|E|=e ) 是每一个面至少由 k(k 3)条边围成的连通平面图,则 2(ke, 由此证明彼得森图(Peterson)图是非平面图。 (11 分)四、逻辑推演 16%用 CP 规则证明下题(每小题 8 分)1、 FAEDCBA,2、 )()()( xQxPQxP五、计算 18%1、设集合 A=a,b,c ,d上的关系 R= , , , 用矩阵运算求出 R 的传递闭包 t (R)。 (9 分)2、如下图所示的赋权图表示某七个城市 721,v 及预先算出它们之间的一些直接通信线路造价,试给出一个设计方案,使得各城市之间能够通信而且总造价最小。 (分)试卷二试题与答案一、填空 20%

6、 (每小题 2 分)1、 P:你努力,Q:你失败。 “除非你努力,否则你将失败”的翻译为;“虽然你努力了,但还是失败了”的翻译为。2、论域 D=1,2,指定谓词 PP (1,1) P (1,2) P (2,1) P (2,2)T T F F则公式 ),(xy真值为 。2、 设 S=a1 ,a 2 ,a 8,B i 是 S 的子集,则由 B31 所表达的子集是。3、 设 A=2,3,4,5,6上的二元关系 |,是 质 数xyxR,则 R= (列举法) 。R 的关系矩阵 MR=。5、设 A=1,2,3,则 A 上既不是对称的又不是反对称的关系 R= ;A 上既是对称的又是反对称的关系 R= 。6、

7、设代数系统 ,其中 A=a,b,c,则幺元是 ;是否有幂等 性 ;是否有对称性 。7、4 阶群必是 群或 群。8、下面偏序格是分配格的是 。9、n 个结点的无向完全图 Kn 的边数为 ,欧拉图的充要条件是。10、公式 RQPP)()( 的根树表示为。二、选择 20% (每小题 2 分)1、在下述公式中是重言式为( )A )()(QP;B )()()( PQP;* a b cabca b cb b cc c bC QP)(; D )(QP。2、命题公式 )( 中极小项的个数为( ) ,成真赋值的个数为( ) 。A0; B1; C2 ; D3 。3、设 ,S,则 S 有( )个元素。A3; B6;

8、 C7 ; D8 。4、 设 ,21,定义 上的等价关系 , | cbdaSdcSbadcbaR 则由 R 产 生的 S上一个划分共有( )个分块。A4; B5; C6 ; D9 。5、设 3,21,S 上关系 R 的关系图为则 R 具有( )性质。A自反性、对称性、传递性; B反自反性、反对称性;C反自反性、反对称性、传递性; D自反性 。6、设 , 为普通加法和乘法,则( ) ,S是域。A ,3|QbaxS B ,2|ZbanxC ,12Zn D 0= N 。7、下面偏序集( )能构成格。8、在如下的有向图中,从 V1 到 V4 长度为 3 的道路有( )条。A1; B2; C 3; D4

9、 。9、在如下各图中( )欧拉图。10、设 R 是实数集合, “”为普通乘法,则代数系统 是( ) 。A群; B独异点; C半群 。三、证明 46%1、 设 R 是 A 上一个二元关系, ),(),(|, RbccaAcbaS 且有对 于 某 一 个试证明若 R 是 A 上一个等价关系,则 S 也是 A 上的一个等价关系。 (9 分)2、 用逻辑推理证明:所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。(11 分)3、 若 BAf:是从 A 到 B 的函数,定义一个函数 ABg2:对任意 Bb有)()(|)( bxfxbg,证明:若 f 是 A 到 B 的满射,则 g

10、是从 B 到 A2的单射。 (10 分)4、 若无向图 G 中只有两个奇数度结点,则这两个结点一定连通。 (8 分)5、 设 G 是具有 n 个结点的无向简单图,其边数2)(12nm,则 G 是Hamilton 图(8 分)四、计算 14%1、 设是一个群,这里+ 6 是模 6 加法,Z 6=0 ,1,2 ,3,4 ,5 ,试求出的所有子群及其相应左陪集。 (7 分)2、 权数 1,4,9,16,25,36,49,64,81,100 构造一棵最优二叉树。 (7 分)试卷三试题与答案一、 填空 20% (每空 2 分)1、 设 f,g 是自然数集 N 上的函数 xgxfx2)(,1)(, ,则

11、)(x 。2、 设 A=a,b,c,A 上二元关系 R= , , , 则 s(R)= 。3、 A=1,2,3,4,5,6,A 上二元关系 |,是 素 数yxT,则用列举法T= ;T 的关系图为;T 具有 性质。4、 集合 2,A的幂集 A= 。5、 P,Q 真值为 0 ;R,S 真值为 1。则)()()( SRQPSRwf 的真值为 。6、 f的主合取范式为 。7、 设 P(x):x 是素数, E(x):x 是偶数,O(x):x 是奇数 N (x,y):x 可以整数y。则谓词 ),()()(yNOyPwf 的自然语言是。8、 谓词 ),(),(),( uyxQzyxzyf 的前束范式为。二、

12、选择 20% (每小题 2 分)1、 下述命题公式中,是重言式的为( ) 。A、 )()(qp; B、 )()()( pqpq;C、 ; D、 。2、 rwf)(的主析取范式中含极小项的个数为( ) 。A 、2; B、 3; C、5; D、0; E、 8 。3、 给定推理 )(xGFxP )yUS (P ) ES (yGTI )xUG)()(xGF推理过程中错在( ) 。A、-; B、-; C、-; D、-; E、-4、 设 S1=1, 2,8,9,S 2=2,4,6,8 ,S 3=1,3,5,7,9,S 4=3,4,5,S5=3, 5,在条件 31X且 下 X 与( )集合相等。A、 X=S

13、2 或 S5 ; B、X=S 4 或 S5;C、X=S 1,S 2 或 S4; D、X 与 S1,S 5 中任何集合都不等。5、 设 R 和 S 是 P 上的关系,P 是所有人的集合, ,|的 父 亲是 yxyx,, 的 母 亲是则 R1表示关系 ( ) 。A、 ,|的 丈 夫是 ;B、 , 的 孙 子 或 孙 女是 yxPyx ;C、 ; D、 ,|的 祖 父 或 祖 母是 yx。6、 下面函数( )是单射而非满射。A、 12)(,: xfRf ;B、 Zln;C、 的 最 大 整 数表 示 不 大 于 xff ,)(,: ;D、 12x。其中 R 为实数集,Z 为整数集, R+,Z +分别

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

15、、 )()()( xQxPQxP四、 (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 是函数,证明 gf也是函数。2、 (10 分)设函数 STS:,证明 STf:有一左逆函数当且仅当 f 是入射函数。卷号:4 湖北师范学院期末考试试卷离散数学

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 参考答案

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。