离散数学试题与答案

1、离散数学试题与答案【篇一：离散数学试题及答案】一、填空题1设集合a,b,其中a=1,2,3,b=1,2,则a-b=;_.3. 设集合a=a,b,b=1,2,则从a到b的所有映射是,其中双射的是4. 已知命题公式g=?(p?q)Ar,则g的主析取范式是5. 设g是完全二叉树，g有7个点，其中4个叶点，则g的总度数为，分枝点数为.7 .设r是集合a上的等价关系，则r所具有的关系的三个特性是8 .设命题公式g=?(p?(q?r),则使公式g为真的解释有，9 .设集合a=1,2,3,4,a上的关系ri=(1,4),(2,3),(3,2),ri=(2,1),(3,2),(4,3),则r1?r2=,r2?

2、r110 .设有限集a,b，|a|=m,|b|=n,则|?(a?b)|=11设a,b,r是三个集合，其中r是实数集，a=x|-1<x<1,x?r,b=x|0<x2,x?则a-b=,b-a=,aAb=,.13 .设集合a=2,3,4,5,6,r是a上的整除，则r以集合形式(列举法)记为14 .设一阶逻辑公式g=?xp(x)?xq(x)，则g的前束范式是15 .设g是具有8个顶点的树，则g中增加条边才能把g变成完全图。?(a)-?(b)r1216 .设谓词的定义域为a,b,将表达式？xr(x)-?xs(x)中量词消除，写成与之对应的命题公式是17 .设集合a=1,2,3,4,a上

3、的二元关系r=(1,1),(1,2),(2,3),s=(1,3),(2,3),(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)反对称性则元3设半序集(a,w菠系啪哈斯图如下所示，若a的子集素6为b的()。(a)下界(b)上界(c)最小上界(d)以上答案都不对4下列语句中，()是命题。(a)请把门关上(b

4、)地球外的星球上也有人(c)x+56(d)下午有会吗？5设i是如下一个解释：d=a,b,p(a,a)p(a,b)p(b,a)p(b,b)1010则在解释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 .设g、h是一阶逻辑公式，p是一个谓词，g=?xp(x),h=?xp(x),则一阶逻辑公式g?h是().(a)恒真

5、的(b)恒假的可满足的(d)前束范式.8设命题公式g=?(p?q),h=p?(q?p)，则g与h的关系是()。(a)g?h(b)h?g(c)g=h(d)以上都不是.9设a,b为集合,当()时ab=b.(a)a=b(b)a?b(c)b?a(d)a=b=?.10设集合a=1,2,3,4,a上的关系r=(1,1),(2,3),(2,4),(3,4),则r具有()。(a)自反性(b)传递性对称性(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，

6、g(x)都取真值1.(b)有一个x0，使g(x0)取真值1.有某些x,使g(x0)取真值1.(d)以上答案都不对.13. 设g是连通平面图，有5个顶点，6个面，则g的边数是().(a)9条(b)5条(c)6条(d)11条.14. 设g是5个顶点的完全图，则从g中删去()条边可以得到树.(a)6(b)5(c)10(d)4.1111?0100?，则1011?0101?0110?0?1的相邻矩阵为?1?1?115.设图gg的顶点数与边数分别为().(a)4,5(b)5,6(c)4,10(d)5,8.三、计算证明题1.设集合a=1,2,3,4,6,8,9,12,r为整除关系。(1) 画出半序集(a,r

7、)的哈斯图；(2) 写出a的子集b=3,6,9,12的上界，下界，最小上界，最大下界；(3) 写出a的最大元，最小元，极大元，极小元。2.设集合a=1,2,3,4,a上的关系r=(x,y)|x,y?a且x?y,求1) )画出r的关系图；2) )写出r的关系矩阵.3) 设r是实数集合，？,？,？是r上的三个映射，？(x)=x+3,?(x)=2x,?(x)=x/4,试求复合映射?，?,?,?，?.4) 设i是如下一个解释：d=2,3,a3b2f(2)3f(3)2p(2,2)p(2,3)p(3,2)p(3,3)0011试求(1)p(a,f(a)Ap(b,f(b);(2)?x?yp(y,x).5.设集

8、合a=1,2,4,6,8,12，为a上整除关系。(1) 画出半序集(a,r)的哈斯图；(2) 写出a的最大元，最小元，极大元，极小元；(3) 写出a的子集b=4,6,8,12的上界，下界，最小上界，最大下界.6. 设命题公式g=?(pfq)V(qA(?pfr),求g的主析取范式。7. (9分)设一阶逻辑公式：g=(?xp(x)V?yq(y)f?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. 通过求主析取范式

9、判断下列命题公式是否等价：(1) g=(pAq)V(?pAqAr)(2) h=(pV(qAr)A(qV(?pAr)13.设r和s是集合a=a,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)计算r?s,rUs,r1,s1?r1.四、证明题1 .利用形式演绎法证明：pfq,rs,pVr蕴涵qVs。2 .设a,b为任意集合，证明：(a-b)-c=a-(bUc).3 .(本题10分)利用形式演绎法证明：?aVb,?c-?b,c-藤涵ado4 .(本题10分)a,b为两个任意集合，求证

10、：a(aAb)=(aUb)b.参考答案一、填空题1. 3;3,1,3,2,3,1,2,3.2. 2.n23. ?1=(a,1),(b,1),?2=(a,2),(b,2),?3=(a,1),(b,2),?4=(a,2),(b,1);?3,?4.4. (pA?qAr).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?n.11. x|-1<x0,x?r;x|1x2,x?r;x|0<x<1

11、,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)Vq(x).15.21.【篇二：离散数学练习题及答案】的表示方法有两种：法。请把“奇整数集合”表示出，k?z来。1、列举；描述；x|x?2k?12 、无向连通图g含有欧拉回路的充分必要条件是2*、连通有向图d含有欧拉回路的充分必要条件是d中每个结点的入度=出度.3 、设r是集合a上的等价关系，则r所具有的关系的三个特性是自反性、对称性、传递性.4 、有限图g是树的一个等价定义是：.5、设n(x)：x是自然数，z(y)；y是整数，则命题“自然数

12、都是整数，而有的整数不是自然数”符号化为?x(n(x)?z(x)?x(z(x)?n(x)6 、在有向图的邻接矩阵中，第i行元素之和,第j列元素之和分别为结点v的出度和结点v的入度7 、设a，b为任意命题公式，c为重言式，若a?c?b?c，那么命题a?b是重言式的真值是18 、命题公式?(p?q)的主析取范式为9、设图g=v,e和g?=v?,e?,若g?是g的真子图，若，贝Ug?是g的生成子图.v?v或e?e;v?v,e?e10、在平面图g?v,e?中,则11、设a?a,b,?deg(r)=淇中r(i=1,2,rig的面iiri?1b?1,2，则从a到b的所有映射是11、?1=(a，1)，(b，

13、1)；?2=(a，2)，(b，2)；?3=(a，1)，(b，2)；?4=(a，2)，(b，1)12、表达式？x?yl(x,y)中谓词的定义域是a,b,c,将其中的量词消除，写成与之等价的命题公式为12、(l(a，a)?l(a，b)?l(a，c)?(l(b，a)?l(b，b)?l(b，c)?(l(c，a)?l(c，b)?l(c，c)12*、设个体域d=a,b,公式？x(g(x)?yh(x,y)消去量词化为13、含有三个命题变项p，q，r的命题公式p?q的主析取范式是14、设r，s都是集合a上的等价关系，则对称闭包s(r?s)=15、设g是连通平面图，v,e,r分别表示g的结点数，边数和面数，则v

14、,e和r满足的关系式是v?r?e?16、设g是n个结点的简单图，若g，则g一定是哈密顿图.17、一个有向树t称为根树，若称为树叶.若有向图t恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；出度为0的结点.18、图的通路中边的数目称为结点不重复的通路是通路.边不重复的通路是通路.通路长度；初级；简单.19、设a和b为有限集，|a|=m，|b|=n，则有个从a到b的关系，有个从a到b的函数，其中当m?n时有个入射，当m=n时，有个双射。19、2m*nm,nm,cn?m!,m!2a?n|n?n(是/不是)可数的。是20、集合21、设l?1,2,3,4,12?上的整除关系?a1,a2a1,a

15、2?l,a1整除a2?在l上定义两个二元运算?和?：对任意a,b?l，a?b?glb(a,b)，a?b?lub(a,b)o请填空(在横线上填是或不是)：是是是不是代数系统?l,?,?格。代数系统?l,?,?有界格。代数系统？l,?,?有补格。代数系统？l,?,?分配格。二、单项选择题(选择一个正确答案的代号，填入括号中)1 、设命题公式g=?(p?q)，h=p?(q?p)，则g与h的关系是(a)。ag?hbh?gcg=hd以上都不是2 、下列命题公式等值的是(c)(a)?p?q,p?q(c)q?(p?q),?q?p?q(b)a?(a?b),?a?(a?b)(d)?a?(a?b),b3、设v=a

16、,b,c,d,与v能构成强连通向的边集e=(a)(a) a,b,a,c,d,a,b,d,c,d(b)a,d,b,a,b,c,b,d,d,c(c)a,c,b,a,b,c,d,a,d,c(d)a,d,b,a,b,d,c,d,d,c4、设l(x)：x是演员，j(x)：x是老师，a(x,y)：x佩服y.那么命题“所有演员都佩服某些老师”符号化为(b)(a)?xl(x)?a(x,y)(b) ?x(l(x)?y(j(y)?a(x,y)(c)?x?y(l(x)?j(y)?a(x,y)(d)?x?y(l(x)?j(y)?a(x,y)5 、在由3个元素组成的集合上，可以有(d)种不同的关系。(a)3(b)8(c

17、)9(d)5126、设s1=?,s2=?,s3=p(?),s4=p(?)则命题为假的是(a)(a)s2?s4(b)s1?s3(c)s2?s4(d)s4?s37 、设g是连通平面图，有v个结点，e条边，r个面，则r=(a)(a)ev2(b)ve2(c)ev2(d)ev28 、下列命题正确的是(a)。a?=?b?=?ca?a，b，cd?a，b，c9、设a,b,c都是集合，如果a?c=b?c,则有(c)(a)a=b(b)a?b(c)当ac=bc时，有a=b(d)当c=u时，有a?b10 、设(b,?,?,0,1)是布尔代数，?a,b?b,a?b，则下式不成立的是(d)(a)ab?0(b)a?b?1(

18、c)a?b?a(d)a?b?111 、下面给出的一阶逻辑等价式中，(a)是错的。a?x(a(x)?b(x)=?xa(x)?xb(x)ba?xb(x)=?x(a?b(x)c?x(a(x)?b(x)=?xa(x)?xb(x)d?xa(x)=?x(?a(x)三、多重选择题(每道小题都可能有一个以上的正确选项，须选出所有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。)1、命题公式(pA(pfq)fq是式。1 1)重言(2)矛盾(3)可满足(4)非永真的可满足2 、给定解释i=(d,ic)=(整数集，f(x,y):f(x,y)=x-y；g(x,y):g(x,y)=x+y；p(x,y):xy)，

19、下列公式中在解释i下为真。(1)p(f(x,y),g(x,y)(2)?x?yp(f(x,y),g(x,y)？x?y(p(x,y)-p(f(x,y),x)(4)?x?yp(f(x,y),g(x,y)3、A是集合，a=10,则p(a)=。(1)100(2)99(3)2048(4)1024(5)5124、集合A=x|x是整数，x230,B=x|x是质数，x20,c=1,3,5,则 (a?b)?c=; (b?a)?c=; (c?a)?(b?a)=; (b?c)?a=。(1)1,2,3,5(2)?(3)0(4)1,3,5,7,11,13,17,19(5)1,3,5,7(6)7,11,13,17,195、

20、设a、b、c是集合，下列四个命题中，在任何情况下都是正确的。(1)若a?b且bGc,贝fjac(2)若a?b且bGc,贝fja?c(3)若aGb且b?c,则a?c(4)若aGb且b?c，则aGc6、设集合A=a,b,c,d,e,f,g,A的一个划分？=a,b,c,d,e,f,g,则?所对应的等价关系有个二元组。(1)14(2)15(3)16(4)17(5)8(6)49(7)5127、s=1,2,3,4,5,6,7,8,9,10,11,12,号是s上的整除关系。s的子集B=2,4,6,则在s,w中，B的最大元是;B的最小元是;B的上确界是;B的下确界是。(1)不存在的(2)36(3)24(4)1

21、2(5)6(6)1(7)28、设有有限布尔代数(b,+,*,0,1，则)b=能成立。(1)1(2)2(3)3(4)4(5)5(6)8(7)99、g=0,1,2,?,n,nGn,定义？为模n加法，即x?y=(x+y)modn，则代数系统(g，?)。(1)是半群但不是群(2)是无限群(3)是循环群(4)是变换群(5)是交换群10、仅有一个结点的图称为()，当然也是()(1)零图(2)平凡图(3)补图(4)子图1.1、3。2.4。3.4。4.1；4；2；2。5.4。7.1；7；4；7。8.2、4、6。9.3、5。10.2；1。四、化简解答题1、(1)设图g(如第1题图)，作图g的嵌入图，说明图g是平

22、面图.第1题图1、(1)图g的嵌入图，如第12题答案图.故图g为平面图(4分)第12题答案图(2)在具有n个顶点的完全图kn中删去多少条边才能得到树？解：n个顶点的完全图kn中共有6.4。n?(n?1)条边，n个顶点的树应有n?1条边，于是，删2n?(n?1)(n?1)?(n?2)?(n?1)?去的边有：。222、判别谓词公式?x?yf(x,y)?y?xf(x,y)的类型.2、设i为任意一个解释，d为i的个体域.若在解释i下，该公式的前件为0，无论?y?xf(x,y)如何取值，?x?yf(x,y)?y?xf(x,y)为1；若在解释i下，该公式的前件为1，则?x0?d,使得?yf(x,y)为1，

23、它蕴含着?y?d,f(x0,y?)为1?xf(x,y?)为1，由y?的任意性，必有？y?xf(x,y)为1,于是？x?yf(x,y)?y?xf(x,y)为1.所以，?x?yf(x,y)?y?xf(x,y)是永真式3、化简集合表达式：(a?b?c)?(a?c)(c?(cb)a)3、(a?b?c)?(a?c)(c?(cb)?a)=(a?c)(c?a)(两次用吸收律)=(a?c)?(c?a)=(a?c)?(c?c)?a?(a?c)=(a?c)?a=a4、判断下列哪些运算结果是对的？哪些是错的？请将错误的运算结果更正过来(1)?(2)?(3)?,?(4)?,?,?(5)(a?b)?b?a(6)(a?b

24、)?b?a(7)a?a?a(8)(a?b)?a?4、(1)对(2)错应为?(3)对(4)错应为?(5)错应为a?b(6)错应为a?b(或a?b或aab)(7)错应为?，即a?a?a?a?a?a?(8)对5、将命题公式?p?q?(?r?p)化为只含?和?的尽可能简单的等值式5、?p?q?(?r?p)?(p?q)?(r?p)(优先级有误)?(p?q)?(?p?r)不惟一.(1)v1e5v5e7v2e2v3(2)v5e6v2e2v3e3v4e8v2e7v5v254(3)v2e7v5e6v2(4)v1e1v2e2v3e3v4e8v2e6v5ev46、(1)初级通路；(2)简单回路；(3)初级回路；(4

25、)简单通路.e3vev7、试问n取何值时，无向完全图kn，存在一条欧拉回路？6、设图g如右图.已知通路7、由于kn有n个结点，并且每个结点的度数均为n1，于是，当n为奇数时，kn的每个结点的度数都是偶数，所以存在一条欧拉回路8、已知(l，*，?)是格，且二元运算*和?满足分配律，?a,b,c?l，化简表达式(a*b)?(a*c)*(a*b)?(b*c)解答：(a*b)?(a*c)*(a*b)?(b*c)=(a*b)?(a*c)*(b*c)(分配律)=(a*b)?(a*b)*c)(幂等律)=a*b(吸收律)9 、化简(?p?(?q?r)?(q?r)?(p?r)。10 、(?p?(?q?r)?(q

26、?r)?(p?r)=(?p?q?q?p)?r=(?p?q?p)?r=r11 、试将一阶逻辑公式?x?yp?x,y?yq?y?r?x?化成前束范式。解：【篇三：离散数学试卷及答案】t>一、填空20%(每小题2分)1.设a?x|(x?n)且(x?5),b?x|x?e且x?7(n：自然数集，e+正偶数)则a?b?。2a，b，c表示三个集合，文图中阴影部分的集合表达式为。3 设p，q的真值为0，r，s的真值为1，则?(p?(q?(r?p)?(r?s)的真值=。4 公式(p?r)?(s?r)?p的主合取范式为。5 若解释i的论域d仅包含一个元素，则?xp(x)?xp(x)在i下真值为。6 设a=1

27、，2，3，4，a上关系图为则r2=。7设a=a，b，c，d，其上偏序关系r的哈斯图为则r=。8图的补图为。9设a=a，b，c，d，a上二元运算如下：那么代数系统a，*的幺元是，它们的逆元分别为。10下图所示的偏序集中，是格的为。二、选择20%（每小题2分）1、下列是真命题的有（）aa?a；b?,?；c?,?；d?。2、下列集合中相等的有（）a4，3?；b?，3，4；c4，?，3，3；d3，4。3、设a=1，2，3，则a上的二元关系有（）个。a23；b32；c23?3；d32?2。4、设r，s是集合a上的关系，则下列说法正确的是（）a若r，s是自反的，则r?s是自反的；b若r，s是反自反的，则r

28、?s是反自反的；c若r，s是对称的，则r?s是对称的；d若r，s是传递的，则r?s是传递的。5、设a=1，2，3，4，p（a）（a的幂集）上规定二元系如下r?s,t?|s,t?p（a）?（|s|?|t|则p（a）/r=（）aa；bp（a）；c1，1，2，1，2，3，1，2，3，4；d?，2，2，3，2，3，4，a6、设a=?,1,1,3,1,2,3则a上包含关系“？的哈斯图为（）7、下列函数是双射的为（）af:i?e,f（x）=2x；bf:n?n?n,f（n）=n,n+1；cf:r?i,f（x）=x；df:i?n,f（x）=|x|。（注：i整数集，e偶数集，n自然数集，r实数集）8、图中从v1到v3长度为3的通路有（）条。a0；b1；c2；d3。9、下图中既不是eular图，也不是hamilton图的图是（）10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。a1；b2；c3；d4。三、证明26%1、r是集合x上的一个自反关系，求证：r是对称和传递的，当且仅当a,b和a