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

1、一、選擇題：（每題2）1、下列語句中不是命題的有（ ）。A離散數(shù)學(xué)是計算機(jī)專業(yè)的一門必修課。B雞有三只腳。C太陽系以外的星球上有生物。D你打算考碩士研究生嗎?2、命題公式A與B是等價的，是指（ ）。A A與B有相同的原子變元 B A與B都是可滿足的C 當(dāng)A的真值為真時，B的真值也為真D A與B有相同的真值3、所有使命題公式P(Q¬R)為真的賦值為（ ）。A 010，100，101，110，111B 010，100，101，111C 全體賦值D 不存在4、合式公式Ø(PQ)®R的主析取范式中含極小項(xiàng)的個數(shù)為（ ）。A2B3C5D0 5、一個公式在等價意義下，下面哪個

2、寫法是唯一的（ ）。A析取范式 B合取范式 C主析取范式 D以上答案都不對6、下述公式中是重言式的有（ ）。A(PQ) ® (PQ)B(P«Q) « ( P®Q)(Q®P)CØ(P ®Q)QDP ®(PQ)7、命題公式 (ØP®Q) ®(ØQP) 中極小項(xiàng)的個數(shù)為（ ），成真賦值的個數(shù)為（ ）。A0B1C2D3 8、若公式 (PQ)(ØPR) 的主析取范式為 m001m011m110m111 則它的主合取范式為（ ）。Am001m011m110m111BM000M0

3、10M100M101CM001M011M110M111Dm000m010m100m1019、下列公式中正確的等價式是（ ）。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) ) 

4、9; "x P(x) "x Q(x)B$x ( P(x) Q(x) ) Û $x P(x) $x Q(x)C"x ( P(x) ®Q ) Û "x P(x) ® QD$x ( P(x) ®Q ) Û $x P(x) ® Q11、設(shè)個體域?yàn)檎麛?shù)集，下列真值為真的公式是（）。A"x$y（x·y=1）B$x"y（x·y=0）C"x"y（x·y=y）D$x"y（x+y=2y）12、設(shè)S=Æ,1,1,2，則

5、有（ ）ÍS。A1,2 B1,2 C1 D2 13、下列是真命題的有（ ）。AaÍa BÆÎÆ,ÆCÆÎÆ,Æ DÆÎÆ,Æ 14、設(shè)S=Æ,1,1,2，則2S 有（ ）個元素。A3B6 C7D8 15、已知冪集的基數(shù)|r( A)|=2048，則集合A的基數(shù)|A|為（ ）。A11B12C10D916、設(shè)A=1，2，3，則A上的二元關(guān)系有（ ）個。A 23 B 32 C23´3D32´217、設(shè)A=a, b, c, d，A上的等

6、價關(guān)系R=<a, b>,<b, a>,<c, d>,<d, c>IA，則對應(yīng)于R的A的劃分是（ ）。Aa, b, c, d Ba, b, c, dCa, b, c, d Da, b, c, d18、設(shè)R，S是集合A上的關(guān)系，則下列說法正確的是（ ）。A若R、S是自反的，則R°S是自反的B若R、S是反自反的，則R°S是反自反的C若R、S是對稱的，則R°S是對稱的D若R、S是傳遞的，則R°S是傳遞的19、集合A上的相容關(guān)系R的關(guān)系矩陣M(R)的對角線元素（ ）。A全是1B全是0C有的是1，有的是0D有的是220

7、、設(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上關(guān)系R的關(guān)系圖為（如圖所示），則R具有（ ）性質(zhì)。A自反性、對稱性、傳遞性 B反自反性、反對稱性 C反自反性、反對稱性、傳遞性 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

8、的函數(shù)的是（ ）。AR=<1,a>,<2,a>,<3,a>BR=<1,a>,<2,a>,<2,b>,<3,a>CR=<1,a>,<2,b>DR=<2,a>,<2,b>24、設(shè)R為實(shí)數(shù)集，映射f：R®R，f(x)= -x2+2x-1，則f是（ ）。A單射而非滿射 B滿射而非單射C雙射 D既不是單射，也不是滿射25、設(shè)A=F，1，1，3，1，2，3則A上包含關(guān)系“Í”的哈斯圖為（ ）。 AB CD26、N是自然數(shù)集合，定義f：N®N，f

9、(x) = x mod 3（即x除以3的余數(shù)），則 f 是（ ）。A滿射不是單射B單射不是滿射C雙射D不是單射也不是滿射27、設(shè)S=Æ,1,1,2，則有（ ）ÍS。A1,2 B1,2 C1 D2 28、集合A=x | x=2nnÎN 對（ ）運(yùn)算封閉。A加法B減法C乘法D|xy|29、設(shè)*是集合A上的二元運(yùn)算，稱Z是A上關(guān)于運(yùn)算*的零元，若（ ）。A"x ÎA，有x*Z=Z*x=ZBZ ÎA，且"x ÎA有x*Z=Z*x=ZCZ ÎA，且"x ÎA有x*Z=Z*x=xDZ Î

10、A，且$x ÎA有x*Z=Z*x=Z30、下面偏序集（ ）能構(gòu)成格。31、在（ ）中，補(bǔ)元是唯一的。A有界格B有補(bǔ)格 C分配格D有補(bǔ)分配格。32、下面四組數(shù)能構(gòu)成無向簡單圖的度數(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é)點(diǎn)之間的連通性，是結(jié)點(diǎn)集之間的一個（ ）。A 連通關(guān)系B 偏序關(guān)系C 等價關(guān)系D 函數(shù)關(guān)系34、已知圖G的相鄰矩陣為：則G有（ ）。A5點(diǎn)，8邊B6點(diǎn)，7邊C5點(diǎn)，7邊D6點(diǎn)，8邊35、下列四組數(shù)為結(jié)點(diǎn)度序列，能構(gòu)成無向圖的是（ ）。A2, 3, 4,

11、 5, 6, 7B1, 2, 2, 3, 4C2, 1, 1, 1, 2 D3, 3, 5, 6, 036、下列幾個圖是簡單圖的有（ ）。AG1=(V1,E1)，其中 V1=a, b, c, d, e，E1=(a,b), (b,e), (e,b), (a,e), (d,e)BG2=(V2,E2)，其中V2=V1，E2=<a,b>, <b,c>, <c,a>, <a,d>, <d,a>, <d,e>CG3=(V3,E3)，其中V3=V1，E3=(a,b), (b,e), (e,d), (c,c)DG4=(V4,E4)，其中V

12、4=V1，E4=<a,a>, <a,b>, <b,c>, <e,c>, <e,d>37、在一棵樹中有7片樹葉，3個3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)則該樹有（ ）個4度結(jié)點(diǎn)。A1B2C3D4 38、一棵樹有2個4度結(jié)點(diǎn)，3個3數(shù)度結(jié)點(diǎn)，其余是樹葉，則該樹中樹葉的個數(shù)是（ ）。A8B9C10D1139、設(shè)圖G是有6個頂點(diǎn)的連通圖，總度數(shù)為20，則從G中刪去（ ）邊后使之變成樹。A10B 5C 3D 240、下面那一個圖可一筆畫出（ ）。41、在如下各圖中（ ）歐拉圖。42、下圖中既不是歐拉圖，也不是哈密爾頓圖的是（ ）。43、在如下的有向圖中，

13、從V1到V4長度為3 的道路有（ ）條。A1B2C3D4 44、圖 中 從v1到v3長度為3 的通路有（ ）條。A0B1C2D3二、判斷題（每題 1分）1。 （ Y ）2設(shè)A，B， C是任意三個集合。（1）若AÎB且BÍC，則AÎC。 （ Y ） （2）若AÍB且BÎC，則AÎC。（ N ）（3）若AÎB且BËC，則AÏC。 （ N ） （4）(AÅB)C=(A×C) Å (B×C)。（ Y ）（5）AÅ(BÅC)= (AB)Å(AC)

14、。 （ N ）3A，B，C為任意集合，若AB=AC，則B = C 。（ N ）4可能有某種關(guān)系，既不是自反的，也不是反自反的。（ Y ）5可能有某種關(guān)系，既是對稱的，又是反對稱的。（ Y ）6設(shè)R是實(shí)數(shù)集，R上的關(guān)系S=<x, y>|x-y|2x,yÎR，S是相容關(guān)系。（ Y ）7若集合A上的關(guān)系R是對稱的，則Rc也是對稱的。（ Y ）8數(shù)集合上的不等關(guān)系（）可確定A的一個劃分（ N ）9設(shè)集合A、B、C為任意集合，若A×B = A×C，則B = C。（ N ）10函數(shù)的復(fù)合運(yùn)算“ ° ”滿足結(jié)合律。（ Y ）11集合A上的恒等關(guān)系是一個雙射

15、函數(shù)。（ Y ）12任何一個循環(huán)群必定是阿貝爾群。（ Y ）13任何循環(huán)群必定是阿貝爾群，反之亦真。（ N ）14設(shè)< A， >是偏序集，BÍA，則B的極大元bÎB且唯一。（ N ）15群是每個元素都有逆元的半群。（ N ）16在代數(shù)系統(tǒng)< S , *> 中，若一個元素的逆元是唯一的，其運(yùn)算*必是可結(jié)合的。（ N ）17每一個有限整環(huán)一定是域，反之也對。（ N ）18設(shè)<A,>是布爾代數(shù)，則<A,>一定為有補(bǔ)分配格。（ Y ）19若平面圖共有v個結(jié)點(diǎn)，e條邊和r個面，則v e + r = 2。（ N ）20任何有向圖中各結(jié)點(diǎn)入

16、度之和等于邊數(shù)。（ Y ）21若兩圖結(jié)點(diǎn)數(shù)相同，邊數(shù)相等，度數(shù)相同的結(jié)點(diǎn)數(shù)目相等，則兩圖是同構(gòu)的。（ N ）22一個圖是平面圖，當(dāng)且僅當(dāng)它包含與3,3或5在度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。（ N ）23有割點(diǎn)的連通圖可能是哈密爾頓圖。（ N ）24無多重邊的圖是簡單圖。（ N ）25根樹中最長路徑的端點(diǎn)都是葉子。（ N ）26在完全二叉樹中，若有片葉子，則邊的總數(shù) e =2 t1 。（ N ）27群中可以有零元（對階數(shù)大于1的群）。 （ N ）28任何循環(huán)群必定是阿貝爾群，反之亦真。 （ N ）29每一個鏈都是分配格。 （ Y ）30不可能有偶數(shù)個結(jié)點(diǎn)，奇數(shù)條邊的歐拉圖。 （ N ）31集合A上的恒等關(guān)系

17、是一個雙射函數(shù)。 （ Y ）32設(shè)Q為有理數(shù)集，Q上運(yùn)算 * 定義為，則是半群。（ Y ）33在完全二元樹中，若有片葉子，則邊的總數(shù) 。 （ N ）34能一筆畫出的圖不一定是歐拉圖。 （ Y ）35根樹中最長路徑的端點(diǎn)都是葉子。 （ N ）36命題公式(A(A®B)®B是一個矛盾式。 （ N ）37設(shè)R是實(shí)數(shù)集，R上的關(guān)系F=<x,y>| |x-y|<2x,yÎR ，則F是相容關(guān)系。（ Y ）38設(shè)< A，>是偏序集，BÍA，則B的極大元bÎB且唯一。 （ N ）39無多重邊的圖是簡單圖。 （ N ）40謂詞公式$

18、xP(x) ®"xQ(x)$yR(y)的前束范式是"x"z$y(P(x)®Q(z)R(y)。（ Y ）三、解答題（本題分4小題，共計35分）1、試求的主析取范式。2、用真值表判斷下列公式是永真式？永假式？可滿足式？（1）(PØP)«Q（2）Ø(P®Q) Q（3）(P®Q)(Q®R)®(P®R)解：（1）真值表：P QØP PØP (PØP)«Q0 01 0 10 11 0 01 00 0 11 10 0 0 因此公式（1）為可

19、滿足。 （2）真值表P QP®Q Ø（P®Q） Ø(P®Q)Q0 01 0 00 11 0 01 00 1 01 11 0 0 因此公式（2）為永假式。 （3）真值表P Q RP®Q Q®R P®R （P®Q）（Q®R）®（P®R）0 0 01 1 1 10 0 11 1 1 10 1 01 0 1 10 1 11 1 1 11 0 00 1 0 11 0 10 1 1 11 1 01 0 0 11 1 11 1 1 1 因此公式（3）為永真式。3、設(shè)個體域是D=2，3，6，

20、F(x):x3，G(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)Û FT ÛF4、求下列公式的前束范式： (1) "xF(x)$xG(x) (2) ("xF(x,y)$yG(y)"xH(x,y)5、通過求主析取范式判斷下列命題公式是否等值：(PQ)(ØPQR) 與(P(QR)(Q(ØPR)。解：(PQ)(ØPQR)&#

21、219; (PQ(ØRR)(ØPQR)Û (PQØR)(PQR)(ØPQR)Û M1M0M4Û M0M1M4 Û(0,1,4)Û (2,3,5,6,7) (P(QR)(Q(ØPR)Û (PQ)(PR)(ØPQ)(QR)Û (PQR)(PQØR)(PQR)(PØQR)(ØPQR)(ØPQØR)(PQR) (ØPQR)Û (PQR)(PQØR)(PØQR)(ØPQR)(&

22、#216;PQØR)Û m7m6m5m3m2Û (2,3,5,6,7) 由此可見 (PQ)(ØPQR) Û (P(QR)(Q(ØPR)6、設(shè)個體域?yàn)镈=-2,3,6，謂詞，求謂詞公式的真值： 7、若集合A=a,b,c的冪集為r(A)，集合B=Æ,Æ的冪集為r(B)，求：r(A) År(B)。解：r(A)= Æ,a,b,c,a,b,c r(B)=Æ,Æ,Æ, Æ,Æ r(A) År(B)= a,b,c,a,b,c,Æ,Æ

23、;, Æ,Æ 8、設(shè)集合A=2, 3, 4, 6, 8, 12, 24，R為A上的整除關(guān)系， (1) 畫出偏序集<A, R>的哈斯圖；(2) 寫出集合A中的最大元、最小元、極大元、極小元；(3) 寫出A的子集B=2, 3, 6, 12的上界、下界、最小上界、最大下界。9、集合S=1，2，3，4，5，找出S上的等價關(guān)系，此關(guān)系能產(chǎn)生劃分1，2，3，4，5，并畫出關(guān)系圖。 10、已知Aa，b，c，d ，A上的關(guān)系R定義為：R<a, b>，<b, a>，<a, c>，<b, d>，<d, a>，求：r(R)，

24、s(R)，t(R)。11、已知A1，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、集合上的關(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,

25、 4, 6, 8, 12, 24，R為A上的整除關(guān)系，畫出偏序集<A, R>的哈斯圖。14、已知G=1,2,3,4,5,6，×7為模7乘法。試說明<G, ×7>是否構(gòu)成群？是否為循環(huán)群？若是，生成元是什么？15、一棵樹T中，有3個2度結(jié)點(diǎn)，一個3度結(jié)點(diǎn)，其余結(jié)點(diǎn)都是樹葉。（1）T中有幾個結(jié)點(diǎn)；（2）畫出具有上述度數(shù)的所有非同構(gòu)的無向圖。16、設(shè)A=1，2，3，4，5，A上的偏序關(guān)系如右圖所示，求：A的子集3，4，5和1，2，3的上界，下界，上確界和下確界。17、求圖中A到其余各頂點(diǎn)的最短路徑，并寫出它們的權(quán)。18、設(shè)帶權(quán)無向圖如下，求其最小生成樹T及

26、該樹的總權(quán)值。19、權(quán)數(shù)1，4，9，16，25，36，49，64，81，100構(gòu)造一棵最優(yōu)二叉樹。20、如下圖所示的賦權(quán)圖表示某七個城市v1, v2, , v7及預(yù)先算出它們之間的一些直接通信線路造價，試給出一個設(shè)計方案，使得各城市之間能夠通信而且總造價最小。四、寫出對應(yīng)下面推理的證明：（本題10分，1*10=10）1、(A®B)(C®D)，B®E，D®F，(EF)，A®CÞA2、PW®R，R®ST，S®T，TQÞW3、如果小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王

27、去看電影。所以，當(dāng)小趙去看電影時，小李也去看電影。 4、如果小張去看電影，則當(dāng)小王去看電影時，小李也去。小趙不去看電影或小張去看電影。小王去看電影。所以當(dāng)小趙去看電影時，小李也去。5、如果我學(xué)習(xí)（P），那么我數(shù)學(xué)不會不及格。如果我不熱衷于玩撲克（R），那么我將學(xué)習(xí)。但我數(shù)學(xué)不及格（Q）。因此我熱衷于玩撲克。（注：請按括號中提示的字母翻譯并進(jìn)行論證。）6、或者是天晴，或者是下雨。如果是天晴，我去看電影。如果我去看電影，我就不看書。所以，如果我在看書，則天在下雨。7、所有牛都有角，有些動物是牛；所以，有些動物有角。（P(x)：x是牛；Q(x)：x有角；R(x)：x是動物）8、每個喜歡步行的人都不喜

28、歡坐汽車；每個人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行車。因而有的人不喜歡步行。（先將推理在一階邏輯中符號化，隨后驗(yàn)證其正確性）五、解答題（本題10分，1*10=10）1、某班有25個學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另外一種球（指籃球或排球），求不會打這三種球的人數(shù)。2、120名學(xué)生參加考試，這次考試有A、B和C共3道題，考試結(jié)果如下：12名學(xué)生3道題都做對了；20名學(xué)生做對A和B；16名學(xué)生做對A和C；28名學(xué)生做對B和C；做對A題的有48名學(xué)生；做對B題的有56名學(xué)生；還有16名學(xué)生

29、一道題也沒做對。試求做對了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；構(gòu)造一棵最優(yōu)二叉樹。6、畫出哈斯圖：設(shè)Ba,b,c，R=<s1,s2>|s1Ís2Ùs1,s2ÎP(B)7、偏序集的關(guān)系圖如下圖所示，(1) 畫出的哈斯圖；(2) 設(shè)B=b,c，求B的所有上界、上確界，下界和下確界。8、給