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

专业好文档离散数学试题(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)(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)(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,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，证明：(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 （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)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(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）六、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,则有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的同一个连通分支中，则，不是图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: (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) 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分，总计20分）1、用等值演算算法证明等值式 (pq)(pq)p2、构造下面命题推理的证明如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分，总计30分）1、设，求公式：的真值。2、设集合上的关系 ，求出它的自反闭包，对称闭包和传递闭包。3、设上的整除关系，是否为上的偏序关系？若是，则：1、画出的哈斯图；（10分）2、求它的极小元，最大元，极大元，最大元。（5分）四、用推导法求公式的主析取范式和主合取范式。（本大题10分）答案：一、 选择题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（(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. 该公式的真值是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.阶实数矩阵，关于矩阵的加法和乘法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.简单回路 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 若连通平面图有4个结点，3个面，则有条边。7 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有个度数为1的结点。8 无向图是由（）棵数组成的森林，至少要添加条边才能使成为一棵树。三、求解题（20分） 1 试写出中每个子群及其相应的左陪集。 （6分）274412313652 若一个有向图是欧拉图，它是否一定是强连通的？若一个有向图是强连通的，它是否一定是欧拉图？说明理由。 （6分）3 有向图如图3-1所示。（1）求的邻接矩阵； （2分）（2）中到长度为4的路径有几条？ （2分）（3）中到自身长度为3的回路有几条？ （2分）（4）是哪类连通图？ （2分）图3-1四、证明题（30分）1 设是一群，。定义：，。证明也是一群。 2 证明：（1）证明在格中成立：。 （5分）（2）证明布尔恒等式：。 （5分）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 ，； 2 ，；3 5，；4 交换群；5 同构；6 5；7 9；8 。三、求解题1 解：子群有：，。的左陪集为：，的左陪集为：，的左陪集为：，2 答：（1）一个有向欧拉图一定是强连通图。因为是欧拉图，存在欧拉回路，中的每个结点至少在中出现一次。因而中任意两点，都在中，相互可达，故是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。3 解：（1） （2）由中可知，到长度为4的路径有条（56748，）。（3）由中可知，到自身长度为3的回路有1条（）。（4）是单向连通图。四、证明题1 证明：显然是上的二元运算（即满足封闭性），要证是群，需证结合律成立，同时有单位元，每个元素有逆元。 ，有 运算是可结合的。 其次，是的单位元。事实上，有； 最后证明，是在中的逆元。事实上， 由以上证明，是群。2 证明：（1） （公式(13)分配不等式）又因为，所以。（2）因为，所以有， （吸收律）即等式成立。 3 证明：（1）因图中结点数和边数分别为，根据欧拉公式，得。又，而简单连通平面图的每个面至少由3条边围成，所以在6个结点12条边的连通平面简单图中，每个面由3条边围成。（2）设图为简单连通平面图，有个面。（反证法） 若，由欧拉公式知，而每个面至少由3条边围成，有，则，且是整数，所以；又对任结点，有，故，且是整数，所以。这样就有，与矛盾，所以结论正确。安徽大学2007 2008学年第 2 学期离散数学（下）考试试卷（a卷）一、单项选择题（每小题2分，共20分）1. 下列集合关于数的加法和乘法运算不能构成环的是（ ）a.自然数集合； b.整数集合； c.有理数集合； d.实数集合。2. 设为整数集合，则下列集合关于数的加法运算不能构成独异点的是（ ）a.； b.； c.； d.。3. 设，为模加法，则下列元素是的生成元的是（ ）a.2； b.3； c.4； d.5。4. 设是整环，则不一定是（ ）a.可交换环； b.无零因子环； c.含么环； d.域。5. 格不一定具有（ ）a.交换律； b.结合律； c.分配律； d.吸收律。6. 设，和分别表示求最小公倍数和最大公约数运算，则是（ ）a.有补格； b.分配格； c.有补分配格； d.布尔代数。7. 一个含个结点的无向图中有个结点的度数分别为，则第个结点的度数不可能是（ ）a.0； b.1； c.2； d.4。8. 设连通的简单平面图中有10条边和5个面，则的结点数为（ ）a.6； b.7； c.8； d.9。9. 设无向树中有个结点度数为，个结点度数为，个结点度数为，则中的树叶数为（ ）a.10； b.11； c.12； d.13。10.设为连通的无向图，若仅有个结点的度数是奇数，则一定具有（ ）a、欧拉路径； b、欧拉回路； c、哈密尔顿路径； d、哈密尔顿回路。二、填空题（每小空2分，共20分）1. 设为实数集合，则在代数中，关于运算的么元是 ，零元是 。2. 设为模加法，则在中，元素的阶为 ，的阶为 。3. 设，和分别为求最大公约数和最小公倍数运算，则在布尔代数中，原子的个数为 ，元素的补元为 。4. 在格中，当且仅当 当且仅当 。5. 一个具有个结点的简单连通无向图的边数至少为 ，至多为 。三、解答题（第1小题12分，第2小题8分，共20分）1. 设图如图1所示，(1) 求的邻接矩阵；(2) 求，说明从到的长为的路径各有几条；(3) 求的可达矩阵； (4) 求的强连通分图。2. 求群的所有子群及由元素确定的各子群的左陪集，其中，是模加法。四、证明题（每小题10分，共40分）1. 证明布尔恒等式：。2. 设为实数集合，和为数的加法和乘法运算，对，证明：为独异点。3. 证明：若简单无向图满足，则图是连通图。4. 设是一个群，；定义一个映射，使得对于有；证明：是安徽大学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.，； 2.，； 3.，； 4.，； 5.，。三、解答题（第1小题12分，第2小题8分，共20分）1. (1) 的邻接矩阵； 2分(2) ； 5分从到的长为的路径的条数分别为； 8分(3) 的可达矩阵为； 10分(4) 因，故的强连通分图的结点集为，。 12分2. 的子群为：，； 4分元素确定的各子群的左陪集对应为：，。 8分四、证明题（每小题10分，共40分）1. 2分 6分。 10分2. 因对和运算封闭，故对运算封闭；对， 2分,故，从而上的运算满足结合律； 6分因对，故为运算的么元； 综合以上，为上的可结合的二元运算，且关于运算有么元，所以为独异点。 10分3. 假设有个连通分图，则因为简单无向图，故， 4分因为，所以， 8分所以，这与矛盾！所以图是连通图。 10分4. 对，若，则，故，从而为单射； 3分，且，因此，使，所以为满射； 6分，故为同态； 9分所以是的群自同构。 10分if we dont do that it will go on and go on. we have to stop it; we need the courage to do it.his comments came hours after fifa vice-president jeffrey webb - also in london for the fas celebrations - said he wanted to meet ivory coast international toure to discuss his complaint.cska general director roman babaev says the matter has been exaggerated by the ivorian and the british media.blatter, 77, said: it has been decided by the fifa congress that it is a nonsense for racism to be dealt with with fines. you can always find money from somebody to pay them.it is a nonsense to have matches played without spectators because it is against the spirit of football and against the visiting team. it is all nonsense.we can do something better to fight racism and discrimination.this is one of the villains we have today in our game. but it is only with harsh sanctions that racism and discrimination can be washed out of football.the (lack of) air up there watch mcayman islands-based webb, the head of fifas anti-racism taskforce, is in london for the football associations 150th anniversary celebrations and will attend citys premier league match at chelsea on sunday.i am going to be at the match tomorrow and i have asked to meet yaya toure, he told bbc sport.for me its about how he felt and i would like to speak to him first to find out what his experience was.uefa hasopened disciplinary proceedings against cskafor the racist behaviour of their fans duringcitys 2-1 win.michel platini, president of european footballs governing body, has also ordered an immediate investigation into the referees actions.cska said they were surprised and disappointed by toures complaint. in a statement the russian side added: we found no racist insults from fans of cska.baumgartner the disappointing news: mission aborted.the supersonic descent could happen as early as sunda.the weather plays an important role in this mission. starting at the ground, conditions have to be very calm - winds less than 2 mph, with no precipitation or humidity and limited cloud cover. the balloon, with capsule attached, will move through the lower level of the atmosphere (the troposphere) where our day-to-day weather lives. it will climb higher than the tip of mount everest (5.5 miles/8.85 kilometers), drifting even higher than the cruising altitude of commercial airliners (5.6 miles/9.17 kilometers) and into the stratosphere. as he crosses the boundary layer (called the tropopause),e can expect a lot of turbulence.the balloon will slowly drift to the edge of space at 120,000 feet ( then, i would assume, he will slowly step out onto something resembling an olympic diving platform.below, the earth becomes the concrete bottom of a swimmi