安陽工學(xué)院離散數(shù)學(xué)

離散數(shù)學(xué)200題一、單項選擇題1．下列是兩個命題變元p，q的小項是（）A．p∧┐p∧qB．┐p∨qC．┐p∧qD．┐p∨p∨q2．令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（）A．p→┐qB．p∨┐qC．p∧qD．p∧┐q3．下列語句中是命題的只有（）A．1+1=10B．x+y=10C．sinx+siny<0D．xmod3=24．下列等值式不正確的是（）A．┐(x)A(x)┐AB．(x)(B→A(x))B→(x)A(x)C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)5．謂詞公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z)中量詞x的轄域是（）A．(x)Q(x,z)→(x)(y)R(x,y,z))B．Q(x,z)→(y)R(x,y,z)C．Q(x,z)→(x)(y)R(x,y,z)D．Q(x,z)6．設(shè)R為實數(shù)集，函數(shù)f：R→R，f(x)=2x，則f是（）A．滿射函數(shù)B．入射函數(shù)C．雙射函數(shù)D．非入射非滿射7．設(shè)A={a,b,c,d}，A上的等價關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，則對應(yīng)于R的A的劃分是（）A．{{a},{b,c},9nxljnz}B．{{a,b},{c},3v7dlxh}C．{{a},,{c},z37b7bx}D．{{a,b},{c,d}}8．設(shè)A={?}，B=P(P(A))，以下正確的式子是（）A．{?,{?}}∈BB．{{?,?}}∈BC．{{?},{{?}}}∈BD．{?,{{?}}}∈B9.無向樹T中有3個3度,2個2度頂點,其余頂點都是樹葉，T有幾片樹葉。A.8B.6C.4D.510.設(shè)A={a,b,c}，則下列哪個是集合A的劃分。A.{{b,c},{c}}B.{{a,b},{a,c}}C.{{a,b},{c}}D.{a,{b,c}}11.設(shè)集合X={0,1,2,3}R是X上的二元關(guān)系，R={<0,0>,<0,2>,<1,0>,<1,1>,<2,3>,<3,2>,<3,3,>}，則哪個是R的關(guān)系矩陣MR。A．B.C.D.12.從下列描述中，指出不正確的表述。A.P({a,{b,c}})={φ,{a},{{b,c}},{a,{b,c}}}B.P({φ})={φ,{φ}}C.(φ)={φ}D.P({a,{b,c}})={{φ},{a},{{b,c}},{a,{b,c}}}13.從下列圖中找出歐拉圖。14.令F(x):x是金屬，G(y):y是液體，H(x,y):x可以溶解在y中，則命題“任何金屬可以溶解在某種液體中”可符號化為什么邏輯表達(dá)式。A.(x)(F(x)∧(y)(G(y)∧H(x,y)))B.(x)((x)F(x)→(G(y)→H(x,y)))C.(x)(F(x)→(y)(G(y)∧H(x,y)))D.(x)(F(x)→(y)(G(y)→H(x,y))15.在個體域D={a,b}中，指出與公式(x)A(x)等價又不含量詞的公式。A.A(a)∧A(b)B.A(a)→A(b)C.A(a)∨A(b)D.A(b)→A(a)16.指出下列是命題的句子。A.水開了嗎?B.x>1.5C.再過9000年，地球上就沒水了。D.我沒講真話。17.給定算式:(((a＋(b＊c))＊d－e)÷(f＋g))－((h＊i)＊j)找出與此算式對應(yīng)的波蘭符號表示式。A．－＊＊a＋bc＋def－g＊hij＊＊B.abc＊＋d＊e－fg＋÷hi＊j＊－C．－÷－＊＋a＊bcde＋fg＊＊hijD.ab＋c＊de＋＊fgh＊－＋ij＊－18.設(shè)N是自然數(shù)集，函數(shù)f:N→N×N.f(n)＝﹤n,n＋1﹥,f({5})是什么。A．滿射函數(shù)B．單射函數(shù)C．{<5,6>}D．雙射函數(shù)19.已知(p→q)←→r的主析取范式是m1∨m3∨m4∨m7，指出與其對應(yīng)的主合取范式。A．m1∨m2∨m5∨m7B．M0∧M2∧M5∧M6C．m0∧m3∧m5∧m6D．M1∨M3∨M5∨M620.設(shè)T(x)：x具有性質(zhì)T，S(y)：y具有性質(zhì)S。命題“若存在x具有性質(zhì)T，則所有的y都沒有性質(zhì)S“的符號化形式是什么。A.x(T(x)→S(x))B.x(T(x)∧S(x))C.xT(x)→yS(y)D.xT(x)→y?S(y)21.判斷下列各非負(fù)整數(shù)列哪個不是可圖化的。A.(5,5,4,4,2,1)B.(4,4,2,1,3)C.(5,4,3,2,2)D.(3,3,1,1)22.設(shè)Z,N分別為整數(shù)和自然數(shù)集，函數(shù)g:Z→N,g(x)＝|x|,g是什么函數(shù)。A．滿射函數(shù)B．滿射非單射C．單射函數(shù)D．單射非滿射23.給定下列各圖，判斷哪些為簡單圖。G1=<V1,E1>,其中,V1={a,b,c,d,e},E1={(a,b),(b,c),(c,d),(a,e)}G2=<V2,E2>,其中,V2=V1,E2={(a,b),(b,e),(e,b),(a,e),(d,e)}D3=<V3,E3>,其中,V3=V1,E3={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}D4=<V4,E4>,其中,V4=V1,E4={<a,b>,<a,b>,<b,c>,<d,e>,<c,d>}A.G1,D4B.G1,D3C.G2,D3,D4D.G2,D424.下列哪個不是平面圖。25設(shè)A={a,b,c}，B={1,2,3}，以下哪一個關(guān)系是從A到B的雙射函數(shù)？A、f={<a,2>,<b,2>,<c,1>}B、f={<a,3>,<b,1>,<c,2>}C、f={<a,1>,<b,2>,<c,3>,<a,3>}D、f={<a,1>,<b,2>}26.給定命題公式如右：p∨（q∧┐r），指出公式的成真賦值。A、無B、全體賦值C、000，100，101，111D、010，110，27．設(shè)S={?，{1}，{1，2}}，則P（S）有幾個元素。A、3B、6C、7D、828.下述哪一個不是命題？A、離散數(shù)學(xué)是計算機(jī)系的一門必修課。B、不存在最大偶數(shù)。(C)E={(a,c),(b,a),(b,c),(d,a),(d,c)}(D)E={(a,d),(a,c),(a,d),(b,d),(c,d)}73設(shè)集合A={a1,a2,a3,a4},B={b1,b2,b3},σ是從A到B的函數(shù)，σ={（a1,b2）,(a2,b2),(a3,b1),(a4,b3)}，則σ是下面4個中的哪一種（）（A）雙射；（B）滿射但不是單射；（C）單射但不是滿射（D）非單射也非滿射74．當(dāng)且僅當(dāng)為下面4個中的哪一個時，無向圖G是歐拉圖（）（A）G的所有結(jié)點的次數(shù)為偶數(shù)（B）G的所有結(jié)點的次數(shù)為奇數(shù)（C）G連通且所有結(jié)點的次數(shù)為偶數(shù)（D）G連通且所有結(jié)點的次數(shù)為奇數(shù)75~79.75個學(xué)生去書店買語文,數(shù)學(xué),英語書,每種書每個學(xué)生至多買1本.已知20個學(xué)生每人買3本書,55個學(xué)生每人至少買2本書.每本書的價格都是1元,所有學(xué)生總共花費140元,恰好買2本書的有()多少個學(xué)生.至少買2本書的學(xué)生花費()元.買1本書的有()個學(xué)生.至少買1本書的有()個學(xué)生.沒買書的有()個學(xué)生.A.55B.40C.35D.15E.30F.130G.65H.140J.60K.1080~86.為每個邏輯斷言選擇正確的解釋。T(x)：x今天來上課，S(x)：x學(xué)計算機(jī)專業(yè)的學(xué)生，P(x)：x編程序，G(x)：x玩游戲。個體域是殷都大學(xué)。xT(x)表示（），?xT(x)表示（），x?T(x)表示（），x(S(x)→P(x))表示（），x(S(x)∧G(x))表示（），x(S(x)∧P(x))表示（），x(S(x)→G(x))表示（）。A學(xué)計算機(jī)專業(yè)的學(xué)生會編程序，B殷都大學(xué)的學(xué)生都是計算機(jī)專業(yè)且會編程序。C有些計算機(jī)專業(yè)的學(xué)生玩游戲，D所有同學(xué)今天都來上課了，E今天有同學(xué)沒來上課。F計算機(jī)專業(yè)的學(xué)生玩游戲，G今天沒有同學(xué)來上課。87~91對60個人的調(diào)查表明有25人閱讀News,26人閱讀Times,26人閱讀Happy,9人閱讀News和Happy,11人閱讀News和Times,8人閱讀Times和Happy,還有8人什么雜志也不閱讀.問閱讀全部3種雜志的有()人,只閱讀News的有()人,只閱讀Times的有()人,只閱讀Happy的有()人,只閱讀一本雜志的有()人.A.5B.8C.3D.15E.30F.13G.65H.12J.60K.1092設(shè)個體域是正整數(shù)集，則下列公式中真值為真的公式是()A.(x)(y)(x·y=0)B.(x)(y)(x·y=1)C.(x)(y)(x·y=2)D.(x)(y)(z)(x÷y=2)93設(shè)A={a,b,c},R是A的關(guān)系且R={<a,b>,<a,c>},則R是的()A.傳遞B.自反C.對稱D.反自反94下述不是命題的是()A.做人真難啊!B.后天是陰天。C.2是偶數(shù)。D.地球是方的。95.命題公式P→(P∨Q∨R)是()A.恒真的B.恒假的C.可滿足的D.合取范式96.設(shè)有A={a,b,c}上的關(guān)系R={<a,a>,<b,b>,<a,b>,<b,a>,<c,a>}，則R不具有()A.自反性B.對稱性C.傳遞性D.反對稱性97下列等值式不正確的是（）A．┐("x)A?($x)┐AB．("x)(B→A(x))?B→("x)A(x)C．("x)(A(x)∧B(x))?("x)A(x)∧("x)B(x)D．("x)($y)(A(x)→B(y))?("x)A(x)→($y)B(y)98謂詞公式("x)P(x,y)∧($x)(Q(x,z)→($x)("y)R(x,y,z))中量詞（$x）的轄域是（）A．($x)Q(x,z)→($x)("y)R(x,y,z))B．Q(x,z)→("y)R(x,y,z)C．Q(x,z)→($x)("y)R(x,y,z)D．Q(x,z)99設(shè)X，Y，Z是集合，一是集合相對補(bǔ)運(yùn)算，下列等式不正確的是（）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)100設(shè)G是連通平面圖，G中有6個頂點8條邊，則G的面的數(shù)目是（）A．2個面B．3個面C．4個面D．5個面二、填空題101.設(shè)p:天下雨，q:天刮風(fēng)，r:我去書店，則命題“如果天不下雨并且不刮風(fēng)，我就去書店”的符號化形式為_______________。102.設(shè)F(x):x是人，H(x,y):x與y一樣高，在一階邏輯中，命題“人都不一樣高”的符號化形式為______________________________。103.設(shè)A={a，b}，則A上共有__________個不同的二元關(guān)系。104.設(shè)A={1,2},B={2,3},C={a,b,c}，則(A∪B)×C=__________________________________。105.無環(huán)有向圖的關(guān)聯(lián)矩陣的所有元素之和為106.設(shè)G是完全二叉樹，G有15個點，其中8個葉子，則G的總度數(shù)為__________。107.設(shè)，，，則domR=。108.設(shè)簡單圖G所有結(jié)點的度之和為12，則G一定有條邊。109.圖4中結(jié)點V6的度數(shù)為____。110.(p∧q)→r的主合取范式為________________________111.┐(┐p→(q∨r))的成真賦值為______________________________。112.(p∧q)→r的主合取范式為________________________。113.設(shè)A={2,3,6,12},≤是A上的整除關(guān)系，則偏序集〈A，≤〉的最大元是_______。114.設(shè)A={φ,{φ}},B={0,1},從A到B的雙射函數(shù)有________個。115.設(shè)G是完全二叉樹，G有15個點，其中8個葉點，則G的分枝點數(shù)為________________。116.一棵無向樹有2個4度頂點，3個3度頂點，其余的都是樹葉，則該樹有片樹葉。117．設(shè)A={a,b,c}，B={1,2,3}，則A到B共可產(chǎn)生_____________個不同的雙射函數(shù)。118.某公司有銷售人員82人，維修人員191人，既做銷售又搞維修的人員20人，既非銷售人員又非維修人員有912人，則該公司總?cè)藬?shù)為______。119.設(shè)個體域是{a,b,c}，則("x)S(x)等價于命題公式__________120．一公式為之充分必要條件是其析取范式之每一析取項中均必同時包含一命題變元及其否定；一公式為之充分必要條件是其合取范式之每一合取項中均必同時包含一命題變元及其否定。121．前束范式具有形式(Q1V1)(Q2V2)…(QnVn)A，其中Qi(1≤i≤n)為，A為的謂詞公式。122．設(shè)論域是{a,b,c}，則(x)S(x)等價于命題公式；()S(x)等價于命題公式123．設(shè)R為A上的關(guān)系，則R的自反閉包r(R)=，對稱閉包s(R)=。124．某集合A上的二元關(guān)系R具有對稱性，反對稱性，自反性和傳遞性，此關(guān)系R是，其關(guān)系矩陣是。125．設(shè)<S,≤>是一個偏序集，如果S中的任意兩個元素都有和，則稱S關(guān)于≤構(gòu)成一個格。126．設(shè)Z是整數(shù)集，在Z上定義二元運(yùn)算*為a*b=a+b+a?b，其中+和?是數(shù)的加法和乘法，則代數(shù)系統(tǒng)<Z,*>的幺元是，零元是。127．如下平面圖有2個面R1和R2，其中deg(R1)=，deg(R2)=。128．無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是，并且所有結(jié)點的度數(shù)都是。129.設(shè)p:小王走路,q:小王聽音樂,在命題邏輯中，命題“小王邊走路邊聽音樂”的符號化形式為___________________。130.設(shè)F(x):x是人，H(x,y):x與y一樣高，在一階邏輯中，命題“人都不一樣高”的符號化形式為_________________。131.設(shè)G是n階無向帶權(quán)邊通圖，各變的權(quán)均為a(a>0),設(shè)T是G的一棵最小生成樹，則T的權(quán)W(T)=_______________________。132.設(shè)G1,G2,G3,G4都是4階3條邊的無向簡單圖，則它們之間至少有___________________個是同構(gòu)的。133．設(shè)G是n（n2）階二部圖，又是平面圖，則命題“G的對偶圖是歐拉圖”的真值為_______________________。134.設(shè)為整數(shù)集，，則f的值域ranf=___________。135.設(shè)則A上共有____________個不同的等價關(guān)系。136.設(shè)，恒等關(guān)系IA的傳遞閉包t(IA)=_________________。137.在實數(shù)集合R上定義二元運(yùn)算如下：____________其中“-”為普通的減法，命題“是代數(shù)系統(tǒng)”的真值為___________________。138.在一階邏輯中將命題”鳥都會飛翔”符號化___________________.139.在一階邏輯中將命題”沒有不愛看電影的人”符號化__________________140.將命題”如果今天是1號，則明天是2號”符號化___________________。141.R={<1,1>,<2,2>.}是A={1,2}上的二元關(guān)系,則R具有哪些性質(zhì)__________________。141.設(shè)p:小王走路,q:小王聽音樂,在命題邏輯中，命題“小王邊走路邊聽音樂”的符號化形式為___________________。142.設(shè)F(x):x是人，H(x,y):x與y一樣高，在一階邏輯中，命題“人都不一樣高”的符號化形式為_________________。143.p∧q的成真賦值為________________________。144.設(shè)f={<1,2>,<3,4>}為整數(shù)集，則f的值域ranf=___________。145.設(shè)│A│=3則A上共有____________個不同的二元關(guān)系。146命題公式p∧(q∨┓r)的成真指派的是_______________。147q的主合取范式為____________。148A={ab}，則A上共有__________個不同的偏序關(guān)系。149設(shè)A={a,b,c}，B={1,2,3}，則A到B共可產(chǎn)生_____________個不同的雙射函數(shù)。150設(shè)A是n(n≥1)元集，則A上共有22n個二元運(yùn)算，其中有______________個是A到A的函數(shù)。三、計算與應(yīng)用題151求出從A={1,2}到B={x,y}的所有函數(shù)，并指出哪些是雙射函數(shù)，哪些是滿射函數(shù)。152如果論域是集合{a,b,c}，試消去給定公式中的量詞：。153設(shè)A={a,b,c}，P（A）是A的冪集，是集合對稱差運(yùn)算。已知<P(A),>是群。在群<P(A),>中，①找出其幺元。②找出任一元素的逆元。③求元素x使?jié)M足{a}x=。154用等值演算法求公式┐(p→q)(p→┐q)的主合取范式155畫出5個具有5個結(jié)點5條邊的非同構(gòu)的無向連通簡單圖。156在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除關(guān)系，求集合D={2,3,4,6}的極大元，極小元，最大元，最小元，最小上界和最大下界。設(shè)<A,R>為一個偏序集，其中，A={1，2，3，4，6，9，24，54},R是A上的整除關(guān)系。157.畫出<A,R>的哈斯圖；158.求R關(guān)于A的極大元；159.求B={4,6,9}的最小上界和最大下界。160設(shè)7個字母在通信中出現(xiàn)的頻率如下:a:30%,b:20%,c:15%,d:10%,e:15%,f:5%,g:5%.編一個最佳2元前綴碼.在這個前綴碼中,a,b,c,d,e,f,g的碼長分別是多少?傳輸10000個按上述比例出現(xiàn)的字母需要多少個二進(jìn)制數(shù)字?161.設(shè)A={a,b,c,d,},R=IA∪{<a,b>,<b,a>,<c,d>,<d,c>,}是A上的等價關(guān)系，求商集A/R及各元素的等價類。162求公式p→((q∧r)∧(p∨(?q∧?r)))的主析取范式163判斷推理是否正確設(shè)y＝2|x|,x為實數(shù)，推理如下：若y在x＝0可導(dǎo)，則y在x＝0連續(xù)。y在x＝0連續(xù)。所以，y在x＝0可導(dǎo)。在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,24}，≤是Z中的整除關(guān)系。163.求集合D={2,3,4,6}的極大元，極小元；164.求集合D={2,3,4,6}的最大元，最小元；165.求集合D={2,3,4,6}的最小上界和最大下界。166設(shè)集合A={1,3,5,7,9,11,13,15},A上的一個劃分S={{1,15},{3,9,11,13},{5,7}}。試求由S導(dǎo)出的A上的等價關(guān)系R。167求出從A={1,2}到B={x,y}的所有函數(shù)，并指出哪些是雙射函數(shù)，哪些是滿射函數(shù)。168．用等值演算法求公式┐(p→q)∧(p→┐q)的主合取范式169．在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除關(guān)系，求集合D={2,3,4,6}的極大元，極小元，最大元，最小元，最小上界和最大下界。設(shè)二元關(guān)系R={<{a},b>,<{φ},φ>,<{φ},{φ}>}求：171計算domR172計算ranR173計算R·R174計算R-1·R-1..設(shè)，，試求：176作出〈A，R〉的哈斯圖177求A的最大元、最小元、上界、下