《離散數(shù)學(xué)》復(fù)習(xí)題

1、離散數(shù)學(xué)復(fù)習(xí)題一、填空題(每小題1分，共10分)1、P：你努力，Q：你失敗?！俺悄闩Γ駝t你將失敗”的翻譯為;2、一階邏輯公式Vx(F(x)tG(x)人Vy(F(y)tG(y)的類型是TOC o 1-5 h z3、設(shè)個(gè)體域?yàn)檎麛?shù)集合，命題Vx3y(x+y=0)的真值為。4、對(duì)于任意兩個(gè)集合A,B,它們有共同的子集。5、如果關(guān)系R是傳遞的，則RR匸。6、集合S=a,0，Y上的二元運(yùn)算*為*a0Y6a6a0Y0a0Y6Y0YYY6a6Y6TOC o 1-5 h z那么，代數(shù)系統(tǒng)vS,*中的幺元是0,a的逆元是。7、一個(gè)無向圖G=(V,E是二部圖，當(dāng)且僅當(dāng)G中無的回路。8、無向圖G有12條邊，6

2、個(gè)的3度節(jié)點(diǎn)和2個(gè)4度節(jié)點(diǎn)。此命題的真值為。9、當(dāng)n3并且n為奇數(shù)時(shí)，無向完全圖k是歐拉圖。此命題的真值為。n10、設(shè)代數(shù)系統(tǒng)V=*，其中Q是有理數(shù)集合，*表示對(duì)Vx,ygQ有x*y二x+y-xy,則Q上關(guān)于*的幺員(或稱單位元)是。二、選擇題(每小題1分，共10分)1設(shè)A=0,B=p(p(A),以下不正確的式子是()A0,0gBB0gBC.0匸BD0,0匸B2.設(shè)E(x)：“X是偶數(shù)”;D(x,y)：“x除盡y”,P(x):“x是質(zhì)數(shù)”,則公式Vx(P(x)4y(E(y)人D(x,y)正確的翻譯是：()A、所有質(zhì)數(shù)都能除盡偶數(shù)；B、所有不能除盡偶數(shù)的數(shù)是質(zhì)數(shù)；C、對(duì)任一質(zhì)數(shù)，都有被它除盡的偶

3、數(shù)；D、對(duì)任一偶數(shù)，都有被它除盡的質(zhì)數(shù)。99下列既是歐拉圖又是哈密爾頓圖的是（）99下列既是歐拉圖又是哈密爾頓圖的是（）3下列論述哪個(gè)是錯(cuò)誤的？（）A、任何一個(gè)群，均無零元；B、任何一個(gè)群，其中至少有兩個(gè)元素是等冪元；C、任何一個(gè)群，其中的二元運(yùn)算滿足消去律；D、群中每個(gè)元素的逆元是唯一的。4設(shè)集合A=123,4,下列關(guān)系R中是等價(jià)關(guān)系的是()R=,2,2,3,3,1,4,4,1R=,2,3R=,4,3R=,1,45設(shè)A=123,B=1,2,則下列命題不正確的是()B、AB=1,2,3C、C、A-B=3D、Ap|BH06下面哪個(gè)序集是格？其中丨是整除關(guān)系。（）A、(A、(2,3,4,6,8,1

4、2,|)；B、(2,3,4,6,8,12,24,|)；D、(1,2,3,4,6,8,12,|)。)D、(1,2,3,4,6,8,12,|)。)7在下列代數(shù)系統(tǒng)中，不是群的只有（A.,其中Q是有理數(shù)，X是通常的乘法運(yùn)算;B.Q,+,其中Q是有理數(shù)，+是通常的加法運(yùn)算；C全體n階實(shí)對(duì)稱矩陣集合，對(duì)矩陣的加法運(yùn)算；D.，其中R為實(shí)數(shù)集，X是通常的乘法運(yùn)算。8設(shè)無向圖G中有10條邊，已知G中3度結(jié)點(diǎn)有4個(gè)，其余結(jié)點(diǎn)的度均小于3,則G中的結(jié)點(diǎn)數(shù)至少是（）A.6B.9C.8D.710一棵樹有1個(gè)4度結(jié)點(diǎn)，4個(gè)3度結(jié)點(diǎn)，其余的結(jié)點(diǎn)是樹葉，則該樹中結(jié)點(diǎn)的個(gè)數(shù)是（）A.8；B.15；C.7；D.13三、名詞解釋

5、（每題4分，共20分）1、等價(jià)關(guān)系2、命題公式3、強(qiáng)連通圖4、半群5、格四、簡(jiǎn)答題（每題5分，共30分）1、設(shè)S=1,2,3,4,6,8,12,24,“”為S上整除關(guān)系，問：偏序集S,的Hass圖如何？偏序集S,的極小元、最小元、極大元、最大元是什么？2、設(shè)解釋R如下：Dr是實(shí)數(shù)集，Dr中特定元素a=0，DR中特定函數(shù)f（x,y）二x-y，特定謂詞F（x,y）:xy，問公式A=VxVyVz（F（x,y）TF（f（x,z）,f（y,z）的涵義如何？真值如何？3、什么是有向圖的歐拉路？指出判斷一個(gè)圖中有歐拉路的充分必要條件。4、設(shè)S=2n|neN，加法是S上的二元代數(shù)運(yùn)算么？乘法呢？5、判定下列各

6、題的正確與錯(cuò)誤：（1）aea；（2）aca，b，c；（3）0ea，b，c；（4）0ca，b，c；（5）a，bca，b，c，a，b，c；（6）a，1，3，4ua,3，4，1；（7）a，bca，b，a，b；(8)如果AcB=B，貝VA=E。6、將下列三個(gè)命題符號(hào)化：（1）每一個(gè)有理數(shù)都是實(shí)數(shù)。（2）某些實(shí)數(shù)是有理數(shù)。五、證明題（30分）1、命題演繹證明：AvBTCaD,DvETFnATF2、證明：在6個(gè)結(jié)點(diǎn)12條邊的連通平面簡(jiǎn)單圖中，每個(gè)面的面度數(shù)都是3。一、填空題(每空2分，共30分)設(shè)A為任意的公式，B為重言式，則A人B的類型為.無向圖G是歐拉圖的充分必要條件是.(iAiB)aiA假言推理定律

7、.在一階邏輯中將命題符號(hào)化時(shí)，若沒指明個(gè)體域，則使用個(gè)體域.若R既是、則稱R是整環(huán)；設(shè)0,1和(0,1)分別表示實(shí)數(shù)集上的閉區(qū)間和開區(qū)間，則下列命題中為真的是A.0,1匸(0,1)B.0,1匸0,1C.(0,1)匸0,1D.0,1uQE.0,1cZ已知RcAxA且A=a,b,c,R的關(guān)系矩陣100TOC o 1-5 h zM(R)=011011則傳遞閉包t(R)的關(guān)系矩陣M(t(R)=.;設(shè)R為實(shí)數(shù)集合，f：RtR,f(x)=x2x+2,g：RtR,g(x)=x3,則fbg(x)=；設(shè)Z為整數(shù)集，Va,be乙ab=a+b-1,VaeZ,a的逆元a-1=；設(shè)G=是24階循環(huán)群，則G的生成元為；設(shè)

8、L為鉆石格，則L有個(gè)2元子格；n階k-正則圖G的邊數(shù)m=；在完全圖K2k(k2)上至少加條邊，才能使所得圖為歐拉圖；6階無向連通圖至多有棵不同構(gòu)的生成樹；(15)在環(huán)中計(jì)算(a+b)3二；二、在自然推理系統(tǒng)P中，用直接證明法構(gòu)造下面推理的證明(10分)前提：(paq),qfr,r結(jié)論：p三、證明題(每題10分共30分)設(shè)E=1,2,.,12,A=1,3,5,7,9,11,B=2,3,5,7,11,C=2,3,6,12,D=2,4,8，計(jì)算：AuB,AcC,C-(AuB),A-B,C-D,BD.設(shè)Z為模18整數(shù)加群，求所有元素的階.183求帶權(quán)為5,5,6,7,10,15,20,30的最優(yōu)樹T并

9、求W(T).四、應(yīng)用題(每題10分共20分)判斷正整數(shù)集合Z+和下面的每個(gè)二元運(yùn)算是否構(gòu)成代數(shù)系統(tǒng).如果是，則說明這個(gè)運(yùn)算是否適合交換律、結(jié)合律和冪等律，并求出單位元和零元.aob=max(a,b),a*b=min(a,b),ab=ab,aOb=(a/b)+(b/a)計(jì)算機(jī)系張、王、李、趙4位教授下學(xué)期要承擔(dān)他們都熟悉的4門課程：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、C語言和JAVA試討論學(xué)院安排他們授課的方案數(shù)；在上述各方案中，有多少種是完全不同的方案(即，每位教授所授課程都不相同的方案數(shù))?五、判斷解答(10分)判斷正整數(shù)集合Z+和下面的每個(gè)二元運(yùn)算是否構(gòu)成代數(shù)系統(tǒng).如果是，則說明這個(gè)運(yùn)算是否適合交換律、結(jié)

10、合律和冪等律，并求出單位元和零元.ab=max(a,b),a*b=min(a,b),ab=ab,aOb=(a/b)+(b/a)答案一、填空矛盾式G連通且無奇度頂點(diǎn).血全總交換環(huán)、含幺環(huán)、無零因子環(huán)BCEM(R)x2-x-19.2=a10.a,a5,a7,aii,ai3,ai7,ai9,a23_11.712.kn12.kn13.k14.615.略二略計(jì)算(每題9分共27分)設(shè)E=1,2,.,12,A=1,3,5,7,9,11,B=2,3,5,7,11,C=2,3,6,12,D=2,4,8，計(jì)算：AuB,AcC,C-(AuB),A-B,CD,BD.OOOOAuB=1,2,3,5,7,9,11AcB

11、=3C-(AuB)=6,12A-B=1,9C-D=3,6,12BD=3,4,5,7,8,11|0|=1,|9|=2，|6|=|12|=3,|3|=|15|=6,|2|=|4|=|8|=|10|=|14|=|16|=9,|1|=|5|=|7|=|11|=|13|=|17|=183求帶權(quán)為5,5,6,7,10,15,20,30的最優(yōu)樹T并求W(T).答案W(T)=267判斷解答(每題9分共18分)1.判斷正整數(shù)集合Z+和下面的每個(gè)二元運(yùn)算是否構(gòu)成代數(shù)系統(tǒng).如果是，則說明這個(gè)運(yùn)算是否適合交換律、結(jié)合律和冪等律，并求出單位元和零元.aob=max(a,b),a*b=min(a,b),ab=ab,ab=

12、(a/b)+(b/a)o,運(yùn)算構(gòu)成代數(shù)系統(tǒng)；和*運(yùn)算滿足交換律、結(jié)合律與幕等律.*運(yùn)算零兀是1,運(yùn)算單位兀是1.2.4!4種完全不同的方案。五、判斷解答判斷正整數(shù)集合Z+和下面的每個(gè)二元運(yùn)算是否構(gòu)成代數(shù)系統(tǒng).如果是，則說明這個(gè)運(yùn)算是否適合交換律、結(jié)合律和幕等律,并求出單位兀和零兀.aob=max(a,b),a*b=min(a,b),ab=ab,ab=(a/b)+(b/a)o,運(yùn)算構(gòu)成代數(shù)系統(tǒng)；和*運(yùn)算滿足交換律、結(jié)合律與幕等律.*運(yùn)算零兀是1,運(yùn)算單位兀是1.AA、Vx(M(x)aP(x)；B、(3x(M(x)TP(x)；一、填空題(每小題1分，共10分)1、設(shè)P(x):x是偶數(shù);R(x,y)

13、:x+y是偶數(shù)，變量x,y代表整數(shù)，則VxByR(x,y),表示的語義是TOC o 1-5 h z2、設(shè)A,B為非空集合，A|=m,|B=n，那么從A到B的不同函數(shù)有個(gè)。3、設(shè)集合A=0,a,貝Up(A)x0=。4、對(duì)任何一個(gè)圖G,九(G),k(G)和6(G)分別是它的邊連通度、點(diǎn)連通度和最小度，則它們之間的關(guān)系是。5、如圖所示是偏序關(guān)系R的哈斯圖,則集合c,d,f的最小上界是6、設(shè)VH,*6、設(shè)VH,*是有限群VG,aH和Hb分別是左右陪TOC o 1-5 h z集,則它們所含元素個(gè)數(shù)是個(gè)。7、無向圖G為歐拉圖,當(dāng)且僅當(dāng)G是連通的,且G中無結(jié)點(diǎn)8、設(shè)謂詞A(x)的論域是a,a,a，則A(a)

14、aA(a)aaA(a)o。12n12n9、如果把可達(dá)性看成是有向圖結(jié)點(diǎn)集一個(gè)二元關(guān)系，那么它具有和性質(zhì)。10、布爾代數(shù)0,1,v,a/上的布爾表達(dá)式E(x,x)=xax的合取范式是1212二、選擇題(每小題1分，共10分)1下面命題公式()不是重言式。A、Qf(PvQ);B、(PaQ)fP；C、C、一(PaiQ)a(iPvQ)；D、(PfQ)(PvQ)o)o2命題“沒有不犯錯(cuò)誤的人”符號(hào)化為()o設(shè)M(x)：x是人，P(x)：x犯錯(cuò)誤。C、(3x(M(x)aP(x)；D、(3x(M(x)aP(x)。TOC o 1-5 h z3.設(shè)A二,B=n(D(A),下列各式中哪個(gè)是錯(cuò)誤的()A、匸B；B、

15、匸B,C、gB；D、,匸口(A)。對(duì)自然數(shù)集合N,哪種運(yùn)算不是可結(jié)合的，運(yùn)算定義為任a,bgN()。A、a*b=min(a,b)；B、a*b=a+2b；C、a*b=a+b+3；D、a*b=a,b(mod3)。5設(shè)Z為整數(shù)集，下面哪個(gè)序偶不夠成偏序集()。A、Z,(：小于關(guān)系)；B、乙(:小于等于關(guān)系)；C、(=:等于關(guān)系)；D、(：整除關(guān)系)。6任意具有多個(gè)等冪元的半群，它()。A、不能構(gòu)成群；B、不一定能構(gòu)成群；C、不能構(gòu)成交換群；D、能構(gòu)成交換群。設(shè)A,是一個(gè)有界格，它也是有補(bǔ)格，只要滿足()。A、每個(gè)元素都有一個(gè)補(bǔ)元；B、每個(gè)元素都至少有一個(gè)補(bǔ)元；C、每個(gè)元素都無補(bǔ)元；D、每個(gè)元素都有多

16、個(gè)補(bǔ)元。設(shè)G=為無向圖，V=7,E=23，則G一定是()。A、完全圖；B、樹；C、簡(jiǎn)單圖；D、多重圖。給定無向圖G=，如下圖所示，下面哪個(gè)邊集不是其邊割集()。A、A、,；1434B、,；1546C、C、,；4748D、,。1223有n個(gè)結(jié)點(diǎn)（n3）,m條邊的連通簡(jiǎn)單圖是平面圖的必要條件（）。A、n3m6；B、n3n6；D、m3n6。三、名詞解釋（每題4分，共20分）1、擬序關(guān)系2、演繹3、Hamilton圖4、整除5、子群四、簡(jiǎn)答題（每題5分，共30分）1、舉例說明什么是環(huán)？2、用等值演算法求下面公式的主析取范式,并求其成真賦值。（PvQ）tR3、集合A二1,2,3,4上的關(guān)系R二,，寫出關(guān)系矩陣Mr，畫出關(guān)系圖并討論R的性質(zhì)。4、有n個(gè)藥箱，若每?jī)蓚€(gè)藥箱里有一種相同的藥，而每種藥恰好在兩個(gè)藥箱中，問共有多