电大离散数学期末考试试题(有几套带答案).doc
《电大离散数学期末考试试题(有几套带答案).doc》由会员分享,可在线阅读,更多相关《电大离散数学期末考试试题(有几套带答案).doc(14页珍藏版)》请在三一文库上搜索。
1、专业好文档离散数学试题(A卷及答案)一、证明题(10分)1)(P(QR)(QR)(PR)R证明: 左端(PQR)(QP)R)(PQ)R)(QP)R)(PQ)R)(QP)R)(PQ)(QP)R(PQ)(PQ)RTR(置换)R2)$x(A(x)B(x) xA(x)$xB(x)证明 :$x(A(x)B(x)$x(A(x)B(x)$xA(x)$xB(x)xA(x)$xB(x)xA(x)$xB(x)二、求命题公式(P(QR)(PQR)的主析取范式和主合取范式(10分)证明:(P(QR)(PQR)(P(QR)(PQR)(P(QR))(PQR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR
2、)(PQR)m0m1m2m7M3M4M5M6三、推理证明题(10分)第 14 页 共 14 页1) CD, (CD) E, E(AB), (AB)(RS)RS证明:(1) (CD)E (2) E(AB) (3) (CD)(AB)(4) (AB)(RS) (5) (CD)(RS) (6) CD (7) RS2) 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)
3、(11)Q(y)$x(P(x)R(x)四、设m是一个取定的正整数,证明:在任取m1个整数中,至少有两个整数,它们的差是m的整数倍证明 设,为任取的m1个整数,用m去除它们所得余数只能是0,1,m1,由抽屉原理可知,这m1个整数中至少存在两个数和,它们被m除所得余数相同,因此和的差是m的整数倍。五、已知A、B、C是三个集合,证明A-(BC)=(A-B)(A-C) (15分)证明 x A-(BC) x Ax(BC) x A(xBxC) (x AxB)(x AxC) x(A-B)x(A-C) x(A-B)(A-C)A-(BC)=(A-B)(A-C)六、已知R、S是N上的关系,其定义如下:R=| x,
4、yNy=x2,S=| x,yNy=x+1。求R-1、R*S、S*R、R1,2、S1,2(10分)解:R-1=| x,yNy=x2,R*S=| x,yNy=x2+1,S*R=| x,yNy=(x+1)2,七、若f:AB和g:BC是双射,则(gf)-1=f-1g-1(10分)。证明:因为f、g是双射,所以gf:AC是双射,所以gf有逆函数(gf)-1:CA。同理可推f-1g-1:CA是双射。因为f-1g-1存在z(g-1f-1)存在z(fg)gf(gf)-1,所以(gf)-1=f-1g-1。R1,2=,,S1,2=1,4。八、(15分)设是半群,对A中任意元a和b,如ab必有a*bb*a,证明:(
5、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。试证:若n2,则G是哈密尔顿图 证明 若n2,则2nm23m6
6、 (1)。若存在两个不相邻结点、使得d()d()m,则有2nm(m2)(m3)mm23m6,与(1)矛盾。所以,对于G中任意两个不相邻结点、都有d()d()m,所以G是哈密尔顿图。离散数学试题(B卷及答案)一、证明题(10分)1)(PQ)(P(QR)(PQ)(PR)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(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)
7、xP(x)xQ(x)x(P(x)Q(x)二、求命题公式(PQ)(PQ) 的主析取范式和主合取范式(10分)解:(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QPQ)(PQ)M1m0m2m3三、推理证明题(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 CP2) 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
8、(c) T(3),US(5)Q(c) T(2)(4),I(6)$x Q(x) T(5),EG四、例5在边长为1的正方形内任意放置九个点,证明其中必存在三个点,使得由它们组成的三角形(可能是退化的)面积不超过1/8(10分)。证明:把边长为1的正方形分成四个全等的小正方形,则至少有一个小正方形内有三个点,它们组成的三角形(可能是退化的)面积不超过小正方形的一半,即1/8。五、已知A、B、C是三个集合,证明A(BC)=(AB)(AC) (10分)证明:x A(BC) x Ax(BC) x A(xBxC)( x AxB)(x AxC) x(AB)x AC x(AB)(AC)A(BC)=(AB)(AC
9、)六、p=A1,A2,An是集合A的一个划分,定义R=|a、bAi,I=1,2,n,则R是A上的等价关系(15分)。证明:aA必有i使得aAi,由定义知aRa,故R自反。a,bA,若aRb ,则a,bAi,即b,aAi,所以bRa,故R对称。a,b,cA,若aRb 且bRc,则a,bAi及b,cAj。因为ij时AiAj=F,故i=j,即a,b,cAi,所以aRc,故R传递。总之R是A上的等价关系。七、若f:AB是双射,则f-1:BA是双射(15分)。证明: 对任意的xA,因为f是从A到B的函数,故存在yB,使f,f-1。所以,f-1是满射。对任意的xA,若存在y1,y2B,使得f-1且f-1,
10、则有f且f。因为f是函数,则y1=y2。所以,f-1是单射。 因此f-1是双射。八、设是群,和是的子群,证明:若ABG,则AG或BG(10分)。证明 假设AG且BG,则存在aA,aB,且存在bB,bA(否则对任意的aA,aB,从而AB,即ABB,得BG,矛盾。)对于元素a*bG,若a*bA,因A是子群,a-1A,从而a-1 * (a*b)b A,所以矛盾,故a*bA。同理可证a*bB,综合有a*bABG。综上所述,假设不成立,得证AG或BG。九、若无向图G是不连通的,证明G的补图是连通的(10分)。证明 设无向图G是不连通的,其k个连通分支为、。任取结点、G,若和不在图G的同一个连通分支中,则
11、,不是图G的边,因而,是图的边;若和在图G的同一个连通分支中,不妨设其在连通分支(1)中,在不同于的另一连通分支上取一结点,则,和,都不是图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:
12、(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是奇数(2)只有王荣努力学习,她才能取得好成绩。(B)设p:王荣努力学习,q:王荣取得好成绩(3)每列火车都比某些汽车快。(C)设F(x):x是火车,G(y):y是汽车,H(x,y):x比y快。A: pq pq pq B: pq qp pqC: x $y (F(x
13、) 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 1C: 3 6 7 8 D: 1 二、证明(本大题共2小题,第1小题10分,第2小题10分,
14、总计20分)1、用等值演算算法证明等值式 (pq)(pq)p2、构造下面命题推理的证明如果今天是星期三,那么我有一次英语或数学测验;如果数学老师有事,那么没有数学测验;今天是星期三且数学老师有事,所以我有一次英语测验。三、计算(本大题共4小题,第1小题5分,第2小题10分,第3小题15分,总计30分)1、设,求公式:的真值。2、设集合上的关系 ,求出它的自反闭包,对称闭包和传递闭包。3、设上的整除关系,是否为上的偏序关系?若是,则:1、画出的哈斯图;(10分)2、求它的极小元,最大元,极大元,最大元。(5分)四、用推导法求公式的主析取范式和主合取范式。(本大题10分)答案:一、 选择题1. A
15、: 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((pq) (qq)) (分配律) p((pq)1) (排中律) p (pq) (同一律) p (吸收律)2.解:p:今天是星期三。 q:我有一次英语测验。 r:我有一次数学测验。 s:数学老师有事。 前提:p(qr) , sr , ps 结论:q 证明:ps 前提引入p 化简p(qr) 前提引入qr 假言推理s 化简sr 前提引入r 假言推理q 析取三段论推理正确。三、计算1. 该公式的真值是
16、1,真命题。或者2、3、(1) 是上的偏序关系。(2)极小元、最小元是1,极大元、 最大元是24。四、安徽大学2004-2005学年第二学期离散数学期末考试试卷(A卷)参考答案一、单项选择1 在自然数集上,下列哪种运算是可结合的?( )A. B. C. D. 2 下列代数系统中,哪个是群?( )A. ,*是模7加法 B. (有理数集合),*是一般乘法C. (整数集合),*是一般减法 D. ,*是模11乘法3 若是的真子群,且,则有( )。A. 整除 B. 整除 C. 整除且 整除 D. 不整除且 不整除4 下面哪个集合关于指定的运算构成环?( )A. ,关于数的加法和乘法abcdefgB.阶实
17、数矩阵,关于矩阵的加法和乘法C. ,关于数的加法和乘法D. ,关于矩阵的加法和乘法5 在代数系统中,整环和域的关系为( )。A. 域一定是整环 B.域不一定是整环 C. 整环一定是域 D. 域一定不是整环6 是自然数集,是小于等于关系,则是( )。A. 有界格 B.有补格 C. 分配格 D. 有补分配格7 图1-1给出的哈斯图表示的格中哪个元素无补元?( )A. B. C. D. 图1-18 给定下列序列,可构成无向简单图的结点度数序列的是( )。A.(1,1,2,2,3) B.(1,3,4,4,5)C.(0,1,3,3,3) D.(1,1,2,2,2)9 欧拉回路是( )。A.路径 B.简单
18、回路 C.既是基本回路也是简单回路 D.既非基本回路也非简单回路10 哈密尔顿回路是( )。A.路径 B.简单回路 C.既是基本回路也是简单回路 D.既非基本回路也非简单回路二、填空题(以下每个下划线为一空,请按要求填入合适的内容。每空2分,共30分)。1 设是非空有限集,代数系统中,对运算的单位元是,零元是,对运算的单位元是。 a b ca a b a b cc c 2 在运算表2-1中空白处填入适当符号,使成为群。,。3 设,是群的子群,其中,是模12加法,则有个真子群,的左陪集,。4设是一个布尔代数,如果在上定义二元运算为:,则是一个。表2-15 任何一个具有个元素的有限布尔代数都是。6
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 电大 离散数学 期末 考试 试题 有几套带 答案
链接地址:https://www.31doc.com/p-5098432.html