资源预览内容
第1页 / 共20页
第2页 / 共20页
第3页 / 共20页
第4页 / 共20页
第5页 / 共20页
第6页 / 共20页
第7页 / 共20页
第8页 / 共20页
第9页 / 共20页
第10页 / 共20页
亲,该文档总共20页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
本卷由 12 级计科班杨重路整理离散数学试题与答案试卷一一、填空20% (每小题2 分)1设7|),5()( |xExxBxNxxA且且(N:自然数集,E+正偶数)则BA。2A,B,C 表示三个集合,文图中阴影部分的集合表达式为。3设 P,Q 的真值为 0,R,S的真值为1,则)()(SRPRQP的真值 = 。4公式PRSRP)()(的主合取范式为。5若解释I 的论域 D 仅包含一个元素,则)()(xxPxxP在 I 下真值为。6设 A=1 ,2,3, 4 ,A 上关系图为则 R2 = 。7设 A=a ,b,c,d ,其上偏序关系R 的哈斯图为则 R= 。8图的补图为。A B C 9设 A=a ,b,c,d ,A 上二元运算如下:* a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统 的幺元是,有逆元的元素为,它们的逆元分别为。10下图所示的偏序集中,是格的为。二、选择20% (每小题2 分)1、下列是真命题的有()Aaa;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 ;C332;D223。4、设 R,S 是集合 A 上的关系,则下列说法正确的是()A若 R,S 是自反的,则SR是自反的;B若 R, S 是反自反的,则SR是反自反的;C若 R, S 是对称的,则SR是对称的;D若 R,S 是传递的,则SR是传递的。5、设 A=1 ,2,3, 4,P(A) (A 的幂集)上规定二元系如下|(|)(,|,tsAptstsR则 P(A)/ R=()AA ; B P(A) ; C1,1 ,2 , 1 ,2,3 ,1 ,2,3,4 ;D,2 ,2 ,3 ,2 , 3,4 ,A 6、设 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;B1;C2;D3。9、下图中既不是Eular 图,也不是Hamilton 图的图是()10、在一棵树中有7 片树叶, 3 个 3 度结点,其余都是4 度结点则该树有()个 4度结点。A1; B2;C3;D4 。三、证明26% 、 R 是集合 X 上的一个自反关系,求证:R 是对称和传递的,当且仅当和 在 R 中有 在 R 中。 (8 分)、 f 和 g 都是群 到的同态映射, 证明 是 的一个子群。其中 C=)()(|1xgxfGxx且(8 分) 、 G= (|V| = v ,|E|=e ) 是每一个面至少由k(k3)条边围成的连通平面图,则2)2(kvke , 由此证明彼得森图(Peterson)图是非平面图。 (11 分)四、逻辑推演16% 用 CP 规则证明下题(每小题8 分)1、FAFEDDCBA,2、)()()()(xxQxxPxQxPx五、计算18% 1、设集合A=a ,b,c,d上的关系R= , , , 用矩阵运算求出 R 的传递闭包t (R)。(9 分)2、如下图所示的赋权图表示某七个城市721,vvv及预先算出它们之间的一些直接通信线路造价, 试给出一个设计方案,使得各城市之间能够通信而且总造价最小。(分)试卷二试题与答案一、填空20% (每小题 2 分)1、 P:你努力, Q:你失败。“除非你努力,否则你将失败”的翻译为; “虽然你努力了,但还是失败了”的翻译为。2、论域 D=1 ,2,指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式),(xyyPx真值为。2、 设 S=a1 ,a2 ,, , a8,Bi是 S 的子集,则由B31所表达的子集是。3、 设 A=2 , 3, 4, 5, 6 上的二元关系|,是质数xyxyxR,则R= (列举法)。R 的关系矩阵MR= 。5 、 设A=1, 2 , 3 , 则A上 既 不 是 对 称 的 又 不 是 反 对 称 的 关 系R= ; A上 既 是 对 称 的 又 是 反 对 称 的 关 系R= 。6、设代数系统 ,其中 A=a ,b,c, 则 幺 元 是; 是 否 有 幂 等性;是否有对称性。7、4 阶群必是群或群。8、下面偏序格是分配格的是。9、n 个结点的无向完全图Kn的边数为,欧拉图的充要条件是。10、公式RQPQPP)()(的根树表示为。* a b c a b c a b c b b c c c b 二、选择20% (每小题 2 分)1、在下述公式中是重言式为()A)()(QPQP;B)()()(PQQPQP;CQQP)(;D)(QPP。2、命题公式)()(PQQP中极小项的个数为() ,成真赋值的个数为() 。A0;B1;C2;D3 。3、设2, 1,1 ,S,则S2有()个元素。A3;B6;C7;D8 。4、 设3,2, 1S,定义SS上的等价关系,|,cbdaSSdcSSbadcbaR则由R 产 生的SS上一个划分共有()个分块。A4;B5;C6;D9 。5、设3,2, 1S,S 上关系 R 的关系图为则 R 具有()性质。A自反性、对称性、传递性;B反自反性、反对称性;C反自反性、反对称性、传递性;D自反性。6、设,为普通加法和乘法,则(),S是域。A,3|QbabaxxSB,2|ZbanxxSC,12|ZnnxxSD0|xZxxS= N 。7、下面偏序集()能构成格。8、在如下的有向图中,从V1到 V4长度为 3 的道路有()条。A1;B2;C3;D4 。9、在如下各图中()欧拉图。10、设 R 是实数集合,“”为普通乘法,则代数系统 是() 。A群;B独异点;C半群。三、证明46% 1、 设 R 是 A 上一个二元关系,),(),(|,RbcRcaAcAbabaS且有对于某一个试 证明若 R 是 A 上一个等价关系,则S也是 A 上的一个等价关系。 (9 分)2、 用逻辑推理证明:所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。(11 分)3、 若BAf :是从A 到B 的函数,定义一个函数ABg2:对任意Bb有)()( |)(bxfAxxbg, 证明:若 f 是 A 到 B 的满射,则 g 是从 B 到A2的单射。(10 分)4、 若无向图 G 中只有两个奇数度结点,则这两个结点一定连通。(8 分)5、 设 G 是具有n 个结点的无向简单图,其边数2)2)(1(21nnm ,则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 构造一棵最优二叉树。 (7 分)试卷三试题与答案一、填空 20% (每空 2 分)1、 设 f,g 是自然数集N 上的函数xxgxxfNx2)(,1)(,,则)(xgf。2、 设 A=a ,b,c ,A 上二元关系R= , , , 则 s(R)= 。3、 A=1 ,2,3,4, 5,6, A 上二元关系|,是素数yxyxT,则用列举法T= ;T 的关系图为;T 具有性质。4、 集合2,2,A的幂集A2= 。5、 P,Q 真值为 0 ;R,S真值为 1。则)()()(SRQPSRPwff的真值为。6、RRQPwff)(的主合取范式为。7、 设 P(x) :x 是素数,E(x): x 是偶数, O(x):x 是奇数N (x,y):x 可以整数y。则谓词),()()(xyNyOyxPxwff的自然语言是。8、 谓词),(),(),(uyxuQzyPzxPzyxwff的前束范式为。二、选择 20% (每小题2 分)1、 下述命题公式中,是重言式的为() 。A、)()(qpqp;B、)()()(pqqpqp;C、qqp)(;D、qpp)(。2、rqpwff)(的主析取范式中含极小项的个数为() 。A 、2;B、 3;C、5;D、0;E、 8 。3、 给定推理)()(xGxFxP)()(yGyFUS)(xxFP)(yFES)( yGT I )(xxGUG)()()(xxGxGxFx推理过程中错在() 。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,在条件31SXSX且下 X 与()集合相等。A、 X=S2或 S5 ;B、X=S4或 S5;C、X=S1,S2或 S4;D、X 与 S1,, , S5中任何集合都不等。5、 设R和S是P上的关系,P是所有人的集合,,|,的父亲是yxPyxyxR,,|,的母亲是yxPyxyxS则RS1表示关系() 。A、,|,的丈夫是yxPyxyx;B、,|,的孙子或孙女是yxPyxyx;C、;D、,|,的祖父或祖母是yxPyxyx。6、 下面函数()是单射而非满射。A、12)(,:2xxxfRRf;B、xxfRZfln)(,:;C、的最大整数表示不大于 xxxxfZRf,)(,:;D、12)(,:xxfRRf。其中 R 为实数集, Z 为整数集, R+,Z+分别表示正实数与正整数集。7、 设 S=1, 2,3 ,R 为 S上的关系,其关系图为则 R 具有()的性质。A、 自反、对称、传递;B、什么性质也没有;C、反自反、反对称、传递;D、自反、对称、反对称、传递。8、 设2, 1,1 ,S,则有()S。A、1,2 ;B、1,2 ;C、1 ;D、2 。9、 设 A=1 ,2 ,3 ,则 A 上有()个二元关系。A、23; B、32; C、322; D、232。10、全体小项合取式为() 。A、可满足式;B、矛盾式;C、永真式;D、A,B,C 都有可能。三、用 CP 规则证明16% (每小题8 分)1、FAFEDDCBA,2、)()()()(xxQxxPxQxPx四、 (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 分)设函数STfTSg:,证明STf :有一左逆函数当且仅当f 是入射函数。试卷四试题与答案一、填空 10% (每小题2 分)1、 若 P,Q,为二命题,QP真值为 0 当且仅当。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号