02324離散數(shù)學(xué)2008年04月試卷

浙02324#離散數(shù)學(xué)試卷第5頁(yè)（共5頁(yè)）全國(guó)2008年4月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1.設(shè)P：天下大雨,Q：他在室內(nèi)運(yùn)動(dòng),命題“除非天下大雨，否則他不在室內(nèi)運(yùn)動(dòng)”可符合化為（）A.P∧Q B.P→QC.P→Q D.P→Q2.下列命題聯(lián)結(jié)詞集合中，是最小聯(lián)結(jié)詞組的是（）A.{，} B.{，∨，∧}C.{，∧} D.{∧，→}3.下列命題為假命題的是（）A.如果2是偶數(shù)，那么一個(gè)公式的析取范式惟一B.如果2是偶數(shù)，那么一個(gè)公式的析取范式不惟一 C.如果2是奇數(shù)，那么一個(gè)公式的析取范式惟一D.如果2是奇數(shù)，那么一個(gè)公式的析取范式不惟一4.謂詞公式x(P(x)∨yR(y))→Q(x))中變?cè)獂是（）A.自由變?cè)?B.約束變?cè)狢.既不是自由變?cè)膊皇羌s束變?cè)?D.既是自由變?cè)彩羌s束變?cè)?.若個(gè)體域?yàn)檎麛?shù)減，下列公式中值為真的是（）A.xy(x+y=0) B.yx(x+y=0) C.xy(x+y=0) D.xy(x+y=0)6.下列命題中不正確的是（）A.x∈{x}-{{x}} B.{x}{x}-{{x}} C.A={x}∪x,則x∈A且xA D.A-B=A=B7.設(shè)P={x|(x+1)2≤4}，Q={x|x2+16≥5x},則下列選項(xiàng)正確的是（）A.PQ B.PQC.QP D.Q=P8.下列表達(dá)式中不成立的是（）A.A∪(BC)=(A∪B)(A∪C) B.A∩(BC)=(A∩B)(A∩C)C.(AB)×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ú)異點(diǎn)}{群}{半群} D.{半群}{群}{獨(dú)異點(diǎn)}10.下列集合對(duì)所給的二元運(yùn)算封閉的是（）A.正整數(shù)集上的減法運(yùn)算 B.在正實(shí)數(shù)的集R+上規(guī)定為ab=ab-a-b a,b∈R+C.正整數(shù)集Z+上的二元運(yùn)算為xy=min(x,y) x,y∈Z+D.全體n×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,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：Z→Z,f(j)=j(mod) B.f：N→N,f(j)=C.f：Z→N,f(j)=|2j|+1 D.f：R→R,f(r)=2r-1513.設(shè)集合A={a,b,c}上的關(guān)系如下，具有傳遞性的是（）A.R={<a,c>,<c,a>,<a,b>,<b,a>} B.R={<a,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)單圖有（）A.2個(gè) B.3個(gè)C.4個(gè) D.5個(gè)15.設(shè)D的結(jié)點(diǎn)數(shù)大于1，D=<V,E>是強(qiáng)連通圖，當(dāng)且僅當(dāng)（）A.D中至少有一條通路 B.D中至少有一條回路C.D中有通過每個(gè)結(jié)點(diǎn)至少一次的通路 D.D中有通過每個(gè)結(jié)點(diǎn)至少一次的回路二、填空題(本大題共10小題，每小題2分，共20分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16.設(shè)A={1,2,3}，B={3,4,5}，則AA=___________，AB=___________。17.設(shè)A={1,2,3,4,5}，RA×A，R={<1,2>，<3,4>,<2,2>}，則R的自反閉包r(R)=__________。對(duì)稱閉包t(R)=__________。18.設(shè)P、Q為兩個(gè)命題，德摩根律可表示為_____________，吸收律可表示為____________。19.對(duì)于公式x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,當(dāng)論域?yàn)閧1,2}時(shí)，其真值為_____________,當(dāng)論域?yàn)閧0,1,2}時(shí)，其真值為_____________。20.設(shè)f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,則復(fù)合函數(shù),。21.3個(gè)結(jié)點(diǎn)可構(gòu)成_________個(gè)不同構(gòu)的簡(jiǎn)單無向圖，可構(gòu)成________個(gè)不同構(gòu)的簡(jiǎn)單有向圖。22.無向圖G=<V,E>如左所示，則G的最大度Δ(G)=_____________，G的最小度δ(G)=_____________。23.設(shè)圖G<V,E>,V={v1,v2,v3,v4},若G的鄰接矩陣，則deg-(v1)=_________,deg+(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)系圖，并求出A中各元素的等價(jià)類。27.構(gòu)造命題公式（P∨Q）（P∧Q）的真值表。28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（P∧Q））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∧（b∨c）≥（a∧b）∨（a∧c）；a∨（b∧c）≤（a∨b）∧（a∨c）。32.設(shè)R是A上的自反和傳遞關(guān)系，如下定義A上的關(guān)系T，使得x,y∈A，<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的一條路。五、應(yīng)用題（本大題共2小題，第34題7分，第35題8分，共15分）34.構(gòu)造下面推理的證明。