離散數(shù)學(xué) 自考真題 附答案 打印版

年

A.〈Q*是體有理數(shù)集*數(shù)

B.(

B離散數(shù)學(xué)試題：02324一、單項(xiàng)選擇(本大題共15小題，小題分，共分在每題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符題目要求的，請(qǐng)將正確選項(xiàng)前的母填在題后的括號(hào)內(nèi)。一個(gè)連的無(wú)向圖G，果的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，那么它具有一條()漢密爾頓回路歐回C.漢密爾頓通路初回路設(shè)是連通簡(jiǎn)單平面圖G中有11個(gè)頂點(diǎn)個(gè)，則中邊是()A.10B.12在布爾數(shù)L中，表達(dá)(∧∨(a∧b∧c)∨∧c)的等價(jià)是()∧(a∨(a∧∨(a(a∨∧(a∨∨∧(b∨(b∨∧(a∨c)設(shè)i是數(shù)復(fù)乘法運(yùn)，則·是群，下列是G的子群是()A.<{1},·>〈〈{i},〈{-i},設(shè)Z為數(shù)集A為合A冪集為P(A),+-/為數(shù)的加、減、除運(yùn)算，∩為集合的交運(yùn)算，下列系統(tǒng)中是代數(shù)系統(tǒng)的()〈ZB.〈，〉〈〉〈P(A)，∩〉下各代數(shù)系統(tǒng)中不含有零元素的是()

的乘法運(yùn)算〈Mn(R),*〉,Mn(R)是全體n階矩陣集合，*矩陣乘法運(yùn)算〈Z，是整數(shù)集，義為xxy=xy,x,y∈Z〈+是數(shù)集是數(shù)的加法運(yùn)算設(shè)A={1,2,3}A上元系的關(guān)系圖如下：R有的性質(zhì)是自反性對(duì)稱性傳遞性反自反性設(shè)，A上二元關(guān)系R={〈a,a〉,a,c}則關(guān)系的稱閉包S(R)()∪IB.RAC.R∪{c,a}∩IA設(shè)X上恒等關(guān)系，要使Ix〈∪R為X上的等價(jià)關(guān)系，應(yīng)取()｛〉，〈a,c〉｝B.{〈〉}C.{〈〉，〈b,a〉}D.{a,c〉}10.下列式子正確的()∈B.{}{}設(shè)解釋R如：論域D為數(shù)，下列公式在下真的()(x)(y)(z)(A(x,y))→A(f(x,z),f(y,z))(x)A(f(a,x),a)(x)(（(x)(y)(A(x,y)A(f(x,a),a))12.設(shè)B是不含變?cè)獂的式，謂詞公式(x)(A(x)→等于()x)A(x)→B

→(x)A(x)→(x)B謂詞公式(x)(P(x,y))(z)Q(x,z)∧中元x()是自由變?cè)皇羌s束變?cè)炔皇亲杂勺冊(cè)植皇羌s束變?cè)仁亲杂勺冊(cè)质羌s束變?cè)羌s束變?cè)皇亲杂勺冊(cè)?4.若P明Q用功；則“他雖聰明用化()∨∧┐QC.P→┐Q∨┐Q以命題公式中，為永假式的是()→(p∨∨r)→→┐p┐(q→q)∧p┐∨→(p∧┐p)二、填空題每空1分，共)16.在一棵根樹(shù)中，僅有一個(gè)結(jié)點(diǎn)的入度為，為樹(shù)根，其余結(jié)點(diǎn)的入度均為_(kāi)。17.A={1,2,3,4}上元關(guān)系R={〈4〈32〉}R的系矩陣M中=______,m。R24〈是則么s除______外，不可能有別的冪等元；若〉有零元，則設(shè)A為合P(A)為A的集，則〈，〉格，若x,yP(A),則x,y大下界是_小上界是_____設(shè)函數(shù)f:X→如果對(duì)X中任意兩個(gè)不同的x和x，們的象和121y也同，我們說(shuō)f是_____函數(shù)，2如果則稱f______數(shù)。21.設(shè)為空集合A上等價(jià)關(guān)系，其等價(jià)類(lèi)記為〔x〕R。x,y∈A，RR-1n-nn11026.2RR-1n-nn11026.21M=222ijij若〈x,y〉∈，則〔x〕與y〕的系是，而Rx,y〕。22.使公式(x)(∧

寫(xiě)出解的過(guò)程。

在圓桌旁，使得任意一個(gè)人認(rèn)識(shí)其旁邊的兩個(gè)人據(jù)是什么?B(y))(

∧(

成立的條件是_不含有y不含有x。設(shè)M(x):x是人是死的，則命題“所有的人都是要死的”可符號(hào)化為(其中量詞(x)的轄域是。若∧H…H是_____則稱1H1,H2,…Hn是容的，若∧H1∧…∧H是______則稱H,…n1H是相容的。n25.判斷一個(gè)語(yǔ)句是否為命題，先要看它是否為，后看它是否具有唯一的。三、計(jì)算題(共30分)分設(shè)有向圖G=(V,E)如下圖所示試用鄰接矩陣方法求長(zhǎng)度為2的的總數(shù)和回路總數(shù)。(5)設(shè)A={a,b},P(A)是A的冪集，是對(duì)稱差運(yùn)算以驗(yàn)<P(A)>是群。設(shè)是正數(shù)，求({a}{a}){a}{a}分)設(shè)A={1,2,3,4,5},A上序關(guān)系〈1255〉}I;A作出偏序關(guān)系的哈斯圖令B={1,2,3,5}，求B最大，最小元，極大、極小元，上界，下確界，下界，下確界。分)求→Q)(P→的主合取范式并給出所有使命題為真的賦值。分設(shè)帶權(quán)無(wú)向圖G如的最小生成樹(shù)T及T的總和，要求

31.(4分)求公┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。四、證明題(共20分分)是非平凡的無(wú)向樹(shù)，T中度數(shù)最大的頂點(diǎn)有個(gè)它們的數(shù)為k(k≥2),證明T中少有片樹(shù)葉。分設(shè)A是空集合F是有從A到A的射函數(shù)的集合，是數(shù)復(fù)合運(yùn)算。證明〉是群。34.(6)在個(gè)體域D={a…}證1n明等價(jià)式：(x)(A(x)→B(x))(→(五、應(yīng)用題(共15分)分如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過(guò)DELPHI語(yǔ)而學(xué)過(guò)語(yǔ)言。只要他學(xué)過(guò)DELPHI語(yǔ)或者語(yǔ)言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序請(qǐng)用命題邏輯推理方法，證明該推理的有效結(jié)論。分一學(xué)術(shù)會(huì)議的理事會(huì)共有個(gè)人參加，他們之間有的相互認(rèn)識(shí)但有的相互不認(rèn)識(shí)。但對(duì)任意兩個(gè)人，他們各自認(rèn)識(shí)的人的數(shù)目之和不小于20否把這20個(gè)排

答：一、單項(xiàng)選擇(本大題共題，每小題分，共15分1.B2.D3.A4.A5.D6.D7.D8.C10.B11.A12.A14.B二、填空題0110單位元1x∩yxy入射［x］=［yRB(y)(M(x)→D(x))M(x)→D(x)可滿足式永式或盾式陳述句真三、計(jì)算題011111021144MMijiG中度為2的路總數(shù)為18長(zhǎng)度nn-1n-nnn-1nn-1n-nn-1-1n｛｝-1-1AAAA111221122f=fA111-112nn-1n-nnn-1nn-1n-nn-1-1n｛｝-1-1AAAA111221122f=fA111-1122121111212n12nx12ni為回路總數(shù)為。

令為e上權(quán)，則ii

封閉的。27.當(dāng)偶數(shù)時(shí)，x∈=

a<a<a<a1357

f,g,h∈由函數(shù)復(fù)合運(yùn)算的結(jié)當(dāng)n是奇數(shù)時(shí)，x∈P(A),x=x于是n是數(shù)｛｝｛b｝｛｝

取的e∈的e的e∈113的∈的e即，45

合律有f(gh)=(fg)故算是可結(jié)合的。(3)A上恒等函數(shù)I也是A到AA=

(｝)｛｝a｝=當(dāng)n是奇數(shù)時(shí)，｛a｝｛)

｛｝｛｝｛｝

n｛｝｛｝(｛｝)｛｝n｛｝｝｝｛｝=28.(1)偏序關(guān)系的斯圖為

的雙射函數(shù)即I∈F,且f∈F有T的總權(quán)和=1+2+3+4+5=15If=fI=f,故I是，〉中的31.原式┐xF(x,y)→G(x,y))幺∨H(x)(名)(4)f∈F,因?yàn)閒是射函數(shù)其┐→G(x,y逆數(shù)是存在的也是AA的∨H(x)

射函數(shù)f

-1-1

f=I此y┐(F(x,y)→G(x,y∨H(x)

f是f的元由此上知〈，

〉是群x

y(,y)→

34.證

→B(x))┐G(x,y∨H(x)A(x)B(x))1四、證明題

┐A(a)∨))∨(┐A(a)∨的大元：無(wú)，最小元：無(wú)；極大元：25，極小元：1，3下界：，下確界；上界：無(wú)，上確界：無(wú)29.原(┐→Q)→(P→┐∧((P→┐Q)→┐(P→((P→Q)∨(P→∧(┐(P→┐Q)∨┐(P→

32.設(shè)中片葉y個(gè)支點(diǎn)B(a∨…∨┐)B(a)))2n是T中個(gè)點(diǎn)，有條(┐A(a)∨)∨∨┐A(a)邊，由握手定理知T中有頂點(diǎn)的∨(B(a)∨B(a)∨∨1度數(shù)之的┐(A(a)A(a∧∧))∨┐B(a)∨B(a)…∨d(vi)=2(x+y-1)┐x)A(x)∨(x)B(x)i(x)A(x)→(又樹(shù)葉的度為任一分支點(diǎn)的度五、應(yīng)用題大于等于35.：他是計(jì)算機(jī)系科生(┐P∨Q∨┐Q)∧┐

且度最大的頂點(diǎn)必是分支點(diǎn)，于是

：他是計(jì)算機(jī)系研究生(┐∨∨(P┐Q))(∧Q)∨∧┐Q))(P∧∨∧┐

xi

d(v)

≥

r：他學(xué)過(guò)DELPHI語(yǔ)他學(xué)過(guò)語(yǔ)t:他會(huì)編程序∧(Q∨∨(Q∧(P∨∧∨┐

x·1+2(y-2)+k+k=x+2y+2K-4從而2(x+y-1)≥x+2y+2k-4x≥2k-2

前提：∨→(r∧s),(rs)→結(jié)論：pt證命題為真的賦值是和30.令=(v,v),=(v)136e=(v,v),=(v)356

33.從定義出發(fā)證明：由集合A是非①pP(附前提)空的故然從A到A的射函數(shù)②∨T①I(mǎi)總是存在的，如A上恒等函數(shù)，因③∨→(r∧前引入)此非④∧T③Ie=(v,v),=(v)532

f,gF,為f和g都是A到A

⑤rTIe=(v,v),=(v)743

的雙射函數(shù)故f

g也A到A的⑥r(nóng)∨TIe=(v,v),=(v,v)956

雙射函數(shù)而集合關(guān)運(yùn)算是⑦∨→P(前提引入++iiiij+++x++iiiij+++x⑧⑤I36.可以把這20個(gè)人排在圓桌旁，使得任一人認(rèn)識(shí)其旁邊的兩個(gè)人。根據(jù)：構(gòu)造無(wú)向簡(jiǎn)單圖G=<V,E>,其中V={v…V}以20個(gè)12為頂點(diǎn)的集合，E中邊是若任兩個(gè)人v和v相互認(rèn)識(shí)則在v與v之ijij間連一條邊。V∈V,d(v是與相互認(rèn)識(shí)的人的數(shù)目，由題意知v,v∈V有

．列等值式不正確的是（）A┐x)A(┐AB(x)(BB→(x)A(x)．x)(A(x)∧B(x))(∧(x)B(x)Dx)(y)(A(x)→x)A(x)→(y)B(y)．詞公式∧(x)(Q(x,z)→y)R(x,y,z)中詞x的轄域是（）A(→(y)R(x,y,z))B．→(y)R(x,y,z)

D．Z，且有11．在自然數(shù)集N上，下列定義的運(yùn)算中不可結(jié)合的只有（）A．．的大公約數(shù)D．a(chǎn)*b=a(modb)為數(shù)集∈∧，*數(shù)乘法運(yùn)算<R*是個(gè)群下列集合關(guān)于數(shù)的乘法運(yùn)構(gòu)成該群的子群的是（）A{R中有理數(shù)}d(v)+d(v)ij

于G中存在漢密

C．Q(x,z)→(

B{R中的無(wú)理}爾頓回路。設(shè)C=VV…VV是G中條i1i2i20i1漢密爾頓回路，按這條回路的順序按其排座位即符合要求。國(guó)2004年4月離散數(shù)學(xué)題課代：第一部選擇題（共分）一單選題本題小題每題1分，共分）下是兩個(gè)命題元pq小項(xiàng)是（）．p∧∧．┐p．┐p∧．┐∨p∨q．令p今天下雪了，q：路滑，則命題“雖然今天下雪了是路不”可

D．R為數(shù)集ff(x)=2，則f是）．滿射函數(shù)．入射函數(shù)．雙射函數(shù)．非入射非滿射．A={a,b,c,d}，上的等價(jià)關(guān)系R={<><<>,<d,c>}IA對(duì)應(yīng)于的A的分是（）A{{a},{b,c},jp5ykr6}．{{a,b},{c},kmq4l9w}．{{a},,{c},bhebxel}．{{a,b},{c,d}}設(shè)A={?}B=P(P(A))以下正確的式子是（）．{?,{?}}∈B．{{?,?}}∈．{{?},{{?}}}B．{?,{{?}}}B．XYZ是集合，一是集合相對(duì)

．中自然數(shù)}．{1，，3}．<A,*,>是，則下列正確的是（）．>交換群．A,*是加法群．對(duì)*是可分配的．*對(duì)是可分配的下各圖不是歐拉圖的（）．設(shè)是連通平面圖，中6個(gè)頂點(diǎn)8條邊，則的面的數(shù)目是（）．2面．3個(gè)．個(gè)面．面符號(hào)化為（）

補(bǔ)運(yùn)算下列等式不正確的（）

第二部

非選擇（共分）．p→．p∨┐．p∧q．p∧．下列語(yǔ)句中是命題的只有（）A1+1=10．x+y=10．．xmod

．(X-Z=X-(YZ)．(X-Y)-Z=(X-Z)-Y．(X-Y)-Z=(X-Z)-Z)．(X-Z=X-(YZ)．設(shè)*集合A上的二元運(yùn)算，稱是A上關(guān)于運(yùn)*零元，若（）AA,x*Z=Z*x=ZB，A有C．，且A有x*Z=Z*x=x

二填題本題小題，空分，分）公為之充分必要條件是其析取范式之每一析取項(xiàng)中均必同時(shí)包含一命題變?cè)捌浞穸ü綖橹直匾獥l件其合取范式之每一合取項(xiàng)中均必同時(shí)包含一命題變?cè)捌浞穸?。．前束范式具有形?QV)(QV)…12(QV，其中(1≤i≤n)ni為，A為的謂詞公式。．設(shè)論域{a,b,c}，(等價(jià)于命題公式()S(x)等價(jià)于命題公式。．設(shè)為A上關(guān)系，則的反

四明（本題小第32~33小每題分，34小題分，分6分用等值演算法證明((q∧→r)→∨r))(s(p→q))→分）設(shè)階向樹(shù)<V>中有m條，證明1。閉包r(R)=。

，對(duì)稱閉包

三計(jì)題本題小題第—27小每題分，、

分P={?,{1},{1,2},{1,2,3}}是集合P上包含關(guān)。．某集合A上的二元關(guān)系具對(duì)稱性對(duì)稱性性傳遞性此關(guān)系是，其關(guān)系矩陣是。．<≤是個(gè)偏序集，如果中的任意兩個(gè)元素都有和稱S關(guān)≤構(gòu)成一個(gè)格。．設(shè)Z是整數(shù)集，在Z上義二元運(yùn)算*為·b，中+和是數(shù)的加法和乘法則代數(shù)統(tǒng)<>的元是，元是。．如下平面圖有2個(gè)和，1中deg(R)=，)=。12

小每題，2931題每題6分共30分）分求出從A={1,2}到B={x,y}的所有函數(shù)出哪些是雙射函數(shù)，哪些是滿射函數(shù)。分如論域是{a,b,c}試消去給定公式中的量詞：(y0)。）設(shè)}（A）是A的冪集，集合對(duì)稱差運(yùn)算。知P(A),>是群在群<中①找出其幺元②找出任一元素的逆元。③求元素x使足{a}x=。分用等值演算法求公式┐(p

（）明<P，>是偏集。（1基上證明>是全序集五應(yīng)題本題小題第小9分，36小6分，共15分分在謂詞邏輯中構(gòu)下面推理的證明個(gè)學(xué)校讀書(shū)的人都獲得知識(shí)以果沒(méi)有人獲得知識(shí)就沒(méi)有人在學(xué)校讀書(shū)：所有人的集合）分設(shè)等個(gè)人，已知a會(huì)英語(yǔ)b會(huì)英語(yǔ)、漢語(yǔ)；c會(huì)英、俄d會(huì)日、漢語(yǔ)；會(huì)講德語(yǔ)、俄語(yǔ)f會(huì)講法語(yǔ)、日語(yǔ)g會(huì)法、德語(yǔ)?！鷔)

→┐q)主合取范式

試用圖論方法安排園桌座位人都能與其身邊的人交談。．無(wú)向圖具有一條歐拉回路，且僅當(dāng)G是，并且所有點(diǎn)的度數(shù)都是。圖中的數(shù)是，2結(jié)點(diǎn)v的數(shù)是。5

分畫(huà)出個(gè)有5個(gè)點(diǎn)5條邊的非同構(gòu)的無(wú)向連通簡(jiǎn)單圖。6分在偏序集<Z,≤>中其中Z={1,2,3,4,6,8,12,14}中整除關(guān)系，求集合D={2,3,4,6}的極大元小大小，最小上界和最大下界。．．．．-ij．．．．．-ij．全國(guó)月高等教育自學(xué)考試：02324一、單項(xiàng)選擇(本大題共15小題，小題分，共分在每小題列出的四個(gè)備選項(xiàng)中只一

a*b=a-b-2ab設(shè)群G=<A,*>中A的元素個(gè)數(shù)大于，元素∈A的元為∈A，a*b的算結(jié)果()B.b中零元素中元

改寫(xiě)成)(z)(p(z,y)y)Q(z,y))s)(z)(p(z,(s)Q(x,y)R(z,y)C.個(gè)是符合題目要求的將其代填寫(xiě)

非空集A上二元關(guān)系若是自反

(x)(p(x,m)(y)Q(x,m)R(m,m)在題后的括號(hào)內(nèi)錯(cuò)選多選或選均無(wú)分。下列各圖是平面圖的()設(shè)是個(gè)頂點(diǎn)的無(wú)向簡(jiǎn)單圖下列說(shuō)法不正確的是)若是樹(shù)，則其邊數(shù)等于n-1若是拉圖，則G中有邊C.若中歐拉路，則是連通圖，且有零個(gè)或兩個(gè)奇度數(shù)頂點(diǎn)D.若中任意一對(duì)頂點(diǎn)的度數(shù)之和大于等于，則G中漢密爾頓路格L是分配格的充要條件是L不與下面哪一個(gè)選項(xiàng)同構(gòu)的子()鏈鉆石格五角格五角格與鉆石格設(shè)<是限環(huán)群，則下列說(shuō)法不正確的是()<G,*>的生成元是唯一的有限循環(huán)群中的運(yùn)算*適合交換律中存在一元素a使中一元素都由a的組成D.設(shè)是<G,*>的生成元，則對(duì)任一正整數(shù)i，存在正整數(shù)j使=a在實(shí)數(shù)合上列義的運(yùn)算中是可結(jié)合的只有)

和對(duì)稱的，則R是)偏序關(guān)系等價(jià)關(guān)系相容關(guān)系擬序關(guān)系下面的是｛｝關(guān)系R的關(guān)系圖從G(R)可判斷R所具有的性質(zhì)是()。。3。自反，對(duì)稱，傳遞反自反，非對(duì)稱反自反，對(duì)稱，非傳遞反自反，對(duì)稱，反對(duì)稱，傳遞設(shè)A=｛，，3B=｛a,b列二元關(guān)系為A到B的數(shù)的是()｛｝R=｛<1,a>,<2,b>R=｛｝｛<1,b>,<2,a>,<3,b>,<1,a>10.設(shè)φ為集P(x)是合x(chóng)的冪，下列論斷不正確的是)φ∈φφφ){}（φ{(diào)}P（φ）φ∈P（（（（φ）D.{φ}（φφ}φ）利謂詞的約束變?cè)拿?guī)則和自由變?cè)胍?guī)則，可將如下公式：(x)(p(x,y)(z))(y)R(x,y)

(x)(p(y,(y))12.設(shè)論域?yàn)檎麛?shù)集，下列謂詞公式中真值為假的)(0)(((x)(y)(y13.在命題演算中，語(yǔ)句為真為假的一種性質(zhì)稱為)真值陳述句命題謂詞14.設(shè)P：明天天晴；：我去爬山；那“除非明天天晴則不去爬山可符號(hào)化為)15.下列命題是真式是()(pq)(pq)q(pp)二、填空題本大題共10題，每空1分，共分-1-1請(qǐng)?jiān)诿啃☆}的空格中填上正確答填、不填均無(wú)分。一棵有個(gè)結(jié)點(diǎn)的完全叉樹(shù)，有_個(gè)內(nèi)點(diǎn)；而若一棵樹(shù)有2個(gè)點(diǎn)度數(shù)為2一個(gè)結(jié)點(diǎn)度數(shù)為，個(gè)結(jié)點(diǎn)度數(shù)為4，其余是葉結(jié)點(diǎn)，則該樹(shù)有_個(gè)葉結(jié)點(diǎn)。在一棵根樹(shù)中，有且只有一個(gè)結(jié)點(diǎn)

小題分第32題分共49分)用等值演算法P∨(Q∧的主析取范式，并按，QR順序，寫(xiě)成編碼形式。設(shè)，給定A上元關(guān)系R={<1,1>,<1,2>,<2,3>}求r(R),s(R)。

是兩城市間的矩離了衛(wèi)油管不受破壞，在每段油管間派一連士兵看守，為保證每個(gè)城市石油的正常供應(yīng)最少需多少連士兵看守輸管道總長(zhǎng)度越短士兵越好防守求他們看守道的最短的總長(zhǎng)度。(要求寫(xiě)出求解過(guò)程的入度為_(kāi)____，其余所有結(jié)點(diǎn)的入度

28.

求公式均為_(kāi)。設(shè)≤>格中一個(gè)命題P是a≤∨∧則的偶命題是∧∧c)。設(shè)Z是數(shù)集+是整數(shù)加法運(yùn)算，則Z,+>是群其幺元是_對(duì)任一整數(shù)i,其逆元是_。20.當(dāng)f:XY是_函數(shù)時(shí)f有函數(shù)，且f。

(x)(f(x)y)G(x,z))(z)H(x,z)的前束范式。29.對(duì)如下有向圖D，中度為的路有多少條中回路有多少?21.

設(shè)

30.設(shè)，義A上E={1,2,3,4,5,6},A={1,4},B={1,2,3},C={2,4},則(～A∩～B)∩C=_____,冪集～AB)。22.設(shè)論域則(x)(。

二元關(guān)系∈A且字符串包含于字符串y中}，即R=I∪A驗(yàn)RA上序系。作出R的斯圖向中最少添加幾個(gè)序偶可使之成

四證明題本大題共2小每題823.

使公式

為等價(jià)關(guān)系求該等價(jià)關(guān)系所確定的

分，共分(x)(y)(A(x)B(y))((x)A(x)∨(成立的條件是_____不含有y，不有x。由命題變?cè)捌浞穸ㄋM成的有限個(gè)析取式的合取式稱為_(kāi)___，由命題變?cè)捌浞穸ㄋM成的有限個(gè)合取式的析取式稱為_(kāi)____。不包含_的命題叫做原子命題，包含_的命題稱為復(fù)合命題。三、計(jì)算題本大題共7題，第26

集合A的分。31.某科研所要從3個(gè)項(xiàng)目ABC中選擇～個(gè)項(xiàng)目上馬于某種原，立項(xiàng)時(shí)要滿足以下條件：若A上則C也上；若，則C不上；若C不，則A或B可上。請(qǐng)找出所有的立項(xiàng)方案32.設(shè)有個(gè)城市V，V，…V，126們之間有輸油管連通，其布置如下圖

證明((P(x)├→x)Q(x)證明當(dāng)每個(gè)結(jié)點(diǎn)的度數(shù)大于等于時(shí)，不存在有7條的連通簡(jiǎn)單平面圖。小題每小題5分，第27小

(字)中i

i題每小題7分，第29、小題每

為邊的編號(hào)括號(hào)內(nèi)數(shù)字為邊的-1-1B∨┐p)→∈-1-1B∨┐p)→∈A∧，R({2，3．．B1+1=1.0C．，3>，<6x國(guó)2006年4月離散數(shù)學(xué)試題：02324一、單項(xiàng)選擇題（本大題共小題，每小題分，共分）在每小題列出的四個(gè)備選項(xiàng)中只一個(gè)是符合題目要求的，請(qǐng)將其碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、選或未選均無(wú)分。．下列命題公式為重言式的是（）Ap∨q)

1>，，，2><3，則是）A自反關(guān)系C．稱關(guān)系設(shè)集合X人的全體在X上義關(guān)系R、為R={<a，b|a，b∈∧是b的親}S={<ab>|a∈X∧是b的親}那關(guān)系{<ab>|a∈x∧a的母}的表達(dá)式為（）ASC．SR．A是正整數(shù)集R={(x，y)|x，

列整數(shù)集對(duì)于整除關(guān)系都構(gòu)成偏序集，而能構(gòu)成格的是（）．，37}．{l，23，7}點(diǎn)數(shù)為奇數(shù)且所有結(jié)點(diǎn)的度數(shù)也為奇數(shù)的連通圖必定是（）．歐拉圖．漢密爾頓圖．向圖是歐拉圖當(dāng)且僅當(dāng)是C．q∧┐qD．→

連通的且（）．下列語(yǔ)句中不是題的有（）A這個(gè)語(yǔ)句是假的。C．碟來(lái)自地球外的星球。設(shè)p我累我學(xué)習(xí)命：“除我很累，否則我就去學(xué)習(xí)”的符號(hào)化正確的是（）．┐∧q．┐p→．┐p→．p→．下列等價(jià)式正確的是（）A┐(┐．()()A(A．┐()(┐

46}×{23，6})=（）AB{<3D．石都可練成金。D．{<3，，<6，2>，<9．列式子不正確的是（）A(A-B)-C=(A-C)-BC．(A-B)-C=(A-C)-(B-C)．下列命題正確的是（）A{l2}{{12}{l2，3}1}B{1，2}{1，{l2}，{l23}，2}C．，2}{{1}，{2}{12}}D．{1，2}{1，，{2}，{l2，3}}11在下列代數(shù)系統(tǒng)中不是環(huán)的只有

．G中各頂點(diǎn)的度數(shù)均相等．G中頂點(diǎn)的度數(shù)之和為偶數(shù)C．G中頂點(diǎn)的度數(shù)均為偶數(shù)D．G中各頂點(diǎn)的度數(shù)均為奇數(shù)．面圖(如下的三個(gè)面的數(shù)分別是（）B(A-B)-C=A-(BD．A-(B∪C)=(A-B)CA，，4B．，3C．，3D．，4二、填空題（本大題共小，每小題，共20分一個(gè)公式的主析取或主合取范式的方法______法和______。D

．

（）

給謂詞合式公式A其一部分()(Ax(x))A(x)()B()A<Z+，*)，其Z為數(shù)集+，*別整數(shù)加法和乘法。

公式形式為)B(x)或x)B(x)，則量．在公式中變?cè)獃是）．自由變?cè)s束變?cè)?)(P()(z))(P(,zC．是自由變?cè)?，又是約束變?cè)狣．既不是自由變?cè)?，又不是約變?cè)狝={1上元關(guān)系S={<1，

B+*)其中為理數(shù)集，*別有理數(shù)加法和乘法。．+，*>，其中R為實(shí)數(shù)集為實(shí)數(shù)加法。．，+，*>，其中M(R)為nn數(shù)集n×n矩陣結(jié)合*是矩陣加法和乘法。

詞后面所跟的x稱，而稱B為相應(yīng)量詞____。．X，，Y都實(shí)數(shù)集，f：1X，且f(x)→；f：→V，l2且f(u)＝u；f：VY，且2332333231f。那么fff

的定義

R。域是_______，而復(fù)合函數(shù)(fff。

．G是簡(jiǎn)單平面圖G有n個(gè)頂點(diǎn)m條且明中．集合X={a，，c，上元關(guān)系

三、計(jì)算題(本大題共題，第26

在一項(xiàng)點(diǎn)v，

（v）R={<ad><b，c>，<bd>，<e，d>}，的自反閉包r(R)=_________，對(duì)稱閉包。．已知G=<{l，，i-i}，·>(其是數(shù)的乘法)是，則-l的階是___i的階是_。．對(duì)代數(shù)系<，*>，中*是上的二元運(yùn)算，若a，∈S，且對(duì)任意的x∈，有a*x=x*a=x，b*x=x*b=b，則稱為算“*的，稱b為算*的。．設(shè)<，*>群，則<，*>滿足結(jié)合律和；若｜S｜>l，S中不可能有_。．寫(xiě)出如右有向圖的一條初級(jí)回路：，長(zhǎng)度是_______。個(gè)______且________的無(wú)向圖稱為樹(shù)。在單無(wú)向圖中如果V中每個(gè)結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接，則該圖稱為_(kāi)_____________，如果V有個(gè)結(jié)點(diǎn)么還是_度正則圖。

題各分第2829題各，第30題8分共分)．若集合，，c}}的集為，合B={，{}}冪為P(B)，求P(A)∩P(B)。．構(gòu)造命題公式(p∧r))→p的真值表。．求圖＝<V的達(dá)矩陣，其中V｛v,v,v｝124E＝｛(v,v),(v,v,v),(v),1223(v,v),(v),(v)｝311下公式的主析取范式和主合取范式∧Q∨（∧．設(shè)A＝348RA上除系，試<A，R>的哈斯圖，并求A中最大元，最小元，極大元，極小元。四、證明題（本大題共小題，第31小各分，第33題分，共20分）．設(shè)M偶數(shù)集，＋和·是數(shù)的加、乘運(yùn)算，證明<M＋>是個(gè)環(huán)。．設(shè)是集合X上二元關(guān)系，明R是X上傳遞關(guān)系當(dāng)且僅當(dāng)

≤。五、應(yīng)用題（本大題共2小題，第34題，第35題9分，共分）判下面推理是否正確證明你的結(jié)論。如果小王今天家里有事他會(huì)來(lái)開(kāi)會(huì)。如果小張今天看到小王，則小王今天來(lái)開(kāi)會(huì)了張今天到小王。所以小王今天家里沒(méi)事。．個(gè)莊Vi=l，…，6欲i修建道路使村村可通已有修方案如下帶權(quán)無(wú)向圖所示邊表示道路上數(shù)字表示修建該道路所需費(fèi)用應(yīng)擇修建哪些道路可使得任二個(gè)村莊之間是可通的且總的修建費(fèi)用最低求寫(xiě)出求解過(guò)程出符合要求的最費(fèi)用的道路網(wǎng)絡(luò)圖并計(jì)算其費(fèi)用。22．．．22．．．國(guó)2007年4月離散數(shù)學(xué)試題：02324一、單項(xiàng)選擇題（本大題共小題，每小題分，共分）在每小題列出的四個(gè)備選項(xiàng)中只一個(gè)是符合題目要求的，請(qǐng)將其碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、選或未選均無(wú)分。．列命題公式中不是言式的是

（）Ap(q→r)B．→→p)．→(pp)．→→r))→(p→．列語(yǔ)句中為命題的是（）A這朵花是誰(shuí)的？．這朵花真美麗啊?。@朵花是你的嗎？．這朵花是他的。．個(gè)體域是整數(shù)集，則下列命題真值為真的是（）Ayx(x·

．xy·y≠0)．xy·y=y)．yx(xy=x)．于謂詞公式（x）y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下的描述中錯(cuò)誤的（）x）的轄域是（y（）∧）．z是謂詞公式的約束變?cè)┹犛蚴荘（x,y）．x是謂詞公式的約束變?cè)O(shè)論域D={a,b}，公式xA（x．．．-1-1等價(jià)的命題公式是（）AA（a）∧A（）

設(shè)代數(shù)系統(tǒng)G=〈A*A是所有命題公式的集合為題公

二、填空題（本大題共小，每小題，共20分B．A）→（）

式的合取運(yùn)算，則

G的元是．A（）∨（）．A）→A（）．集合A={1，3}上的下列關(guān)系矩陣中符合等價(jià)關(guān)系條件的是（）

（）A矛盾式B重言式C．滿足式．公式∧q11實(shí)數(shù)集合上列義的運(yùn)中不可結(jié)合的是（）

．不能再分解的命題稱為，少包含一個(gè)聯(lián)結(jié)詞的命題稱為_(kāi)。在題演算中五個(gè)聯(lián)結(jié)詞的義是由其表唯一確定

Aa*b=a+b+2ab

由其類(lèi)似的A

B0

C．

含確定。

0

1

列合關(guān)于所給定的運(yùn)算成為群

．使公式（xy（x）B

0

的是（）

（y）（）A（x→（）C．1D

A已給實(shí)數(shù)a的整次冪的全體，

（y）成的條件是

1

且a{0，，-1}，于數(shù)的乘法

不含有y，____________不含有x。．設(shè)A={?}B=P（（A

B所有非負(fù)整數(shù)的集合，關(guān)于數(shù)的加

．A為任意集合，請(qǐng)?zhí)钊脒m當(dāng)?shù)恼_的式子是（）

法

運(yùn)

算

符，

使

式

子A{{?}{{?}}{?，{?}}}含于B

C．有正有理數(shù)的集合，關(guān)于數(shù)的乘法

A____________~A=?成。

；B{{{?}}}含于BC．{{?，}}}括B

D．?dāng)?shù)，