当前位置:首页 >> 数学 >>

离散数学试卷及答案

发到哪?给个邮箱啊~~~~~~~一、填空 20% (每小题 2 分) 1.设 (N:自然数集,E???+ 正偶数) 则 2.A,B,C 表示三个集合,文图中阴影部分的集合表达式为 。 。 3.设 P,Q 的真值为 0,R,S 的真值为 1,则 的真值= 。 4.公式 的主合取范式为 5.若解释 I 的论域 D 仅包含一个元素,则 6.设 A={1,2,3,4},A 上关系图为 。 在 I 下真值为 。 则 R2 = 7.设 A={a,b,c,d},其上偏序关系 R 的哈斯图为 。 则 R= 8.图 的补图为 9.设 A={a,b,c,d} ,A 上二元运算如下: *a b c d a b c da b c d b c d a c d a b d a b c 那么代数系统<A,*>的幺元是 它们的逆元分别为 10.下图所示的偏序集中,是格的为 。 。 ,有逆元的元素为 。 。 , 二、选择 20% (每小题 2 分) 1、下列是真命题的有( ) A. ; B. ; C. ; D. 。 2、下列集合中相等的有( ) A.{4,3} ;B.{ ,3,4};C.{4, ,3,3};D. {3,4}。 3、设 A={1,2,3},则 A 上的二元关系有( )个。 A. 23 ; B. 32 ; C. ; D. 。 4、设 R,S 是集合 A 上的关系,则下列说法正确的是( ) A.若 R,S 是自反的, 则 是自反的; B.若 R,S 是反自反的, 则 是反自反的; C.若 R,S 是对称的, 则 是对称的; D.若 R,S 是传递的, 则 是传递的。 5、设 A={1,2,3,4},P(A)(A 的幂集)上规定二元系如下 则 P(A)/ R=( ) A.A ;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、下列函数是双射的为( ) A.f : I E , f (x) = 2x ; B.f : N N N, f (n) = <n , n+1> ; C.f : R I , f (x) = [x] ; D.f :I N, 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 度结点。 A.1; B.2; C.3; D.4 。 三、证明 26% 1、 R 是集合 X 上的一个自反关系,求证:R 是对称和传递的,当且仅当 < a, b> 和<a , c>在 R 中有<.b , c>在 R 中。(8 分) 2、 f 和 g 都是群<G1 ,★>到< G2, *>的同态映射,证明<C , ★>是<G1, ★>的 一个子群。其中 C= (8 分) 3、 G=<V, E> (|V| = v,|E|=e ) 是每一个面至少由 k(k 3)条边围成的连通 平面图,则 , 由此证明彼得森图(Peterson)图是非平面图。(11 分) 四、逻辑推演 16% 用 CP 规则证明下题(每小题 8 分) 1、 2、 五、计算 18% 1、设集合 A={a,b,c,d}上的关系 R={<a , b > ,< b , a > ,< b, c > , < c , d >} 用矩阵运算求出 R 的传递闭包 t (R)。 (9 分) 2、 如下图所示的赋权图表示某七个城市 及预先算出它们之间的一些直接通信线 路造价, 试给出一个设计方案, 使得各城市之间能够通信而且总造价最小。 (9 分) 试卷一答案: 一、填空 20% (每小题 2 分) 1、{0,1,2,3,4,6}; 2、 ;3、1; 4、 ; 5、1;6、{<1,1>, <1,3>, <2,2>, <2,4> };7、{<a.b>,<a,c>,<a,d>,<b,d>,<c,d>} IA ;8、 9、a ;a , b , c ,d ;a , d , c , d ;10、c; 二、选择 20% (每小题 2 分) 题目 1 2 3 4 5 6 7 8 9 10 答案 C D B、C C A D C A D B A 三、证明 26% 1、 证: “” 若 由 R 对称性知 ,由 R 传递性得 “” 若 , 有 任意 ,因 若 所以 R 是对称的。 若 , 则 即 R 是传递的。 2、 证 ,有 ,又 ★ ★ ★ < C , ★> 是 < G1 , ★>的子群。 3、 证: ①设 G 有 r 个面,则 ,即 。而 故 即得 。(8 分) ②彼得森图为 ,这样 不成立, 所以彼得森图非平面图。(3 分) 二、 逻辑推演 16% 1、 证明: ① P(附加前提) ② T①I ③ P ④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P ⑧ T⑥⑦I ⑨ CP 2、证明 ① P(附加前提) ② US① ③ P ④ US③ ⑤ T②④I ⑥ UG⑤ ⑦ CP 三、 计算 18% 1、 解: , , t (R)={<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , <b,d>,<c,d>} 2、 解: 用库斯克(Kruskal)算法求产生的最优树。算法略。结果如图: 树权 C(T)=23+1+4+9+3+17=57 即为总造价。