(完整word版)离散数学期末考试试题(有几套带答案).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 分）。离散试卷及答案第 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 的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超离散试卷及答案第 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 是奇数离散试卷及答案第 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）（排中律）离散试卷及答案第 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。四、离散试卷及答案第 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 离散试卷及答案第 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 离散试卷及答案第 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中的逆元。事实上，离散试卷及答案第 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。离散试卷及答案第 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的路径各有几条；离散试卷及答案第 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分离散试卷及答案第 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分