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

-.z.單項(xiàng)選擇題第一章命題邏輯1．以下語句，哪一個(gè)是真命題：〔B〕A．我正在說謊B．如果1+1=0，則雪是黑的C．9+5＞18D．存在最大的質(zhì)數(shù)2．下面哪一個(gè)命題是假命題〔A〕A．如果2是偶數(shù)，則一個(gè)公式的析取范式唯一B．如果2是偶數(shù)，則一個(gè)公式的析取范式不唯一C．如果2是奇數(shù)，則一個(gè)公式的析取范式唯一D．如果2是奇數(shù)，則一個(gè)公式的析取范式不唯一3．下面哪個(gè)聯(lián)結(jié)詞運(yùn)算不可交換〔B〕A．；B．C．D．4．設(shè)P：天下大雨，Q：他乘公共汽車上班。命題"只有天下大雨，他才乘公共汽車上班〞符號化為〔B〕A．PQB．QPC．PQD．PQ5．設(shè)P：天下釘子，Q：我去B城。命題"除非天下釘子，否則我去B城〞符號化為：〔C〕A．PQB．QPC．PQD．Q┐P6．設(shè)P：我們劃船，Q：我們跳舞，命題"我們不能既劃船又跳舞〞符號化為〔B〕A．PQ2〕┐〔P∧Q〕C．┐P∧┐QD．┐P∧Q7．令P：今天下雪了，Q：路滑，則命題"雖然今天下雪了，但是路不滑〞可符號化為〔D〕A．P┐QB．P∨┐QC．P∧QD．P∧┐Q8．設(shè)P：我將去鎮(zhèn)上，Q：我有時(shí)間，命題"我將去鎮(zhèn)上，僅當(dāng)我有時(shí)間〞，符號化為〔A〕。A．PQB、QPC、PQD、┐P∨┐Q9．下面哪一個(gè)命題公式是重言式〔D〕A．〔P∨R〕∧〔PQ〕B．P〔Q∨R〕C．〔P∨Q〕〔Q∨R〕D．〔P〔QR〕〕〔PQ〕〔PR〕10．下面哪一組命題公式不是等價(jià)的〔C〕A．〔PQ〕〔QP〕，PQB．〔PQ〕，〔P∧┐Q〕∨〔┐P∧Q〕C．P〔Q∨R〕，┐P∧〔Q∨R〕D．P〔Q∨R〕，〔P∧┐Q〕R11．下面哪個(gè)命題公式是重言式〔B〕A．〔PQ〕〔QP〕B．〔PQ〕PC．〔┐P∨Q〕∧┐〔┐P∧Q〕D．〔PQ〕P12．以下公式哪一個(gè)是兩個(gè)命題變元P，Q的小項(xiàng)〔C〕A．P∧┐P∧QB．┐P∨QC．┐P∧QD．┐P∨P∨Q13．一個(gè)公式在等價(jià)意義下，下面哪個(gè)寫法是唯一的?！睠〕A．析取范式B．合取范式C．主析取范式D．以上答案都不對14．命題公式(PQ)的主析取范式編碼為(D)A．B．∨C．D．15.命題公式(PQ)的主合取范為(a)A．B.C.D.16.命題公式的任意兩個(gè)不同極小項(xiàng)的合取式一定為(b)A.永真式B.永假式C.可滿足式D.不可確定17．下面聯(lián)結(jié)詞集中，哪一個(gè)不是聯(lián)結(jié)詞的極小全功能集〔d〕A．{，}B．{↓}C．{}D．{，，}第二章一階邏輯1．設(shè)S(*):*是三好學(xué)生,a:張三,b:李四,命題"張三是三好學(xué)生而李四不是〞符號化為〔〕DA．S〔a〕，S〔b〕B．S〔a〕∨S〔b〕C．S〔a〕∨S〔b〕D．S〔a〕∧S〔b〕2.令F(*):*是有理數(shù)，G(*):*是實(shí)數(shù)。將命題"所有的有理數(shù)都是實(shí)數(shù)，但有的有實(shí)數(shù)不是有理數(shù)〞符號化為〔〕BA.*(F(*)∧G(*))∧*(G(*)F(*))B.*(F(*)G(*))∧*(G(*)∧F(*))C.*(F(*)∧G(*))∧*(G(*)∧F(*))D.*(F(*)G(*))∧*(G(*)F(*))3．設(shè)F(*)：*是火車，G(*)：*是汽車，H(*,y)：*比y快。"每列火車都比*些汽車快〞符號化為〔〕CA．；B．；C．；D．4．設(shè)：是國家選手，：是強(qiáng)健的。命題"沒有一個(gè)國家選手不是強(qiáng)健的〞可符號化為〔〕CA．；B．；C．；D．；5．設(shè)個(gè)體域A={a、b}，公式在A上消去量詞應(yīng)為〔〕DA．P(*)∧S(*)B．P(a)∧P(b)∧S(a)∨S(b)C．P(a)∧S(b)D．P(a)∧P(b)∧(S(a)∨S(b))6．一階公式*(P(*)∨yR(y))→Q(*)中量詞*的轄域是()AA.(P(*)∨yR(y))B.P(*)C.*(P(*)∨yR(y))D.(P(*)∨yR(y))→Q(*)7、設(shè)論域?yàn)檎麛?shù)集，以下公式中哪個(gè)值為真〔〕AA．B.C.D．8．下面給出的一階邏輯等價(jià)式中，哪一個(gè)是錯(cuò)的?！病矪A．A*B〔*〕*〔AB〔*〕〕B．*〔A〔*〕B〔*〕〕*A〔*〕*B〔*〕C．*〔A〔*〕B〔*〕〕*A〔*〕*B〔*〕D．*A〔*〕*〔A〔*〕〕9．在謂詞演算中，以下各式中，哪式是正確的〔〕。BA．B．C．D．10．設(shè)論域?yàn)檎麛?shù)集，以下公式中哪個(gè)值為假〔〕DA．B．C．D．11．設(shè)I是如下一個(gè)解釋：D＝{a,b},則在解釋I下取真值為1的公式是().DA*yP(*,y)B*yP(*,y)C*P(*,*)D*yP(*,y).12．謂詞公式(*)P(*,y)∧(*)(Q(*,z)(*)(y)R(*,y,z))中量詞*的轄域是〔〕AA．〔Q(*,z)(*)(y)R(*,y,z)〕B．Q(*,z)，R(*,y,z)C．Q(*,z)(y)R(*,y,z)D．Q(*,z)13.謂詞公式中變元χ是()DA．自由變元B．既不是自由變元也不是約束變元C．約束變元D．既是自由變元又是約束變元14.一階邏輯公式*(F(*,y)∧G(y,z))→zF(z,y)是〔〕CA.前束范式B.封閉公式C.永真式D.永假式15．一階邏輯公式*P(*)*P(*)是()AA.永真的B.永假的C.可滿足的D.前束范式.16.一階邏輯公式*P(*)yQ(y)的前束范式是〔d〕A.*y(P(*)Q(y))B.*P(*)∨yQ(y)

C.*yP(*)∨Q(y)D.*y(P(*)Q(y))第三章集合的根本概念和運(yùn)算1．以下式子中正確的選項(xiàng)是〔〕．DA．＝0；B．；C．＝{}；D．｛｝2．以下各式中哪個(gè)是錯(cuò)的〔B〕A、；B、；C、｛｝；D、{}。3．以下命題正確的選項(xiàng)是〔〕。AA．{}=B．{}=C．{a}{a，b，c}D．{a，b，c}4．以下各命題哪一個(gè)是假命題〔〕BA．{a,b}{a,b,c,{a,b,c}}B．{a,b}{a,b,c,{a,b,c}}C．{a,b}{a,b,{a,b}}D．{a,b}{{a,b}}5．設(shè)A={{1,2,3},{4,5},{6,7,8}}，以下哪個(gè)式子為真〔〕CA．1∈AB．{1,2,3}?AC．{{4,5}}?AD．A6．設(shè)A＝{}，B=P〔P〔A〕〕，下式中錯(cuò)的是〔〕DA．B；B．{}B；C．{{}}B；D．{，{}}P〔A〕。7．設(shè)A=，B={,{}}，則B－A是〔〕CA．{{}}；B．{}；C．{,{}}；D．8．集合{0}的所有子集是〔〕BA．；B．,{0}；C．{}；D．{,{0}}9．設(shè)A＝{a,b}，則A的冪集P〔A〕為〔〕DA．{a,b}B．{,{a},}C．{,{a,}}D．{,{a},,{a,b}}10．設(shè)*，Y，Z是集合，"一〞是集合相對補(bǔ)運(yùn)算，以下等式不正確的選項(xiàng)是〔〕ＡA．(*－Y)－Z＝*－(Y∩Z)B．(*－Y)－Z＝(*－Z)－YC．(*－Y)－Z＝(*－Z)－(Y－Z)D．(*－Y)－Z＝*－(Y∪Z)11.設(shè)集合A={2,{a},3,4}，B={1,{a},3,4}，E為全集，則以下命題正確的選項(xiàng)是()CA{2}AB{a}AC{{a}}BD{{a},1,3,4}B.12.設(shè)A,B為集合,A∩B=A∪B成立的充分必要條件是(D)A.A=B=B.A=C.B=D.A=B第四章二元關(guān)系與函數(shù)1．設(shè)A＝{1，2}，B＝{a,b,c}，C＝{c,d}，則A×〔B∩C〕為〔B〕A．B．C．D．2．設(shè)集合A={1，2，3}，A上的關(guān)系R={<1，1>，<1，2>，<2，2>，<3，3>，<3，2>}，則R不具備()BA．傳遞性B．對稱性C．自反性D．反對稱性3．設(shè)R是集合A={a,b,c,d}上的二元關(guān)系，R={<a,a>,<a,b>,<a,c>,<a,d>,<c,b>,<d,b>,<d,c>}，則R具有關(guān)系的哪些性質(zhì)〔〕DA.自反性、反對稱性B.反自反性、傳遞性C.自反性、對稱性D.反對稱性、傳遞性4．設(shè)集合A＝{1,2,3,4}，A上的關(guān)系R＝{<1,1>,<2,2>,<1,3>}，則R具有關(guān)系的哪些性質(zhì)〔〕．AA．傳遞性；B．自反性；C．對稱性；D．以上答案都不對5．設(shè)A={0,b}，B={1,b,3}，則A∪B的恒等關(guān)系為〔〕AA．{<0,0>,<1,1>,<b,b>,<3,3>}；B．{<0,0>,<1,1>,<3,3>}；C．{<1,1>,<b,b>,<3,3>}；D．{<0,1>,<1,b>,<b,3>,<3,0>}6．設(shè)A＝{1，2，4，6，8},集合A上的二元關(guān)系，則和分別為〔〕BA．和B．和C．和D．和7．假設(shè)集合A上的關(guān)系R為等價(jià)關(guān)系，則R的必要條件是〔〕DA．對稱的和傳遞的B．反自反的C．反對稱的D．自反的，對稱的和傳遞的8．設(shè)集合A={a,b,c}，A上所有互不一樣的等價(jià)關(guān)系的數(shù)目為()CA.3B.4C.5D.69．設(shè)A={a,b,c,d}，A上的等價(jià)關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，則對應(yīng)于R的A的劃分是〔〕DA．{{a},{b,c},lhtr7xr}B．{{a,b},{c},3f393pl}C．{{a},,{c},xbxnbxd}D．{{a,b},{c,d}}10．P={a、b、c、d}的最大劃分是〔〕〔即集中元素?cái)?shù)目最多的劃分〕CA．{{a}，{b，c}dnftfv5}；B．{a，{b，c}}；C．{{a}、，{c}，vtfhllp}D．{{a，b，c，d}}11．集合A上的關(guān)系R是偏序關(guān)系的必要條件是〔〕AA．自反的，反對稱的和傳遞的；B．自反的和對稱的；C．傳遞和和對稱的；D．傳遞的和反對稱的。12．集合A＝{1,2,3，4，5，6，7，8，9，10}，A上的整除關(guān)系是一個(gè)偏序關(guān)系，則元素10是集合的〔〕．CA．最大元；B．最小元；C．極大元；D．極小元13.以下關(guān)系中哪一個(gè)是集合A={a,b,c,d,e,f}上偏序關(guān)系？〔〕BA.{<a,c>,<b,c>,<c,b>}∪IAB.{<a,e>,<c,d>,<b,f>}∪IAC.{<a,b>,<b,f>,<f,c>}∪IAD.{<b,d>,<e,f>,<d,b>,<f,e>}∪IA14.集合A=，A上的一個(gè)劃分，則對應(yīng)的等價(jià)關(guān)系〔A〕。A．B．C．D．15.設(shè)A={a,b,c,d}，A上的等價(jià)關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，則對應(yīng)于R的A的劃分是〔D〕

A．{{a},{b,c},npjhvxl}B．{{a,b},{c},v5hpbzf}C．{{a},,{c},jb3hrr3}D．{{a,b},{c,d}}16．設(shè)R為實(shí)數(shù)集，映射f：RR，f〔*〕＝-*2+2*-1，則f是〔〕。DA．單射而非滿射B．滿射而非單射C．雙射D．既不是單射，也不是滿射17．設(shè)f和g都是A到A的雙射函數(shù)，則〔fog〕-1為〔D〕A．f-1og-1B.f-og-1C.〔gof〕-1D.g-1of-118.設(shè)集合A={a,b,c},B={β,ε,θ},則從A到B最多可以定義多少個(gè)雙射函數(shù)()DA.27B.9C.8D.6第七章圖的根本概念1．僅由一個(gè)孤立點(diǎn)組成的圖稱為〔〕BA．零圖B．平凡圖C．多重圖D．子圖2．給以下序列，哪一個(gè)可構(gòu)成無向簡單圖的頂點(diǎn)度數(shù)序列〔B〕〔1〕〔1，1，2，2，3〕〔2〕〔1，1，2，2，2〕〔3〕〔1，2，3，4，5〕〔4〕〔1，3，4，4，5〕3．下面所給的數(shù)值序列，能成為簡單圖的度數(shù)序列的是〔〕CA．(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)4．在任何圖G=＜V，E＞中，頂點(diǎn)總度數(shù)和邊數(shù)的關(guān)系為〔〕CA．B．C．D．5．設(shè)G為有n個(gè)結(jié)點(diǎn)的無向完全圖，則G的邊數(shù)為〔〕AA．B．C．n(n－1)D．n(n+1)6．有向圖G=<V，E>，其中V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是()AA．弱連通圖B．單向連通圖C．強(qiáng)連通圖D．不連通圖7．圖G=<V,E>如以下圖所示，從a到d有多少條簡單通路〔〕CA．5B．6C．7D．88．鄰接矩陣具有對稱性的圖一定是〔〕BA．有向圖B．無向圖C．混合圖D．簡單圖9．G=<V,E>是簡單有向圖，可達(dá)矩陣P〔G〕刻劃以下哪種關(guān)系〔〕AA．點(diǎn)與點(diǎn)B．點(diǎn)與邊C．邊與點(diǎn)D．邊與邊10．設(shè)圖G的鄰接矩陣為，則G的頂點(diǎn)數(shù)與邊數(shù)分別為()DA．4,5B．5,6C．4,10D．5,811．在完全圖的所有非同構(gòu)的生成子圖中，有幾個(gè)是3條邊的？()BA.1B.2C.3D.412．圖G和G’的結(jié)點(diǎn)和邊分別存在——對應(yīng)關(guān)系是〔同構(gòu)〕的〔〕A．充分條件B．充分必要條件C．必要條件D．既不充分也不必要條件13.設(shè)圖G=<V,E>為無向圖，|V|=6，|E|=22，則G一定是DA.完全圖B.正則圖C.簡單圖D.多重圖14．設(shè)A〔G〕是有向圖G=〔V，E〕的鄰接矩接，其中第i行中值為1的元素?cái)?shù)目為〔〕BA．結(jié)點(diǎn)Vi的入度B.結(jié)點(diǎn)Vi的出度C．結(jié)點(diǎn)Vi的度數(shù)D.結(jié)點(diǎn)Vj的度數(shù)15.有3條邊的互不同構(gòu)的4階無向簡單圖的個(gè)數(shù)為〔〕AA.2B.3C.4D.516.有向圖G是強(qiáng)連通圖，當(dāng)且僅當(dāng)DA.圖G中至少有一條通路B.圖G中有通過每個(gè)頂點(diǎn)至少一次的通路C.圖G中至少有一條回路D.圖G中有通過每個(gè)頂點(diǎn)至少一次的回路17.有向圖G是單向連通圖，當(dāng)且僅當(dāng)()BA.圖G中至少有一條通路B.圖G中有通過每個(gè)頂點(diǎn)至少一次的通路C.圖G的連通分枝數(shù)為一.

D.圖G中有通過每個(gè)頂點(diǎn)至少一次的回路.第八章一些特殊的圖1．一個(gè)連通的無向圖G，如果它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則它具有一條()BA．哈密爾頓回路B．歐拉回路C．哈密爾頓通路D．初級回路2．無向圖G是歐拉圖，當(dāng)且僅當(dāng)〔〕DA．G的所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)。B．G中所有結(jié)點(diǎn)的度數(shù)全為奇數(shù)。C．G連通且所有結(jié)點(diǎn)度數(shù)全為奇數(shù)。D．G連通且所有結(jié)點(diǎn)度數(shù)全為偶數(shù)。3．設(shè)G是連通平面圖，有5個(gè)頂點(diǎn)，6個(gè)面，則G的邊數(shù)是()AA．9條B．5條C．6條D．11條4．設(shè)G是連通平面圖，G中有6個(gè)頂點(diǎn)8條邊，則G的面的數(shù)目是〔〕CA．2個(gè)面B．3個(gè)面C．4個(gè)面