離散數(shù)學(xué)復(fù)習題參考帶

一、選擇題：（每題2’）1、以下語句中不是命題的有（

）。A．失散數(shù)學(xué)是計算機專業(yè)的一門必修課。

B．雞有三只腳。C．太陽系之外的星球上有生物

。

D．你打算考碩士研究生嗎2、命題公式

A與

B是等價的，是指（

）。A．A與B有同樣的原子變元C．當A的真值為真時，B的真值也為真

D．

B．A與

A與B都是可知足的B有同樣的真值3、所有使命題公式

P∨(Q∧R)為真的賦值為（

）。A．010，100，101，110，111C．全體賦值

B．D．

010，100，101，111不存在4、合式公式(P∧Q)R的主析取范式中含極小項的個數(shù)為（）。A．2B．3C．5D．05、一個公式在等價意義下，下邊哪個寫法是獨一的（）。A．析取范式B．合取范式C．主析取范式D．以上答案都不對6、下述公式中是重言式的有（）。A．(P∧Q)(P∨Q)B．(PQ)((PQ)∧(QP))C．(PQ)∧QD．P(P∧Q)7、命題公式(PQ)(Q∨P)中極小項的個數(shù)為（），成真賦值的個數(shù)為（）。A．0B．1C．2D．38、若公式(P∧Q)∨(P∧R)的主析取范式為m001∨m011∨m110∨m111則它的主合取范式為（）。A．m001∧m011∧m110∧m111B．M∧M∧M100∧M101000010C．M001∧M011∧M∧M111D．m000∧m010∧m100∧m1011109、以下公式中正確的等價式是（）。A．(x)A(x)(x)A(x)B．(x)(y)A(x,y)(y)(x)A(x,y)C．(x)A(x)(x)A(x)D．(x)(A(x)∧B(x))(x)A(x)∨(x)B(x)10、以下等價關(guān)系正確的選項是（）。A．x(P(x)∨Q(x))xP(x)∨xQ(x)B．x(P(x)∨Q(x))xP(x)∨xQ(x)C．x(P(x)Q)xP(x)QD．x(P(x)Q)xP(x)Q11、設(shè)個體域為整數(shù)集，以下真值為真的公式是（）。A．xy（x·y=1）B．xy（x·y=0）C．xy（x·y=y）D．xy（x+y=2y）12、設(shè)S={,{1},{1,2}}，則有（）S。A．{{1,2}}B．{1,2}C．{1}D．{2}13、以下是真命題的有（）。A．{a}{{a}}B．{{}}{,{}}C．{,{}}D．{}{,{}}S）個元素。14、設(shè)S={,{1},{1,2}}，則2有（A．3B．6C．7D．815、已知冪集的基數(shù)|(A)|=2048，則會合A的基數(shù)|A|為（）。A．11B．12C．10D．916、設(shè)A={1，2，3}，則A上的二元關(guān)系有（）個。323322A．2B．3C．2D．317、設(shè)A={a,b,c,d}，A上的等價關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I，則對應(yīng)于R的A的區(qū)分是（）。AA．{{a},{b,c},6g0ag8q}B．{{a,b},{c},kiweik4}C．{{a},,{c},guamkg0}D．{{a,b},{c,d}}18、設(shè)R，S是會合A上的關(guān)系，則以下說法正確的選項是（）。A．若R、S是自反的，則RS是自反的B．若R、S是反自反的，則RS是反自反的C．若R、S是對稱的，則RS是對稱的D．若R、S是傳達的，則RS是傳達的19、會合A上的相容關(guān)系R的關(guān)系矩陣M(R)的對角線元素（）。A．所有是1B．所有是0C．有的是1，有的是0D．有的是220、設(shè)會合A={1，2，3}，A上的關(guān)系R={<1,1>，<1,2>，<2,2>，<3,3>，<3,2>}，則R不具備（）。A．自反性B．傳達性C．對稱性D．反對稱性21、設(shè)S{1,2,3}，S上關(guān)系R的關(guān)系圖為（以下圖），則R擁有（A．自反性、對稱性、傳達性C．反自反性、反對稱性、傳達性

）性質(zhì)。B．反自反性、反對稱性D．自反性22、設(shè)S={1，2，3}，R為S上的關(guān)系，其關(guān)系圖為則R擁有（）的性質(zhì)。A．自反、對稱、傳達B．什么性質(zhì)也沒有C．反自反、反對稱、傳達D．自反、對稱、反對稱、傳達23、設(shè)A={1,2,3}，B={a,b}，以下各二元關(guān)系中是A到B的函數(shù)的是（）。A．R={<1,a>,<2,a>,<3,a>}B．R={<1,a>,<2,a>,<2,b>,<3,a>}C．R={<1,a>,<2,b>}D．R={<2,a>,<2,b>}24、設(shè)R為實數(shù)集，映照f：RR，f(x)=-x2+2x-1，則f是（）。A．單射而非滿射B．滿射而非單射C．雙射D．既不是單射，也不是滿射25、設(shè)A={，{1}，{1，3}，{1，2，3}}則A上包括關(guān)系“”的哈斯圖為（）。A．B．C．D．26、N是自然數(shù)會合，定義f：NN，f(x)=xmod3（即x除以3的余數(shù)），則f是（）。A．滿射不是單射B．單射不是滿射C．雙射D．不是單射也不是滿射27、設(shè)S={,{1},{1,2}}，則有（）S。A．{{1,2}}B．{1,2}C．{1}D．{2}28、會合A={x|x=2n∧nN}對（）運算關(guān)閉。A．加法B．減法C．乘法D．|x－y|29、設(shè)*是會合A上的二元運算，稱Z是A上對于運算*的零元，若（）。A．xA，有x*Z=Z*x=ZB．ZA，且xA有x*Z=Z*x=ZC．ZA，且xA有x*Z=Z*x=xD．ZA，且xA有x*Z=Z*x=Z30、下邊偏序集（）能組成格。31、在（）中，補元是獨一的。A．有界格B．有補格C．分派格D．有補分派格。32、下邊四組數(shù)能組成無向簡單圖的度數(shù)序列的有（）。A．(2,2,2,2,2)B．(1,1,2,2,3)C．(1,1,2,2,2)D．(1,1,3,3,3)33、無向圖結(jié)點之間的連通性，是結(jié)點集之間的一個（）。A．連通關(guān)系B．偏序關(guān)系C．等價關(guān)系D．函數(shù)關(guān)系34、已知圖G的相鄰矩陣為：則G有（）。A．5點，8邊B．6點，7邊C．5點，7邊D．6點，8邊35、以下四組數(shù)為結(jié)點度序列，能組成無向圖的是（）。A．2,3,4,5,6,7B．1,2,2,3,4C．2,1,1,1,2D．3,3,5,6,036、以下幾個圖是簡單圖的有（）。A．G1=(V1,E1)，此中V1={a,b,c,d,e}，E1={(a,b),(b,e),(e,b),(a,e),(d,e)}B．G2=(V2,E2)，此中V2=V1，E2={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}C．G=(V,E)，此中V=V，E={(a,b),(b,e),(e,d),(c,c)}333313D．G=(V,E)，此中V=V，E={<a,a>,<a,b>,<b,c>,<e,c>,<e,d>}44441437、在一棵樹中有7片樹葉，3個3度結(jié)點，其他都是4度結(jié)點則該樹有（）個4度結(jié)點。A．1B．2C．3D．438、一棵樹有2個4度結(jié)點，3個3數(shù)度結(jié)點，其他是樹葉，則該樹中樹葉的個數(shù)是（）。A．8B．9C．10D．1139、設(shè)圖G是有6個極點的連通圖，總度數(shù)為20，則從G中刪去（）邊后使之變?yōu)闃?。A．10B．5C．3D．240、下邊那一個圖可一筆劃出（）。41、在以下各圖中（）歐拉圖。42、以下圖中既不是歐拉圖，也不是哈密爾頓圖的是（）。43、在以下的有向圖中，從

V1到

V4長度為

3的道路有（

）條。A．1B．2C．3D．444、圖中從v到v長度為3的通路有（）條。13A．0B．1C．2D．3二、判斷題（每題1分）1．x(A(x)B(x))xA(x)xB(x)。（Y）2．設(shè)A，B，C是隨意三個會合。（1）若AB且BC，則AC。（Y）（2）若AB且BC，則AC。（N）（3）若AB且BC，則AC。（N）（4）(AB)C=(A×C)(B×C)。（Y）（5）A∪(BC)=(A∪B)(A∪C)。（N）3．A，B，C為隨意會合，若A∪B=A∪C，則B=C。（N）4．可能有某種關(guān)系，既不是自反的，也不是反自反的。（Y）5．可能有某種關(guān)系，既是對稱的，又是反對稱的。（Y）6．設(shè)R是實數(shù)集，R上的關(guān)系S={<x,y>||x-y|＜2∧x,yR}，S是相容關(guān)系。（Y）c也是對稱的。（Y）7．若會合A上的關(guān)系R是對稱的，則R8．數(shù)會合上的不等關(guān)系（≠）可確立A的一個區(qū)分（N）9．設(shè)會合A、B、C為隨意會合，若A×B=A，×C則B=C。（N）10．函數(shù)的復(fù)合運算“”知足聯(lián)合律。（Y）11．會合A上的恒等關(guān)系是一個雙射函數(shù)。（Y）12．任何一個循環(huán)群必然是阿貝爾群。（Y）13．任何循環(huán)群必然是阿貝爾群，反之亦真。（N）14．設(shè)<A，≤>是偏序集，BA，則B的極大元bB且獨一。（N）15．群是每個元素都有逆元的半群。（N）16．在代數(shù)系統(tǒng)<S,>中，若一個元素的逆元是獨一的，其運算必是可聯(lián)合的。（N）17．每一個有限整環(huán)必定是域，反之也對。（N）18．設(shè)<A,∧,∨>是布爾代數(shù)，則<A,∧,∨>必定為有補分派格。（Y）19．若平面圖共有v個結(jié)點，e條邊和r個面，則v–e+r=2。（N）20．任何有向圖中各結(jié)點入度之和等于邊數(shù)。（Y）21．若兩圖結(jié)點數(shù)同樣，邊數(shù)相等，度數(shù)同樣的結(jié)點數(shù)量相等，則兩圖是同構(gòu)的。（N）22．一個圖是平面圖，當且僅當它包括與Ｋ3,3或Ｋ5在２度結(jié)點內(nèi)同構(gòu)的子圖。（N）23．有割點的連通圖可能是哈密爾頓圖。（N）24．無多重邊的圖是簡單圖。（N）25．根樹中最長路徑的端點都是葉子。（N）26．在完整二叉樹中，如有t片葉子，則邊的總數(shù)e=2t－1。（N）27．群中能夠有零元（對階數(shù)大于1的群）。（N）28．任何循環(huán)群必然是阿貝爾群，反之亦真。（N）29．每一個鏈都是分派格。（Y）30．不行能有偶數(shù)個結(jié)點，奇數(shù)條邊的歐拉圖。（N）31．會合A上的恒等關(guān)系是一個雙射函數(shù)。（Y）32．設(shè)Q為有理數(shù)集，Q上運算*定義為abmax(a,b)，則Q，是半群。（Y）33．在完整二元樹中，如有t片葉子，則邊的總數(shù)e2t1。（N）34．能一筆劃出的圖不必定是歐拉圖。（Y）35．根樹中最長路徑的端點都是葉子。（N）36．命題公式(A∧(AB))B是一個矛盾式。（N）37．設(shè)R是實數(shù)集，R上的關(guān)系F={<x,y>||x-y|<2∧x,yR}，則F是相容關(guān)系。（Y）38．設(shè)<A，≤>是偏序集，BA，則B的極大元bB且獨一。（N）39．無多重邊的圖是簡單圖。（N）40．謂詞公式xP(x)xQ(x)∨yR(y)的前束范式是xzy(P(x)Q(z)∨R(y))。（Y）三、解答題（此題分4小題，合計35分）1、試求P((PQ)(QP))的主析取范式。2、用真值表判斷以下公式是永真式永假式可知足式（1）(P∧P)Q（2）(PQ)∧Q（3）((PQ)∧(QR))(PR)解：（1）真值表：PQPP∧P(P∧P)Q00101011001000111000所以公式（1）為可知足。（2）真值表PQPQ（PQ）(PQ)∧Q00100011001001011100所以公式（2）為永假式。（3）真值表PQRPQQRPR（（PQ）∧（QR））（PR）00011110011111010101101111111000101101011111010011111111所以公式（3）為永真式。3、設(shè)個體域是D={2，3，6}，F(xiàn)(x):x，≤3G(x):x>5，消去公式x(F(x)∧yG(y))中的量詞，并議論其真值。解：x(F(x)∧yG(y))x(F(x))∧yG(y)(F(2)∧F(3)∧F(6))∧(G(2)∨G(3)∨G(6))F∧TF4、求以下公式的前束范式：(1)xF(x)∧﹁xG(x)(2)(xF(x,y)→yG(y))→xH(x,y)5、經(jīng)過求主析取范式判斷以下命題公式能否等值：(P∨Q)∧(P∨Q∨R)與(P∧(Q∨R))∨(Q∧(P∨R))。解：(P∨Q)∧(P∨Q∨R)(P∨Q∨(R∧R))∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M∧M∧M?M∧M∧M∏(0,1,4)∑(2,3,5,6,7)104014(P∧(Q∨R))∨(Q∧(P∨R))(P∧Q)∨(P∧R)∨(P∧Q)∨(Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)m7∨m6∨m5∨m3∨m2∑(2,3,5,6,7)因而可知(P∨Q)∧(P∨Q∨R)(P∧(Q∨R))∨(Q∧(P∨R))6、設(shè)個體域為

D={-2,3,6}，謂詞

P(x):x

3，

G(x):x

5，R(x):x

7，求謂詞公式的真值：x(R(x)

P(x))

G(5)7、若會合A={a,{b,c}}的冪集為(A)，會合B={,{}}的冪集為(B)，求：(A)(B)。解：(A)={,{a},{{b,c}},{a,{b,c}}}(B)={,{},{{}},{{,{}}}(A)(B)={{a},{{b,c}},{a,{b,c}},{},{{}},{{,{}}}8、設(shè)會合A={2,3,4,6,8,12,24}，R為A上的整除關(guān)系，畫出偏序集<A,R>的哈斯圖；寫出會合A中的最大元、最小元、極大元、極小元；寫出A的子集B={2,3,6,12}的上界、下界、最小上界、最大下界。9、會合S={1，2，3，4，5}，找出S上的等價關(guān)系，此關(guān)系能產(chǎn)生區(qū)分{{1，2}，{3}，{4，5}}，并畫出關(guān)系圖。10、已知A＝{a，b，c，d}，A上的關(guān)系R定義為：R＝{<a,b>，<b,a>，<a,c>，<b,d>，<d,a>}，求：r(R)，s(R)，t(R)。11、已知A＝{1，2，3，4，5}，A上的關(guān)系R定義為：R＝{<1,2>，<2,1>，<1,3>，<2,4>，<4,1>，<5,5>，<5,3>，<5,4>}，求：r(R)，s(R)，t(R)。12、會合A{1,2,3,4}上的關(guān)系R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>}，寫出關(guān)系矩陣MR，畫出關(guān)系圖并議論關(guān)系R的性質(zhì)。13、設(shè)會合A={2,3,4,6,8,12,24}，R為A上的整除關(guān)系，畫出偏序集<A,R>的哈斯圖。14、已知G={1,2,3,4,5,6}，×為模7乘法。試說明<G,×>能否組成群能否為循環(huán)群假如，生成元是什么7715、一棵樹T中，有3個2度結(jié)點，一個3度結(jié)點，其他結(jié)點都是樹葉。1）T中有幾個結(jié)點；2）畫出擁有上述度數(shù)的所有非同構(gòu)的無向圖。16、設(shè)A={1，2，3，4，5}，A上的偏序關(guān)系如右圖所示，求：A的子集{3，4，5}和{1，2，3}的上界，下界，上確界和下確界。17、求圖中A到其他各極點的最短路徑，并寫出它們的權(quán)。18、設(shè)帶權(quán)無向圖以下，求其最小生成樹T及該樹的總權(quán)值。v27v354v112333v65v519、權(quán)數(shù)1，4，9，16，25，36，49，64，81，100結(jié)構(gòu)一棵最優(yōu)二叉樹。20、以以下圖所示的賦權(quán)圖表示某七個城市v1,v2,,v7及早先算出它們之間的一些直接通訊線路造價，試給出一個設(shè)計方案，使得各城市之間能夠通訊并且總造價最小。四、寫出對應(yīng)下邊推理的證明：（此題10分，1*10’=10’）1、(AB)∧(CD)，BE，DF，￢(E∧F)，AC￢A2、P∨WR，RS∨T，ST，￢T∧Q￢W3、假如小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王去看電影。所以，當小趙去看電影時，小李也去看電影。4、假如小張去看電影，則當小王去看電影時，小李也去。小趙不去看電影或小張去看電影。小王去看電影。所以當小趙去看電影時，小李也去。5、假如我學(xué)習（

P），那么我數(shù)學(xué)不會不及格。假如我不熱中于玩撲克（

R），那么我將學(xué)習。但我數(shù)學(xué)不及格（Q）。所以我熱中于玩撲克。（注：請按括號中提示的字母翻譯并進行論證。

）6、或許是天晴，或許是下雨。假如是天晴，我去看電影。假如我去看電影，我就不看書。所以，假如我在看書，則天在下雨。7、所有牛都有角，有些動物是牛；所以，有些動物有角。（P(x)：x是牛；Q(x)：x有角；R(x)：x是動物）8、每個喜愛步行的人都不喜愛坐汽車；每個人或許喜愛坐汽車或許喜愛騎自行車；有的人不喜愛騎自行車。因此有的人不喜愛步行。（先將推理在一階邏輯中符號化，隨后考證其正確性）五、解答題（此題10分，1*10’=10’）1、某班有還有

25個學(xué)生，此中14人會打籃球，12人會打排球，6人會打籃球和排球，2人會打這三種球。而6個會打網(wǎng)球的人都會打此外一種球（指籃球或排球）

5人會打籃球和網(wǎng)球，，求不會打這三種球的人數(shù)。2、120名學(xué)生參加考試，此次考試有A、B和名學(xué)生做對A和B；16名學(xué)生做對A和

C共3道題，考試結(jié)果以下：12名學(xué)生C；28名學(xué)生做對B和C；做對A題的有

3道題都做對了；48名學(xué)生；做對

20B題的有

56名學(xué)生；還有

16名學(xué)生一道題也沒做對。試求做對了

C題的學(xué)生有多少名。3、已知

100個學(xué)生中有

32人學(xué)數(shù)學(xué)，

20人學(xué)物理，

45人學(xué)生物，

15人學(xué)數(shù)學(xué)和生物，

7人學(xué)數(shù)學(xué)和物理，10

學(xué)物理和生物，

30人這三門課一門也沒學(xué)。問三門課程所有都學(xué)的學(xué)生人數(shù)是多少4、設(shè)A={a,b,c}，求A上所有的等價關(guān)系。5、給定權(quán)1，4，9，16，25，36，49，64，81，100；結(jié)構(gòu)一棵最優(yōu)二叉樹。6、畫出哈斯圖：設(shè)B＝{a,b,c}，R={<s1,s2>|s1s2s