2022年2022年离散数学期末考试试题 .pdf

离散试卷及答案第 1 页 共 12 页离散数学试题 (A 卷及答案）一、证明题（ 10 分）1)(P(QR) (QR)(PR)R 证明: 左端(P Q R) (QP)R) (P Q) R)(QP) R) ( (PQ)R) (QP)R)( (PQ) (QP)R ( (PQ)(P Q)R T R(置换)R 2)x(A(x)B(x)xA(x)xB(x) 证明： x(A(x)B(x)x( A(x) B(x)x A(x) xB(x)xA(x) xB(x)xA(x)xB(x) 二、求命题公式(P(QR)(PQ R)的主析取范式和主合取范式（10 分）证明： (P(QR)(PQ R)(P(QR) (P QR) （P(Q R)） (PQR) (PQ)(PR) (PQ R) (PQ R)(P Q R)(PQ R) (PQ R) (PQ R) m0 m1 m2 m7 M3 M4 M5 M6 三、推理证明题（10 分）1） CD, (C D)E, E(AB), (AB)(RS)RS 证明： (1) (CD)E (2) E(AB) (3) (CD)(AB) (4) (AB)(RS) (5) (CD)(RS) (6) C D (7) R S 2) x(P(x)Q(y) R(x) ， xP(x)Q(y) x(P(x)R(x) 证明（ 1） xP(x) (2)P(a) (3)x(P(x)Q(y) R(x) (4)P(a)Q(y) R(a) (5)Q(y)R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)R(a) (10)x(P(x) R(x) (11)Q(y) x(P(x) R(x) 四、设m是一个取定的正整数，证明：在任取m1 个整数中，至少有两个整数，它们的差是m的整数倍证明设1a，2a，1ma为任取的m1 个整数，用m去除它们所得余数只能是0，1，m1，由抽屉原理可知，1a，2a，1ma这m1 个整数中至少存在两个数sa和ta，它们被m除所得余数相同，因此sa和ta的差是m的整数倍。五、已知A 、B、C 是三个集合，证明A-(B C)=(A-B) (A-C) （15 分）证明xA-（BC）xAx（BC）xA（ xBxC）（xAxB ）（ xAxC）x（A-B）x（A-C） x（A-B）（ A-C） A-（BC）=（A-B）（ A-C）六、已知R、S 是 N 上的关系，其定义如下：R=| x,yNy=x2 ，S=| x,yNy=x+1 。求 R-1、R*S、S*R、R 1,2 、S1,2（10 分）解： R-1=| x,yNy=x2 ，R*S=| x,yNy=x2+1 ，S*R=| x,yNy=（x+1）2 ，七、若 f:A B和 g:B C是双射，则（ gf ）-1=f-1g-1（10 分） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 离散试卷及答案第 2 页 共 12 页证明：因为f 、g 是双射，所以gf ：AC是双射，所以gf 有逆函数（ gf ）-1：CA。同理可推f-1g-1：CA是双射。因为 f-1g-1存在 z（ g-1 f-1）存在 z（ f g） gf （gf ）-1,所以（ gf ）-1=f-1g-1。R 1,2=,，S1,2=1,4。八、 （15 分）设 是半群，对A中任意元a和b，如ab必有a*bb*a，证明：(1) 对A中每个元a，有a*aa。(2) 对A中任意元a和b，有a*b*aa。(3) 对A中任意元a、b和c，有a*b*ca*c。证明由题意可知，若a*bb*a，则必有ab。(1) 由(a*a)*aa*(a*a) ，所以a*aa。(2) 由a*(a*b*a) (a*a)*(b*a) a*b*(a*a) (a*b*a)*a，所以有a*b*aa。(3) 由(a*c)*(a*b*c) (a*c*a)*(b*c) a*(b*c)(a*b)*c(a*b)*(c*a*c)(a*b*c)*(a*c) ，所以有a*b*ca*c。九、给定简单无向图G，且 |V| m，|E| n。试证：若n21mC2，则G是哈密尔顿图证明若n21mC2，则 2nm23m6 （1） 。若存在两个不相邻结点u 、 v 使得 d( u ) d( v )m，则有 2nVwwd)(m(m2)(m3) mm23m6，与（ 1）矛盾。所以，对于G中任意两个不相邻结点u 、 v 都有 d( u ) d( v) m，所以G是哈密尔顿图。离散数学试题 (B 卷及答案）一、证明题（ 10 分）1)(P Q)(P(Q R) (PQ)(PR)T 证明左端(P Q)(P(QR) (P Q)(PR)( 摩根律 ) (P Q)(PQ)(PR) (P Q)(PR)( 分配律 ) (P Q)(PR) (P Q)(PR) ( 等幂律 ) T ( 代入 ) 2)x(P(x)Q(x) xP(x)x(P(x) Q(x) 证明x(P(x)Q(x) xP(x)x(P(x)Q(x) P(x)x(P(x) Q(x) P(x)x(P(x) Q(x)xP(x) xQ(x)x(P(x) Q(x) 二、求命题公式(PQ)(PQ) 的主析取范式和主合取范式（10 分）解： (PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QP Q)(PQ)M1m0 m2 m3 三、推理证明题（10 分）1)(P(QS) (RP)QRS 证明： （1）R 附加前提(2)RP P (3)P T(1)(2),I (4)P(QS) P (5)QS T(3)(4),I (6)Q P (7)S T(5)(6),I (8)RS CP 2) x(P(x) Q(x) ，xP(x)x Q(x) 证明： (1)xP(x) P (2)P(c) T(1),US (3)x(P(x) Q(x) P (4)P(c)Q(c) T(3),US (5)Q(c) T(2)(4),I (6)x Q(x) T(5),EG 四、例 5 在边长为 1 的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 离散试卷及答案第 3 页 共 12 页过 1/8 （10 分） 。证明： 把边长为 1 的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8 。五、已知A 、B、C 是三个集合，证明A(BC)=(AB)(AC) （10 分）证明： x A （BC） x A x（BC） x A （ xBxC ）（ x A xB）（ x A xC） x（AB）x A C x（A B）（ AC） A（ BC）=（AB ）（ AC）六、=A1，A2， An 是集合 A的一个划分，定义R=|a 、bAi，I=1 ，2， n，则 R是 A上的等价关系（15 分） 。证明：a A必有 i 使得 aAi，由定义知aRa ，故 R自反。a,b A，若 aRb ，则 a,b Ai，即 b,a Ai，所以 bRa，故 R对称。a,b,c A，若 aRb 且 bRc，则 a,b Ai及 b,c Aj。因为 i j 时 AiAj=，故 i=j ，即 a,b,c Ai，所以 aRc，故 R传递。总之 R 是 A 上的等价关系。七、若 f:A B是双射，则f-1:B A是双射（ 15 分） 。证明 :对任意的 xA，因为 f 是从 A到 B的函数，故存在yB，使 f ， f-1。所以 ,f-1是满射。对任意的 xA ，若存在y1,y2B，使得 f-1且 f-1, 则有 f 且f。因为 f 是函数，则y1=y2。所以， f-1是单射。因此 f-1是双射。八、设 是群， 和是的子群，证明：若ABG，则AG或BG（10 分）。证明假设AG且BG，则存在a A，a B，且存在b B，b A（否则对任意的a A，a B，从而A B，即ABB，得BG，矛盾。）对于元素a*b G，若a*b A，因A是子群，a-1A，从而a-1 * (a*b) bA，所以矛盾，故a*b A。同理可证a*b B，综合有a*b ABG。综上所述，假设不成立，得证AG或BG。九、若无向图G是不连通的，证明G的补图 G 是连通的（ 10 分） 。证明设无向图G是不连通的，其k个连通分支为1G 、2G 、kG 。任取结点 u 、 vG，若 u 和 v 不在图G的同一个连通分支中，则 u ， v 不是图G的边，因而 u ， v 是图 G 的边；若 u 和 v 在图G的同一个连通分支中，不妨设其在连通分支iG （1 i k）中，在不同于iG 的另一连通分支上取一结点w ，则 u ， w 和 w ， v 都不是图G的边，因而 u ， w 和 w ， v 都是 G 的边。综上可知，不管那种情况，u 和 v 都是可达的。由u 和 v 的任意性可知，G 是连通的。一、选择题 .( 每小题 2 分，总计 30) 1.给定语句如下：（1）15 是素数（质数）（2）10 能被 2 整除， 3 是偶数。（3）你下午有会吗？若无会，请到我这儿来！（4）2x+30. （5）只有 4 是偶数， 3 才能被 2 整除。(6) 明年 5 月 1 日是晴天。以上 6 个语句中， 是简单命题的为 （A）, 是复合命题的为 （B）, 是真命题的为 （C）, 是假命题的是 （D）, 真值待定的命题是 （E）A: (1)(3)(4)(6) (1)(4)(6) (1) （6） B: (2)(4) (2)(4)(6) (2)(5) C: (1)(2)(5)(6) 无真命题（ 5） D: (1)(2) 无假命题(1)(2)(4)(5) E: (4)(6) （ 6） 无真值待定的命题2. 将下列语句符号化：（1）4 是偶数或是奇数。 （A）设 p：4 是偶数， q：4 是奇数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 离散试卷及答案第 4 页 共 12 页（2）只有王荣努力学习，她才能取得好成绩。（B ）设 p：王荣努力学习，q：王荣取得好成绩（3）每列火车都比某些汽车快。（C）设 F(x):x是火车， G(y):y是汽车， H(x,y):x比 y 快。A: p q p q p q B: p q q p p q C: xy (F(x)G(y) (H(x,y)x (F(x)y(G(y) H(x,y)x (F(x)y(G(y) H(x,y) 3. 设 S=1,2,3,下图给出了S上的 5 个关系 , 则它们只具有以下性质:R1是（ A）,R2是(B),R3是(C) 。A B C: 自反的，对称的，传递的反自反的，对称的自反的反对称的对称的自反的，对称的，反对称的，传递的4. 设S=，1 ，1 ，2 ，则有（1） （A） S （2） (B)S （3） P(S) 有（ C）个元数。（4） （D）既是 S的元素，又是 S的子集A: 1,2 1 B: 1,2 1 C: 3 6 7 8 D: 1 二、证明（本大题共2 小题，第 1 小题 10 分，第 2 小题 10 分，总计 20 分）1、用等值演算算法证明等值式 (p q) (p q)p 2、构造下面命题推理的证明如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。三、计算（本大题共4 小题，第 1 小题 5 分，第 2 小题 10 分，第 3 小题 15 分，总计 30 分）1、设212,，个体域为为，整除为xxQyxyxP，求公式：xQyxPyx,的真值。2、设集合AA,4, 3 ,2, 1上的关系4, 3,3 , 2,1 , 2,2, 1,1 , 1R，求出它的自反闭包，对称闭包和传递闭包。3、设,24,12,8 ,4,2 , 1A上的整除关系212121,aaAaaaaR整除，R是否为A上的偏序关系？若是，则：1、画出R的哈斯图；（10 分）2、求它的极小元，最大元，极大元，最大元。（5 分）四、 用推导法求公式pqp的主析取范式和主合取范式。（本大题 10分）答案：一、 选择题1.A: B: C: D: E: 2.A: B: C: 3.A: B: C: 4.A: B: C: D: 二、证明题1.证明左边（(p q) p）（ (p q) q) ）（分配律） p （ (pq)q) ） (吸收律 ) p （ (pq) (q q) ）（分配律） p （ (pq) 1）（排中律）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 离散试卷及答案第 5 页 共 12 页 p (p q) （同一律） p （吸收律）2. 解： p：今天是星期三。 q：我有一次英语测验。 r：我有一次数学测验。 s：数学老师有事。前提： p(q r) , sr , ps 结论： q 证明： ps 前提引入p 化简p(q r) 前提引入qr 假言推理s 化简sr 前提引入r 假言推理q 析取三段论推理正确。三、计算1. ,1,12,21,112,121,212,22xyP x yQ xyPyQPyQPQPQPQPQ1,11,1,21,2,10,2,21,11,20110011101PPPPQQ该公式的真值是1，真命题。或者TTTFTTTFTFFTTTTQPQPQPQPxQxPxQxPxxQyxPyx22, 221 ,212, 111 , 12,1 ,2、4, 4,3, 3,2, 2,4, 3,3, 2,1 ,2,2, 1,1 , 1)(Rr3, 4,2, 3,4, 3,3 ,2,1 ,2,2, 1,1 , 1)(Rs4, 1,4 ,2,2, 2,3, 1,4, 3,3 ,2,1 ,2,2, 1,1 , 1)(Rt3、 （1）R是A上的偏序关系。（2）极小元、最小元是1, 极大元、最大元是 24。四、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 离散试卷及答案第 6 页 共 12 页2 30 1pqppqppqpppqqpqpq，主合取范式，安徽大学 2004-2005 学年第二学期离散数学期末考试试卷（A 卷）参考答案一、单项选择1 在自然数集N上，下列哪种运算是可结合的？（）A. baba* B. ,max*babaC. baba2* D. )3(mod*baba2 下列代数系统 中，哪个是群？（）A. 5 , 3, 1 , 0S，*是模 7 加法 B. QS（有理数集合） ，*是一般乘法C. ZS（整数集合），*是一般减法 D. 9, 5, 4, 3 ,1S，* 是模 11 乘法3 若是的真子群，且nH，mG，则有（） 。A. n整除m B. m整除nC. n整除m且m整除n D. n不整除m且m不整除n4 下面哪个集合关于指定的运算构成环？（）A. ,|23Zbaba，关于数的加法和乘法B.n阶实数矩阵，关于矩阵的加法和乘法C. ,|2Zbaba，关于数的加法和乘法D. Zbaabba,，关于矩阵的加法和乘法5 在代数系统中，整环和域的关系为（） 。A. 域一定是整环 B.域不一定是整环C. 整环一定是域 D. 域一定不是整环6 N是自然数集，是小于等于关系，则),(N是（） 。A. 有界格 B.有补格 C. 分配格 D. 有补分配格7 图 1-1 给出的哈斯图表示的格中哪个元素无补元？（）A. a B. c C. e D. f图 1-1 8 给定下列序列，可构成无向简单图的结点度数序列的是（） 。A. （1，1，2，2，3） B.（1，3，4，4，5）a b c d e f g 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 离散试卷及答案第 7 页 共 12 页C.（0，1，3，3，3） D.（1，1，2，2，2）9 欧拉回路是（） 。A. 路径 B.简单回路C.既是基本回路也是简单回路 D.既非基本回路也非简单回路10 哈密尔顿回路是（） 。A. 路径 B.简单回路C.既是基本回路也是简单回路 D.既非基本回路也非简单回路二、填空题（以下每个下划线为一空，请按要求填入合适的内容。每空2 分，共 30 分） 。1 设S是非空有限集，代数系统）,),(SP中，)(SP对运算的单位元是，零元是，)(SP对运算的单位元是。2 在运算表 2-1 中空白处填入适当符号，使),(cba成为群。，。3 设8 ,4 ,0H，12,H是群1212,N的子群，其中11,2 ,1 ,012N，12是模 12 加法，则1212,N有个真子群，H的左陪集H3，H4。4 设,A是一个布尔代数，如果在A上定义二元运算为：)()(bababa，则,A是一个。表 2-1 5 任何一个具有n2个元素的有限布尔代数都是。6 若连通平面图G有 4 个结点， 3 个面，则G有条边。7 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有个度数为1 的结点。8 无向图G是由k（2k）棵数组成的森林，至少要添加条边才能使G成为一棵树。三、求解题（ 20 分）1 试写出66,N中每个子群及其相应的左陪集。（6 分）2 若一个有向图G是欧拉图， 它是否一定是强连通的？若一个有向图G是强连通的， 它是否一定是欧拉图？说明理由。（6 分）3 有向图G如图 3-1 所示。（1）求G的邻接矩阵A； （2 分）（2）G中1v到4v长度为 4 的路径有几条？（2 分）（3）G中1v到自身长度为3 的回路有几条？（2 分）（4）G是哪类连通图？（2 分）图 3-1 四、证明题（ 30 分）1 设,*G是一群，Gx。定义：bxaba*，Gba,。证明,G也是一群。2 证明： （1）证明在格中成立：)(*)()*()*(dbcadcba。 （5 分）（2）证明布尔恒等式：)*()*()*()*()*(bacacbbaca。 （5 分）a b c a a b a b c c c e2 e7 v4 e4 v1 v2 v3 e1 e3 e6 e5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - 离散试卷及答案第 8 页 共 12 页3 证明： （1）在 6 个结点 12 条边的连通平面简单图中，每个面由3 条边围成。（5 分）（2）证明当每个结点的度数大于等于3 时，不存在有7 条边的简单连通平面图。安徽大学 2004-2005 学年第二学期离散数学期末考试试卷（A 卷）参考答案一、单项选择1B; 2.D; 3.A; 4.C; 5.A; 6.C; 7.B; 8.D; 9.B; 10.C. 二、填空题1 ，S，S；2 c，b，b，a；3 5 ，11,7,3，0,8 ,4；4 交换群；5 同构；6 5 ；7 9 ；8 1k。三、求解题1 解：子群有：6,0，6,3,0，6,4,2,0。6,0的左陪集为：0， 1，2，3，4，56,3,0的左陪集为： 3, 0，4 ,1，5 ,26,4 ,2,0的左陪集为：4,2, 0，5 ,3 , 12 答： （1）一个有向欧拉图一定是强连通图。因为G是欧拉图，存在欧拉回路C，G中的每个结点至少在C中出现一次。因而G中任意两点u，v都在C中，相互可达，故G是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。3 解：（1）0100100001000121A10000100100013212A01001000010034213A10000100100046214A（2）由4A中4414a可知，1v到4v长度为 4 的路径有条（6411eeee，6764eeee，6521eeee，6531eeee） 。（3）由3A中1311a可知，1v到自身长度为3 的回路有 1 条（111eee） 。（4）G是单向连通图。四、证明题1 证明：显然是G上的二元运算（即满足封闭性），要证G是群，需证结合律成立，同时有单位元，每个元素有逆元。Gcba,，有)()*(*)*()(cbacxbxacxbxacba运算是可结合的。其次，1x是,G的单位元。事实上，Ga，有axxaxa11*；aaxxax*11最后证明，Ga，111*xax是a在,G中的逆元。事实上，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 离散试卷及答案第 9 页 共 12 页1111111*)*(xxaxxaxaxa1111111*)*(xaxxaxaxax由以上证明，,G是群。2 证明： （1）)*(*)*()*()*(dbacbadcba（公式 (13) 分配不等式）又因为aba*，bba *，所以)(*)()*()*(dbcadcba。（2）因为1aa，)*()*(*1cbcb，所以有，)*(*)()*()*()*()*()*(cbaabacacbbaca)*()*()*()*(cbacbabaca)*()*()*()*(cbababcaca（吸收律）)*()*(baca即等式成立。3 证 明 ：（ 1 ） 因 图 中 结 点 数 和 边 数 分 别 为6n，12m， 根 据 欧 拉 公 式2kmn， 得8k。 又242)deg(mvi，而简单连通平面图的每个面至少由3 条边围成，所以在6 个结点 12 条边的连通平面简单图中，每个面由 3 条边围成。（2）设),(mn图为简单连通平面图，有k个面。（反证法）若7m，由欧拉公式知92mkn，而每个面至少由3 条边围成，有mk23，则31432mk，且k是整数，所以4k；又对任结点Vv，3)deg(v，有mn23，故31432mn，且n是整数，所以4n。这样就有844kn，与9kn矛盾，所以结论正确。安徽大学 2007 2008 学年第 2 学期离散数学（下） 考试试卷（ A卷）一、单项选择题（每小题2 分，共 20 分）1. 下列集合关于数的加法和乘法运算不能构成环的是（）A. 自然数集合； B.整数集合； C.有理数集合； D.实数集合。2. 设I为整数集合，则下列集合关于数的加法运算不能构成独异点的是（）A.I； B.2|k kI； C.21|kkI； D.35 |,mn m nI。3. 设60,1,5N，6为模6加法，则下列元素是66,N的生成元的是（）A.2； B.3； C.4； D.5。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 离散试卷及答案第 10 页 共 12 页4. 设,F是整环，则,F不一定是（）A. 可交换环； B.无零因子环； C.含么环； D.域。5. 格不一定具有（）A. 交换律； B.结合律； C.分配律； D.吸收律。6. 设1,2,4,8S，和分别表示求最小公倍数和最大公约数运算，则, ,S是（）A. 有补格； B.分配格； C.有补分配格； D.布尔代数。7. 一个含4个结点的无向图中有3个结点的度数分别为1,2,3，则第4个结点的度数不可能是（）A.0 ； B.1； C.2； D.4。8. 设连通的简单平面图G中有 10 条边和 5 个面，则G的结点数为（）A.6 ； B.7； C.8； D.9。9. 设无向树T中有1个结点度数为2，2个结点度数为3，3个结点度数为4，则T中的树叶数为（）A.10； B.11； C.12； D.13。10. 设G为连通的无向图，若G仅有2个结点的度数是奇数，则G一定具有（）A 、欧拉路径； B、欧拉回路； C、哈密尔顿路径； D、哈密尔顿回路。二、填空题（每小空2 分，共 20 分）1. 设R为实数集合，|01 Sx xRx，则在代数,maxS中，S关于max运算的么元是，零元是。2. 设10为模10加法，则在100,1,9,中，元素5的阶为，6的阶为。3. 设1101,2,5,10,11,22,55,110S，gcd和lcm分别为求最大公约数和最小公倍数运算，则在布尔代数110,gcd,lcmS中，原子的个数为，元素22的补元为。4. 在格, ,L中，,a bL，ab当且仅当a b当且仅当ab。5. 一个具有n个结点的简单连通无向图的边数至少为，至多为。三、解答题（第1 小题 12 分，第 2 小题 8 分，共 20 分）1. 设图G如图 1 所示，(1) 求G的邻接矩阵A；(2) 求(2)(3)(4),AAA，说明从1v到4v的长为2,3, 4的路径各有几条；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - 离散试卷及答案第 11 页 共 12 页(3) 求G的可达矩阵P；(4) 求G的强连通分图。2. 求群88,N的所有子群及由元素5确定的各子群的左陪集，其中80,1,7N，8是模8加法。四、证明题（每小题10 分，共 40 分）1. 证明布尔恒等式：()()()()abacbcabc。2. 设R为实数集合，和为数的加法和乘法运算，对,a bR，bababa*，证明：,R为独异点。3. 证明：若),(mn简单无向图G满足)2)(1(21nnm，则图G是连通图。4. 设,G是一个群，aG；定义一个映射:fGG，使得对于xG有1( )f xaxa；证明：f是,G安徽大学 2007 2008 学年第 2 学期离散数学（下） 考试试卷（ A卷）一、单项选择题（每小题2 分，共 20 分）1.A； 2.C ； 3.D ； 4.D ； 5.C ； 6.B ； 7.B ； 8.B ； 9.A ； 10.A 。二、填空题（每小空2 分，共 20 分）1.0，1； 2.2，5； 3.3，5； 4.a，b； 5.1n，(1)/ 2n n。三、解答题（第1 小题 12 分，第 2 小题 8 分，共 20 分）1. (1) G的邻接矩阵0111001001010010A； 2分(2) (2)0121010100200101A；(3)0222002002020020A；(4)0242020200400202A； 5分从1v到4v的长为2,3, 4的路径的条数分别为1,2,2； 8分(3) G的可达矩阵为0111011101110111P； 10分(4) 因0000011101110111TPP，故G的强连通分图的结点集为1v，234,vv v。 12分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 离散试卷及答案第 12 页 共 12 页2. 88,N的子群为：80,，80, 2,4,6,，80, 4,，88,N； 4分元素5确定的各子群的左陪集对应为：5，1,3,5,7，1,5，8N。 8分四、证明题（每小题10 分，共 40 分）1. ()()()()()abacbcababc 2分()()()() )()ababcabababc 6分1 ()()a bca bc。 10分2. 因R对和运算封闭，故R对运算封闭；对, ,x y zR， 2分xyzyzxzxyzyxzxyyxzxyyxzyxyxzyx)(*)(*)*(, xyzyzxzxyzyxyzzyxyzzyxzyzyxzyx)()(*)*(*故()()xyzxyz，从而R上的运算满足结合律； 6分因对xR，xxxx00*0，xxxx000*，故0为运算的么元；综合以上，为R上的可结合的二元运算，且R关于运算有么元，所以,R为独异点。 10分3. 假设G有(2)k k个连通分图，则因G为简单无向图，故12()(1)mnknk， 4分因为2k，所以02nkn，011nkn， 8分所以1122()(1)(1)(2)mnknknn，这与12(1)(2)mnn矛盾！所以图G是连通图。 10分4. 对12,x xG，若12()()fxfx，则1112axaaxa，故12xx，从而f为单射； 3分yG，1ayaG且1()f ayay，因此xG，使( )f xy，所以f为满射； 6分,x yG，111()()()()( )( )f xyaxyaaxaayaf xfy，故f为同态； 9 分所以f是,G的群自同构。 10分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -