離散數(shù)學(xué)選擇題

1、編號(hào)題目下列是真命題的有（）答:Ca、a匸a；b、珂,®；c、丸,；D、丘。下面命題公式（）不是重言式。答:CA、Qt(PmQ);B、(P/vQ)tP；C、-(Pf-Q)“Px/Q)；D、（PtQ）（PwQ）。命題“沒有不犯錯(cuò)誤的人”符號(hào)化為（）。設(shè)M（x）:x是人，P（x）:x犯錯(cuò)誤。答:DA、燈X（M（X）P（X）；B、-<2x（“（x）Tp（x）；C、(三x(M(x)P(x)；D、(2x(M(x)入P(x)。對(duì)自然數(shù)集合N，哪種運(yùn)算不是可結(jié)合的，運(yùn)算定義為任a,bN（）。答:Ba、a*b=min(a,b)；b、a*b=a+2b；c、a*b=a+b+3；d、a*b=a,b(

2、mod3)。任意具有多個(gè)等幕元的半群，它（）。答:AA、不能構(gòu)成群；B、不一疋能構(gòu)成群；C、不能構(gòu)成交換群；D、能構(gòu)成交換群。設(shè)G=cV,EA為無向圖，V|=7,E|23，則G疋疋（）。答:DA、完全圖；B、樹；C、簡單圖；D、多重圖。給定無向圖G=vV,EA，如下圖所示，下面哪個(gè)邊集不是其邊割集（）。答:BA、VVi,V4A,£V3,V4；B、£V4,V5A,VV4,V6；C、VV4N7V4,V8；3在D、£VV2V2,V3另。有n個(gè)結(jié)點(diǎn)（n>3），m條邊的連通簡單圖是平面圖的必要條件（）。答:Da、n>3-6；c、mx3n6；b、n蘭3m6；d、m

3、蘭3n6。設(shè)A=x|x是整數(shù)且x2<16，下面哪個(gè)命題為假（）。答：AA、0,1,2,4匸A;B、_3,-2,-1匸A;C、§A；D、x|x是整數(shù)且x£4gA設(shè)A=，B=，則BA是（）。答：CA、；B、；c、g;D、。下圖描述的偏序集中，子集b,e,f的上界為（）。答：BA、b,c；b、a,b；貞c、b；d、a,b,c。、d答：C設(shè)f和g都是X上的雙射函數(shù)，則（f”g）為（）。A、fS；b、（g°f）;c、gf；d、gQf。下面集合（）關(guān)于減法運(yùn)算疋土封閉的。答：BA、N;B、2xxG;C、2x+1I;D、xX是質(zhì)數(shù)。具有如下定義的代數(shù)系統(tǒng)vG,*>,

4、（）不構(gòu)成群。答：DA、G=1,10,*是模11乘；B、G=1,3,4,5,9,*是模11乘；C、G=Q（有理數(shù)集），*是普通加法；D、G=Q（有理數(shù)集），*是普通乘法。設(shè)G=2mH3nm,n=I,*為普通乘法。則代數(shù)系統(tǒng)<G,*A的幺元為（）。答：BA、不存在;B、e=20x30；c、e=2><3；d、。下面集合（）關(guān)于整除關(guān)系構(gòu)成格。答：CA、2，3,6，12，24,36;B、1，2,3，4,6,8，12；C、1,2,3,5,6,15,30;D、3,6,9,12。答：C設(shè)V=a,b,c,d,e,f，E=va,b>,vb,c>,vc,a>,va,d>

5、,£d,e>,vf,e>，則有向圖G=<V,E>是()。A、強(qiáng)連通的；B、單側(cè)連通的；C、弱連通的；D、不連通的。下面那一個(gè)圖可一筆畫岀()。答：A在任何圖中必定有偶數(shù)個(gè)()。A、度數(shù)為偶數(shù)的結(jié)點(diǎn)；B、入度為奇數(shù)的結(jié)點(diǎn)；C、度數(shù)為奇數(shù)的結(jié)點(diǎn)；D、岀度為奇數(shù)的結(jié)點(diǎn)。答：C含有3個(gè)命題變?cè)木哂胁煌嬷档拿}公式的個(gè)數(shù)為()。A、23；B、32；C、223；D、232。答：C下列集合中哪個(gè)是最小聯(lián)結(jié)詞集()。A、T；B、，；C、t，；D、，入°。答：A下面哪個(gè)命題公式是重言式()。A、(PtQ)/(QtR)；B、(P/Q)tP；C、(Px/Q)；D、-(

6、Px/Q)"。答：B在謂詞演算中，下列各式哪個(gè)是正確的()。A、三x2yA(x,y)二3xA(x,y)；b、mx2yA(x,y)二X/yX/xA(x,y)；C、=FyA(x,y)uX/y2xA(x,y)；D、A(a)二VxA(x)。答：A命題公式Pt(QwP)是()。矛盾式；B、可滿足式；C、重言式；D、等價(jià)式。答：C下列各式中哪個(gè)不成立()。A、Wx(P(x)wQ(x)=VxP(xVxQ(x)；B、三x(P(x)”Q(x)=2xP(x)w2xQ(x)；C、Px(P(x)aQ(x)=PxP(x)aFxQ(x)；D、燈x(P(x)Q)二FxP(x)aQ。答：A謂詞公式X/x(P(x)M

7、WyR(y)tQ(x)中的x是()。A、自由變?cè)?；B、約束變?cè)?；C、既是自由變?cè)质羌s束變?cè)?；D、既不是自由變?cè)植皇羌s束變?cè)?。答：C6在自然數(shù)集N上，下列()運(yùn)算是可結(jié)合的。(對(duì)任意a,beN)答：Ba、a*b=a_b；b、a*b=max(a,b)；C、a*b=a+5b；d、aMb=a-b|。Q為有理數(shù)集N,Q上定義運(yùn)算*為a*b=a+b-ab,則Q,*的幺元為（）。A、a；B、b;C、1;D、0。答：D給定下列序列，（）可以構(gòu)成無向簡單圖的結(jié)點(diǎn)次數(shù)序列。A、（1，1,2，2，3）;B、（1，1，2，2，2）;C、（0，1，3，3，3）；D、（1，3，4，4，5）。答：B設(shè)G是簡單有向圖，可

8、達(dá)矩陣P（G）刻劃下列（）關(guān)系。A、點(diǎn)與邊；B、邊與點(diǎn)；C、點(diǎn)與點(diǎn)；D、邊與邊。答：C一顆樹有兩個(gè)2度結(jié)點(diǎn)，1個(gè)3度結(jié)點(diǎn)和3個(gè)4度結(jié)點(diǎn)，貝91度結(jié)點(diǎn)數(shù)為（）。A、5；B、7；C、9；D、8。答：C設(shè)A=1，2，3，4，5，下面（）集合等于A。A、1，2，3，4，5，6；B、xX是整數(shù)且X?蘭25；C、XX是正整數(shù)且X蘭5；D、XX是正有理數(shù)且X蘭5。答：C設(shè)A=1，2，3，4，5，6，7，8，下列各式中（）是錯(cuò)的。A、匸A；B、6，7，8EA；C、4，5Ua；D、1，2,3Ua。答：D六階群的子群的階數(shù)可以是（）。A、1，2，5；B、2，4；C、3，6，7；D、2，3。答：D設(shè)S匸AxB，下列

9、各式中（）是正確的。domSB；B、domS§A；C、ranS$A；D、domSranS=S。答：DvG,*是群，則對(duì)*（）。A、滿足結(jié)合律、交換律；B、有單位元，可結(jié)合；C、有單位兀、可交換；D、每兀有逆兀，有零兀。答：B下面（）哈斯圖所描述的偏序關(guān)系構(gòu)成分配格。答：D下列（）中的運(yùn)算符都是可交換的。A、入，M,T；B、T，；C、2,c,x；D、7小。答：D設(shè)G是n個(gè)結(jié)點(diǎn)、m條邊和r個(gè)面的連通平面圖，則m等于（）。A、n+r-2；B、n-葉2；C、n-r-2；D、n+r+2。答：An個(gè)結(jié)點(diǎn)的無向完全圖Kn的邊數(shù)為（）。答：Dn(ni)A、n(n+1)；b、；C、n(n1)；2n(n

10、1)D、2下列圖中（）是根樹。答:CA、G1=<a,b,c,d,<a,aa,ca,ba,vc,d>aB、G2=<a,b,c,d,ca,ba,cb,da,<c,d>>C、G3=<a,b,c,d,ca,b>,ca,da,cc,a>>d、G4xa,b,c,d,ca,b>,ca,c>,vd,d刃>0設(shè)P:22=5,Q:雪是黑的，R:2M-8,S:太陽從東方升起,下列（）命題的真值為真。答:AA、PtQ/R；B、RtPaS；C、StQ八RD、(PaR)m(QaS)0設(shè)L（x）:x是演員，J（x）:x是老師，A（x,y）:

11、x欽佩y，命題所有演員都?xì)J佩某些老師符（）o號(hào)化為答:BA>Vx(L(x)tA(x,y)；B、丸x(L(x)t3y(J(y)aA(x,y)；C、于xy(L(x)aJ(y)aA(x,y)；d、耳x2y(L(x),aJ(y)tA(x,y)集合A=xx=2n,neN對(duì)（）運(yùn)算封閉。答:CA、加法；B、減法；C、乘法；D、Xy|0設(shè)I為整數(shù)集合，m是任意正整數(shù)，Zm是由模m的同余類組成的同余類集合，在Zm上定義運(yùn)算答:BNj=（ixj）modm，則代數(shù)系統(tǒng)Zm/最確切的性質(zhì)是（）。A、封閉的代數(shù)系統(tǒng)；B、半群；C、獨(dú)異點(diǎn)；D、群。連通非平凡的無向圖G有一條歐拉回路當(dāng)且僅當(dāng)圖G（A、只有一個(gè)奇度結(jié)

12、點(diǎn)；B、只有兩個(gè)奇度結(jié)點(diǎn)；C、只有三個(gè)奇度結(jié)點(diǎn)；D、沒有奇度結(jié)點(diǎn)。）。答:D設(shè)無向圖G=V,E是連通的且|v|=n,|e|=m若（）貝0G是樹。答:BA、M=N+1；B、n=m+1；C、m蘭3n-6；D、n蘭3m-6。如果解釋1使公式A為真，且使公式AtB也為真，則解釋A、真；B、假；C、可滿足；D、與解釋I無關(guān)。I使公式B為（）。答:A設(shè)A=£»，則P(A)xa=(）。答:CA、A；B、P(A)；C、,a>,v,b><a,a><a,b>,<b,a><b,b>,£A,a>,VA,b>.d、&l

13、t;a,acb,aca,aacb,aa,ca,bacb,ba,A>,£b,AA。設(shè)集合a,b是有窮集合，且|A=m,B|=n，則從a到b有（）個(gè)不同的雙射函數(shù)。答:DA、n；b、m；c、n!；D、m!。設(shè)K=e,a,b,c,<K嚴(yán)a是Klein四元群，則元素a的逆元為（)。答:BA、e；B、a；C、b；D、c。一個(gè)割邊集與任何生成樹之間（）。A、沒有關(guān)系；B、割邊集誘導(dǎo)子圖是生成樹；c、有一條公共邊;D、至少有一條公共邊。答:D下列語句中不是命題的有（)答:B、CA、9+5<12；B、x+3=5；C、我用的計(jì)算機(jī)CPU主頻是1G嗎？；D、我要努力學(xué)習(xí)。命題“我不能一

14、邊聽課，一邊看小說”的符號(hào)化為（)答:A、DA、PtQ；B、PtQ；C、；D、（PQ）。下列表達(dá)式正確的有（）答:A、CA、（PtQ）二Q；B、PwQ二P；C、(PaQ)"(PeQ)=P；D、Pt(PtQ)二T。若公式（PaQ）"（PaR）的主析取范式為答:Bm°01“monwm11owm111則它的主合取范式為（)A、m001八m01amnam111；B、M000入M010入M100入M101C、M001八M011/VM110/vM11；d、m000八m010八m100八m101。命題“盡管有人聰明，但未必一切人都聰明”的符號(hào)化（P（x）:x是聰明的，M（x）:

15、x是人）（)答:CA、3x(M(x)TP(x)入(Vx(M(x)TP(x)B、5x(M(x)P(x)八(Px(M(x)P(x)C、三x(M(x)aP(x)_，O/x(M(x)tP(x)D、2x(M(x)P(x)w(Wx(M(x)tP(x)設(shè)A=，B=P（P（A）下列（）表達(dá)式成立。答:A、B、A、匸B；B、如匸B；C、価eB；D、也匸B。A是素?cái)?shù)集合，B是奇數(shù)集合，則A-B-（）A、素?cái)?shù)集合；B、奇數(shù)集合；C、；D、2。答：B集合B=,的幕集為（）。A、,；B、,®,44®,®®,B；C、啓川,打,少,446,6,4圧,B；D、4任,。，,*,46,B答

16、：B下列結(jié)果正確的是（）。A、（AuB）-A=B；B、（AcB）-A=6；C、（A-B）uB=A；D、5。=；答：Bwff（paqjTr的主析取范式中含極小項(xiàng)的個(gè)數(shù)為（）。A、2；B、3；C、5；D、0；E、8。答：C在（）下有AxBGA。A、A=B；b、B9A；c、AGB；d、A=或B=0答：D下列二元關(guān)系中是函數(shù)的有（）。A、R=cx,yrxNayENax+yvIO；2B、R=£x,y沖x壬R入ywRey=x；2C、R=cx,y>|x壬R入ywRex=y答：B在有理數(shù)集Q上定義的二元運(yùn)算*，Vx,yQ有x*y=x+yxy，貝UQ中滿足（）。A、所有元素都有逆元；B、只有唯一

17、逆元；C、X/xQ,xH1時(shí)有逆元x；D、所有元素都無逆元。答：C設(shè)S=0，1，*為普通乘法，則S,*是（）。A、半群，但不是獨(dú)異點(diǎn)；B、只是獨(dú)異點(diǎn)，但不是群；C、群；D、環(huán)，但不是群。答：B1b$da圖°給岀一個(gè)格L,則L是（）。A、分配格；B、有補(bǔ)格；C、布爾格；D、A,B,C都不對(duì)。答：Di有向圖D=<V,E>£A、0；B、1；，則V1到V4長度為2的通路有（）條。C、2；D、3o答：B在Peterson圖占中，至少填加（）條邊才能構(gòu)成Euler圖。A、1；B、2；C、4；D、5。答：D下面各集合都是N的子集，（）集合在普通加法運(yùn)算下是封閉的。A、x|x的

18、幕可以被16整除；B、x|x與5互質(zhì)；C、x|x是30的因子；D、x|x是30的倍數(shù)。答：A、D設(shè)G1Y0,1,2,°，G2M0,1,*A，其中匸表示模3加法，*表示模2乘法，則積代數(shù)GMG2的幺元是（）。A、0,0；B、0,1；C、1,0；D、1,1。答：B設(shè)集合S=1,2,3,6，“”為整除關(guān)系，則代數(shù)系統(tǒng)S,是（）。A、域；B、格，但不是布爾代數(shù)；C、布爾代數(shù)；D、不是代數(shù)系統(tǒng)。答：C設(shè)n階圖G有m條邊，每個(gè)結(jié)點(diǎn)度數(shù)不是k就是k+1，若G中有Nk個(gè)k度結(jié)點(diǎn)，則Nk=（）。A、nk；B、n（k+1）；C、n（k+1）-m；D、n（k+1）-2m。答：D一棵樹有7片樹葉，3個(gè)3度結(jié)

19、點(diǎn)，其余全是4度結(jié)點(diǎn)，則該樹有（）個(gè)4度結(jié)點(diǎn)。A、1；B、2；C、3；D、4。答：A設(shè)A，+，是環(huán)，Wa,b匸A，ab的關(guān)于“+"的逆元是（）。A、（-a）（-b）；B、（-a）b；C、a（-b）；D、ab。答：B、C設(shè)A，+，是一代數(shù)系統(tǒng)且A，+是Abel群，如果還滿足（）A，+，是域。答：DA、A,是獨(dú)異點(diǎn)且對(duì)+可分配；B、A-日,是獨(dú)異點(diǎn)，無零因子且對(duì)+可分配；C、A-0,是Abel群且無零因子;D、A-日,是Abel且對(duì)+可分配。設(shè)A,+,是一代數(shù)系統(tǒng)，+、為普通加法和乘法運(yùn)算，當(dāng)A為（）時(shí)，A,+,是域。A、x|x=a+b叮5a,b均為有理數(shù)；B、x|x=a+b：/5a,b

20、均為有理數(shù)；altc、x|x=,a,b|十且akb；d、x|xeO,xe1。b答：A設(shè)A,是一個(gè)格，由格誘導(dǎo)的代數(shù)系統(tǒng)為A»則（）成立。a、cA,込入滿足沖對(duì)/的分配律；B、弋a(chǎn),b代a蘭buawb=b；c、/a,b,cA,若a/b=awc則b=c；d、Na,bA,有8“心/匕）=匕且a/（ayb）=b。答：B設(shè)a,w是偏序集，“蘭”定義為：Pa,bw代a蘭bwa|b，則當(dāng)a=（）時(shí)，a,蘭是格。A、1,2,3,4,6,12；B、1,2,3,4,6,8,12,14；C、1,2,3,，12；D、1,2,3,4。答：A設(shè)R和S是P上的關(guān)系，P是所有人的集合，R=cx,y|x,yp入x是y

21、的父親,S=vx,y|x,ywpex是y的母親則SaQR表示關(guān)系（）。A、cx,yx,y匸Pax是y的丈夫；B、cx,ya|x,yPax是y的孫子或?qū)O女；C、；D、vx,ya|x,ypax是y的祖父或祖母。答：A在（）中，補(bǔ)元是唯一的。A、有界格；B、有補(bǔ)格；C、分配格；D、有補(bǔ)分配格。答：D在布爾代數(shù)A,“，e,中，bac=0當(dāng)且僅當(dāng)（）。a、b蘭c；b、c蘭b；c、b蘭c；d、c蘭b。答：C設(shè)£A,y,a,-是布爾代數(shù)，f是從An到A的函數(shù)，則（）。A、f是布爾代數(shù)；B、f能表示成析取范式，也能表示成合取范式；C、若A=0,1，則f一定能表示成析取范式，也能表示成合取范式；D、若

22、f是布爾函數(shù)，它一定能表示成析（合）取范式。答：C、D下列命題正確的有（）。答：A、Da、若g,f是滿射，則gQf是滿射；b、若gQf是滿射，則g,f都是滿射；c、若g°f是單射，則g,f都是單射；d、若g°f單射，則f是單射。設(shè)f，g是函數(shù)，當(dāng)（）時(shí)，f=g。答：BA、燈xedomf都有f(x)=g(x)；b、domg匸domf且f匸g；C、f與g的表達(dá)式相同；D、domg=domf,rangef=rangef下列關(guān)系，（）能構(gòu)成函數(shù)。答：C、DA、f=CX"X2a|為，X2EN且Xj+X2=10;2B、f=£X2:為，X2ER,Xj=X2；C、f=c

23、x2A|x2N,x2為小于右的素?cái)?shù)的個(gè)數(shù)；D、f=<X,c>|R。設(shè)R，S是集合A上的關(guān)系，則下列（）斷言是正確的。答：AA、R,S自反的，貝UROS是自反的；B、若R,S對(duì)稱的，則R°S是對(duì)稱的；C、若R,S傳遞的，貝UR°S是傳遞的；D、若R,S反對(duì)稱的，貝URS是反對(duì)稱的。設(shè)S=1,2,3，定義S漢S上的等價(jià)關(guān)系答：BR=£ca,b>,cc,d>|ca,b>ES匯S,cc,d匯S,a+d=b+c則由R產(chǎn)生的S漢S上一個(gè)劃分共有（）個(gè)分塊。A.4；B.5；C.6；D.9o“沒有不犯錯(cuò)誤的人”的邏輯符號(hào)化為（）。答：B、D設(shè)H（x）:x是人，P（x）:x犯錯(cuò)誤。A、3x(H(x)TP(x)；B、(mx(H(x)AP(x)；C、(三x(H(x)TP(x)；D、Wx(H(x)TP(x)。下列各符號(hào)串，不是合式公式的有（）。答：B、CA、(P/Q)-R；B、(PtQ)t(RaS)；C、PVvaR；D、(PQ)aR)“So下列語句是命題的有（)o答：A、CA、2是素?cái)?shù)；B、x+5>6；C、地球外的星球上也有人；D、這朵花多好看呀！。下列問題成立的有（）。答：C、DA、若A“C二BC，則AuB；B、若BC，則AuB；C、若B，則A=B；D、若A尋B，則-1A=""