20062010自學(xué)考試離散數(shù)學(xué)試題匯編

1、全國(guó)2006年4月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1下列命題公式為重言式的是（ ）Ap (pq)B(pp)qCqqDpq2下列語(yǔ)句中不是命題的只有（ ）C飛碟來(lái)自地球外的星球。D凡石頭都可練成金。3設(shè)p：我很累，q：我去學(xué)習(xí)，命題：“除非我很累，否則我就去學(xué)習(xí)”的符號(hào)化正確的是ApqBpqCpqDpq4下列等價(jià)式正確的是（ ）AABCAD5在公式中變?cè)獃是（ ）A自由變?cè)狟約束變?cè)狢既是自由變?cè)?，又是約束變?cè)狣既不是自

2、由變?cè)?，又不是約束變?cè)?設(shè)A=1，2，3，A上二元關(guān)系S=<1，1>，<1，2>，<3，2>，<3，3>，則S是（ ）A自反關(guān)系B反自反關(guān)系C對(duì)稱關(guān)系D傳遞關(guān)系7設(shè)集合X為人的全體，在X上定義關(guān)系R、S為R=<a，b|a，bXa是b的父親，S=<a，b>|a，bXa是b的母親，那么關(guān)系<a，b>|a，bx a是b的祖母的表達(dá)式為（ ）ARSBR-1SCSRDRS-18設(shè)A是正整數(shù)集，R=(x，y)|x，yAx+3y=12，則R (2，3，4，6×2，3，4，6)=（ ）AO/B<3，3>C<

3、;3，3>，<6，2>D<3，3>，<6，2>，<9，1>9下列式子不正確的是（ ）A(A-B)-C=(A-C)-BB(A-B)-C=A-(BC)C(A-B)-C=(A-C)-(B-C)DA-(BC)=(A-B) C10下列命題正確的是（ ）Al，21，2，l，2，3，1B1，21，l，2，l，2，3，2C1，21，2，1，2D1，21，2，2，l，2，311在下列代數(shù)系統(tǒng)中，不是環(huán)的只有（ ）A<Z，+，*)，其中Z為整數(shù)集，+，*分別為整數(shù)加法和乘法。B(Q，+，*)，其中Q為有理數(shù)集，+，*分別為有理數(shù)加法和乘法。C<R，

4、+，*>，其中R為實(shí)數(shù)集，+為實(shí)數(shù)加法，a*b=a+2b。D<Mn (R)，+，*>，其中Mn(R)為實(shí)數(shù)集n×n階矩陣結(jié)合，+，*是矩陣加法和乘法。12下列整數(shù)集對(duì)于整除關(guān)系都構(gòu)成偏序集，而能構(gòu)成格的是（ ）Al，2，3，4，5B1，2，3，6，12C2，3，7Dl，2，3，713結(jié)點(diǎn)數(shù)為奇數(shù)且所有結(jié)點(diǎn)的度數(shù)也為奇數(shù)的連通圖必定是（ ）A歐拉圖B漢密爾頓圖C非平面圖D不存在的14無(wú)向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通的且（ ）AG中各頂點(diǎn)的度數(shù)均相等BG中各頂點(diǎn)的度數(shù)之和為偶數(shù)CG中各頂點(diǎn)的度數(shù)均為偶數(shù)DG中各頂點(diǎn)的度數(shù)均為奇數(shù)15平面圖(如下)的三個(gè)面的次數(shù)分別是（）

5、A11，3，4B11，3，5C12，3，6D10，4，3二、填空題（本大題共10小題，每小題2分，共20分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16求一個(gè)公式的主析取或主合取范式的方法，有_法和_法。17給定謂詞合式公式A，其中一部分公式形式為()B(x)或(x)B(x)，則量詞，后面所跟的x稱為_，而稱B為相應(yīng)量詞的_。18設(shè)X，U，V，Y都是實(shí)數(shù)集，f1：XU，且fl(x)ex； f2：UV，且f2(u)u (1+u)；f3：VY，且f3(v)=cosv。那么f3f2f1的定義域是_，而復(fù)合函數(shù)(f3f2f1)(x)= _。19集合X=a，b，c，d上二元關(guān)系R=<a，

6、b>，<a，c>，<a，d>，<b，c>，<b，d>， <e，d>，則R的自反閉包r(R)= _，對(duì)稱閉包s(R)= _。20已知G=<l，-1，i，-i，·>(其中i=，是數(shù)的乘法)是群，則-l的階是_；i的階是_。21對(duì)代數(shù)系統(tǒng)<S，*>，其中*是S上的二元運(yùn)算，若a，bS，且對(duì)任意的xS，都有a*x=x*a=x，b*x=x*b=b，則稱a為運(yùn)算“*”的_，稱b為運(yùn)算“*”的_。22設(shè)<S，*>是群，則<S，*>滿足結(jié)合律和_；若S>l，S中不可能有_。23寫出

7、如右有向圖的一條初級(jí)回路：_，其長(zhǎng)度是_。24一個(gè)_且_的無(wú)向圖稱為樹。25在簡(jiǎn)單無(wú)向圖G=<V，E>中，如果V中的每個(gè)結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接，則該圖稱為_，如果V有n個(gè)結(jié)點(diǎn)，那么它還是_度正則圖。三、計(jì)算題(本大題共5小題，第26、27題各5分，第28、29題各6分，第30題8分，共30分)26若集合A=a，b，c的冪集為P(A)，集合B=O/，O/ 的冪集為P(B)，求P(A)P(B)。27構(gòu)造命題公式(p (q r)p的真值表。28求圖G<V，E>的可達(dá)矩陣，其中Vv1,v2,v3,v4E(v1,v2), (v2,v3), (v2,v4), (v3,v2),

8、(v3,v4), (v3,v1), (v4,v1)29求下列公式的主析取范式和主合取范式：（PQ）（PR）30設(shè)A2，3，4，6，8，12，24，R為A上整除關(guān)系，試畫<A，R>的哈斯圖，并求A中的最大元，最小元，極大元，極小元。四、證明題（本大題共3小題，第31、32小題各6分，第33題8分，共20分）31設(shè)M是偶數(shù)集，和·是數(shù)的加、乘運(yùn)算，證明<M，·>是一個(gè)環(huán)。32設(shè)R是集合X上的二元關(guān)系，證明R是X上傳遞關(guān)系當(dāng)且僅當(dāng)RRR。33設(shè)G是簡(jiǎn)單平面圖，G有n個(gè)頂點(diǎn)m條邊，且m<30，證明G中存在一項(xiàng)點(diǎn)v，d（v）4。五、應(yīng)用題（本大題共2小題

9、，第34題6分，第35題9分，共15分）34判斷下面推理是否正確，并證明你的結(jié)論。如果小王今天家里有事，則他不會(huì)來(lái)開會(huì)。如果小張今天看到小王，則小王今天來(lái)開會(huì)了。小張今天看到小王。所以小王今天家里沒事。35有6個(gè)村莊Vi，i=l，2，6欲修建道路使村村可通?，F(xiàn)已有修建方案如下帶權(quán)無(wú)向圖所示，其中邊表示道路，邊上的數(shù)字表示修建該道路所需費(fèi)用，問應(yīng)選擇修建哪些道路可使得任二個(gè)村莊之間是可通的且總的修建費(fèi)用最低?要求寫出求解過程，畫出符合要求的最低費(fèi)用的道路網(wǎng)絡(luò)圖并計(jì)算其費(fèi)用。2006年7月全國(guó)自考離散數(shù)學(xué)試題試卷真題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小

10、題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1下列語(yǔ)句中不是命題的只有（）A雞毛也能飛上天？B或重于泰山，或輕于鴻毛。C不經(jīng)一事，不長(zhǎng)一智。D牙好，胃口就好。2從真值角度看，命題公式的全部類型是（）A永真式B永假式C永真式，永假式D永真式，永假式，可滿足式3設(shè)M（x）：x是人；F（x）：x要吃飯。用謂詞公式表達(dá)下述命題：所有的人都要吃飯，其中錯(cuò)誤的表達(dá)式是（）ABCD4下列公式是前束范式的是（）ABCD5設(shè)論域?yàn)檎麛?shù)集，下列真值為真的公式是（）A BCD6下列是謂詞演算中的合式公式的是（）ABCD（ ）（）ABCD（）8下列式子正確的是（

11、）A（AB）-C=A-（BC）BA（BC）=（AB）CC（AB）=（BA）D（AB）A9下列集合對(duì)所給的運(yùn)算是封閉的只有（）A非零整數(shù)集合Z*上的除法運(yùn)算B全體n×n實(shí)可逆矩陣集合Mn（R）上的矩陣加法和乘法運(yùn)算C全體n×n實(shí)矩陣集合Mn（R）上的矩陣加法和乘法運(yùn)算DA=1，2，10，x*y=LCM（x，y），即x，y最小公倍數(shù)10設(shè)<A，*>是環(huán)，則下列說法不正確的是（）A<A，>是交換群B<A， *>是半群C*對(duì)是可分配的D對(duì)*是可分配的11下列四個(gè)格，是分配格的是（）CD（）AB12下列各圖是無(wú)向完全圖的是（）13下列各有向圖是強(qiáng)連

12、通圖的是（）14設(shè)是具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，若在中存在一條漢密爾頓路，則中每一對(duì)結(jié)點(diǎn)的度數(shù)之和與n-1的關(guān)系為（）A大于B大于等于C等于D小于15設(shè)連通平面圖，共有n個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則歐拉證明成立的公式是（）Ae-n+r=2Bn+r-e=2Cn-r+e=2Dn-e-r=2二、填空題（本大題共10小題，每小題2分，共20分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16所謂_是指不能再分解的命題，而復(fù)合命題是由一些_經(jīng)過聯(lián)結(jié)詞復(fù)合而成的命題。17在命題演算中，兩個(gè)_的合取、析取、條件、雙條件均為_。18使公式成立的條件是_中不含y，_中不含x。19設(shè)A=1，2，3，4，R是A上

13、的二元關(guān)系，R=<x,y>|x/y是素?cái)?shù)，則domR=_;ranR=_。20設(shè)無(wú)向圖有n個(gè)結(jié)點(diǎn)m條邊，每個(gè)結(jié)點(diǎn)的度數(shù)為k或k+1，記Nk為度數(shù)等于k的結(jié)點(diǎn)數(shù)，則Nk=_。如果無(wú)向簡(jiǎn)單圖C的結(jié)點(diǎn)的度數(shù)均為相同的偶數(shù)，且m=7，則n=_。21設(shè)X=1，3，5，9，15，45，R是X上的整除關(guān)系，則R是X上的偏序，其最大元是_，極小元是_。22設(shè)<>是有界格，a,bL,若ab=0,則a=b=_；若ab=1,則a=b=_。23設(shè)e是群G上的幺元，若aG且a2=e,則a-1=_ ,a-2=_。24代數(shù)系統(tǒng)<A,。>，其中A為命題公式集合，。為析取運(yùn)算，則<A，。

14、>中零元素是_，幺元是_。25樹是不包含_的_圖。三、計(jì)算題（本大題共6小題，第26、27題各4分，第28、29題各5分，第30、31題各6分，共30分）26如果論域是集合a,b,c，試消去下面公式中的量詞：27求公式（的主析取范式。28設(shè)A=a,b,c,A上二元關(guān)系R=<a,a>,<a,c>,<b,a>,用關(guān)系矩陣法求最小的自然數(shù)m,n,m<n使Rm=Rn。29根據(jù)下列條件如果能畫則請(qǐng)畫出一個(gè)歐拉圖，如果不能畫則請(qǐng)說明理由。（1）偶數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊（2）奇數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊（3）偶數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊（4）奇數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊30下列各整數(shù)集合

15、對(duì)于整除關(guān)系“|”都構(gòu)成偏序集，判斷哪些偏序集能構(gòu)成格？并說明理由。1)L=1,2,3,4,52) L=1,2,3,6,123)L=1,2,3,4,6,9,12,18,364)L=1,2,22,23,2n31設(shè)A=2，3，5，12，19，等價(jià)關(guān)系R=<x,y>|x,(mod 3),寫出各元素的等價(jià)類，并求A/R。四、證明題（本大題共3小題，第32、33題各6分，第34題8分，共20分）32用等價(jià)變換法證明：是永真式。33若無(wú)向圖G是歐拉圖，G中是否存在割邊？為什么？34設(shè)A是一個(gè)集合，X=P（A），R是X上元素之間的包含關(guān)系，試證明<X,R>是偏序集。（注：P（A）為A

16、的冪集）五、應(yīng)用題（本大題共2小題，第35題6分，第36題9分，共15分）35設(shè)有n個(gè)村莊要修路，（1）若要使所有村莊之間都有通路，問需在兩村之間至少修幾條路？（2）若要使任意兩村莊之間有一條直接的路，則至少修幾個(gè)路？（3）若修一條連接所有村莊的環(huán)路，問有多少種修路方案？36設(shè)有推理：(a)沒有不守信用的人是可信賴的；(b)有些可以信賴的人是受過教育的人；(c)因此有些受過教育的人是守信用的。試構(gòu)造推理的證明，要求把推理的前提，結(jié)論符號(hào)化為謂詞形式，并寫出推理過程。（個(gè)體域：人的集合）提示：設(shè)F（x）表示x是守信用的人；G（x）表示x是可信賴的人；H（x）表示x是受過教育的人。全國(guó)2007年4

17、月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1下列命題公式中不是重言式的是（）Ap(qr)Bp(qp)Cp(pp)D(p(qr)(q(pr)2下列語(yǔ)句中為命題的是（）A這朵花是誰(shuí)的？B這朵花真美麗啊！C這朵花是你的嗎？D這朵花是他的。3設(shè)個(gè)體域是整數(shù)集，則下列命題的真值為真的是（）Ayx(x·y=1)Bxy (x·y0)Cxy (x·y=y2)Dyx(x·y=x2)4關(guān)于謂詞公式（x）(y

18、)(P(x,y)Q(y,z)(x)p(x,y),下面的描述中錯(cuò)誤的是（）A（x）的轄域是（y）（P（x,y）Q(y,z)）Bz是該謂詞公式的約束變?cè)狢（x）的轄域是P（x,y）Dx是該謂詞公式的約束變?cè)?設(shè)論域D=a,b，與公式xA（x）等價(jià)的命題公式是（）AA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a）6集合A=1，2，3上的下列關(guān)系矩陣中符合等價(jià)關(guān)系條件的是（）ABCD7設(shè)A=Ø，B=P（P（A），以下不正確的式子是（）AØ ，Ø ，Ø，Ø 包含于BBØ 包含于BCØ，Ø 包括于BD&#

19、216; ，Ø，Ø 包含于B8設(shè)Z是整數(shù)集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，則f（）A僅是滿射B僅是入射C是雙射D無(wú)逆函數(shù)9設(shè)A=1，2，3，4，5，A上二元關(guān)系R=1，2，3，4，2，2，S=2，4，3，1，4，2，則S-1R-1的運(yùn)算結(jié)果是（）A4，1，2，3，4，2B2，4，2，3，4，2C4，1，2，3，2，4D2，2，3，1，4，410設(shè)有代數(shù)系統(tǒng)G=A，*，其中A是所有命題公式的集合，*為命題公式的合取運(yùn)算，則G的幺元是（）A矛盾式B重言式C可滿足式D公式pq11在實(shí)數(shù)集合R上，下列定義的運(yùn)算中不可結(jié)合的是（）Aa*b=a+b+2abBa

20、*b=a+bCa*b=a+b+abDa*b=a-b12下列集合關(guān)于所給定的運(yùn)算成為群的是（）A已給實(shí)數(shù)a的正整數(shù)次冪的全體，且a0，1，-1，關(guān)于數(shù)的乘法B所有非負(fù)整數(shù)的集合，關(guān)于數(shù)的加法C所有正有理數(shù)的集合，關(guān)于數(shù)的乘法D實(shí)數(shù)集，關(guān)于數(shù)的除法13設(shè)無(wú)向圖中有6條邊，有一個(gè)3度頂點(diǎn)和一個(gè)5度頂點(diǎn)，其余頂點(diǎn)度為2，則該圖的頂點(diǎn)數(shù)是（）A3B4C5D614下列各圖中既是歐拉圖，又是漢密爾頓圖的是（）A B C D15設(shè)無(wú)向圖G的邊數(shù)為m，結(jié)點(diǎn)數(shù)為n，則G是樹等價(jià)于（）AG連通且m=n+1BG連通且n=m+1CG連通且m=2nD每對(duì)結(jié)點(diǎn)之間至少有一條通路二、填空題（本大題共10小題，每小題2分，共2

21、0分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16不能再分解的命題稱為_，至少包含一個(gè)聯(lián)結(jié)詞的命題稱為_。17在命題演算中，五個(gè)聯(lián)結(jié)詞的含義是由其_表唯一確定的，而不是由其類似的_語(yǔ)言的含義確定。18使公式（x）（y）（A（x）B（y）（x）A（x）（y）B（y）成立的條件是_不含有y，_不含有x。19設(shè)A為任意集合，請(qǐng)?zhí)钊脒m當(dāng)?shù)倪\(yùn)算符，使式子A_A=Ø；A_A=Ø成立。20設(shè)A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，則domR=_，ranR=_。21稱集合S是給定非空集合A的覆蓋：若S=S1，S2，Sn，其中SiA，SiØ

22、，i=1，2，n，且_；進(jìn)一步若_，則S是集合A的劃分。22對(duì)實(shí)數(shù)的普通加法和乘法，_是加法的冪等元，_是乘法的冪等元。23在代數(shù)系統(tǒng)A，*中，A=a，*是A上二元運(yùn)算，則該代數(shù)系統(tǒng)的單位元是_，零元是_。24設(shè)A，是偏序集，若A中_都有最小上界和_則稱A關(guān)于偏序構(gòu)成格。25若一條路中，所有邊均不相同，則此路稱作_；若一條路中所有的結(jié)點(diǎn)均不相同，則稱此路為_。三、計(jì)算題（本大題共6小題，第26、27小題各4分，第28、29小題各5分，第30、31小題各6分，共30分）36試畫出結(jié)點(diǎn)數(shù)為3的（1）強(qiáng)連通圖；（2）單向連通圖；（3）弱連通圖；（4）非連通圖。27設(shè)A=0，1，2，3，R=x,y|x

23、,yA(y=x+1y=)，S=x,y|x,yA（x=y+2）。試求RSR28在全體正整數(shù)集合Z+中規(guī)定，為：對(duì)任意的a,bZ+，ab=a,b，即求a,b的最小公倍數(shù)；ab=(a,b)，即求a,b的最大公約數(shù)；則運(yùn)算，滿足結(jié)合律，交換律和吸收律，于是Z+，是一個(gè)格。判斷下列集合是否是<Z+，>的子格？1）A=1，2，3，9，12，722）A=1，2，3，12，183）A=5，52，53，5n4）T=2Z+=2k|kZ+29求命題公式（pq）（qp）的主析取范式。30結(jié)出命題公式（p(pq)）(pq)q)的二叉樹表示。31設(shè)A=a,b,c,d, R=a,c，c,b，b,a，a,d，求R

24、，r(R),s(R),t(R)的關(guān)系圖。四、證明題（本大題共3小題，第32、33小題各6分，第34小題8分，共20分）32設(shè)A是非空集合，P（A）是A的冪集，是集合的包含關(guān)系，則P（A），是格，證明：P（A），是有補(bǔ)格。33設(shè)a,b,*是半群，其中a*a=b，證明：（1）a*b=b*a；（2）b*b=b。34若一棵樹恰有2個(gè)結(jié)點(diǎn)的度數(shù)為1，則它必是一條歐拉路。五、應(yīng)用題（本大題共2小題，第35小題6分，第36小題9分，共15分）35設(shè)I是整數(shù)集，<，>，是上的二元關(guān)系，分別表示小于，大于、等于、小于等于，大于等于，不等于，那么這些關(guān)系會(huì)滿足什么性質(zhì)？試填寫下表自反反自反對(duì)稱反對(duì)稱傳

25、遞<>=36設(shè)R=，Z是整數(shù)集，則：（1）R對(duì)矩陣的加法和乘法構(gòu)成一個(gè)環(huán)；（2）R中存在元素x是右零因子但不是左零因子。全國(guó)2007年7月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為（）APQBPQCPQDPQ2下列命題公式為重言式的是（）AQ（PQ）BP（PQ）C（PQ）PD（PQ）Q3下列4個(gè)推理定律中，不正確的是（）AA（AB）B（AB）

26、ABC（AB）ABD（AB）BA4謂詞公式x(P(x)yR(y)Q(x)中量詞的轄域是（）ABP（x）C(P(x)yR(y)DP(x), Q(x)5設(shè)個(gè)體域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下列選項(xiàng)中錯(cuò)誤的是（）AØØBØØCØØDØØ7設(shè)A=a,b,c,d，A上的等價(jià)關(guān)系R=<a, b>, <b, a>, <c, d>, <d, c>

27、IA，則對(duì)應(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|xRx>0，*是數(shù)的乘法運(yùn)算，<R+，*>是一個(gè)群，則下列集合關(guān)于數(shù)的乘法運(yùn)算構(gòu)成該群的子群的是（）AR+中的有理數(shù)BR+中的無(wú)理數(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整

28、環(huán)D含零因子環(huán)12設(shè)A=a, b, c，R是A上的二元關(guān)系，R=<a, a>, <a, b>, <a, c>, <c, a>，那么R是（）A反自反的B反對(duì)稱的C可傳遞的D不可傳遞的13設(shè)D=<V, E>為有向圖，V=a, b, c, d, e, f, E=<a, b>, <b, c>, <a, d>, <d, e>, <f, e>是（）A強(qiáng)連通圖B單向連通圖C弱連通圖D不連通圖14在有n個(gè)結(jié)點(diǎn)的連通圖中，其邊數(shù)（）A最多有n-1條B至少有n-1條C最多有n條D至少有n條15連

29、通圖G是一棵樹，當(dāng)且僅當(dāng)G中（）A有些邊不是割邊B每條邊都是割邊C無(wú)割邊集D每條邊都不是割邊二、填空題（本大題共10小題，每小題2分，共20分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16任意兩個(gè)不同的小項(xiàng)的合取為_式，全體小項(xiàng)的析取式必為_式。17公式x(P(x)Q(x,y)zR(y, z)S(x)中的自由變?cè)獮開，約束變?cè)獮開。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=<1, 2>,<2,3>,<3,1>,g=<1,2>,&

30、lt;2,3>,<3,3>，則fg=_，gf=_。20設(shè)A=a,b,c，R是A上的二元關(guān)系，且給定R=<a,b>,<b,c>,<c,a>，則R的自反閉包r(R)= _，對(duì)稱閉包s(R)= _。21設(shè)Q為有理數(shù)集，笛卡爾集S=Q×Q，*是S上的二元運(yùn)算，<a, b>,<x, y>S, <a, b>*<x, y>=<ax, y+b>, 則*運(yùn)算的幺元是_。<a, b>S, 若a0，則<a, b>的逆元是_。22設(shè)*是集合S上的二元運(yùn)算，若運(yùn)算*滿足_且

31、存在_，則稱<S，*>為獨(dú)異點(diǎn)。23令A(yù)=a, b, c，<A, *>是循環(huán)群，a是單位元，則b2=_，c的階是_。24如下無(wú)向圖割點(diǎn)是_，割邊是_。25無(wú)向圖G具有生成樹，當(dāng)且僅當(dāng)_。G的所有生成樹中_的生成樹稱為最小生成樹。三、計(jì)算題（本大題共5小題，第26、27小題各5分，第28、29小題各6分，第30小題8分，共30分）26集合A=a, b, c, d, e上的二元關(guān)系R為R=<a,a>, <a,b>, <a,c>, <a,d>, <a,e>, <b,b>, <b,c>, <

32、;b,e>, <c,c>, <c,d>, <c,e>, <d,d>, <d,e>, <e,e>（1）寫出R的關(guān)系矩陣；（2）判斷R是不是偏序關(guān)系，為什么？27利用真值表判斷公式（PQ）（QR）（PR）是否為重言式。28給定圖G如下所示，（1）寫出G的可達(dá)矩陣；（2）G中長(zhǎng)度為4的路有幾條？29求下列公式的主析取范式和主合取范式：（PQ）（QR）30設(shè)A為54的因子構(gòu)成的集合，RA×A，x,yA, xRyx整除y。畫出偏序集<A,R>的哈斯圖，并求A中的最大元，最小元，極大元，極小元。五、證明題（

33、本大題共3小題，第31、32小題各6分，第33小題8分，共20分）31設(shè)R是A上的一個(gè)自反關(guān)系，證明：R是一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng)若<a,b>R，<a,c>R，則<b,c>R。32設(shè)<G，*>是一個(gè)群，xG，定義：ab=a*x*b，a,bG。證明：<G,>也是一個(gè)群。33設(shè)圖G是具有6個(gè)結(jié)點(diǎn)，12條邊的無(wú)向簡(jiǎn)單圖，證明圖G是漢密爾頓圖。五、應(yīng)用題（本大題共2小題，第34小題8分，第35小題7分，共15分）34構(gòu)造下面推理的證明。 如果今天是星期六，我們就要到頤和園或圓明園去玩。如果頤和園游人太多，我們就不去頤和園玩。今天是星期六，頤和園

34、游人太多，所以我們?nèi)A明園玩。35n個(gè)城市用k條公路的網(wǎng)絡(luò)連結(jié)。一條公路定義為兩個(gè)城市間的一條不穿過任何中間城市的道路。任意兩個(gè)城市之間至多修一條公路。證明如果k>(n-1)(n-2)，則人們總能通過連結(jié)的公路，在任何兩個(gè)城市間旅行。全國(guó)2008年4月自考離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1.設(shè)P：天下大雨,Q：他在室內(nèi)運(yùn)動(dòng),命題“除非天下大雨，否則他不在室內(nèi)運(yùn)動(dòng)”可符合化為（）A.ùPQB.ùPQC.

35、9;PùQùQ2.下列命題聯(lián)結(jié)詞集合中，是最小聯(lián)結(jié)詞組的是（）A.ù， B.ù，C.ù，D.，假命題的是（）A.如果2是偶數(shù)，那么一個(gè)公式的析取范式惟一B.如果2是偶數(shù)，那么一個(gè)公式的析取范式不惟一C.如果2是奇數(shù)，那么一個(gè)公式的析取范式惟一D.如果2是奇數(shù)，那么一個(gè)公式的析取范式不惟一x(P(x)$yR(y)Q(x)中變?cè)獂是（）5.若個(gè)體域?yàn)檎麛?shù)減，下列公式中值為真的是（）A.x$y(x+y=0)B.$yx(x+y=0)C.xy(x+y=0)D.ù$x$y(x+y=0)不正確的是（）x-xB.xÍx-xC.A=xx,則x

36、A且xÍAD.A-B=ÆÛA=B7.設(shè)P=x|(x+1)24，Q=x|x2+165x,則下列選項(xiàng)正確的是（）ÉQÊQÉPD.Q=P不成立的是（）(BÅC)=(AB) Å (AC)(BÅC)=(AB) Å (AC)C.(AÅB)×C=(A×C) Å (B×C)D.(A-B) ×C=(A×C)-(B×C)9.半群、群及獨(dú)異點(diǎn)的關(guān)系是（）A.群Ì獨(dú)異點(diǎn)Ì半群B.獨(dú)異點(diǎn)Ì半群Ì群C.獨(dú)

37、異點(diǎn)Ì群Ì半群D.半群Ì群Ì獨(dú)異點(diǎn)10.下列集合對(duì)所給的二元運(yùn)算封閉的是（）+上規(guī)定*為a*b=ab-a-b a,bR+上的二元運(yùn)算*為x*y=min(x,y) x,yZ+×n實(shí)可逆矩陣集合Rn×n上的矩陣加法11.設(shè)集合A=1，2，3，下列關(guān)系R中不是等價(jià)關(guān)系的是（）A.R=<1,1>,<2,2>,<3,3>B.R=<1,1>,<2,2>,<3,3>,<3,2>,<2,3>C.R=<1,1>,<2,2>,<3

38、,3>,<1,2>D.R=<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>12.下列函數(shù)中為雙射的是（）A.f：ZZ,f(j)=j(mod)B.f：NN,f(j)=C.f：ZN,f(j)=|2j|+1D.f：RR,f(r)=2r-1513.設(shè)集合A=a,b, c上的關(guān)系如下，具有傳遞性的是（）A.R=<a,c>,<c,a>,<a,b>,<b,a>B.R=<a,

39、c>,<c,a>C.R=<a,b>,<c,c>,<b,a>,<b,c>D.R=<a,a>14.含有5個(gè)結(jié)點(diǎn)，3條邊的不同構(gòu)的簡(jiǎn)單圖有（）15.設(shè)D的結(jié)點(diǎn)數(shù)大于1，D=<V,E>是強(qiáng)連通圖，當(dāng)且僅當(dāng)（）二、填空題(本大題共10小題，每小題2分，共20分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16.設(shè)A=1,2,3，B=3,4,5，則AÅA=_，AÅB=_。17.設(shè)A=1,2,3,4,5，RÍA×A，R=<1,2>，<3,4>,<

40、;2,2>，則R的自反閉包r(R)=_。對(duì)稱閉包t(R)=_。18.設(shè)P、Q為兩個(gè)命題，德摩根律可表示為_，吸收律可表示為_。x(P(x)Q(x)，其中P(x)x=1,Q(x)x=2,當(dāng)論域?yàn)?,2時(shí)，其真值為_ ,當(dāng)論域?yàn)?,1,2時(shí)，其真值為_。RR,f(x)=x+3,gRR,g(x)=2x+1,則復(fù)合函數(shù),。21.3個(gè)結(jié)點(diǎn)可構(gòu)成_個(gè)不同構(gòu)的簡(jiǎn)單無(wú)向圖，可構(gòu)成_個(gè)不同構(gòu)的簡(jiǎn)單有向圖。22.無(wú)向圖G=<V,E>如左所示，則G的最大度(G)=_，G的最小度(G)=_。23.設(shè)圖G<V,E>,V=v1,v2,v3,v4,若G的鄰接矩陣，則deg-(v1)=_ _,d

41、eg+(v4)=_。24.格L是分配格，當(dāng)且僅當(dāng)L既不含有與_同構(gòu)的子格，也不含有與_同格的子格。25.給定集合A=1,2,3,4,5，在集合A上定義兩種關(guān)系：R=<1,2>,<3,4>,<2,2>,S=<4,2>,<2,5>,<3,1>,<1,3>，則，。三、計(jì)算題（本大題共5小題，第26、27題各5分，第28、29題各6分，第30題8分，共30分）26.設(shè)A=a,b,c,d，A上的等價(jià)關(guān)系R=<a,b>,<b,a>,<c,d>,<d,c>IA，畫出R的關(guān)系圖，

42、并求出A中各元素的等價(jià)類。ù（PQ） （ùPQ）的真值表。28.求下列公式的主析取范式和主合取范式：P（QP）（ùPQ）29.設(shè)A=a,b,c,d,e，R為A上的關(guān)系，R=<a,d>，<a,c>，<a, b>, <a, e>, <b, e>,<c, e>, <d, e>IA，試畫<A，R>的哈斯圖，并求A中的最大元，最小元，極大元，極小元。30.給定圖G如圖所示，（1）G中長(zhǎng)度為4的路有幾條？其中有幾條回路？（2）寫出G的可達(dá)矩陣。四、證明題（本大題共3小題，第31、32題各6分，第33題8分，共20分）31.設(shè)（L，）是格，試證明：a, b, c L, 有a（bc）（ab）（ac）；a（bc）（ab）（ac）。32.設(shè)R是A上的自反和傳遞關(guān)系，如下定義A上的關(guān)系T，使得x, yA，<x, y>T<x, y>R(y, x)R。證明T是A上的等價(jià)關(guān)系。33.設(shè)有G=<V, E>, V的結(jié)點(diǎn)數(shù)|V|=n，稱該圖為n階圖，若從結(jié)點(diǎn)vi到vj存在路，證明從vi到vj必存在長(zhǎng)度小于等于n-1的一條路