離散數(shù)學(xué)試題與答案

1、離散數(shù)學(xué)試題與答案【篇一：離散數(shù)學(xué)試題及答案】一、填空題1設(shè)集合a,b,其中a=1,2,3,b=1,2,則a-b=;_.3. 設(shè)集合a=a,b,b=1,2,則從a到b的所有映射是,其中雙射的是4. 已知命題公式g=?(p?q)Ar,則g的主析取范式是5. 設(shè)g是完全二叉樹，g有7個點，其中4個葉點，則g的總度數(shù)為，分枝點數(shù)為.7 .設(shè)r是集合a上的等價關(guān)系，則r所具有的關(guān)系的三個特性是8 .設(shè)命題公式g=?(p?(q?r),則使公式g為真的解釋有，9 .設(shè)集合a=1,2,3,4,a上的關(guān)系ri=(1,4),(2,3),(3,2),ri=(2,1),(3,2),(4,3),則r1?r2=,r2?

2、r110 .設(shè)有限集a,b，|a|=m,|b|=n,則|?(a?b)|=11設(shè)a,b,r是三個集合，其中r是實數(shù)集，a=x|-1<x<1,x?r,b=x|0<x2,x?則a-b=,b-a=,aAb=,.13 .設(shè)集合a=2,3,4,5,6,r是a上的整除，則r以集合形式(列舉法)記為14 .設(shè)一階邏輯公式g=?xp(x)?xq(x)，則g的前束范式是15 .設(shè)g是具有8個頂點的樹，則g中增加條邊才能把g變成完全圖。?(a)-?(b)r1216 .設(shè)謂詞的定義域為a,b,將表達式？xr(x)-?xs(x)中量詞消除，寫成與之對應(yīng)的命題公式是17 .設(shè)集合a=1,2,3,4,a上

3、的二元關(guān)系r=(1,1),(1,2),(2,3),s=(1,3),(2,3),(3,2)。則r?s=r2=二、選擇題1設(shè)集合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設(shè)集合a=1,2,3,a上的關(guān)系r=(1,1),(2,2),(2,3),(3,2),(3,3),則r不具備().(a)自反性(b)傳遞性(c)對稱性(d)反對稱性則元3設(shè)半序集(a,w菠系啪哈斯圖如下所示，若a的子集素6為b的()。(a)下界(b)上界(c)最小上界(d)以上答案都不對4下列語句中，()是命題。(a)請把門關(guān)上(b

4、)地球外的星球上也有人(c)x+56(d)下午有會嗎？5設(shè)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 .若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是().(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 .設(shè)g、h是一階邏輯公式，p是一個謂詞，g=?xp(x),h=?xp(x),則一階邏輯公式g?h是().(a)恒真

5、的(b)恒假的可滿足的(d)前束范式.8設(shè)命題公式g=?(p?q),h=p?(q?p)，則g與h的關(guān)系是()。(a)g?h(b)h?g(c)g=h(d)以上都不是.9設(shè)a,b為集合,當(dāng)()時ab=b.(a)a=b(b)a?b(c)b?a(d)a=b=?.10設(shè)集合a=1,2,3,4,a上的關(guān)系r=(1,1),(2,3),(2,4),(3,4),則r具有()。(a)自反性(b)傳遞性對稱性(d)以上答案都不對11 下列關(guān)于集合的表示中正確的為()。(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. 設(shè)g是連通平面圖，有5個頂點，6個面，則g的邊數(shù)是().(a)9條(b)5條(c)6條(d)11條.14. 設(shè)g是5個頂點的完全圖，則從g中刪去()條邊可以得到樹.(a)6(b)5(c)10(d)4.1111?0100?，則1011?0101?0110?0?1的相鄰矩陣為?1?1?115.設(shè)圖gg的頂點數(shù)與邊數(shù)分別為().(a)4,5(b)5,6(c)4,10(d)5,8.三、計算證明題1.設(shè)集合a=1,2,3,4,6,8,9,12,r為整除關(guān)系。(1) 畫出半序集(a,r

7、)的哈斯圖；(2) 寫出a的子集b=3,6,9,12的上界，下界，最小上界，最大下界；(3) 寫出a的最大元，最小元，極大元，極小元。2.設(shè)集合a=1,2,3,4,a上的關(guān)系r=(x,y)|x,y?a且x?y,求1) )畫出r的關(guān)系圖；2) )寫出r的關(guān)系矩陣.3) 設(shè)r是實數(shù)集合，？,？,？是r上的三個映射，？(x)=x+3,?(x)=2x,?(x)=x/4,試求復(fù)合映射?，?,?,?，?.4) 設(shè)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.設(shè)集

8、合a=1,2,4,6,8,12，為a上整除關(guān)系。(1) 畫出半序集(a,r)的哈斯圖；(2) 寫出a的最大元，最小元，極大元，極小元；(3) 寫出a的子集b=4,6,8,12的上界，下界，最小上界，最大下界.6. 設(shè)命題公式g=?(pfq)V(qA(?pfr),求g的主析取范式。7. (9分)設(shè)一階邏輯公式：g=(?xp(x)V?yq(y)f?xr(x)，把g化成前束范式.9. 設(shè)r是集合a=a,b,c,d.r是a上的二元關(guān)系,r=(a,b),(b,a),(b,c),(c,d),(1) 求出r(r),s(r),t(r)；(2) 畫出r(r),s(r),t(r)的關(guān)系圖.11. 通過求主析取范式

9、判斷下列命題公式是否等價：(1) g=(pAq)V(?pAqAr)(2) h=(pV(qAr)A(qV(?pAr)13.設(shè)r和s是集合a=a,b,c,d上的關(guān)系，其中r=(a,a),(a,c),(b,c),(c,d),s=(a,b),(b,c),(b,d),(d,d).(1) 試寫出r和s的關(guān)系矩陣；(2)計算r?s,rUs,r1,s1?r1.四、證明題1 .利用形式演繹法證明：pfq,rs,pVr蘊涵qVs。2 .設(shè)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.【篇二：離散數(shù)學(xué)練習(xí)題及答案】的表示方法有兩種：法。請把“奇整數(shù)集合”表示出，k?z來。1、列舉；描述；x|x?2k?12 、無向連通圖g含有歐拉回路的充分必要條件是2*、連通有向圖d含有歐拉回路的充分必要條件是d中每個結(jié)點的入度=出度.3 、設(shè)r是集合a上的等價關(guān)系，則r所具有的關(guān)系的三個特性是自反性、對稱性、傳遞性.4 、有限圖g是樹的一個等價定義是：.5、設(shè)n(x)：x是自然數(shù)，z(y)；y是整數(shù)，則命題“自然數(shù)

12、都是整數(shù)，而有的整數(shù)不是自然數(shù)”符號化為?x(n(x)?z(x)?x(z(x)?n(x)6 、在有向圖的鄰接矩陣中，第i行元素之和,第j列元素之和分別為結(jié)點v的出度和結(jié)點v的入度7 、設(shè)a，b為任意命題公式，c為重言式，若a?c?b?c，那么命題a?b是重言式的真值是18 、命題公式?(p?q)的主析取范式為9、設(shè)圖g=v,e和g?=v?,e?,若g?是g的真子圖，若，貝Ug?是g的生成子圖.v?v或e?e;v?v,e?e10、在平面圖g?v,e?中,則11、設(shè)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*、設(shè)個體域d=a,b,公式？x(g(x)?yh(x,y)消去量詞化為13、含有三個命題變項p，q，r的命題公式p?q的主析取范式是14、設(shè)r，s都是集合a上的等價關(guān)系，則對稱閉包s(r?s)=15、設(shè)g是連通平面圖，v,e,r分別表示g的結(jié)點數(shù)，邊數(shù)和面數(shù)，則v

14、,e和r滿足的關(guān)系式是v?r?e?16、設(shè)g是n個結(jié)點的簡單圖，若g，則g一定是哈密頓圖.17、一個有向樹t稱為根樹，若稱為樹葉.若有向圖t恰有一個結(jié)點的入度為0，其余結(jié)點入度為1；入度為0的結(jié)點；出度為0的結(jié)點.18、圖的通路中邊的數(shù)目稱為結(jié)點不重復(fù)的通路是通路.邊不重復(fù)的通路是通路.通路長度；初級；簡單.19、設(shè)a和b為有限集，|a|=m，|b|=n，則有個從a到b的關(guān)系，有個從a到b的函數(shù)，其中當(dāng)m?n時有個入射，當(dāng)m=n時，有個雙射。19、2m*nm,nm,cn?m!,m!2a?n|n?n(是/不是)可數(shù)的。是20、集合21、設(shè)l?1,2,3,4,12?上的整除關(guān)系?a1,a2a1,a

15、2?l,a1整除a2?在l上定義兩個二元運算?和?：對任意a,b?l，a?b?glb(a,b)，a?b?lub(a,b)o請?zhí)羁?在橫線上填是或不是)：是是是不是代數(shù)系統(tǒng)?l,?,?格。代數(shù)系統(tǒng)?l,?,?有界格。代數(shù)系統(tǒng)？l,?,?有補格。代數(shù)系統(tǒng)？l,?,?分配格。二、單項選擇題(選擇一個正確答案的代號，填入括號中)1 、設(shè)命題公式g=?(p?q)，h=p?(q?p)，則g與h的關(guān)系是(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、設(shè)v=a

16、,b,c,d,與v能構(gòu)成強連通向的邊集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、設(shè)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)種不同的關(guān)系。(a)3(b)8(c

17、)9(d)5126、設(shè)s1=?,s2=?,s3=p(?),s4=p(?)則命題為假的是(a)(a)s2?s4(b)s1?s3(c)s2?s4(d)s4?s37 、設(shè)g是連通平面圖，有v個結(jié)點，e條邊，r個面，則r=(a)(a)ev2(b)ve2(c)ev2(d)ev28 、下列命題正確的是(a)。a?=?b?=?ca?a，b，cd?a，b，c9、設(shè)a,b,c都是集合，如果a?c=b?c,則有(c)(a)a=b(b)a?b(c)當(dāng)ac=bc時，有a=b(d)當(dāng)c=u時，有a?b10 、設(shè)(b,?,?,0,1)是布爾代數(shù)，?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)=(整數(shù)集，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是整數(shù)，x230,B=x|x是質(zhì)數(shù)，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、設(shè)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、設(shè)集合A=a,b,c,d,e,f,g,A的一個劃分？=a,b,c,d,e,f,g,則?所對應(yīng)的等價關(guān)系有個二元組。(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上的整除關(guān)系。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、設(shè)有有限布爾代數(shù)(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，則代數(shù)系統(tǒng)(g，?)。(1)是半群但不是群(2)是無限群(3)是循環(huán)群(4)是變換群(5)是交換群10、僅有一個結(jié)點的圖稱為()，當(dāng)然也是()(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)設(shè)圖g(如第1題圖)，作圖g的嵌入圖，說明圖g是平

22、面圖.第1題圖1、(1)圖g的嵌入圖，如第12題答案圖.故圖g為平面圖(4分)第12題答案圖(2)在具有n個頂點的完全圖kn中刪去多少條邊才能得到樹？解：n個頂點的完全圖kn中共有6.4。n?(n?1)條邊，n個頂點的樹應(yīng)有n?1條邊，于是，刪2n?(n?1)(n?1)?(n?2)?(n?1)?去的邊有：。222、判別謂詞公式?x?yf(x,y)?y?xf(x,y)的類型.2、設(shè)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、判斷下列哪些運算結(jié)果是對的？哪些是錯的？請將錯誤的運算結(jié)果更正過來(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)錯應(yīng)為?(3)對(4)錯應(yīng)為?(5)錯應(yīng)為a?b(6)錯應(yīng)為a?b(或a?b或aab)(7)錯應(yīng)為?，即a?a?a?a?a?a?(8)對5、將命題公式?p?q?(?r?p)化為只含?和?的盡可能簡單的等值式5、?p?q?(?r?p)?(p?q)?(r?p)(優(yōu)先級有誤)?(p?q)?(?p?r)不惟一.(1)v1e5v5e7v2e2v3(2)v5e6v2e2v3e3v4e8v2e7v5v254(3)v2e7v5e6v2(4)v1e1v2e2v3e3v4e8v2e6v5ev46、(1)初級通路；(2)簡單回路；(3)初級回路；(4

25、)簡單通路.e3vev7、試問n取何值時，無向完全圖kn，存在一條歐拉回路？6、設(shè)圖g如右圖.已知通路7、由于kn有n個結(jié)點，并且每個結(jié)點的度數(shù)均為n1，于是，當(dāng)n為奇數(shù)時，kn的每個結(jié)點的度數(shù)都是偶數(shù)，所以存在一條歐拉回路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?化成前束范式。解：【篇三：離散數(shù)學(xué)試卷及答案】t>一、填空20%(每小題2分)1.設(shè)a?x|(x?n)且(x?5),b?x|x?e且x?7(n：自然數(shù)集，e+正偶數(shù))則a?b?。2a，b，c表示三個集合，文圖中陰影部分的集合表達式為。3 設(shè)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 設(shè)a=1

27、，2，3，4，a上關(guān)系圖為則r2=。7設(shè)a=a，b，c，d，其上偏序關(guān)系r的哈斯圖為則r=。8圖的補圖為。9設(shè)a=a，b，c，d，a上二元運算如下：那么代數(shù)系統(tǒng)a，*的幺元是，它們的逆元分別為。10下圖所示的偏序集中，是格的為。二、選擇20%（每小題2分）1、下列是真命題的有（）aa?a；b?,?；c?,?；d?。2、下列集合中相等的有（）a4，3?；b?，3，4；c4，?，3，3；d3，4。3、設(shè)a=1，2，3，則a上的二元關(guān)系有（）個。a23；b32；c23?3；d32?2。4、設(shè)r，s是集合a上的關(guān)系，則下列說法正確的是（）a若r，s是自反的，則r?s是自反的；b若r，s是反自反的，則r

28、?s是反自反的；c若r，s是對稱的，則r?s是對稱的；d若r，s是傳遞的，則r?s是傳遞的。5、設(shè)a=1，2，3，4，p（a）（a的冪集）上規(guī)定二元系如下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、設(shè)a=?,1,1,3,1,2,3則a上包含關(guān)系“？的哈斯圖為（）7、下列函數(shù)是雙射的為（）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整數(shù)集，e偶數(shù)集，n自然數(shù)集，r實數(shù)集）8、圖中從v1到v3長度為3的通路有（）條。a0；b1；c2；d3。9、下圖中既不是eular圖，也不是hamilton圖的圖是（）10、在一棵樹中有7片樹葉，3個3度結(jié)點，其余都是4度結(jié)點則該樹有（）個4度結(jié)點。a1；b2；c3；d4。三、證明26%1、r是集合x上的一個自反關(guān)系，求證：r是對稱和傳遞的，當(dāng)且僅當(dāng)a,b和a