離散數(shù)學(xué)B卷和答案

1、武漢理工大學(xué) 離散數(shù)學(xué)考試試題 (B卷) 站點(diǎn)： 姓名： 專業(yè)： 層次一、單項選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（）APQBPQCPQDPQ2下列命題公式為重言式的是（）AQ（PQ）BP（PQ）C（PQ）PD（PQ）Q3下列4個推理定律中，不正確的是（）AA（AB）B（AB）ABC（AB）ABD（AB）BA4謂詞公式x(P(x)yR(y)Q(x)中量詞的轄域是（）ABP（x）C(P(x)yR(y)DP

2、(x), Q(x)5設(shè)個體域A=a,b，公式xP(x)xS(x)在A中消去量詞后應(yīng)為（）AP(x)S(x)BP(a)P(b)(S(a)S(b)CP(a)S(b)DP(a)P(b)S(a)S(b)6下列選項中錯誤的是（）ABCD7設(shè)A=a,b,c,d，A上的等價關(guān)系R=, , , IA，則對應(yīng)于R的A的劃分是（）Aa,b, c,dBa, b,c, dCa,b,c,dDa, b, c,d8設(shè)R為實(shí)數(shù)集，函數(shù)f：RR，f(x)=2x，則f是（）A滿射函數(shù)B入射函數(shù)C雙射函數(shù)D非入射非滿射9設(shè)R為實(shí)數(shù)集，R+=x|xRx0，*是數(shù)的乘法運(yùn)算，是一個群，則下列集合關(guān)于數(shù)的乘法運(yùn)算構(gòu)成該群的子群的是（）A

3、R+中的有理數(shù)BR+中的無理數(shù)CR+中的自然數(shù)D1，2，310下列運(yùn)算中關(guān)于整數(shù)集不能構(gòu)成半群的是（）Aab=maxa, bBab=bCab=2abDab=|a-b|11設(shè)Z是整數(shù)集，+，分別是普通加法和乘法，則（Z，+，）是（）A域B整環(huán)和域C整環(huán)D含零因子環(huán)12設(shè)A=a, b, c，R是A上的二元關(guān)系，R=, , , ，那么R是（）A反自反的B反對稱的C可傳遞的D不可傳遞的13設(shè)D=為有向圖，V=a, b, c, d, e, f, E=, , , , 是（）A強(qiáng)連通圖B單向連通圖C弱連通圖D不連通圖14在有n個結(jié)點(diǎn)的連通圖中，其邊數(shù)（）A最多有n-1條B至少有n-1條C最多有n條D至少有n

4、條15連通圖G是一棵樹，當(dāng)且僅當(dāng)G中（）A有些邊不是割邊B每條邊都是割邊C無割邊集D每條邊都不是割邊二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。16任意兩個不同的小項的合取為_式，全體小項的析取式必為_式。17公式x(P(x)Q(x,y)zR(y, z)S(x)中的自由變元為_，約束變元為_。18設(shè)集合M=x|1x12,x被2整除，xZ,N=x|1x12,x被3整除，xZ，則 MN=_，MN=_。19設(shè)X=1，2，3，f：XX，g：XX，f=,g=,，則fg=_，gf=_。20設(shè)A=a,b,c，R是A上的二元關(guān)系，且給定R=,，則R的自

5、反閉包r(R)= _，對稱閉包s(R)= _。21設(shè)Q為有理數(shù)集，笛卡爾集S=QQ，*是S上的二元運(yùn)算，,S, *=, 則*運(yùn)算的幺元是_。S, 若a0，則的逆元是_。22設(shè)*是集合S上的二元運(yùn)算，若運(yùn)算*滿足_且存在_，則稱為獨(dú)異點(diǎn)。23令A(yù)=a, b, c，是循環(huán)群，a是單位元，則b2=_，c的階是_。24如下無向圖割點(diǎn)是_，割邊是_。25無向圖G具有生成樹，當(dāng)且僅當(dāng)_。G的所有生成樹中_的生成樹稱為最小生成樹。三、計算題（本大題共5小題，第26、27小題各5分，第28、29小題各6分，第30小題8分，共30分）26集合A=a, b, c, d, e上的二元關(guān)系R為R=, , , , ,

6、, , , , , , , , （1）寫出R的關(guān)系矩陣；（2）判斷R是不是偏序關(guān)系，為什么？27利用真值表判斷公式（PQ）（QR）（PR）是否為重言式。28給定圖G如下所示，（1）寫出G的可達(dá)矩陣；（2）G中長度為4的路有幾條？29求下列公式的主析取范式和主合取范式：（PQ）（QR）30設(shè)A為54的因子構(gòu)成的集合，RAA，x,yA, xRyx整除y。畫出偏序集的哈斯圖，并求A中的最大元，最小元，極大元，極小元。五、證明題（本大題共3小題，第31、32小題各6分，第33小題8分，共20分）31設(shè)R是A上的一個自反關(guān)系，證明：R是一個等價關(guān)系，當(dāng)且僅當(dāng)若R，R，則R。32設(shè)是一個群，xG，定義：ab=a*x*b，a,bG。證明：也是一個群。33設(shè)圖G是具有6個結(jié)點(diǎn)，12條邊的無向簡單圖，證明圖G是漢密爾頓圖。五、應(yīng)用題（本大題共2小題，第34小題8分，第35小題7分，共15分）34構(gòu)造下面推理的證明。 如果今天是星期六，我們就要到頤和園或圓明園去玩。如果頤和園游人太多，我們就不去頤和園玩。今天是星期六，頤和園游人太多，所以我們?nèi)A明園玩。35n個城市用k條公路的網(wǎng)絡(luò)連結(jié)。一條公路定義為兩個城市間的一條