离散数学试题(十五套).doc
《离散数学试题(十五套).doc》由会员分享,可在线阅读,更多相关《离散数学试题(十五套).doc(78页珍藏版)》请在咨信网上搜索。
(完整版)离散数学试题(十五套) 087ynu离散数学试题与答案试卷一 一、填空 20% (每小题2分) 1.设 (N:自然数集,E+ 正偶数) 则 。 2.A,B,C表示三个集合,文图中阴影部分的集合表达式为 A B C . 3.设P,Q 的真值为0,R,S的真值为1,则 的真值= 。 4.公式的主合取范式为 。 5.若解释I的论域D仅包含一个元素,则 在I下真值为 。 6.设A={1,2,3,4},A上关系图为 则 R2 = 。 7.设A={a,b,c,d},其上偏序关系R的哈斯图为 则 R= 。 8.图的补图为 。 9.设A={a,b,c,d} ,A上二元运算如下: * a b c d a b c d a 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}}0 6、设A={,{1},{1,3},{1,2,3}}则A上包含关系“”的哈斯图为( ) 7、下列函数是双射的为( ) A.f : IE , f (x) = 2x ; B.f : NNN, f (n) = <n , n+1〉 ; C.f : RI , f (x) = [x] ; D.f :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度结点. 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(k3)条边围成的连通平面图,则, 由此证明彼得森图(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即为总造价。 试卷二试题与答案 一、填空 20% (每小题2分) 1、 P:你努力,Q:你失败。“除非你努力,否则你将失败”的翻y译为 ;“虽然你努力了,但还是失败了”的翻译为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式真值为 。 2、 设S={a1 ,a2 ,…,a8},Bi是S的子集,则由B31所表达的子集是 。 3、 设A={2,3,4,5,6}上的二元关系,则R= (列举法)。 R的关系矩阵MR= 。 5、设A={1,2,3},则A上既不是对称的又不是反对称的关系R= ;A上既是对称的又是反对称的关系R= 。 * a b c a b c a b c b b c c c b 6、设代数系统<A,*>,其中A={a,b,c}, 则幺元是 ;是否有幂等 性 ;是否有对称性 。 7、4阶群必是 群或 群. 8、下面偏序格是分配格的是 . 9、n个结点的无向完全图Kn的边数为 ,欧拉图的充要条件是 。 10、公式的根树表示为 。 二、选择 20% (每小题2分) 1、在下述公式中是重言式为( ) A.;B.; C.; D.。 2、命题公式 中极小项的个数为( ),成真赋值的个数为( ). A.0; B.1; C.2; D.3 。 3、设,则 有( )个元素. A.3; B.6; C.7; D.8 。 4、 设,定义上的等价关系 则由 R产 生的上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设,S上关系R的关系图为 则R具有( )性质. A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 . 6、设 为普通加法和乘法,则( )是域。 A. B. C. D.= N 。 7、下面偏序集( )能构成格. 8、在如下的有向图中,从V1到V4长度为3 的道路有( )条。 A.1; B.2; C.3; D.4 。 9、在如下各图中( )欧拉图。 10、设R是实数集合,“”为普通乘法,则代数系统〈R ,×〉 是( )。 A.群; B.独异点; C.半群 。 三、证明 46% 1、 设R是A上一个二元关系, 试证明若R是A上一个等价关系,则S也是A上的一个等价关系。(9分) 2、 用逻辑推理证明: 所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。(11分) 3、 若是从A到B的函数,定义一个函数对任意有,证明:若f是A到B的满射,则g是从B到 的单射.(10分) 4、 若无向图G中只有两个奇数度结点,则这两个结点一定连通。(8分) 5、 设G是具有n个结点的无向简单图,其边数,则G是Hamilton图(8分) 四、计算 14% 1、 设<Z6,+6〉是一个群,这里+6是模6加法,Z6={[0 ],[1],[2],[3],[4],[5]},试求出<Z6,+6〉的所有子群及其相应左陪集.(7分) 2、 权数1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。(7分) 试卷二答案: 一、 填空 20%(每小题2分) 1、;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,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、;图中无奇度结点且连通 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自反的 ,由R自反,, (2) S对称的 (3) S传递的 由(1)、(2)、(3)得;S是等价关系。 2、11分 证明:设P(x):x 是个舞蹈者; Q(x) :x很有风度; S(x):x是个学生; a:王华 上述句子符号化为: 前提:、 结论: ……3分 ① P ② P ③ US② ④ T①I ⑤ T③④I ⑥ T①I ⑦ T⑤⑥I ⑧ EG⑦ ……11分 3、10分 证明 : 。 4、8分 证明:设G中两奇数度结点分别为u 和v,若 u,v不连通,则G至少有两个连通分支G1、G2 ,使得u和v分别属于G1和G2,于是G1和G2中各含有1个奇数度结点,这与图论基本定理矛盾,因而u,v一定连通. 5、8分 证明: 证G中任何两结点之和不小于n。 反证法:若存在两结点u,v 不相邻且,令,则G-V1是具有n-2个结点的简单图,它的边数,可得,这与G1=G-V1为n—2个结点为简单图的题设矛盾,因而G中任何两个相邻的结点度数和不少于n。 所以G为Hamilton图。 四、 计算 14%d 1、 7分 解:子群有〈{[0]},+6〉;〈{[0],[3]},+6〉;<{[0],[2],[4]},+6〉;〈{Z6},+6> {[0]}的左陪集:{[0]},{[1]};{[2]},{[3]};{[4]},{[5]} {[0],[3]}的左陪集:{[0],[3]};{[1],[4]};{[2],[5]} {[0],[2],[4]}的左陪集:{[0],[2],[4]};{[1],[3],[5]} Z6的左陪集:Z6 。 2、 7分 试卷三试题与答案 一、 填空 20% (每空 2分) 1、 设 f,g是自然数集N上的函数, 则 。 2、 设A={a,b,c},A上二元关系R={< a, a > , 〈 a, b 〉,〈 a, c >, 〈 c, c〉} , 则s(R)= 。 3、 A={1,2,3,4,5,6},A上二元关系,则用列举法 T= ; T的关系图为 ; T具有 性质。 4、 集合的幂集= 。 5、 P,Q真值为0 ;R,S真值为1。则的真值为 。 6、 的主合取范式为 。 7、 设 P(x):x是素数, E(x):x 是偶数,O(x):x是奇数 N (x,y):x可以整数y。则谓词的自然语言是 。 8、 谓词的前束范式为 。 二、 选择 20% (每小题 2分) 1、 下述命题公式中,是重言式的为( ). A、; B、; C、; D、。 2、 的主析取范式中含极小项的个数为( )。 A 、2; B、 3; C、5; D、0; E、 8 。 3、 给定推理 ① P ② US① ③ P ④ ES③ ⑤ T②④I ⑥ UG⑤ 推理过程中错在( ). A、①—〉②; B、②-〉③; C、③—〉④; D、④->⑤; E、⑤->⑥ 4、 设S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5}, S5={3,5},在条件下X与( )集合相等. A、 X=S2或S5 ; B、X=S4或S5; C、X=S1,S2或S4; D、X与S1,…,S5中任何集合都不等。 5、 设R和S是P上的关系,P是所有人的集合,,则表示关系 ( )。 A、; B、; C、 ; D、. 6、 下面函数( )是单射而非满射。 A、; B、; C、; D、。 其中R为实数集,Z为整数集,R+,Z+分别表示正实数与正整数集. 7、 设S={1,2,3},R为S上的关系,其关系图为 则R具有( )的性质。 A、 自反、对称、传递; B、什么性质也没有; C、反自反、反对称、传递; D、自反、对称、反对称、传递. 8、 设,则有( )。 A、{{1,2}} ;B、{1,2 } ; C、{1} ; D、{2} 。 9、 设A={1 ,2 ,3 },则A上有( )个二元关系. A、23 ; B、32 ; C、; D、。 10、全体小项合取式为( ). A、可满足式; B、矛盾式; C、永真式; D、A,B,C 都有可能。 三、 用CP规则证明 16% (每小题 8分) 1、 2、 四、(14%) 集合X={〈1,2>, <3,4>, <5,6>,… },R={〈<x1,y1〉,<x2,y2〉>|x1+y2 = x2+y1} 。 1、 证明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%) 1、(10分)设f和g是函数,证明也是函数。 2、(10分)设函数,证明 有一左逆函数当且仅当f是入射函数. 答案: 五、 填空 20%(每空2分) 1、2(x+1);2、;3、; 4、 反对称性、反自反性;4、;5、1; 6、;7、任意x,如果x是素数则存在一个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、 ① P(附加前提) ② T①I ③ P ④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P ⑧ T⑥⑦I ⑨ CP 2、 ① P(附加前提) ② T①E ③ ES② ④ P ⑤ US④ ⑥ T③⑤I ⑦ EG⑥ ⑧ CP 八、 14% (1) 证明: 1、 自反性: 2、 对称性: 3、 传递性: 即 由(1)(2)(3)知:R是X上的先等价关系。 2、X/R= 九、 10% 1、; 关系图 2、 t (R)={〈a , a> , 〈a , b〉 , < a , c> , <a , d 〉 , 〈b , a > , 〈 b ,b 〉 , 〈 b , c 。 〉 , 〈 b , d 〉 , < c , d > }。 六、 20% 1、(1) (2) 。 2、证明: 。 。 试卷四试题与答案 一、 填空 10% (每小题 2分) 1、 若P,Q,为二命题,真值为0 当且仅当 . 2、 命题“对于任意给定的正实数,都存在比它大的实数”令F(x):x为实数,则命题的逻辑谓词公式为 。 3、 谓词合式公式的前束范式为 . 4、 将量词辖域中出现的 和指导变元交换为另一变元符号,公式其余的部分不变,这种方法称为换名规则。 5、 设x是谓词合式公式A的一个客体变元,A的论域为D,A(x)关于y是自由的,则 被称为存在量词消去规则,记为ES。 二、 选择 25% (每小题 2.5分) 1、 下列语句是命题的有( )。 A、 明年中秋节的晚上是晴天; B、; C、当且仅当x和y都大于0; D、我正在说谎。 2、 下列各命题中真值为真的命题有( ). A、 2+2=4当且仅当3是奇数;B、2+2=4当且仅当3不是奇数; C、2+2≠4当且仅当3是奇数; D、2+2≠4当且仅当3不是奇数; 3、 下列符号串是合式公式的有( ) A、;B、;C、;D、。 4、 下列等价式成立的有( )。 A、;B、; C、 ; D、。 5、 若和B为wff,且则( )。 A、称为B的前件; B、称B为的有效结论 C、当且仅当;D、当且仅当。 6、 A,B为二合式公式,且,则( )。 A、为重言式; B、; C、; D、; E、为重言式。 7、 “人总是要死的”谓词公式表示为( )。 (论域为全总个体域)M(x):x是人;Mortal(x):x是要死的。 A、; B、 C、;D、 8、 公式的解释I为:个体域D={2},P(x):x>3, Q(x):x=4则A的真值为( )。 A、1; B、0; C、可满足式; D、无法判定。 9、 下列等价关系正确的是( ). A、; B、; C、; D、。 10、 下列推理步骤错在( )。 ① P ② US① ③ P ④ ES③ ⑤ T②④I ⑥ EG⑤ A、②;B、④;C、⑤;D、⑥ 三、 逻辑判断30% 1、 用等值演算法和真值表法判断公式的类型。(10分) 2、 下列问题,若成立请证明,若不成立请举出反例:(10分) (1) 已知,问成立吗? (2) 已知,问成立吗? 3、 如果厂方拒绝增加工资,那么罢工就不会停止,除非罢工超过一年并且工厂撤换了厂长.问:若厂方拒绝增加工资,面罢工刚开始,罢工是否能够停止。(10分) 四、计算10% 1、 设命题A1,A2的真值为1,A3,A4真值为0,求命题 的真值。(5分) 2、 利用主析取范式,求公式的类型。(5分) 五、谓词逻辑推理 15% 符号化语句:“有些人喜欢所有的花,但是人们不喜欢杂草,那么花不是杂草”.并推证其结论。 六、证明:(10%) 设论域D={a , b , c},求证:。 答案: 十、 填空 10%(每小题2分) 1、P真值为1,Q的真值为0;2、;3、;4、约束变元;5、,y为D的某些元素. 十一、 选择 25%(每小题2.5分) 题目 1 2 3 4 5 6 7 8 9 10 答案 A,C A,D C,D A,D B,C A,B,C,D,E C A B (4) 十二、 逻辑判断 30% 1、(1)等值演算法 (2)真值表法 P Q A 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 1 所以A为重言式. 2、(1)不成立。 若取 但A与B不一定等价,可为任意不等价的公式. (2)成立. 证明: 即: 所以故 。 3、解:设P:厂方拒绝增加工资;Q:罢工停止;R罢工超壶过一年;R:撤换厂长 前提: 结论: ① P ② P ③ T①②I ④ P ⑤ T④I ⑥ T⑤E ⑦ T③⑥I 罢工不会停止是有效结论. 四、计算 10% (1) 解: (2) 它无成真赋值,所以为矛盾式. 五、谓词逻辑推理 15% 解: 证明: ⑴ P ⑵ ES⑴ ⑶ T⑵I ⑷ T⑵I ⑸ P ⑹ US⑸ ⑺ T⑶⑹I ⑻ T⑺E ⑼ US⑷ ⑽ US⑻ ⑾ T⑼⑽I ⑿ UG⑾ 十三、 证明10% 试卷五试题与答案 一、填空15%(每空3分) 1、设G为9阶无向图,每个结点度数不是5就是6,则G中至少有 个5度结点。 2、n阶完全图,Kn的点数X (Kn) = 。 3、有向图 中从v1到v2长度为2的通路有 条. 4、设[R,+,·]是代数系统,如果①[R,+]是交换群 ②[R,·]是半群 ③ 则称[R,+,·]为环。 5、设是代数系统,则满足幂等律,即对有 。 二、选择15%(每小题3分) 1、 下面四组数能构成无向简单图的度数列的有( )。 A、(2,2,2,2,2); B、(1,1,2,2,3); C、(1,1,2,2,2); D、(0,1,3,3,3)。 2、 下图中是哈密顿图的为( )。 3、 如果一个有向图D是强连通图,则D是欧拉图,这个命题的真值为( ) A、真; B、假。 4、 下列偏序集( )能构成格。 5、 设,*为普通乘法,则[S,*]是(). A、代数系统; B、半群; C、群; D、都不是. 三、证明 48% 1、(10%)在至少有2个人的人群中,至少有2 个人,他们有相同的朋友数。 2、(8%)若图G中恰有两个奇数度顶点,则这两个顶点是连通的。 3、(8%)证明在6个结点12条边的连通平面简单图中, 每个面的面数都是3。 4、(10%)证明循环群的同态像必是循环群。 5、(12%)设是布尔代数,定义运算*为, 求证[B,*]是阿贝尔群. 四、计算22% 1、在二叉树中 1) 求带权为2,3,5,7,8的最优二叉树T。(5分) 2) 求T对应的二元前缀码.(5分) 2、 下图所示带权图中最优投递路线并求出投递路线长度(邮局在D点)。 答案: 一、填空(15%)每空3 分 1、 6;2、n;3、2;4、+对·分配且·对+分配均成立;5、. 二、选择(15%)每小题3分 题目 1 2 3 4 5 答案 A,B B,D B C D 三、证明(48%) 1、(10分)证明:用n个顶点v1,…,vn表示n个人,构成顶点集V={v1,…,vn},设,无向图G=(V,E) 现证G中至少有两个结点度数相同。 事实上,(1)若G中孤立点个数大于等于2,结论成立. (2) 若G中有一个孤立点,则G中的至少有3个顶点,既不考虑孤立点。设G中每个结点度数均大于等于1,又因为G为简单图,所以每个顶点度数都小于等于n—1,由于G中n顶点其度数取值只能是1,2,…,n—1,由鸽巢原理,必然至少有两个结点度数是相同的。 2、(8分)证:设G中两个奇数度结点分别为u,v。若 u,v不连通则至少有两个连通分支G1、G2,使得u,v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点,与握手定理矛盾。因而u,v必连通。 3(8分)证:n=6,m=12 欧拉公式n-m+f=2知 f=2—n+m=2—6-12=8 由图论基本定理知:,而,所以必有,即每个面用3条边围成。 4(10分) 证:设循环群[A,·]的生成元为a,同态映射为f,同态像为[f(A),*],于是都有 对n=1有 n=2, 有 若n=k—1时 有 对n=k时, 这表明,f(A)中每一个元素均可表示为,所以[f(A),*]为f(a) 生成的循环群。 5、证: (1) 交换律:有 (2) 结合律:有 而: (3) 幺:有 (4) 逆: 综上所述:[B,*]是阿贝尔群。 四、计算(22%) 1、(10分) (1)(5分)由Huffman方法,得最佳二叉树为: (2)(5分)最佳前缀码为:000,001,01,10,11 2、(12分) 图中奇数点为E、F ,d(E)=3,d(F)=3,d(E,F)=28 p=EGF 复制道路EG、GF,得图G‘,则G‘是欧拉图. 由D开始找一条欧拉回路:DEGFGEBACBDCFD。 道路长度为: 35+8+20+20+8+40+30+50+19+6+12+10+23=281。 试卷六试题与答案 一、 填空 15% (每小题 3分) 1、 n阶完全图结点v的度数d(v) = 。 2、 设n阶图G中有m条边,每个结点的度数不是k的是k+1,若G中有Nk个k度顶点,Nk+1个k+1度顶点,则N k = 。 3、 算式 的二叉树表示为 。 4、 如图 给出格L,则e的补元是 . 5、 一组学生,用二二扳腕子比赛法来测定臂力的大小,则幺元是 . 二、选择 15% (每小题 3分) 1、设S={0,1,2,3},≤为小于等于关系,则{S,≤}是( )。 A、群;B、环;C、域;D、格。 2、设[{a , b , c},*]为代数系统,*运算如下: * a b c a a b c b b a c c c c c 则零元为( )。 A、a; B、b; C、c; D、没有。 3、如右图 相对于完全图K5的补图为( ). 4、一棵无向树T有7片树叶,3个3度顶点,其余顶点均为4度。则T有( )4度结点. A、1; B、2; C、3; D、4。 5、设[A,+,·]是代数系统,其中+,·为普通加法和乘法,则A=( )时,[A,+,·]是整环。 A、; B、; C、; D、。 三、证明 50% 1、设G是(n,m)简单二部图,则。(10分) 2、设G为具有n个结点的简单图,且,则G是连通图。(10分) 3、记“开”为1,“关”为0,反映电路规律的代数系统[{0,1},+,·]的加法运算和乘法运算。如下: + 0 1 · 0 1 0 0 1 0 0 0 1 1 0 1 0 1 证明它是一个环,并且是一个域。(14分) 4、 是一代数格,“≤”为自然偏序,则[L,≤]是偏序格.(16分) 四、10% 设是布尔代数上的一个布尔表达式,试写出的析取范式和合取范式(10分) 五、10% 如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价(单位:万元),试给出一个设计方案,使得各城市之间既能够通信又使总造价最小. 答案: 一、填空 15%(每小题3分) 1、n-1;2、n(k+1)—2m;3、如右图;4、0 ;5、臂力小者 二、选择 15%(每小题 3分) 题目 1 2 3 4 5 答案 D C A A D 三、证明 50% (1) 证:设G=(V,E) 对完全二部图有 当时,完全二部图的边数m有最大值 故对任意简单二部图有。 (2) 证:反证法:若G不连通,不妨设G可分成两个连通分支G1、G2,假设G1和G2的顶点数分别为n1和n2,显然 与假设矛盾。所以G连通。 (3) (1)[{0,1},+,·]是环 ①[{0,1},+]是交换群 乘:由“+”运算表知其封闭性。由于运算表的对称性知:+运算可交换。 群: (0+0)+0=0+(0+0)=0 ;(0+0)+1=0+(0+1)=1; (0+1)+0=0+(1+0)=1 ; (0+1)+1=0+(1+1)=0; (1+1)+1=1+(1+1)=0 …… 结合律成立。 幺:幺元为0。 逆:0,1逆元均为其本身. ②[{0,1},·]是半群 乘:由“· ”运算表知封闭 群: (0·0)·0=0·(0·0)=0 ;(0·0)·1=0·(0·1)= 0; (0·1)·0=0·(1·0)=0 ; (0·1)·1=0·(1·1)=0; (1·1)·1=1·(1·1)=0 。 ③·对+的分配律 Ⅰ 0·(x+y)=0=0+0=(0·x)+(0·y); Ⅱ 1·(x+y) 当x=y (x+y)=0 则 ; 当()则 所以均有 同理可证: 所以·对+ 是可分配的。 由①②③得,[{0,1},+,·]是环. (2)[{0,1},+,·]是域 因为[{0,1},+,·]是有限环,故只需证明是整环即可。 ①乘交环: 由乘法运算表的对称性知,乘法可交换. ②含幺环:乘法的幺元是1 ③无零因子:1·1=1≠0 因此[{0,1},+,·]是整环,故它是域。 4- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 试题 十五
咨信网温馨提示:
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文