首页 华科离散数学试题与答案试卷

华科离散数学试题与答案试卷

举报
开通vip

华科离散数学试题与答案试卷华科离散数学试题与答案试卷 离散数学试题与答案试卷一 一、填空 20% (每小题2分) ,+A,{x|(x,N)且(x,5)},B,{x|x,E且x,7}1(设 (N:自然数集,E 正偶 A,B,数) 则 。 2(A,B,C表示三个集合,文图中阴影部分的集合表达式为 。 A B C 3(设P,Q 的真值为0,R,S的真值为1,则 ,(P,(Q,(R,,P))),(R,,S)的真值= 。 (P,R),(S,R),,P4(公式的主合取范式为 。 ,xP(x),,xP(x)5(若解释I的论域D仅包含一...

华科离散数学试题与答案试卷
华科离散数学 试题 中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 试卷 离散数学试题与答案试卷一 一、填空 20% (每小题2分) ,+A,{x|(x,N)且(x,5)},B,{x|x,E且x,7}1(设 (N:自然数集,E 正偶 A,B,数) 则 。 2(A,B,C 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示三个集合,文图中阴影部分的集合表达式为 。 A B C 3(设P,Q 的真值为0,R,S的真值为1,则 ,(P,(Q,(R,,P))),(R,,S)的真值= 。 (P,R),(S,R),,P4(公式的主合取范式为 。 ,xP(x),,xP(x)5(若解释I的论域D仅包含一个元素,则 在I下真值为 。 6(设A={1,2,3,4},A上关系图为 2则 R = 。 7(设A={a,b,c,d},其上偏序关系R的哈斯图为 则 R= 。 8(图的补图为 。 9(设A={a,b,c,d} ,A上二元运算如下: * a b c d a a b c d b b c d a c c d a b d d a b c 那么代数系统的幺元是 ,有逆元的元素为 ,它们的逆元分别为 。 10(下图所示的偏序集中,是格的为 。 二、选择 20% (每小题 2分) 1、下列是真命题的有( ) {a},{{a}}{{,}},{,,{,}}A( ; B(; ,,{{,},,}{,},{{,}}C( ; D( 。 2、下列集合中相等的有( ) ,,,, A({4,3};B({,3,4};C({4,,3,3};D( {3,4}。 3、设A={1,2,3},则A上的二元关系有( )个。 2,23,33 2 32 A( 2;B( 3;C( ; D( 。 4、设R,S是集合A上的关系,则下列说法正确的是( ) R,S A(若R,S 是自反的, 则是自反的; R,S B(若R,S 是反自反的, 则是反自反的; R,S C(若R,S 是对称的, 则是对称的; R,S D(若R,S 是传递的, 则是传递的。 5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下 R,{,s,t,|s,t,p(A),(|s|,|t|}则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 : IE , f (x) = 2x ; B(f : NNN, f (n) = ; ,,C(f : RI , f (x) = [x] ; D(f :IN, f (x) = | x | 。 (注:I—整数集,E—偶数集, N—自然数集,R—实数集) 8、图 中 从v到v长度为3 的通路有( )条。 13 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% ,、R是集合X上的一个自反关系,求证:R是对称和传递的,当且仅当 < a, b> 和在R中有<.b , c>在R中。(8分) ,、f和g都是群到< G*>的同态映射,证明的一个子12, 1 {x|x,G且f(x),g(x)}1群。其中C= (8分) ,,、G= (|V| = v,|E|=e ) 是每一个面至少由k(k3)条边围成的连通平面 k(v,2)e,k,2图,则, 由此证明彼得森图(Peterson)图是非平面图。(11分) 四、逻辑推演 16% 用CP规则证明下题(每小题 8分) A,B,C,D,D,E,F,A,F1、 ,x(P(x),Q(x)),,xP(x),,xQ(x)2、 五、计算 18% 1、设集合A={a,b,c,d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。 (9分) v,v,?,v1272、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价,试给出一个设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ,使得各城市之间能够通信而且总造价最小。 (,分) 试卷一答案: 一、填空 20% (每小题2分) (B,C),A(,P,S,R),(,P,,S,R)1、{0,1,2,3,4,6}; 2、;3、1; 4、; :5、1;6、{<1,1>, <1,3>, <2,2>, <2,4> };7、{,,,,} I ;8、 A 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 C A D C A D B A 答案 B、C 三、证明 26% 1、 证: ,a,b,c,X, , R,“” 若由R对称性知 , , R,由R传递性得 , R , R , Ra,b,X,“” 若,有 任意 ,因 , R , R? , R若 所以R是对称的。 , R , R , R ,,b,c,,R? , R若, 则 即R是传递的。 ,a,b,Cf(a),g(a),f(b),g(b)2、 证,有 ,又 ,1,1,1,1,1,1,1,1f(b),f(b),g(b),g(b)?f(b),f(b),g(b),g(b) ,1,1,1,1b),f(a)*f(b),g(a)*g(b),g(ab)?f(a?? ,1?ab,C?? < C , ?> 是 < G , ?>的子群。 1 3、 证: r2e2e,d(F),rkr,,iv,e,r,2k,1i?设G有r个面,则,即 。而 故 2ek(v,2)2,v,e,r,v,e,e,kk,2即得 。(8分) k(v,2)e,k,5,e,15,v,10k,2?彼得森图为,这样不成立, 所以彼得森图非平面图。(3分) 逻辑推演 16% 二、 1、 证明: A? P(附加前提) A,B? T?I A,B,C,D? P C,D? T??I D? T?I D,E? T?I D,E,F? P F? T??I A,F? CP 2、证明 ,xP(x)? P(附加前提) P(c)? US? ,x(P(x),Q(x))? P P(c),Q(c)? US? Q(c)? T??I ,xQ(x)? UG? ,xP(x),,xQ(x)? CP 三、 计算 18% 1、 解: 10100100,,,,,,,,01011010,,,,,,,MMM,M2RRR,,R,,00000001,,,,,,,,00000000,,,, , 0101,,,,1010,,,,MM,M32R,,RR0000,,,,0000,,, 1010,,,,0101,,,,MM,M43R,,RR0000,,,,0000,, 1111,,,,1111,,,,,,,MMMMM234t(R)R,,RRR0001,,,,0000,, ? t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > } 2、 解: 用库斯克(Kruskal)算法求产生的最优树。算法略。结果如图: 树权C(T)=23+1+4+9+3+17=57即为总造价。 试卷二试题与答案 一、填空 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 ,x,yP(y,x)则公式真值为 。 、 设S={a2,a,„,a},B是S的子集,则由B所表达的子集是 1 2 8i31 。 R,{,x,y,|x,y,x是质数}3、 设A={2,3,4,5,6}上的二元关系,则R= (列举法)。 R的关系矩阵M= R 。 5、设A={1,2,3},则A上既不是对称的又不是反对称的关系 R= ;A上既是对称的又是反对称的关系 R= 。 6、设代数系统,其中A={a,b,c}, * a b c a a b c b b b c 则幺元是 ;是否有幂等 性 ;是否有对称性 。 c c c b 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n个结点的无向完全图K的边数为 ,欧拉图的充要条件是 n 。 (P,(,P,Q)),((,P,Q),,R10、公式的根树表示为 。 二、选择 20% (每小题2分) 1、在下述公式中是重言式为( ) (P,Q),(P,Q)(P,Q),((P,Q),(Q,P))A(;B(; ,(P,Q),QP,(P,Q)C(; D(。 (,P,Q),(,Q,P)2、命题公式 中极小项的个数为( ),成真赋值的个数 为( )。 A(0; B(1; C(2; D(3 。 SS,{,,{1},{1,2}}23、设,则 有( )个元素。 A(3; B(6; C(7; D(8 。 S,{ 1, 2, 3 }S,S4、 设,定义上的等价关系 R,{,,a,b,,,c,d, | ,a,b,,S,S,,c,d,,S,S,a,d,b,c}则由 R产 生 S,S的上一个划分共有( )个分块。 A(4; B(5; C(6; D(9 。 S,{ 1, 2, 3 }5、设,S上关系R的关系图为 则R具有( )性质。 A(自反性、对称性、传递性; B(反自反性、反对称性; C(反自反性、反对称性、传递性; D(自反性 。 ,,,,S,,,,,、设 为普通加法和乘法,则( )是域。 6 S,{x|x,a,b3,a,b,Q}S,{x|x,2n,a,b,Z}A( B( S,{x|x,2n,1,n,Z}S,{x|x,Z,x,0} D(= N 。 C( 7、下面偏序集( )能构成格。 8、在如下的有向图中,从V到V长度为3 的道路有( )条。 14 A(1; B(2; C(3; D(4 。 9、在如下各图中( )欧拉图。 10、 ,设R是实数集合,“”为普通乘法,则代数系统 是( )。 A(群; B(独异点; C(半群 。 三、证明 46% 1、 设R是A上一个二元关系, S,{,a,b,|(a,b,A),(对于某一个c,A,有,a,c,,R且,c,b,,R)}试证明若R是A上一个等价关系,则S也是A上的一个等价关系。(9分) 2、 用逻辑推理证明: 所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。(11分) Ag:B,2f:A,Bb,B3、 若是从A到B的函数,定义一个函数对任意有 Ag(b),{x|(x,A),(f(x),b)}2,证明:若f是A到B的满射,则g是从B到 的单射。(10分) 4、 若无向图G中只有两个奇数度结点,则这两个结点一定连通。(8分) 1m,(n,1)(n,2),225、 设G是具有n个结点的无向简单图,其边数,则G是 Hamilton图(8分) 四、计算 14% 1、 设是一个群,这里+是模6加法,Z={[0 ],[1],[2],[3],[4],[5]},6666 试求出的所有子群及其相应左陪集。(7分) 66 2、 权数1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。(7分) 试卷二答案: 一、 填空 20%(每小题2分) B,B,{a,a,a,a,a},P,QP,Q3100011111456781、;2、T 3、4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5, 11111,,,,11111,, ,,00011,, 11111,, ,,00000,,3>,<5,4>,<5,5>,<5,6>}; 5、R={<1,2>,<1,3>,<2,1>};R={<1,1>,<2,2>,<3,3>} 6、a ;否;有 7、Klein四元群;循环群 8、 B 9、 1n(n,1)2;图中无奇度结点且连通 10 、 二、 选择 20%(每小题 2分) 题目 1 2 3 4 5 6 7 8 9 10 答案 B、D D;D D B D A B B B B、C 三、 证明 46% 1、(9分) (1) S自反的 ?(,a,a,,R),(,a,a,,R)?,a,a,,S,a,A,由R自反,, (2) S对称的 ,a,b,A ,a,b,,S,(,a,c,,R),(,c,b,,R)?S定义 ,(,a,c,,R),(,c,b,,R)?R对称 ,,b,a,,S?R传递 (3) S传递的 ,a,b,c,A ,a,b,,S,,b,c,,S ,(,a,d,,R),(,d,b,,R),(,b,e,,R),(,e,c,,R),(,a,b,,R),(,b,c,,R)?R传递 ,,a,c,,S?S定义 由(1)、(2)、(3)得;S是等价关系。 2、11分 证明:设P(x):x 是个舞蹈者; Q(x) :x很有风度; S(x):x是个学生; a:王华 上述句子符号化为: ,x(P(x),Q(x))S(a),P(a),x(S(x),Q(x))前提:、 结论: „„3分 S(a),P(a)? P ,x(P(x),Q(x))? P P(a),Q(a)? US? P(a)? T?I Q(a).? T??I S(a)? T?I S(a),Q(a)? T??I ,x(S(x),Q(x)? EG? „„11分 ,、,0分 ,b,b,B,(b,b)?f满射?,a,a,A121212证明 : 使f(a),b,f(a),b,且f(a),f(a),由于f是函数,?a,a11221212 又g(b),{x|(x,A),(f(x),b)},g(b),{x|(x,A),(f(x),b)}1122?a,g(b),a,g(b)但a,g(b),a,g(b)?g(b),g(b)1122122112 由b,b任意性知,g为单射12。 4、8分 证明:设G中两奇数度结点分别为u 和v,若 u,v不连通,则G至少有两个连 通分支G、G,使得u和v分别属于G和G,于是G和G中各含有1个奇数度结12 1212 点,这与图论基本定理矛盾,因而u,v一定连通。 5、8分 证明: 证G中任何两结点之和不小于n。 V,{u,v}d(u),d(v),n,11反证法:若存在两结点u,v 不相邻且,令,则G-V1 1'm,(n,1)(n,2),2,(n,1)2是具有n-2个结点的简单图,它的边数,可得1'm,(n,2)(n,3),12,这与G=G-V为n-2个结点为简单图的题设矛盾,因而G11 中任何两个相邻的结点度数和不少于n。 所以G为Hamilton图. 四、 计算 14% 1、 7分 解:子群有<{[0]},+>;<{[0],[3]},+>;<{[0],[2],[4]},+>;<{Z},+> 66666{[0]}的左陪集:{[0]},{[1]};{[2]},{[3]};{[4]},{[5]} {[0],[3]}的左陪集:{[0],[3]};{[1],[4]};{[2],[5]} {[0],[2],[4]}的左陪集:{[0],[2],[4]};{[1],[3],[5]} Z的左陪集:Z。 66 2、 7分 试卷三试题与答案 一、 填空 20% (每空 2分) ,x,N,f(x),x,1,g(x),2x1、 设 f,g是自然数集N上的函数, f,g(x),则 。 2、 设A={a,b,c},A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} , 则s(R)= 。 T,{,x,y,|x,y是素数}3、 A={1,2,3,4,5,6},A上二元关系,则用列举 法 T= ; T的关系图为 ; T具有 性质。 A,{{,,2},{2}}4、 集合的幂集 A2= 。 wff(P,(R,S)),((P,Q),(R,S))5、 P,Q真值为0 ;R,S真值为1。则的 真值为 。 wff,((P,Q),R),R6、 的主合取范式 为 。 7、 设 P(x):x是素数, E(x):x 是偶数,O(x):x是奇数 N (x,y):x可以整数y。 wff,x(P(x),,y(O(y),N(y,x)))则谓词的自然语言是 。 wff,x,y(,z(P(x,z),P(y,z)),,uQ(x,y,u))8、 谓词的前束范式为 。 二、 选择 20% (每小题 2分) 1、 下述命题公式中,是重言式的为( )。 (p,q),(p,q)(p,q),((p,q)),(q,p))A、; B、; ,(p,q),q(p,,p),qC、; D、。 wff,(p,q),r2、 的主析取范式中含极小项的个数为( )。 A 、2; B、 3; C、5; D、0; E、 8 。 3、 给定推理 ,x(F(x),G(x))? P F(y),G(y)? US? ,xF(x)? P F(y)? ES? G(y)? T??I ,xG(x)? UG? ?,x(F(x),G(x)),,xG(x) 推理过程中错在( )。 A、?->?; B、?->?; C、?->?; D、?->?; E、?->? 4、 设S={1,2,„,8,9},S={2,4,6,8},S={1,3,5,7,9},S={3,4,5}, 1234 X,S且X,S13S={3,5},在条件下X与( )集合相等。 5 A、 X=S或S; B、X=S或S; 25 45 C、X=S,S或S; D、X与S,„,S中任何集合都不等。 12415 5、 设R和S是P上的关系,P是所有人的集合,R,{,x,y,|x,y,P,x是y的父亲}S,{,x,y,|x,y,P,x是y的母亲}, ,1S,R则表示关系 ( )。 {,x,y,|x,y,P,x是y的丈夫}A、; {,x,y,|x,y,P,x是y的孙子或孙女}B、; {,x,y,|x,y,P,x是y的祖父或祖母},C、 ; D、。 6、 下面函数( )是单射而非满射。 2f:R,R,f(x),,x,2x,1A、; ,f:Z,R,f(x),lnxB、; f:R,Z,f(x),[x],[x]表示不大于x的最大整数C、; f:R,R,f(x),2x,1D、。 ++其中R为实数集,Z为整数集,R,Z分别表示正实数与正整数集。 7、 设S={1,2,3},R为S上的关系,其关系图为 则R具有( )的性质。 A、 自反、对称、传递; B、什么性质也没有; C、反自反、反对称、传递; D、自反、对称、反对称、传递。 S,{,,{1},{1,2}},S8、 设,则有( )。 A、{{1,2}} ;B、{1,2 } ; C、{1} ; D、{2} 。 9、 设A={1 ,2 ,3 },则A上有( )个二元关系。 32233222 ; C、; D、。 A、2 ; B、3 10、全体小项合取式为( )。 A、可满足式; B、矛盾式; C、永真式; D、A,B,C 都有可能。 三、 用CP规则证明 16% (每小题 8分) A,B,C,D,D,E,F,A,F1、 ,x(P(x),Q(x)),,xP(x),,xQ(x)2、 四、(14%) 集合X={<1,2>, <3,4>, <5,6>,„ },R={<,>|x+yx+y} 。 112212 = 211、 证明R是X上的等价关系。 (10分) 2、 求出X关于R的商集。(4分) 五、(10%) 设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R的关系矩阵和关系图。(4分) 2、用矩阵运算求出R的传递闭包。(6分) 六、(20%) f,g1、(10分)设f和g是函数,证明也是函数。 g:S,Tf:T,Sf:T,S2、(10分)设函数,证明 有一左逆函数当且仅当f是入射函数。 答案: 五、 填空 20%(每空2分) {,a ,a,,,a ,b,,,a ,c,,,c ,c,,,b ,a,,,c ,a,}1、2(x+1);2、;3、 {,2,1,,,3,1,,,5,1,,,4,2,,,6,2,,,6,3,,; 4、 {,,{{,,2}},{{2}},{{,,2},{2}}}反对称性、反自反性;4、;5、1; (P,,Q,R),(,P,Q,R),(P,Q,R)6、;7、任意x,如果x是素数则 ,x,y,z,u(,P(x,z),,P(y,z),Q(x,y,u))存在一个y,y是奇数且y整除x ;8、。 六、 选择 20%(每小题 2分) 1 2 3 4 5 6 7 8 9 10 题目 C C C C A B D A D C 答案 七、 证明 16%(每小题8分) 1、 A? P(附加前提) A,B? T?I A,B,C,D? P C,D? T??I D? T?I D,E? T?I D,E,F? P F? T??I A,F? CP 2、 ?,xP(x),,xQ(x),,(,x)P(x),,xQ(x)本题可证,x(P(x),Q(x)),,(,xP(x),,xQ(x) ,(,xP(x))? P(附加前提) ,x(,P(x))? T?E ,P(a)? ES? ,x(P(x),Q(x))? P P(a),Q(a)? US? Q(a)? T??I ,xQ(x)? EG? ,(,xP(x),,xQ(x)? CP 八、 14% 1) 证明: ( ,,x,y,,X,由于x,y,x,y1、 自反性: ?,,x,y,,,x,y,,,R?R自反 ,,x,y,,X,,,x,y,,X11222、 对称性: 当,,x,y,,,x,y,,,R时即x,y,x,y也即x,y,x,y112212212112 故,,x,y,,,x,y,,,R?R有对称性2211 ,,x,y,,X,,,x,y,,X,,x,y,,X1122333、 传递性: 当,,x,y,,,x,y,,,R且,,x,y,,,x,y,,,R时11222233 ,,,(1)xyxy,1221即,x,y,x,y(2)2332, (1),(2)x,y,x,y,x,y,x,y12232132 x,y,x,y1331即 故,,x,y,,,x,y,,,R?R有传递性1133 由(1)(2)(3)知:R是X上的先等价关系。 {[,1,2,]}R2、X/R= 九、 10% 0100,,,,1010,,,MR,,0001,,,,0000,,1、; 关系图 1010,,,,0101,,,,MM,M2RR,,R0000,,,,0000,,2、 0101,,,,1010,,,,MM,M32R,,RR0000,,,,0000,, 1010,,,,0101,,M,M,M,,M432RRRR,,0000,,,,M,M,M,M,?00005364RRRR,, 1111,,,,1111,,,,,,,MMMMM234t(R)R,,RRR0001,,,,0000,, ? t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }。 六、 20% f,g,{,x,y,|x,domf,x,domg,y,f(x),y,g(x)} ,{,x,y,|x,domf,domg,y,f(x),g(x)}1、(1) 令h,f,g ?domf,g,domh,{x|x,domf,domg,f(x),g(x)} h,{,x,y,|x,domf,domg,y,h(x),f(x),g(x)}(2) 对x,domh若有y,y使得12 y,h(x),f(x),g(x),y,h(x),f(x),g(x)12 由于f(或g)是函数,有y,y即,x,domh有唯一y使得y,h(x)12 ?f,g也是函数。 2、证明: ","若f有一左逆g,则对,t,Tg,f(t),t 故g,f是入射,所以f是入射。 ","f是入射,f:T,S定义如下: ,s,f(T),由f入射,,|t,T,使f(t),s此时令g(s),t,若s,f(T)令g(s),c,T则对,s,S,g(s)只有一个值t或c且若f(t),s则g,f(t),g(s),t,故g是f的左逆元 即若f入射,必能构造函数g,使g为f左逆函数。
本文档为【华科离散数学试题与答案试卷】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
最新资料
资料动态
专题动态
is_792768
暂无简介~
格式:doc
大小:148KB
软件:Word
页数:22
分类:生活休闲
上传时间:2017-10-14
浏览量:41