《离散数学习题集(十五套)》由会员分享,可在线阅读,更多相关《离散数学习题集(十五套)(80页珍藏版)》请在金锄头文库上搜索。
1、离散数学试题与答案试卷一一、填空一、填空 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图的补图为 。9设 A=a,b,c
2、,d ,A 上二元运算如下:A BC*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是 ,有逆元的元素为 ,它们的逆元分别为 。10下图所示的偏序集中,是格的为 。二、选择二、选择 20% (每小题(每小题 2 分)分)1、下列是真命题的有( )A aa ; 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 332; D 223。4、设 R,S 是集合 A 上的关系,则下列说法正确的是( )A若 R,S 是自
3、反的, 则SRo是自反的;B若 R,S 是反自反的, 则SRo是反自反的;C若 R,S 是对称的, 则SRo是对称的;D若 R,S 是传递的, 则SRo是传递的。5、设 A=1,2,3,4,P(A) (A 的幂集)上规定二元系如下|(|)(,|,tsAptstsR则 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 : IE , f (x) = 2x ; Bf : NNN, f (n) = ;Cf : RI , f (x)
4、 = 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 片树叶,3 个 3 度结点,其余都是 4 度结点则该树有( )个 4度结点。A1;B2;C3;D4 。三、证明三、证明 26%、R 是集合 X 上的一个自反关系,求证:R 是对称和传递的,当且仅当和在 R 中有在 R 中。 (8 分)、f 和 g 都是群到的同态映射,证明是的一个子群。其中 C=)(
5、)(|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,vvvL及预先算出它们之间的一些直接通信线路造价,试给出一个设计
6、方案,使得各城市之间能够通信而且总造价最小。 (分)试卷一答案: 一、填空一、填空 20% (每小题(每小题 2 分)分)1、0,1,2,3,4,6; 2、ACB)(;3、1; 4、)()(RSPRSP; 5、1;6、, , , ;7、, U IA ;8、9、a ;a , b , c ,d ;a , d , c , d ;10、c; 二、选择二、选择 20% (每小题(每小题 2 分)分)题目12345678910答案C DB、CCADCADBA三、证明三、证明 26%1、 证:“” Xcba,若R c, ab, aa, bc, bb, ac, ac, ba, ab, aa, bb, acb,
7、ab,c, a 是 的子群。3、 证:设 G 有 r 个面,则rkFderii1)(2 ,即 ker2 。而 2rev故keevrev22 即得 2)2( kvke 。 (8 分)彼得森图为10,15, 5vek,这样2)2( kvke 不成立,所以彼得森图非平面图。 (3 分) 二、二、 逻辑推演逻辑推演 16%1、 证明:AP(附加前提)BATIDCBAPDC TIDTIED TIFEDPFTIFA CP2、证明 )(xxPP(附加前提))(cPUS)()(xQxPxP)()(cQcPUS)(cQTI)(xxQUG)()(xxQxxPCP三、三、 计算计算 18%1、 解:00001000
8、01010010RM, 00000000101001012RRRMMMo000000000101101023RRRMMMo,000000001010010134RRRMMMo0000100011111111432)(RRRRRtMMMMMt (R)= , , , , , , , , 2、 解: 用库斯克(Kruskal)算法求产生的最优树。算法略。结果如图:树权 C(T)=23+1+4+9+3+17=57 即为总造价。试卷二试题与答案试卷二试题与答案一、填空一、填空 20% (每小题(每小题 2 分)分)1、 P:你努力,Q:你失败。 “除非你努力,否则你将失败”的翻译为;“虽然你努力了,但还
9、是失败了”的翻译为。2、论域 D=1,2,指定谓词 PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式),(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、下面偏序格是分配格
10、的是 。9、n 个结点的无向完全图 Kn的边数为 ,欧拉图的充要条件是。10、公式RQPQPP)()(的根树表示为。二、选择二、选择 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 , 1 S,定义SS 上的等价关系, | ,cbdaSSdcSSbadcbaR则由 R 产 生的
11、SS 上一个划分共有( )个分块。*a b cabca b cb b cc c bA4; B5; C6; D9 。5、设 3 , 2 , 1 S,S 上关系 R 的关系图为则 R 具有( )性质。A自反性、对称性、传递性; B反自反性、反对称性;C反自反性、反对称性、传递性; D自反性 。6、设 o ,为普通加法和乘法,则( )o,S是域。A,3|QbabaxxSB,2|ZbanxxSC, 12|ZnnxxSD0|xZxxS= N 。7、下面偏序集( )能构成格。8、在如下的有向图中,从 V1到 V4长度为 3 的道路有( )条。A1; B2; C3; D4 。9、在如下各图中( )欧拉图。1
12、0、设 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 中只有两个奇数度结