文档介绍：离散数学试题与答案试卷一一、填空 20% (每小题 2 分) 1 .设}7|{ )}, 5()(|{???????xExxBxNxxA且且(N :自然数集, E ? ??+正偶数) 则??BA 。 ,B,C 表示三个集合,文图中阴影部分的集合表达式为。 3 .设 P,Q 的真值为 0,R,S 的真值为 1 ,则)( ))) (((SRPRQP????????的真值=。 4 .公式 PRSRP?????)()( 的主合取范式为。 5 .若解释 I 的论域 D 仅包含一个元素,则)()(x xP x xP???在I 下真值为。 6 .设 A={1 ,2,3, 4},A 上关系图为则R 2=。 7 .设 A={a ,b,c, d} ,其上偏序关系 R 的哈斯图为则 R=。 8 .图的补图为。 9 .设 A={a ,b,c, d},A 上二元运算如下: ABC *abcd abcd abcdbcdacdabdabc 那么代数系统<A , *> 的幺元是, 有逆元的元素为, 它们的逆元分别为。 10 .下图所示的偏序集中,是格的为。二、选择 20% (每小题 2 分) 1 、下列是真命题的有( ) A. }} {{ }{aa?;B. }}{,{ }} {{????; C.} }, {{????;D. }} {{}{???。 2 、下列集合中相等的有( ) A. {4, 3}??;B.{?,3, 4};C. {4,?,3, 3};D. {3, 4}。 3 、设 A={1 ,2, 3} ,则 A 上的二元关系有( )个。 3; 2; ?; ?。 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= () ;B. P(A) ;C. {{{1}} , {{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 、下列函数是双射的为( ) :I? E,f (x) = 2x;:N? N? N,f (n) = <n, n+1> ; :R? I,f (x) = [x] ; :I? N,f (x) =|x|。(注: I—整数集, E—偶数集, N—自然数集, R—实数集) 8 、图中从v 1到v 3 长度为 3 的通路有( )条。 ;;;。 9 、下图中既不是 Eular 图,也不是 Hamilton 图的图是( ) 10 、在一棵树中有 7 片树叶, 3个3 度结点,其余都是 4 度结点则该树有( )个 4 度结点。 ;;;。三、证明 26% 1、 R 是集合 X 上的一个自反关系,求证: R 是对称和传递的,当且仅当< a, b>和<a, c>在R 中有<.b , c>在R中。(8 分) 2、 f和g 都是群<G 1,★>到<G 2, *> 的同态映射, 证明<C ,★>是<G 1,★> 的一个子群。其中 C= )}()(|{ 1xgxfGxx??且(8分) 3、 G=<V, E> (|V| =v, |E|=e ) 是每一个面至少由 k(k? 3 )条边围成的连通平面图,则 2 )2(???k vke , 由此证明彼得森图( Peterson )图是非平面图。( 11分) 四、逻辑推演 16% 用 CP 规则证明下题(每小题 8 分) 1、FAFEDDCBA???????, 2、)()( ))()((x xQ x xP xQxPx??????五、计算 18% 1 、设集合 A={a ,b,c, d} 上的关系 R={<a ,b> ,<b,a> ,< b,c>,<c,d >} 用矩阵运算求出 R 的传递闭包 t (R) 。(9 分) 2、如下图所示的赋权图表示某七个城市 721,,,vvv?及预先算出它们之间的一些直接通信线路造价, 试给出一个设计方案, 使得各城市之间能够通信而且总造价最小。( 9分) 试卷一答案: