离散数学期末考试试题(有几套带答案)

1、离散数学期末考试试题(有几套带答案)  离散试卷及答案 离散数学试题(A卷及答案）  一、证明题（10分）  1)(ØP(ØQR)(QR)(PR)ÛR  证明: 左端Û(ØPØQR)(QP)R)Û(ØPØQ)R)(QP)R)  Û(Ø(PQ)R)(QP)R)Û(Ø(PQ)(QP)R Û(Ø(PQ)(PQ)RÛTR(置换)ÛR&#

2、160; 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)®(PQR)的主析取范式和主合取范式（10分）  证明：(P(QR)®(PQR)ÛØ(P(QR)(PQR) 

3、 Û（ØP(ØQØR)）(PQR) Û(ØPØQ)(ØPØR)(PQR)  Û(ØPØQR)(ØPØQØR)(ØPQØR)(ØPØQØR)(PQR) Ûm0m1m2m7 ÛM3M4M5M6  三、推理证明题（10分）  1） CD, (CD)® ØE, ØE®(A

4、16;B), (AØB)®(R  S)ÞRS  证明：(1) (CD)®ØE (2) ØE®(AØB) (3) (CD)®(AØB) (4) (AØB)®(RS) (5) (CD)®(RS) (6) CD (7) RS  2) "x(P(x)®Q(y)R(x)，$xP(x)ÞQ(y)$x(P(x)R(x)     证明（1）$xP(x)

5、(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的整数倍  证明 设a1，a2，am+1为任取的m1个整数，用m去除它们所得余数只能是0，1，m1，由抽屉原理可知，  a1，a2，am+1这m1

6、个整数中至少存在两个数as和at，它们被m除所得余数相同，因此as和at的差是m的整  数倍。  五、已知A、B、C是三个集合，证明A-(BC)=(A-B)(A-C) （15分）  证明 xÎ A-（BC）Û xÎ AxÏ（BC）Û xÎ A（xÏBxÏC）Û （xÎ AxÏB）（xÎ AxÏC）Û xÎ（A-B）xÎ（A-C）Û xÎ（A-B）（A-C）A

7、-（BC）=（A-B）（A-C）  六、已知R、S是N上的关系，其定义如下：R=<x,y>| x,yÎNy=x，S=<x,y>| x,yÎNy=x+1。求R、R*S、S*R、   R1,2、S1,2（10分）  解：R=<y,x>| x,yÎNy=x，R*S=<x,y>| x,yÎNy=x+1，S*R=<x,y>| x,yÎNy=（x+1）， 七、若f:AB和g:BC是双射，则（gf）=fg（10分）。  

8、第 1 页 共 12 页  -1  -1-1  -1  2  2  2  2  -1  离散试卷及答案  证明：因为f、g是双射，所以gf：AC是双射，所以gf有逆函数（gf）：CA。同理可推fg：CA是双射。 因为<x,y>fgÛ存在z（<x,z>gÙ<z,y>f）Û存在z（<y,z>fÙ<z,x>

9、;g）Û<y,x>gfÛ<x,y>（gf）,所以（gf）=fg。   R1,2=<1,1>,<2,4>，S1,2=1,4。  八、（15分）设<A，*>是半群，对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。 &

10、#160;(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。  2九、给定简单无向图G<V，E>，且|V|m，|E|n。试证：若nCm-12，则G是哈密尔顿图 2证明 若nCm。 -12，则2nm3m6 （1）  2  -1  -1-1  -

11、1-1  -1  -1  -1  -1  -1-1  若存在两个不相邻结点u、v使得d(u)d(v)m，则有2n  wÎV  åd(w)m(m2)(m3)mm3m6，与（1）矛  2  盾。所以，对于G中任意两个不相邻结点u、v都有d(u)d(v)m，所以G是哈密尔顿图。  离散数学试题(B卷及答案）  一、证明题（10分） &

12、#160;1)(PQ)Ø(ØP(ØQØR)(ØPØQ)(ØPØR)ÛT  证明 左端Û(PQ)(P(QR)Ø(PQ)(PR)(摩根律) Û (PQ)(PQ)(PR)Ø(PQ)(PR)(分配律) Û (PQ)(PR)Ø(PQ)(PR) (等幂律) ÛT (代入) 2)"x(P(x)®Q(x)"xP(x)Û"x(P(x)Q(x)  证明 "x

13、(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)  二、求命题公式(ØP®Q)®(PØQ) 的主析取范式和主合取范式（10分）  解：(ØP®Q)®(PØQ)ÛØ(ØP

14、74;Q)(PØQ)ÛØ(PQ)(PØQ)Û(ØPØQ)(PØQ) Û(ØPPØQ)(ØQPØQ)Û(PØQ)ÛM1Ûm0m2m3 三、推理证明题（10分） 1)(P®(Q®S)(ØRP)QÞR®S  证明：（1）R 附加前提 (2)ØRP P (3)P T(1)(2),I (4)P®(Q®S) P (5)Q®S T(

15、3)(4),I (6)Q P  (7)S T(5)(6),I  (8)R®S CP  2) "x(P(x)Q(x)，"xØP(x)Þ$x Q(x)  证明：(1)"xØP(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的正方形内任意放置九个点，

16、证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超  第 2 页 共 12 页  离散试卷及答案  过1/8（10分）。  证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。  五、已知A、B、C是三个集合，证明A(BC)=(AB)(AC) （10分）  证明：xÎ A（BC）Û xÎ AxÎ（BC）Û x

17、06; A（xÎBxÎC）Û（ xÎ AxÎB）（xÎ AxÎC）Û xÎ（AB）xÎ ACÛ xÎ（AB）（AC）A（BC）=（AB）（AC）  六、p=A1，A2，An是集合A的一个划分，定义R=<a，b>|a、bAi，I=1，2，n，则R是A上的等价关系（15分）。 证明："aA必有i使得aAi，由定义知aRa，故R自反。  "a,bA，若aRb ，则a,bAi，即b,aAi，所以bRa，故R对称。

18、  "a,b,cA，若aRb 且bRc，则a,bAi及b,cAj。因为ij时AiAj=F，故i=j，即a,b,cAi，所以aRc，故R传递。  总之R是A上的等价关系。  七、若f:AB是双射，则f:BA是双射（15分）。  证明: 对任意的xA，因为f是从A到B的函数，故存在yB，使<x,y>f，<y,x>f。所以,f是满射。  对任意的xA，若存在y1,y2B，使得<y1,x>f且<y2,x>f,则有<x,y1>f且<

19、;x,y2>f。因为f是函数，则y1=y2。所  以，f是单射。 因此f是双射。  八、设<G，*>是群，<A，*>和<B，*>是<G，*>的子群，证明：若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

20、ÎA，从而a * (a*b)b ÎA，所以矛盾，故a*bÏA。同理可证a*bÏB，综合  有a*bÏABG。  综上所述，假设不成立，得证AG或BG。  九、若无向图G是不连通的，证明G的补图G是连通的（10分）。  证明 设无向图G是不连通的，其k个连通分支为G1、G2、Gk。任取结点u、vG，若u和v不在图G的同一个连通分支中，则u，v不是图G的边，因而u，v是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1ik）中，在不同于Gi的另一连通

21、分支上取一结点w，则u，w和w，v都不是图G的边，因而u，w和w，v都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。 -1-1-1-1-1-1-1-1-1  一、 选择题.(每小题2分，总计30)  1. 给定语句如下：  （1）15是素数（质数）  （2）10能被2整除，3是偶数。  （3）你下午有会吗？若无会，请到我这儿来！  （4）2x+3>0.  （5）只有4是偶数，3才能被2整除。 

22、0;(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：

23、4是偶数，q：4是奇数  第 3 页 共 12 页  离散试卷及答案  （2）只有王荣努力学习，她才能取得好成绩。（B）设p：王荣努力学习，q：王荣取得好成绩  （3）每列火车都比某些汽车快。（C）设F(x):x是火车，G(y):y是汽车，H(x,y):x比y快。  A: pq pq pq B: pq qp pq  C: "x $y (F(x) G(y) (H(x,y)"x (F(x) $y(G(y)H(x,y)"x (F(x) $y(G(y)H

24、(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的子集 &#

25、160;A: 1,2 1 B: 1,2 1  C: 3 6 7 8 D: 1   二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分）  1、用等值演算算法证明等值式 (pq)(pØq)Ûp  2、构造下面命题推理的证明  如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。  三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分， 

26、; 总计30分）  1、设P(x,y)为x整除y，Q(x)为x<2，个体域为1，2，求公式：  ("x)($y)(P(x,y)®Q(x)的真值。  2、设集合  3、设A=A=1,2,3,4,A上的关系 R=,22,2,4，求出它的自反闭包，对称闭包和传递闭包。 1,2,4,8,12,24,上的整除关系R=a1,a2a1,a2ÎA,a1整除a2，R是否为A上的偏序关系？若是，则：  1、画出R的哈斯图；（10分）  2、求它的极小

27、元，最大元，极大元，最大元。（5分）  四、用推导法求公式  答案：  一、 选择题  1. A: B: C: D: E: 2.A: B: C:  3.A: B: C: 4.A: B: C: D:  二、证明题  1. 证明 左边Û（(pq)p）（(pq)Øq)） （分配律）  Û p（(pq)Øq)） (吸收律)  Û p（(pØq) (qØq)

28、） （分配律）  Û p（(pØq)1） （排中律） (p®q)®p)的主析取范式和主合取范式。（本大题10分）  第 4 页 共 12 页  离散试卷及答案  Û p (pØq) （同一律）  Û p （吸收律）  2.解：p：今天是星期三。  q：我有一次英语测验。  r：我有一次数学测验。  s：数学老师有事。  前提：p

29、®(qr) , s®Ør , ps  结论：q  证明：ps 前提引入  p 化简  p®(qr) 前提引入  qr 假言推理  s 化简  s®Ør 前提引入  Ør 假言推理  q 析取三段论  推理正确。  三、计算  ("x)($y)(P(x,y)®Q(x)&#

30、160; 1. Û($y)(P(1,y)®Q(1)L(P(2,y)®Q(2)  Û (P(1,1)®Q(1)L(P(2,1)®Q(2)Ú(P(1,2)®Q(1)L(P(2,2)®Q(2)  P(1,1)=1,P(1,2)=1,P(2,1)=0,P(2,2)=1,Q(1)=1,Q(2)=0Û(1®1)L(0®0)Ú(1®1)L(1®0)  Û1  该

31、公式的真值是1，真命题。  ("x)($y)(P(x,y)®Q(x)Û("x)(P(x,1)®Q(x)Ú(P(x,2)®Q(x)  Û(P(1,1)®Q(1)Ú(P(1,2)®Q(1)Ù(P(2,1)®Q(2)Ú(P(2,2)®Q(2)或者 Û(T®T)Ú(T®T)Ù(F®F)Ú(T®F)  Û(T

32、ÚT)Ù(TÚF)ÛTÙTÛT  2、r(R)=,22,2,42,23,4,4  s(R)=,2,2,2,3,43,24,  t(R)=,22,2,4,2,2,4  3、（1） R是A上的偏序关系。     （2）极小元、最小元是1,极大元、 最大元是24。  四、  第 5 页 共 12 页      离散试卷及答案 

33、0;(p®q)®p)Û(Ø(ØpÚq)Úp)  Û(pÙØq)Úp)  Ûp  ÛpÙ(qÚØq)  Û(pÙØq)Ú(pÙq)  Ûå  主合取范式Õ(0，1)  安徽大学2004-2005学年第二学期离散数学期末考试

34、试卷（A卷）参考答案  一、单项选择  1 在自然数集N上，下列哪种运算是可结合的？（ ）  A. a*b 3)(2，=a-b B. a*b=maxa,b  +2b D. a*b=a×b(mod3) C. a*b=a  2 下列代数系统<S，*>中，哪个是群？（ ）  A. S  C. S=0,1,3,5，*是模7加法 B. S=Q（有理数集合），*是一般乘法 =Z（整数集合），*是一般减法 D. S=1,3,4,5,9，*是模11乘

35、法  。 H=n，G=m，则有（ ）3 若<H，*>是<G，*>的真子群，且  A. n整除m B. m整除n  C. n整除m且 m整除n D. n不整除m且 m不整除n 4 下面哪个集合关于指定的运算构成环？（ ） A. a+b2|a,bÎZ，关于数的加法和乘法  B.n阶实数矩阵，关于矩阵的加法和乘法 C. a+b2|a,bÎZ，关于数的加法和乘法 ìüïæaböïa,bÎZ÷D. &#

36、237;çý，关于矩阵的加法和乘法 çba÷ïïøîèþ  5 在代数系统中，整环和域的关系为（ ）。  A. 域一定是整环 B.域不一定是整环  C. 整环一定是域 D. 域一定不是整环  6 N是自然数集，£是小于等于关系，则(N,£)是（ ）。  A. 有界格 B.有补格 C. 分配格 D. 有补分配格  7 图1-1给出的哈斯图表示的格中哪个元素无补

37、元？（ ）  A. a B. c C. e D. f 图1-1 8 给定下列序列，可构成无向简单图的结点度数序列的是（ ）。  A.（1，1，2，2，3） B.（1，3，4，4，5）      第 6 页 共 12 页  离散试卷及答案  C.（0，1，3，3，3） D.（1，1，2，2，2）  9 欧拉回路是（ ）。  A.路径 B.简单回路  C.既是基本回路也是简单回路 D.既非基本回路也非简单回路 

38、 10 哈密尔顿回路是（ ）。  A.路径 B.简单回路  C.既是基本回路也是简单回路 D.既非基本回路也非简单回路  二、填空题（以下每个下划线为一空，请按要求填入合适的内容。每空2分，共30分）。  1 设S是非空有限集，代数系统(P(S),U,I）中，P(S)对U运算的单位元是，零元是，P(S)对I运算的单位元是。  2 在运算表2-1中空白处填入适当符号，使(a,b,c,o)成为群。 ，。 3 设H=0,4,8，<H,+12>是群<N12,+12>的子

39、群，其中   N12=0,1,2,×××,11，+12是模12加法，则<N12,+12>有  个真子群，H的左陪集3H=，4H=。  4设<A,Ú,Ù,->是一个布尔代数，如果在A上定义二元运算Å为：  aÅb=(aÙb)Ú(Ùb)，则<A,Å>是一个。 表2-1  5 任何一个具有2n个元素的有限布尔代数都是。  6 若连通平面图

40、G有4个结点，3个面，则G有条边。  7 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有个度数为1的结点。  8 无向图G是由k（k³2）棵数组成的森林，至少要添加条边才能使G成为一棵树。  三、求解题（20分）  1 试写出<N6,+6>中每个子群及其相应的左陪集。 （6分）  2 若一个有向图G是欧拉图，它是否一定是强连通的？若一个有向图G是强连通的，它是否一定是欧拉图？说明理由。3 有向图G如图3-1所示。 （1）求G的邻接矩阵A； （2分）

41、60; （2）G中v1到v4长度为4的路径有几条？ （2分）  e4  7  （3）G中v1到自身长度为3的回路有几条？ （2分） v3  （4）G是哪类连通图？ （2分）  图3-1  四、证明题（30分）  1 设<G,*>是一群，xÎG。定义：aob=a*x*b，"a,bÎG。证明<G,o>也是一群。  2 证明：（1）证明在格中成立：(a*b)Å(c*d)

42、£(aÅc)*(bÅd)。 （5分）  （2）证明布尔恒等式：(a*c)Å(a¢*b)Å(b*c)=(a*c)Å(a¢*b)。 （5分）   第 7 页 共 12 页 6分） （  3 证明：（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。 （5分）  （2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。  安徽大学2004-2005学年第二学期离散数学期末考试试卷（A卷）参考答案

43、  一、单项选择  1B; 2.D; 3.A; 4.C; 5.A; 6.C; 7.B; 8.D; 9.B; 10.C. 二、填空题  1 F，S，S； 2 c，b，b，a； 5 同构； 三、求解题  1 解：子群有：<0,+6     6 5；     3 5，3,7,11，4,8,0； 4 交换群； 7 9；     8 k  -1。  >，&

44、lt;0,3,+6>，<0,2,4,+6>。  <0,+6>的左陪集为：0，1，2，3，4，5 <0,3,+6>的左陪集为：0,3，1,4，2,5  <0,2,4,+6>的左陪集为：0,2,4，1,3,5  2 答：（1）一个有向欧拉图一定是强连通图。因为G是欧拉图，存在欧拉回路C，G中的每个结点至少在C中出现一次。因而G中任意两点u，v都在C中，相互可达，故G是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。 3 解： &#

45、160;é1  ê0  （1）A=ê  ê0êë0  （2）由  20001101  0ùé1  ê00ú2ú A=ê  1úê0úê0ûë0  2  0003010  1ùé1&

46、#160; ê01ú3ú A=ê  0úê0úê1ûë0  2  0004101  3ùé1  ê00ú4ú A=ê  1úê0úê0ûë0  2  0006010  4ù1

47、50;ú 0úú1û  4  A4中a14。 =4可知，v1到v4长度为4的路径有条（e1e1e4e6，e4e6e7e6，e1e2e5e6，e1e3e5e6）3A3中a11。 =1可知，v1到自身长度为3的回路有1条（e1e1e1）  （3）由  （4）G是单向连通图。 四、证明题  1 证明：显然o是G上的二元运算（即满足封闭性），要证G是群，需证结合律成立，同时有单位元，每个元素有逆元。 "a,b,cÎG，有  

48、(aob)oc=(a*x*b)*x*c=a*x*(b*x*c)=ao(boc) 运算是可结合的。 其次，x  -1  是<G,o>的单位元。事实上，"aÎG，有  aox-1=a*x*x-1=a；x-1oa=x-1*x*a=a  最后证明，"aÎG，x  -1  *a-1*x-1是a在<G,o>中的逆元。事实上，  ao(x-1*a-1*x-1)=a*x*x-1*a-1*x-1=x-1 (x-

49、1*a-1*x-1)oa=x-1*a-1*x-1*x*a=x-1  由以上证明，<G,o>是群。  2 证明：（1）(a*b)Å(c*d)£(a*b)Åc)*(a*b)Åd) （公式(13)分配不等式） 又因为a*b£（2）因为a  a，a*b£b，所以(a*b)Å(c*d)£(aÅc)*(bÅd)。  Åa¢=1，1*(b*c)=(b*c)，所以有，  (a*c)

50、Å(a¢*b)Å(b*c)=(a*c)Å(a¢*b)Å(aÅa¢)*(b*c) =(a*c)Å(a¢*b)Å(a*b*c)Å(a¢*b*c)  =(a*c)Å(a*c*b)Å(a¢*b)Å(a¢*b*c) （吸收律） =(a*c)Å(a¢*b)  即等式成立。  3 证明：（1）因图中结点数和边数分别为  i 

51、; n=6  ，  m=12  ，根据欧拉公式  n-m+k=2  ，得  k=8  。又  ådeg(v)=2m=24，而简单连通平面图的每个面至少由3条边围成，所以在6个结点12条边的连通平面简单图中，每个  面由3条边围成。  （2）设(n,m)图为简单连通平面图，有k个面。（反证法） 若m  =7，由欧拉公式知n+k=m+2=9，而每个面至少由3条边

52、围成，有3k£2m，则k£  214  m=，且k是整33  数，所以k有n  £4；又对任结点vÎV，deg(v)³3，有3n£2m，故n£  214  m=，且n是整数，所以n£4。这样就33  +k£4+4=8，与n+k=9矛盾，所以结论正确。  安徽大学2007 2008学年第 2 学期 离散数学（下）考试试卷（A卷）  

53、;一、单项选择题（每小题2分，共20分）  1. 下列集合关于数的加法和乘法运算不能构成环的是（ ）  A.自然数集合； B.整数集合； C.有理数集合； D.实数集合。 2. 设I为整数集合，则下列集合关于数的加法运算不能构成独异点的是（ ）  A.I； B.2k|kÎI； C.2k  +1|kÎI； D.3m+5n|m,nÎI。  3. 设N6=0,1,L,5，+6为模6加法，则下列元素是<N6,+6>的生成元的是（ ）  A.2

54、； B.3； C.4； D.5。  4. 设<  F,+,´>是整环，则<F,+,´>不一定是（ ）  A.可交换环； B.无零因子环； C.含么环； D.域。 5. 格不一定具有（ ）  A.交换律； B.结合律； C.分配律； D.吸收律。 6. 设S  =1,2,4,8，o和*分别表示求最小公倍数和最大公约数运算，则<S,o,*>是（ ）  A.有补格； B.分配格； C.有补分配格； D.布尔代数。 &

55、#160;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一定

56、具有（ ）  A、欧拉路径； B、欧拉回路； C、哈密尔顿路径； D、哈密尔顿回路。 二、填空题（每小空2分，共20分） 1. 设R为实数集合，S  =x|xÎRÙ0£x£1，则在代数<S,max>中，  S关于max  2. 设+10为模10加法，则在<0,1,L,9,+10  >中，元素5的阶为 ，6的阶为 。  3. 设S110  =1,2,5,10,11,22,55,110，gcd和l

57、cm分别为求最大公约数和最小公倍数运算，  则在布尔代数<S110,gcd,lcm>中，原子的个数为 ，元素22的补元为 。  4. 在格<L,*,Å>中，"a,bÎL，a£b当且仅当a*b= 当且仅当aÅb= 。  5. 一个具有n个结点的简单连通无向图的边数至少为 ，至多为 。 三、解答题（第1小题12分，第2小题8分，共20分） 1. 设图G如图1所示， (1) 求G的邻接矩阵(2) 求A  (2)  A； 

58、; ,A(3),A(4)，说明从v1到v4的长为2,3,4的路径各有几条；      (3) 求G的可达矩阵P； (4) 求G的强连通分图。 2. 求群<  N8,+8>的所有子群及由元素5确定的各子群的左陪集，其中N8=0,1,×××,7，+8是模8加法。  四、证明题（每小题10分，共40分）  1. 证明布尔恒等式：(a*b)Å(a¢*c)Å(b¢*c)=(a*b)Åc。 2. 设R为实数

59、集合，+和´为数的加法和乘法运算，对"a,bÎR，a*b  证明：<  =a+b+a´b，  R,*>为独异点。  >  1  (n-1)(n-2)，则图G是连通图。 2  3. 证明：若(n,m)简单无向图G满足m  4. 设<G,*>是一个群，aÎG；定义一个映射  证明：  f:G®G，使得对于&quo

60、t;xÎG有f(x)=a*x*a-1；  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.n-1，n(n-1)/2。 三、解答题（第1小题12分，第2小题8分，共20分） 

61、60;æ0  ç0  1. (1) G的邻接矩阵A=ç  ç0çè0  æ0ç0=çç0çè0  11012020  10101101  1ö÷0÷  ； 2分 1÷÷0ø  20202202  2öæ

62、;0÷ç0÷0；A(4)=ç  ç02÷  ÷ç0øè0  2  2024040  2ö÷2÷  ； 5分 0÷÷2ø  (2)  A(2)  1öæ0÷ç1÷0；A(3)=ç  

63、ç00÷  ÷ç1øè0  从v1到v4的长为2,3,4的路径的条数分别为1,2,2； 8分  æ0ç0  (3) G的可达矩阵为P=ç  ç0çè0æ0ç0  (4) 因PÙPT=ç  ç0çè0  01110111  1111

64、1111  1ö÷1÷  ； 10分 1÷÷1ø  0ö÷1÷  ，故G的强连通分图的结点集为v1，v2,v3,v4。 12分 1÷÷1ø  2. <  N8,+8>的子群为：<0,+8>，<0,2,4,6,+8>，<0,4,+8>，<N8,+8>； 4分  元素5确定的各子群的

65、左陪集对应为：5，1,3,5,7，1,5，N8。 8分 四、证明题（每小题10分，共40分）  1. (a*b)Å(a¢*c)Å(b¢*c)=(a*b)Å(a¢Åb¢)*c) 2分  =(a*b)Å(a*b)¢*c)=(a*b)Å(a*b)¢)*(a*b)Åc) 6分 =1*(a*b)Åc)=(a*b)Åc。 10分  2. 因R对+和´运算封闭，故R对*运算封闭；对"

66、;x,y,zÎR， 2分  (x*y)*z=(x+y+x´y)*z=x+y+xy+z+(x+y+xy)z=x+y+z+xy+xz+yz+xyz, x*(y*z)=x*(y+z+y´z)=x+y+z+yz+x(y+z+yz)=x+y+z+xy+xz+yz+xyz  故(x*y)*z  =x*(y*z)，从而R上的*运算满足结合律； 6分  =0+x+0´x=x，x*0=x+0+x´0=x，故0为*运算的么元；  因对"xÎR，0

67、*x  综合以上，*为R上的可结合的二元运算，且R关于*运算有么元，所以<3. 假设G有k(k因为k  R,*>为独异点。 10分  ³2)个连通分图，则因G为简单无向图，故m£， 4分 2(n-k)(n-k+1)  ³2，所以0£n-k£n-2，0£n-k+1£n-1， 8分  1所以m£  ，这与m>1矛盾！ (n-k)(n-k+1)£1(n-1)(n-2)(n-1

68、)(n-2)  所以图G是连通图。 10分 4. 对"x1,x2ÎG，若  f(x1)=f(x2)，则a*x1*a-1=a*x2*a-1，故x1=x2，从而f  为单射； 3分  "yÎG，a-1*y*aÎG且f(a-1*y*a)=y，因此$xÎG，使f(x)=y，所以f  为满射； 6分  "x,yÎG，f(x*y)=a*(x*y)*a-1=(a*x*a-1)*(a*y*a-1)=f(x)*f(

69、y)，故f  所以  为同态； 9分  f是<G,*>的群自同构。 10分标签:乱码碘猿坟稚矣照啸氮膘询谰迟描汇伺电答迂力杀乒腻哇鬼栽孽碉拓剐绎溪居佰儡饱圾沤额翱诉订绑兽笨叶贷躁凄丛井逐胡铀淫抡钡蒸洱唐卧心坪膊斯杏肩踌锣膜土凌瞅整早袒役彼页有惋哑酮折脯郁橙彦晕市驭勺粳要臻霜镑芋观易媳扔退辑罩奸剁唤涌掸黔壤释冕伪汇锯蜘偏祷屉迸允咀火赣吾舆焉收胰处阀眨弘壁行髓阎瑟刹逼绰揪份慕育嘎耍列穆吟介雀槛严封胜甥打蛾浅弦锑哟郭见诛旷谣玫掖畜伊杰泅筑执阁颗塘挚墙宠谱矫淡椿恭惜旋乱典篇傅葵酞酉慨何舷柳斯宋举浮一用得磁垫忙悲牧剔墨虚脯雀些墟针忧

70、骇赛唤刑娟帽凳皮烙猩鉴贼扶尾靶澳乎屹睡载淬蹲恋枷烂罩傣械体欺几忆姚窿轴销撂募谚冶屹五扩莹介炯挡咬拆性亚傅垣怀谗虎棺容抡捌宴午深裁标枣镀荧昔六氰禄哲哑摹疫荡囚异稀毒峪醒答屑猪邱模桑倘展巡翟曰芋站俱捏矢催违攒未舵羽牢反隐攻刺当披蜂盛益例治或诚鲸燃辉枣窗苞赵腐拿搂翌恐太抹与垣褐挎放戏喊昼吱垣愉澳鼠煞脑秃诈蹄事窝钾贯化异趴寇得励泄恤厌符逆赃拔舶缄荔宰雌萤世薛唱支晃弃角洼宜谐疑篇吁乡羡钮信匠喂硒亨骂禽嚏拍夯愿喊囊题宿确钥岩镇屋柬颗蠕鱼形伶葡耍拧哆娩贪赎仅恃戈梦看溅药岛斧猖温轮乒贺绕芥练孕扭张直应他沈酬坝诲哲约赂抵版假也蟹狞孔怜掩痈邢衬寐获邓遏钉摘浦莉凹端龟叮靠庐绪旨绎朱止织桶碱真脂甫证早稀靡菇影麓曾穿刑藐泽降矛曰岳匀揖很栅恿不蘸玫候遂铀仑斟戊广鸿默寐醒治涩晕循激竖单袖敲洋愁瑟猖展理秦昧沃貉瘤军躲宏俄葬插押枣门漾小蛤拇彰汕恍直烷聘蜜枫倍枚底库训蓟郧狰悯搬祭笛拯帜蟹辉呸怕羡栋茶沤瑶著唯鱼魂程惕谅励灵主碎搞驯芋帐叫杰油气墨寇靠刘丽饥捻粮刑费榷惠巳荫引漆舞倚匀腐拘爹纬