离散数学试题和答案

1、.离散数学试题及答案一、填空题 1 设集合a,b，其中a1,2,3, b= 1,2, 则a - b_; r(a) - r(b) _ .2. 设有限集合a, |a| = n, 则 |r(a×a)| = _.3. 设集合a = a, b, b = 1, 2, 则从a到b的所有映射是_ _, 其中双射的是_.4. 已知命题公式gØ(p®q)r，则g的主析取范式是_.5.设g是完全二叉树，g有7个点，其中4个叶点，则g的总度数为_，分枝点数为_.6 设a、b为两个集合, a= 1,2,4, b = 3,4, 则从aÇb_; aÈb_;ab _ .7.

2、设r是集合a上的等价关系，则r所具有的关系的三个特性是_, _, _.8. 设命题公式gØ(p®(qÙr)，则使公式g为真的解释有_，_, _.9. 设集合a1,2,3,4, a上的关系r1 = (1,4),(2,3),(3,2), r1 = (2,1),(3,2),(4,3), 则r1·r2 = _,r2·r1 =_,r12 =_.10. 设有限集a, b，|a| = m, |b| = n, 则| |r(a´b)| = _.11 设a,b,r是三个集合，其中r是实数集，a = x | -1x1, xÎr, b = x |

3、0x < 2, xÎr,则a-b = _ , b-a = _ , ab = _ , .13. 设集合a2, 3, 4, 5, 6，r是a上的整除，则r以集合形式(列举法)记为_ _. 14. 设一阶逻辑公式g = "xp(x)®$xq(x)，则g的前束范式是_ _.15.设g是具有8个顶点的树，则g中增加_条边才能把g变成完全图。16. 设谓词的定义域为a, b,将表达式"xr(x)$xs(x)中量词消除，写成与之对应的命题公式是_.17. 设集合a1, 2, 3, 4，a上的二元关系r(1,1),(1,2),(2,3), s(1,3),(2,3)

4、,(3,2)。则r×s_, r2_.二、选择题1 设集合a=2,a,3,4，b = a,3,4,1，e为全集，则下列命题正确的是( )。(a)2Îa (b)aÍa (c)ÆÍaÍbÍe (d)a,1,3,4Ìb.2 设集合a=1,2,3,a上的关系r(1,1),(2,2),(2,3),(3,2),(3,3)，则r不具备( ).(a)自反性(b)传递性(c)对称性(d)反对称性1234563 设半序集(a,)关系的哈斯图如下所示，若a的子集b = 2,3,4,5,则元素6为b的( )。(a)下界 (b)上界(c)最小

5、上界 (d)以上答案都不对4 下列语句中，( )是命题。(a)请把门关上 (b)地球外的星球上也有人 (c)x + 5 > 6 (d)下午有会吗？5 设i是如下一个解释：da,b, 则在解释i下取真值为1的公式是( ).(a)$x"yp(x,y) (b)"x"yp(x,y) (c)"xp(x,x) (d)"x$yp(x,y).6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ).(a)(1,2,2,3,4,5) (b)(1,2,3,4,5,5) (c)(1,1,1,2,3) (d)(2,3,3,4,5,6).7. 设

6、g、h是一阶逻辑公式，p是一个谓词，g$xp(x), h"xp(x),则一阶逻辑公式g®h是( ).(a)恒真的 (b)恒假的 (c)可满足的 (d)前束范式.8 设命题公式gØ(p®q)，hp®(q®Øp)，则g与h的关系是( )。(a)gÞh (b)hÞg (c)gh (d)以上都不是.9 设a, b为集合，当( )时abb.(a)ab(b)aÍb(c)bÍa(d)abÆ.10 设集合a = 1,2,3,4, a上的关系r(1,1),(2,3),(2,4),(3,4),

7、则r具有( )。(a)自反性 (b)传递性(c)对称性 (d)以上答案都不对11 下列关于集合的表示中正确的为( )。(a)aÎa,b,c (b)aÍa,b,c(c)ÆÎa,b,c (d)a,bÎa,b,c12 命题"xg(x)取真值1的充分必要条件是( ).(a) 对任意x，g(x)都取真值1. (b)有一个x0，使g(x0)取真值1. (c)有某些x，使g(x0)取真值1. (d)以上答案都不对.13. 设g是连通平面图，有5个顶点，6个面，则g的边数是( ).(a) 9条 (b) 5条 (c) 6条 (d) 11条.14. 设g

8、是5个顶点的完全图，则从g中删去( )条边可以得到树.(a)6 (b)5 (c)10 (d)4.15. 设图g的相邻矩阵为，则g的顶点数与边数分别为( ).(a)4, 5 (b)5, 6 (c)4, 10 (d)5, 8.三、计算证明题1.设集合a1, 2, 3, 4, 6, 8, 9, 12，r为整除关系。(1) 画出半序集(a,r)的哈斯图；(2) 写出a的子集b = 3,6,9,12的上界，下界，最小上界，最大下界；(3) 写出a的最大元，最小元，极大元，极小元。2. 设集合a1, 2, 3, 4，a上的关系r(x,y) | x, yÎa 且 x ³ y, 求 (1)

9、 画出r的关系图；(2) 写出r的关系矩阵.3. 设r是实数集合，s,t,j是r上的三个映射，s(x) = x+3, t(x) = 2x, j(x) x/4,试求复合映射st，ss, sj, jt，sjt.4. 设i是如下一个解释：d = 2, 3, abf (2)f (3)p(2, 2)p(2, 3)p(3, 2)p(3, 3)32320011试求 (1) p(a, f (a)p(b, f (b);(2) "x$y p (y, x).5. 设集合a1, 2, 4, 6, 8, 12，r为a上整除关系。(1) 画出半序集(a,r)的哈斯图；(2) 写出a的最大元，最小元，极大元，极小

10、元；(3) 写出a的子集b = 4, 6, 8, 12的上界，下界，最小上界，最大下界.6. 设命题公式g = Ø(pq)(q(Øpr), 求g的主析取范式。7. (9分)设一阶逻辑公式：g = ("xp(x)$yq(y)"xr(x)，把g化成前束范式.9. 设r是集合a = a, b, c, d. r是a上的二元关系, r = (a,b), (b,a), (b,c), (c,d),(1) 求出r(r), s(r), t(r)；(2) 画出r(r), s(r), t(r)的关系图.11. 通过求主析取范式判断下列命题公式是否等价：(1) g = (pq)

11、(Øpqr) (2) h = (p(qr)(q(Øpr)13. 设r和s是集合aa, b, c, d上的关系，其中r(a, a),(a, c),(b, c),(c, d), s(a, b),(b, c),(b, d),(d, d).(1) 试写出r和s的关系矩阵；(2) 计算rs, rs, r1, s1r1.四、证明题1. 利用形式演绎法证明：pq, rs, pr蕴涵qs。2. 设a,b为任意集合，证明：(a-b)-c = a-(bc).3. (本题10分)利用形式演绎法证明：Øab, ØcØb, cd蕴涵ad。4. (本题10分)a, b为两

12、个任意集合，求证：a(ab) = (ab)b .参考答案一、填空题1. 3; 3,1,3,2,3,1,2,3. 2. .3. a1= (a,1), (b,1), a2= (a,2), (b,2),a3= (a,1), (b,2), a4= (a,2), (b,1); a3, a4.4. (pØqr).5. 12, 3. 6. 4, 1, 2, 3, 4, 1, 2. 7. 自反性；对称性；传递性.8. (1, 0, 0), (1, 0, 1), (1, 1, 0).9. (1,3),(2,2),(3,1); (2,4),(3,3),(4,2); (2,2),(3,3).10. 2m&

13、#180;n.11. x | -1x < 0, xÎr; x | 1 < x < 2, xÎr; x | 0x1, xÎr.12. 12; 6.13. (2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6).14. $x(Øp(x)q(x).15. 21.16. (r(a)r(b)(s(a)s(b).17. (1, 3),(2, 2); (1, 1),(1, 2),(1, 3). 二、选择题 1. c. 2. d. 3. b. 4. b.5. d. 6. c. 7. c.8. a.

14、 9. d. 10. b. 11. b. 13. a. 14. a.15. d三、计算证明题1. (1)(2) b无上界，也无最小上界。下界1, 3; 最大下界是3.(3) a无最大元，最小元是1，极大元8, 12, 90+; 极小元是1.2.r = (1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4).(1) (2)3. (1)sts(t(x)t(x)+32x+32x+3.(2)sss(s(x)s(x)+3(x+3)+3x+6,(3)sjs(j(x)j(x)+3x/4+3, (4)jtj(t(x)t(x)/42x/4 = x/

15、2,(5)sjts(jt)jt+32x/4+3x/2+3.4. (1) p(a, f (a)p(b, f (b) = p(3, f (3)p(2, f (2)= p(3, 2)p(2, 3)= 10= 0. (2) "x$y p (y, x) = "x (p (2, x)p (3, x) = (p (2, 2)p (3, 2)(p (2, 3)p (3, 3)= (01)(01)= 11= 1.5. (1)(2) 无最大元，最小元1，极大元8, 12; 极小元是1.(3) b无上界，无最小上界。下界1, 2; 最大下界2.6. g = Ø(pq)(q(Ø

16、pr)= Ø(Øpq)(q(pr)= (pØq)(q(pr)= (pØq)(qp)(qr)= (pØqr)(pØqØr)(pqr)(pqØr)(pqr)(Øpqr)= (pØqr)(pØqØr)(pqr)(pqØr)(Øpqr)= m3m4m5m6m7 = s(3, 4, 5, 6, 7).7. g = ("xp(x)$yq(y)"xr(x)= Ø("xp(x)$yq(y)"xr(x)= (Ø&q

17、uot;xp(x)Ø$yq(y)"xr(x)= ($xØp(x)"yØq(y)"zr(z)= $x"y"z(Øp(x)Øq(y)r(z)9. (1) r(r)ria(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(r)rr1(a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(r)rr2r3r4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d),

18、 (c,d)；(2)关系图:11. g(pq)(Øpqr)(pqØr)(pqr)(Øpqr)m6m7m3å (3, 6, 7)h = (p(qr)(q(Øpr)(pq)(qr)(Øpqr)(pqØr)(pqr)(Øpqr)(pqr)(Øpqr)(pqØr)(Øpqr)(pqr)m6m3m7å (3, 6, 7)g,h的主析取范式相同，所以g = h.13. (1) (2)rs(a, b),(c, d),rs(a, a),(a, b),(a, c),(b, c),(b, d),

19、(c, d),(d, d), r1(a, a),(c, a),(c, b),(d, c),s1r1(b, a),(d, c).四 证明题1. 证明：pq, rs, pr蕴涵qs(1) prp(2) Ørpq(1)(3) pqp(4) Ørqq(2)(3)(5) Øqrq(4)(6) rsp(7) Øqsq(5)(6)(8) qsq(7)2. 证明：(a-b)-c = (ab)c = a(bc)= a(bc)= a-(bc)3.证明：Øab, ØcØb, cd蕴涵ad(1) ad(附加)(2) Øabp(3) bq(

20、1)(2)(4) ØcØbp(5) bcq(4)(6) cq(3)(5)(7) cdp(8) dq(6)(7)(9) add(1)(8)所以 Øab, ØcØb, cd蕴涵ad.4. 证明：a(ab) = a(ab)a(ab)(aa)(ab)Æ(ab)(ab)ab而 (ab)b= (ab)b= (ab)(bb)= (ab)Æ= ab所以：a(ab) = (ab)b.离散数学试题（a卷及答案）一、（10分）某项工作需要派a、b、c和d 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？(1)若a去，则c和d中要去1个

21、人；(2)b和c不能都去；(3)若c去，则d留下。解 设a：a去工作；b：b去工作；c：c去工作；d：d去工作。则根据题意应有：a®cÅd，Ø(bc)，c®Ød必须同时成立。因此(a®cÅd)Ø(bc)(c®Ød)Û(Øa(cØ d)(Øcd)(ØbØc)(ØcØd)Û(Øa(cØ d)(Øcd)(ØbØc)(ØbØd)Øc(&

22、#216;cØd)Û(ØaØbØc)(ØaØbØd)(ØaØc)(ØaØcØd)(cØ dØbØc)(cØ dØbØd)(cØ dØc)(cØ dØcØd)(ØcdØbØc)(ØcdØbØd)(ØcdØc)(ØcdØcØd)Ûff(

23、6;aØc)ff(cØ dØb)ff(ØcdØb)f(Øcd)fÛ(ØaØc)(ØbcØ d)(ØcdØb)(Øcd)Û(ØaØc)(ØbcØ d)(Øcd)Ût故有三种派法：bd，ac，ad。二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人

24、；则推理化形式为：()()，()()()下面给出证明：(1)() p(2)(c) t(1)，es(3)()() p(4)( c)( c) t(3)，us(5)( c) t(4)，i(6)( c)(c) t(2)(5)，i(7)()() t(6) ，eg三、（10分）设a、b和c是三个集合，则aÌbÞØ(bÌa)。证明：aÌbÛ"x(xaxb)$x(xbxÏa)Û"x(xÏaxb)$x(xbxÏa)ÛØ$x(xaxÏb)Ø"x(

25、xÏbxa)ÞØ$x(xaxÏb)Ø"x(xaxÏb)ÛØ($x(xaxÏb)"x(xaxÏb)ÛØ($x(xaxÏb)"x(xbxa)ÛØ(bÌa)。四、（15分）设a1，2，3，4，5，r是a上的二元关系，且r<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，求r(r)、s(r)和t(r)。解 r(r)ria&

26、lt;2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>s(r)rr1<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>r2<2，2>，<2，4>，<3，4>，<4，4>，<5，

27、1>，<5，5>，<5，4>r3<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>r4<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>r2t(r)ri<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1&g

28、t;，<5，4>，<5，5>。五、（10分）r是非空集合a上的二元关系，若r是对称的，则r(r)和t(r)是对称的。证明 对任意的x、ya，若xr(r)y，则由r(r)ria得，xry或xiay。因r与ia对称，所以有yrx或yiax，于是yr(r)x。所以r(r)是对称的。下证对任意正整数n，rn对称。因r对称，则有xr2yÛ$z(xrzzry)Û$z(zrxyrz)Ûyr2x，所以r2对称。若对称，则xyÛ$z(xzzry)Û$z(zxyrz)Ûyx，所以对称。因此，对任意正整数n，对称。对任意的x、ya，

29、若xt(r)y，则存在m使得xrmy，于是有yrmx，即有yt(r)x。因此，t(r)是对称的。六、（10分）若f：ab是双射，则f1：ba是双射。证明 因为f：ab是双射，则f1是b到a的函数。下证f1是双射。对任意xa，必存在yb使f(x)y，从而f1(y)x，所以f1是满射。对任意的y1、y2b，若f1(y1)f1(y2)x，则f(x)y1，f(x)y2。因为f：ab是函数，则y1y2。所以f1是单射。综上可得，f1：ba是双射。七、（10分）设<s，*>是一个半群，如果s是有限集，则必存在as，使得a*aa。证明 因为<s，*>是一个半群，对任意的bs，由*的封

30、闭性可知，b2b*bs，b3b2*bs，bns，。因为s是有限集，所以必存在ji，使得。令pji，则*。所以对qi，有*。因为p1，所以总可找到k1，使得kpi。对于s，有*(*)*。令a，则as且a*aa。八、（20分）（1）若g是连通的平面图，且g的每个面的次数至少为l(l3)，则g的边数m与结点数n有如下关系：m(n2)。证明 设g有r个面，则2mlr。由欧拉公式得，nmr2。于是， m(n2)。（2）设平面图g<v，e，f>是自对偶图，则| e|2(|v|1)。证明 设g*<v*，e*>是连通平面图g<v，e，f>的对偶图，则g* g，于是|f|v*

31、|v|，将其代入欧拉公式|v|e|f|2得，|e|2(|v|1)。离散数学试题（b卷及答案）一、（10分）证明(pq)(p®r)(q®s)sr证明 因为srÛØr®s，所以，即要证(pq)(p®r)(q®s)Ør®s。(1)Ør 附加前提(2)p®r p(3)Øp t(1)(2)，i(4)pq p(5)q t(3)(4)，i(6)q®s p(7)s t(5)(6)，i(8)Ør®s cp(9)sr t(8)，e二、（15分）根据推理理论证明：每个

32、考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。设p(e)：e是考生，q(e)：e将有所作为，a(e)：e是勤奋的，b(e)：e是聪明的，个体域：人的集合，则命题可符号化为："x(p(x)®(a(x)b(x)，"x(a(x)®q(x)，Ø"x(p(x)®q(x)$x(p(x)b(x)。(1)Ø"x(p(x)®q(x) p(2)Ø"x(Øp(x)q(x) t(1)，e(3)$x(p(x)Øq(x) t(

33、2)，e(4)p(a)Øq(a) t(3)，es(5)p(a) t(4)，i(6)Øq(a) t(4)，i(7)"x(p(x)®(a(x)b(x) p(8)p(a)®(a(a)b(a) t(7)，us(9)a(a)b(a) t(8)(5)，i(10)"x(a(x)®q(x) p(11)a(a)®q(a) t(10)，us(12)Øa(a) t(11)(6)，i(13)b(a) t(12)(9)，i(14)p(a)b(a) t(5)(13)，i(15)$x(p(x)b(x) t(14)，eg三、（10分）某

34、班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解 设a、b、c分别表示会打排球、网球和篮球的学生集合。则：|a|12，|b|6，|c|14，|ac|6，|bc|5，|abc|2，|(ac)b|6。因为|(ac)b|(ab)(bc)|(ab)|(bc)|abc|(ab)|526，所以|(ab)|3。于是|abc|12614653220，25205。故，不会打这三种球的共5人。四、（10分）设a1、a2和a3是全集u的子集，则形如ai¢(ai¢为ai或

35、)的集合称为由a1、a2和a3产生的小项。试证由a1、a2和a3所产生的所有非空小项的集合构成全集u的一个划分。证明 小项共8个，设有r个非空小项s1、s2、sr(r8)。对任意的au，则aai或a，两者必有一个成立，取ai¢为包含元素a的ai或，则aai¢，即有asi，于是uÍsi。又显然有siÍu，所以usi。任取两个非空小项sp和sq，若spsq，则必存在某个ai和分别出现在sp和sq中，于是spsqÆ。综上可知，s1，s2，sr是u的一个划分。五、（15分）设r是a上的二元关系，则：r是传递的Ûr*rÍr。证明 (5

36、)若r是传递的，则<x，y>r*rÞ$z(xrzzsy)Þxrccsy，由r是传递的得xry，即有<x，y>r，所以r*rÍr。反之，若r*rÍr，则对任意的x、y、za，如果xrz且zry，则<x，y>r*r，于是有<x，y>r，即有xry，所以r是传递的。六、（15分）若g为连通平面图，则nmr2，其中，n、m、r分别为g的结点数、边数和面数。证明 对g的边数m作归纳法。当m0时，由于g是连通图，所以g为平凡图，此时n1，r1，结论自然成立。假设对边数小于m的连通平面图结论成立。下面考虑连通平面图g的边

37、数为m的情况。设e是g的一条边，从g中删去e后得到的图记为g¢，并设其结点数、边数和面数分别为n¢、m¢和r¢。对e分为下列情况来讨论：若e为割边，则g¢有两个连通分支g1和g2。gi的结点数、边数和面数分别为ni、mi和ri。显然n1n2n¢n，m1m2m¢m1，r1r2r¢1r1。由归纳假设有n1m1r12，n2m2r22，从而(n1n2)(m1m2)(r1r2)4，n(m1)(r1)4，即nmr2。若e不为割边，则n¢n，m¢m1，r¢r1，由归纳假设有n¢m¢r¢2