《离散数学习题集(十五套)》由会员分享，可在线阅读，更多相关《离散数学习题集(十五套)（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 中只有两个奇数度结
