離散數(shù)學(xué)習(xí)題集(十五套) - 答案

離散數(shù)學(xué)試題與答案試卷一一、填空20%（每小題2分）ABC1．設(shè)（N：自然數(shù)集，E+正偶數(shù)）則。ABC2．A，B，C表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為。3．設(shè)P，Q的真值為0，R，S的真值為1，則的真值=。4．公式的主合取范式為。5．若解釋I的論域D僅包含一個(gè)元素，則在I下真值為。6．設(shè)A={1，2，3，4}，A上關(guān)系圖為則R2=。7．設(shè)A={a，b，c，d}，其上偏序關(guān)系R的哈斯圖為則R=。8．圖的補(bǔ)圖為。9．設(shè)A={a，b，c，d}，A上二元運(yùn)算如下：*abcdabcdabcdbcdacdabdabc那么代數(shù)系統(tǒng)<A，*>的幺元是，有逆元的元素為，它們的逆元分別為。10．下圖所示的偏序集中，是格的為。二、選擇20%（每小題2分）1、下列是真命題的有（）A．； B．；C．；D．。2、下列集合中相等的有（）A．{4，3}；B．{，3，4}；C．{4，，3，3}；D．{3，4}。3、設(shè)A={1，2，3}，則A上的二元關(guān)系有（）個(gè)。A．23；B．32；C．；D．。4、設(shè)R，S是集合A上的關(guān)系，則下列說(shuō)法正確的是（）A．若R，S是自反的，則是自反的；B．若R，S是反自反的，則是反自反的；C．若R，S是對(duì)稱(chēng)的，則是對(duì)稱(chēng)的；D．若R，S是傳遞的，則是傳遞的。5、設(shè)A={1，2，3，4}，P（A）（A的冪集）上規(guī)定二元系如下則P（A）/R=（）A．A；B．P(A)；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{}，{2}，{2，3}，{{2，3，4}}，{A}}6、設(shè)A={，{1}，{1，3}，{1，2，3}}則A上包含關(guān)系“”的哈斯圖為（）7、下列函數(shù)是雙射的為（）A．f:IE,f(x)=2x；B．f:NNN,f(n)=<n,n+1>；C．f:RI,f(x)=[x]；D．f:IN,f(x)=|x|。（注：I—整數(shù)集，E—偶數(shù)集，N—自然數(shù)集，R—實(shí)數(shù)集）8、圖中從v1到v3長(zhǎng)度為3的通路有（）條。A．0； B．1； C．2； D．3。9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（）10、在一棵樹(shù)中有7片樹(shù)葉，3個(gè)3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)則該樹(shù)有（）個(gè)4度結(jié)點(diǎn)。A．1； B．2； C．3； D．4。三、證明26% R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)稱(chēng)和傳遞的，當(dāng)且僅當(dāng)<a,b>和<a,c>在R中有<.b,c>在R中。（8分）f和g都是群<G1,★>到<G2,*>的同態(tài)映射，證明<C,★>是<G1,★>的一個(gè)子群。其中C=(8分)G=<V,E>(|V|=v，|E|=e)是每一個(gè)面至少由k（k3）條邊圍成的連通平面圖，則，由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演16%用CP規(guī)則證明下題（每小題8分）1、2、五、計(jì)算18%1、設(shè)集合A={a，b，c，d}上的關(guān)系R={<a,b>,<b,a>,<b,c>,<c,d>}用矩陣運(yùn)算求出R的傳遞閉包t(R)。（9分）2、如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先算出它們之間的一些直接通信線(xiàn)路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。（９分）試卷二試題與答案一、填空20%（每小題2分）P：你努力，Q：你失敗?！俺悄闩Γ駝t你將失敗”的翻譯為；“雖然你努力了，但還是失敗了”的翻譯為。2、論域D={1，2}，指定謂詞PP(1,1)P(1,2)P(2,1)P(2,2)TTFF則公式真值為。設(shè)S={a1，a2，…，a8}，Bi是S的子集，則由B31所表達(dá)的子集是。設(shè)A={2，3，4，5，6}上的二元關(guān)系，則R= （列舉法）。R的關(guān)系矩陣MR=。5、設(shè)A={1，2，3}，則A上既不是對(duì)稱(chēng)的又不是反對(duì)稱(chēng)的關(guān)系R=；A上既是對(duì)稱(chēng)的又是反對(duì)稱(chēng)的關(guān)系R=。*abcabcabcbbcccb6、設(shè)代數(shù)系統(tǒng)<A，*>，其中A={a，b，c},則幺元是；是否有冪等性；是否有對(duì)稱(chēng)性。7、4階群必是群或群。8、下面偏序格是分配格的是。9、n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn的邊數(shù)為，歐拉圖的充要條件是。10、公式的根樹(shù)表示為。二、選擇20%（每小題2分）1、在下述公式中是重言式為（）A．；B．；C．；D．。2、命題公式中極小項(xiàng)的個(gè)數(shù)為（），成真賦值的個(gè)數(shù)為（）。A．0；B．1；C．2；D．3。3、設(shè)，則有（）個(gè)元素。A．3；B．6；C．7；D．8。設(shè)，定義上的等價(jià)關(guān)系則由R產(chǎn)生的上一個(gè)劃分共有（）個(gè)分塊。A．4；B．5；C．6；D．9。5、設(shè)，S上關(guān)系R的關(guān)系圖為則R具有（）性質(zhì)。A．自反性、對(duì)稱(chēng)性、傳遞性；B．反自反性、反對(duì)稱(chēng)性；C．反自反性、反對(duì)稱(chēng)性、傳遞性；D．自反性。6、設(shè)為普通加法和乘法，則（）是域。A．B．C．D．=N。7、下面偏序集（）能構(gòu)成格。8、在如下的有向圖中，從V1到V4長(zhǎng)度為3的道路有（）條。A．1；B．2；C．3；D．4。9、在如下各圖中（）歐拉圖。10、設(shè)R是實(shí)數(shù)集合，“”為普通乘法，則代數(shù)系統(tǒng)<R，×>是（）。A．群；B．獨(dú)異點(diǎn)；C．半群。三、證明46%設(shè)R是A上一個(gè)二元關(guān)系，試證明若R是A上一個(gè)等價(jià)關(guān)系，則S也是A上的一個(gè)等價(jià)關(guān)系。（9分）用邏輯推理證明：所有的舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。（11分）若是從A到B的函數(shù)，定義一個(gè)函數(shù)對(duì)任意有，證明：若f是A到B的滿(mǎn)射，則g是從B到的單射。（10分）若無(wú)向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定連通。（8分）設(shè)G是具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，其邊數(shù)，則G是Hamilton圖（8分）四、計(jì)算14%設(shè)<Z6,+6>是一個(gè)群，這里+6是模6加法，Z6={[0]，[1]，[2]，[3]，[4]，[5]}，試求出<Z6,+6>的所有子群及其相應(yīng)左陪集。（7分）權(quán)數(shù)1，4，9，16，25，36，49，64，81，100構(gòu)造一棵最優(yōu)二叉樹(shù)。（7分）試卷二答案：試卷三試題與答案填空20%（每空2分）設(shè)f，g是自然數(shù)集N上的函數(shù)，則。設(shè)A={a，b，c}，A上二元關(guān)系R={<a,a>,<a,b>,<a,c>,<c,c>},則s（R）=。A={1，2，3，4，5，6}，A上二元關(guān)系，則用列舉法T=；T的關(guān)系圖為；T具有性質(zhì)。集合的冪集=。P，Q真值為0；R，S真值為1。則的真值為。的主合取范式為。設(shè)P（x）：x是素?cái)?shù)，E(x)：x是偶數(shù)，O(x)：x是奇數(shù)N(x,y)：x可以整數(shù)y。則謂詞的自然語(yǔ)言是。謂詞的前束范式為。選擇20%（每小題2分）下述命題公式中，是重言式的為（）。A、；B、；C、；D、。的主析取范式中含極小項(xiàng)的個(gè)數(shù)為（）。A、2；B、3；C、5；D、0；E、8。給定推理① P② US①③ P④ ES③⑤ T②④I⑥ UG⑤推理過(guò)程中錯(cuò)在（）。A、①->②;B、②->③;C、③->④;D、④->⑤;E、⑤->⑥設(shè)S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在條件下X與（）集合相等。X=S2或S5；B、X=S4或S5；C、X=S1，S2或S4；D、X與S1，…，S5中任何集合都不等。設(shè)R和S是P上的關(guān)系，P是所有人的集合，，則表示關(guān)系（）。A、；B、；C、；D、。下面函數(shù)（）是單射而非滿(mǎn)射。A、；B、；C、；D、。其中R為實(shí)數(shù)集，Z為整數(shù)集，R+，Z+分別表示正實(shí)數(shù)與正整數(shù)集。設(shè)S={1，2，3}，R為S上的關(guān)系，其關(guān)系圖為則R具有（）的性質(zhì)。自反、對(duì)稱(chēng)、傳遞；B、什么性質(zhì)也沒(méi)有；C、反自反、反對(duì)稱(chēng)、傳遞；D、自反、對(duì)稱(chēng)、反對(duì)稱(chēng)、傳遞。設(shè)，則有（）。A、{{1,2}}；B、{1,2}；C、{1}；D、{2}。設(shè)A={1,2,3}，則A上有（）個(gè)二元關(guān)系。A、23；B、32；C、；D、。10、全體小項(xiàng)合取式為（）。A、可滿(mǎn)足式；B、矛盾式；C、永真式；D、A，B，C都有可能。用CP規(guī)則證明16%（每小題8分）1、2、四、（14%）集合X={<1,2>,<3,4>,<5,6>,…}，R={<<x1,y1>,<x2,y2>>|x1+y2=x2+y1}。證明R是X上的等價(jià)關(guān)系。（10分）求出X關(guān)于R的商集。（4分）五、（10%）設(shè)集合A={a,b,c,d}上關(guān)系R={<a,b>,<b,a>,<b,c>,<c,d>}要求1、寫(xiě)出R的關(guān)系矩陣和關(guān)系圖。（4分）2、用矩陣運(yùn)算求出R的傳遞閉包。（6分）六、（20%）1、（10分）設(shè)f和g是函數(shù)，證明也是函數(shù)。2、（10分）設(shè)函數(shù)，證明有一左逆函數(shù)當(dāng)且僅當(dāng)f是入射函數(shù)。答案：填空20%（每空2分）1、2(x+1)；2、；3、；4、反對(duì)稱(chēng)性、反自反性；4、；5、1；6、；7、任意x，如果x是素?cái)?shù)則存在一個(gè)y，y是奇數(shù)且y整除x；8、。選擇20%（每小題2分）題目12345678910答案CCCCABDADC證明16%(每小題8分)1、① P（附加前提）② T①I(mǎi)③ P④ T②③I⑤ T④I⑥ T⑤I⑦ P⑧ T⑥⑦I⑨ CP2、① P（附加前提）② T①E③ ES②④ P⑤ US④⑥ T③⑤I⑦ EG⑥⑧ CP14%證明：自反性：對(duì)稱(chēng)性：傳遞性：即由（1）（2）（3）知：R是X上的先等價(jià)關(guān)系。2、X/R=10%1、；關(guān)系圖2、 t(R)={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c.>,<b,d>,<c,d>}。六、20%1、（1）（2）。2、證明：。。試卷四試題與答案填空10%（每小題2分）若P，Q，為二命題，真值為0當(dāng)且僅當(dāng)。命題“對(duì)于任意給定的正實(shí)數(shù)，都存在比它大的實(shí)數(shù)”令F(x)：x為實(shí)數(shù)，則命題的邏輯謂詞公式為。謂詞合式公式的前束范式為。將量詞轄域中出現(xiàn)的和指導(dǎo)變?cè)粨Q為另一變?cè)?hào)，公式其余的部分不變，這種方法稱(chēng)為換名規(guī)則。設(shè)x是謂詞合式公式A的一個(gè)客體變?cè)珹的論域?yàn)镈，A(x)關(guān)于y是自由的，則被稱(chēng)為存在量詞消去規(guī)則，記為ES。選擇25%（每小題2.5分）下列語(yǔ)句是命題的有（）。明年中秋節(jié)的晚上是晴天；B、；C、當(dāng)且僅當(dāng)x和y都大于0；D、我正在說(shuō)謊。下列各命題中真值為真的命題有（）。2+2=4當(dāng)且僅當(dāng)3是奇數(shù)；B、2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)；C、2+2≠4當(dāng)且僅當(dāng)3是奇數(shù)；D、2+2≠4當(dāng)且僅當(dāng)3不是奇數(shù)；下列符號(hào)串是合式公式的有（）A、；B、；C、；D、。下列等價(jià)式成立的有（）。A、；B、；C、；D、。若和B為wff，且則（）。A、稱(chēng)為B的前件；B、稱(chēng)B為的有效結(jié)論C、當(dāng)且僅當(dāng)；D、當(dāng)且僅當(dāng)。A，B為二合式公式，且，則（）。A、為重言式；B、；C、；D、；E、為重言式?！叭丝偸且赖摹敝^詞公式表示為（）。（論域?yàn)槿倐€(gè)體域）M(x)：x是人；Mortal(x)：x是要死的。A、；B、C、；D、公式的解釋I為：個(gè)體域D={2}，P(x)：x>3,Q(x)：x=4則A的真值為（）。A、1；B、0；C、可滿(mǎn)足式；D、無(wú)法判定。下列等價(jià)關(guān)系正確的是（）。A、；B、；C、；D、。下列推理步驟錯(cuò)在（）。① P② US①③ P④ ES③⑤ T②④I⑥ EG⑤A、②；B、④；C、⑤；D、⑥邏輯判斷30%用等值演算法和真值表法判斷公式的類(lèi)型。（10分）下列問(wèn)題，若成立請(qǐng)證明，若不成立請(qǐng)舉出反例：（10分）已知，問(wèn)成立嗎？已知，問(wèn)成立嗎？如果廠(chǎng)方拒絕增加工資，那么罷工就不會(huì)停止，除非罷工超過(guò)一年并且工廠(chǎng)撤換了廠(chǎng)長(zhǎng)。問(wèn)：若廠(chǎng)方拒絕增加工資，面罷工剛開(kāi)始，罷工是否能夠停止。（10分）四、計(jì)算10%設(shè)命題A1，A2的真值為1，A3，A4真值為0，求命題的真值。（5分）利用主析取范式，求公式的類(lèi)型。（5分）五、謂詞邏輯推理15%符號(hào)化語(yǔ)句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。六、證明：（10%）設(shè)論域D={a,b,c}，求證：。答案：填空10%（每小題2分）1、P真值為1，Q的真值為0；2、；3、；4、約束變?cè)?、，y為D的某些元素。選擇25%（每小題2.5分）題目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)邏輯判斷30%1、（1）等值演算法（2）真值表法PQA1111111100100101100010011111所以A為重言式。2、（1）不成立。若取但A與B不一定等價(jià)，可為任意不等價(jià)的公式。（2）成立。證明：即：所以故。3、解：設(shè)P：廠(chǎng)方拒絕增加工資；Q：罷工停止；R罷工超壺過(guò)一年；R：撤換廠(chǎng)長(zhǎng)前提：結(jié)論：① P② P③ T①②I④ P⑤ T④I⑥ T⑤E⑦ T③⑥I罷工不會(huì)停止是有效結(jié)論。四、計(jì)算10%解：它無(wú)成真賦值，所以為矛盾式。五、謂詞邏輯推理15%解：證明：⑴ P⑵ ES⑴⑶ T⑵I⑷ T⑵I⑸ P⑹ US⑸⑺ T⑶⑹I⑻ T⑺E⑼ US⑷⑽ US⑻⑾ T⑼⑽I⑿ UG⑾證明10%試卷五試題與答案一、填空15%（每空3分）1、設(shè)G為9階無(wú)向圖，每個(gè)結(jié)點(diǎn)度數(shù)不是5就是6，則G中至少有個(gè)5度結(jié)點(diǎn)。2、n階完全圖，Kn的點(diǎn)數(shù)X(Kn)=。3、有向圖中從v1到v2長(zhǎng)度為2的通路有條。4、設(shè)[R，+，·]是代數(shù)系統(tǒng)，如果①[R，+]是交換群②[R，·]是半群③則稱(chēng)[R，+，·]為環(huán)。5、設(shè)是代數(shù)系統(tǒng)，則滿(mǎn)足冪等律，即對(duì)有。二、選擇15%（每小題3分）下面四組數(shù)能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列的有（）。A、（2，2，2，2，2）；B、（1，1，2，2，3）；C、（1，1，2，2，2）；D、（0，1，3，3，3）。下圖中是哈密頓圖的為（）。如果一個(gè)有向圖D是強(qiáng)連通圖，則D是歐拉圖，這個(gè)命題的真值為（）A、真；B、假。下列偏序集（）能構(gòu)成格。設(shè)，*為普通乘法，則[S，*]是（）。A、代數(shù)系統(tǒng)；B、半群；C、群；D、都不是。三、證明48%1、（10%）在至少有2個(gè)人的人群中，至少有2個(gè)人，他們有相同的朋友數(shù)。2、（8%）若圖G中恰有兩個(gè)奇數(shù)度頂點(diǎn)，則這兩個(gè)頂點(diǎn)是連通的。3、（8%）證明在6個(gè)結(jié)點(diǎn)12條邊的連通平面簡(jiǎn)單圖中，每個(gè)面的面數(shù)都是3。4、（10%）證明循環(huán)群的同態(tài)像必是循環(huán)群。5、（12%）設(shè)是布爾代數(shù)，定義運(yùn)算*為，求證[B，*]是阿貝爾群。四、計(jì)算22%1、在二叉樹(shù)中求帶權(quán)為2，3，5，7，8的最優(yōu)二叉樹(shù)T。（5分）求T對(duì)應(yīng)的二元前綴碼。（5分）下圖所示帶權(quán)圖中最優(yōu)投遞路線(xiàn)并求出投遞路線(xiàn)長(zhǎng)度（郵局在D點(diǎn)）。答案：一、填空（15%）每空3分1、6；2、n；3、2；4、+對(duì)·分配且·對(duì)+分配均成立；5、。二、選擇（15%）每小題3分題目12345答案A,BB,DBCD三、證明（48%）1、（10分）證明：用n個(gè)頂點(diǎn)v1，…，vn表示n個(gè)人，構(gòu)成頂點(diǎn)集V={v1，…，vn}，設(shè)，無(wú)向圖G=（V，E）現(xiàn)證G中至少有兩個(gè)結(jié)點(diǎn)度數(shù)相同。事實(shí)上，（1）若G中孤立點(diǎn)個(gè)數(shù)大于等于2，結(jié)論成立。（2）若G中有一個(gè)孤立點(diǎn)，則G中的至少有3個(gè)頂點(diǎn)，既不考慮孤立點(diǎn)。設(shè)G中每個(gè)結(jié)點(diǎn)度數(shù)均大于等于1，又因?yàn)镚為簡(jiǎn)單圖，所以每個(gè)頂點(diǎn)度數(shù)都小于等于n-1，由于G中n頂點(diǎn)其度數(shù)取值只能是1，2，…，n-1，由鴿巢原理，必然至少有兩個(gè)結(jié)點(diǎn)度數(shù)是相同的。2、（8分）證：設(shè)G中兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u，v。若u，v不連通則至少有兩個(gè)連通分支G1、G2，使得u，v分別屬于G1和G2。于是G1與G2中各含有一個(gè)奇數(shù)度結(jié)點(diǎn)，與握手定理矛盾。因而u，v必連通。3（8分）證：n=6,m=12歐拉公式n-m+f=2知f=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個(gè)面用3條邊圍成。4（10分）證：設(shè)循環(huán)群[A，·]的生成元為a，同態(tài)映射為f，同態(tài)像為[f（A），*]，于是都有對(duì)n=1有n=2,有若n=k-1時(shí)有對(duì)n=k時(shí)，這表明，f(A)中每一個(gè)元素均可表示為，所以[f(A),*]為f(a)生成的循環(huán)群。5、證：交換律：有結(jié)合律：有而：幺：有逆：綜上所述：[B，*]是阿貝爾群。四、計(jì)算（22%）1、（10分）（1）（5分）由Huffman方法,得最佳二叉樹(shù)為：（2）（5分）最佳前綴碼為：000，001，01，10，112、（12分）圖中奇數(shù)點(diǎn)為E、F，d(E)=3,d(F)=3,d(E,F)=28p=EGF復(fù)制道路EG、GF，得圖G‘，則G‘是歐拉圖。由D開(kāi)始找一條歐拉回路：DEGFGEBACBDCFD。道路長(zhǎng)度為：35+8+20+20+8+40+30+50+19+6+12+10+23=281。試卷六試題與答案填空15%（每小題3分）n階完全圖結(jié)點(diǎn)v的度數(shù)d(v)=。設(shè)n階圖G中有m條邊，每個(gè)結(jié)點(diǎn)的度數(shù)不是k的是k+1，若G中有Nk個(gè)k度頂點(diǎn)，Nk+1個(gè)k+1度頂點(diǎn)，則Nk=。算式的二叉樹(shù)表示為。如圖給出格L，則e的補(bǔ)元是。一組學(xué)生，用二二扳腕子比賽法來(lái)測(cè)定臂力的大小，則幺元是。二、選擇15%（每小題3分）1、設(shè)S={0,1,2,3},≤為小于等于關(guān)系，則{S，≤}是（）。A、群；B、環(huán)；C、域；D、格。2、設(shè)[{a,b,c}，*]為代數(shù)系統(tǒng)，*運(yùn)算如下：*abcaabcbbaccccc則零元為（）。A、a；B、b；C、c；D、沒(méi)有。3、如右圖相對(duì)于完全圖K5的補(bǔ)圖為（）。4、一棵無(wú)向樹(shù)T有7片樹(shù)葉，3個(gè)3度頂點(diǎn)，其余頂點(diǎn)均為4度。則T有（）4度結(jié)點(diǎn)。A、1；B、2；C、3；D、4。5、設(shè)[A，+，·]是代數(shù)系統(tǒng)，其中+，·為普通加法和乘法，則A=（）時(shí)，[A，+，·]是整環(huán)。A、；B、；C、；D、。三、證明50%1、設(shè)G是（n,m）簡(jiǎn)單二部圖，則。（10分）2、設(shè)G為具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，且，則G是連通圖。（10分）3、記“開(kāi)”為1，“關(guān)”為0，反映電路規(guī)律的代數(shù)系統(tǒng)[{0，1}，+，·]的加法運(yùn)算和乘法運(yùn)算。如下：+01·01001000110101證明它是一個(gè)環(huán)，并且是一個(gè)域。（14分）是一代數(shù)格，“≤”為自然偏序，則[L，≤]是偏序格。（16分）四、10%設(shè)是布爾代數(shù)上的一個(gè)布爾表達(dá)式，試寫(xiě)出的析取范式和合取范式（10分）五、10%如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先算出它們之間的一些直接通信成路造價(jià)（單位：萬(wàn)元），試給出一個(gè)設(shè)計(jì)方案，使得各城市之間既能夠通信又使總造價(jià)最小。答案：一、填空15%（每小題3分）1、n-1；2、n(k+1)-2m；3、如右圖；4、0；5、臂力小者二、選擇15%（每小題3分）題目12345答案DCAAD三、證明50%證：設(shè)G=（V，E）對(duì)完全二部圖有當(dāng)時(shí)，完全二部圖的邊數(shù)m有最大值故對(duì)任意簡(jiǎn)單二部圖有。證：反證法：若G不連通，不妨設(shè)G可分成兩個(gè)連通分支G1、G2，假設(shè)G1和G2的頂點(diǎn)數(shù)分別為n1和n2，顯然與假設(shè)矛盾。所以G連通。（1）[{0，1}，+，·]是環(huán)①[{0，1}，+]是交換群乘：由“+”運(yùn)算表知其封閉性。由于運(yùn)算表的對(duì)稱(chēng)性知：+運(yùn)算可交換。群：（0+0）+0=0+（0+0）=0；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0……結(jié)合律成立。 幺：幺元為0。 逆：0，1逆元均為其本身。②[{0，1}，·]是半群乘：由“·”運(yùn)算表知封閉群：（0·0）·0=0·（0·0）=0；（0·0）·1=0·（0·1）=0；（0·1）·0=0·（1·0）=0；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0。③·對(duì)+的分配律Ⅰ0·（x+y）=0=0+0=(0·x)+(0·y)；Ⅱ1·（x+y）當(dāng)x=y(x+y)=0則；當(dāng)（）則所以均有同理可證：所以·對(duì)+是可分配的。由①②③得，[{0，1}，+，·]是環(huán)。（2）[{0，1}，+，·]是域因?yàn)閇{0，1}，+，·]是有限環(huán)，故只需證明是整環(huán)即可。①乘交環(huán)：由乘法運(yùn)算表的對(duì)稱(chēng)性知，乘法可交換。②含幺環(huán)：乘法的幺元是1③無(wú)零因子：1·1=1≠0因此[{0，1}，+，·]是整環(huán)，故它是域。4、證：（1）“≤”是偏序關(guān)系，≤自然偏序①反自反性：由代數(shù)格冪等關(guān)系：。②反對(duì)稱(chēng)性：若即：，則③傳遞性：則：（2）在L中存在{x,y}的下（上）確界設(shè)則：事實(shí)上：若{x,y}有另一下界c，則是{x,y}最大下界，即同理可證上確界情況。四、14%解：函數(shù)表為：00000011010001111000101111011111析取范式：合取范式：五、10%解：用庫(kù)斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹(shù)。算法為：結(jié)果如圖：樹(shù)權(quán)C(T)=23+1+4+9+3+17=57（萬(wàn)元）即為總造價(jià)試卷七試題與答案填空15%（每小題3分）任何(n,m)圖G=(V,E),邊與頂點(diǎn)數(shù)的關(guān)系是。當(dāng)n為時(shí),非平凡無(wú)向完全圖Kn是歐拉圖。已知一棵無(wú)向樹(shù)T有三個(gè)3頂點(diǎn),一個(gè)2度頂點(diǎn),其余的都是1度頂點(diǎn),則T中有個(gè)1度頂點(diǎn)。n階完全圖Kn的點(diǎn)色數(shù)X(KN)=。一組學(xué)生,用兩兩扳腕子比賽來(lái)測(cè)定臂力大小,則幺元是。選擇15%（每小題3分）1、下面四組數(shù)能構(gòu)成無(wú)向圖的度數(shù)列的有()。A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。2、圖的鄰接矩陣為()。A、；B、；C、；D、。3、下列幾個(gè)圖是簡(jiǎn)單圖的有()。G1=(V1,E1),其中V1={a,b,c,d,e},E1={ab,be,eb,ae,de}；G2=(V2,E2)其中V2=V1,E2={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}；G=(V3,E3),其中V3=V1,E3={ab,be,ed,cc}；G=(V4,E4),其中V4=V1,E4={（a,a）,（a,b）,（b,c）,（e,c）,（e,d）}。4、下列圖中是歐拉圖的有()。5、，其中，為集合對(duì)稱(chēng)差運(yùn)算，則方程的解為（）。A、；B、；C、；D、。證明34%證明：在至少有2個(gè)人的人群中，至少有2個(gè)人，他的有相同的朋友數(shù)。（8分）若圖G中恰有兩個(gè)奇數(shù)頂點(diǎn)，則這兩個(gè)頂點(diǎn)是連通的。（8分）證明：在6個(gè)結(jié)點(diǎn)12條邊的連通平面簡(jiǎn)單圖中，每個(gè)面的面度都是3。（8分）證明循環(huán)群的同態(tài)像必是循環(huán)群。（10分）中國(guó)郵遞員問(wèn)題13%求帶權(quán)圖G中的最優(yōu)投遞路線(xiàn)。郵局在v1點(diǎn)。根樹(shù)的應(yīng)用13%在通訊中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下：0：30%、1：20%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求傳輸它們最佳前綴碼（寫(xiě)出求解過(guò)程）。10%設(shè)B4={e,a,b,ab}，運(yùn)算*如下表，*則<B4,*>是一個(gè)群（稱(chēng)作Klein四元群答案：填空15%（每小題3分）1、；2、奇數(shù)；3、5；4、n；5、臂力小者選擇15%（每小題3分）題目12345答案BCBBA證明34%1、（10分）證明：用n個(gè)頂點(diǎn)v1，…，vn表示n個(gè)人，構(gòu)成頂點(diǎn)集V={v1，…，vn}，設(shè)，無(wú)向圖G=（V，E）現(xiàn)證G中至少有兩個(gè)結(jié)點(diǎn)度數(shù)相同。事實(shí)上，（1）若G中孤立點(diǎn)個(gè)數(shù)大于等于2，結(jié)論成立。（2）若G中有一個(gè)孤立點(diǎn)，則G中的至少有3個(gè)頂點(diǎn)，現(xiàn)不考慮孤立點(diǎn)。設(shè)G中每個(gè)結(jié)點(diǎn)度數(shù)均大于等于1，又因?yàn)镚為簡(jiǎn)單圖，所以每個(gè)頂點(diǎn)度數(shù)都小于等于n-1，由于G中頂點(diǎn)數(shù)到值只能是1，2，…，n-1這n-1個(gè)數(shù)，因而取n-1個(gè)值的n個(gè)頂點(diǎn)的度數(shù)至少有兩個(gè)結(jié)點(diǎn)度數(shù)是相同的。2、（8分）證：設(shè)G中兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u，v。若u，v不連通，即它們中無(wú)任何通路，則至少有兩個(gè)連通分支G1、G2，使得u，v分別屬于G1和G2。于是G1與G2中各含有一個(gè)奇數(shù)度結(jié)點(diǎn)，與握手定理矛盾。因而u，v必連通。3、（8分）證：n=6,m=12歐拉公式n-m+f=2知f=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個(gè)面用3條邊圍成。4、（10分）證：設(shè)循環(huán)群[A，·]的生成元為a，同態(tài)映射為f，同態(tài)像為<f（A），*>，于是都有對(duì)n=1有n=2,有若n=k-1時(shí)有對(duì)n=k時(shí)，這表明，f(A)中每一個(gè)元素均可表示為，所以<f(A),*>是以f(a)生成元的循環(huán)群。中國(guó)郵遞員問(wèn)題14%解：圖中有4個(gè)奇數(shù)結(jié)點(diǎn)，求任兩結(jié)點(diǎn)的最短路再找兩條道路使得它們沒(méi)有相同的起點(diǎn)和終點(diǎn)，且長(zhǎng)度總和最短：在原圖中復(fù)制出，設(shè)圖G‘，則圖G‘中每個(gè)結(jié)點(diǎn)度數(shù)均為偶數(shù)的圖G‘存在歐拉回路，歐拉回路C權(quán)長(zhǎng)為43。根樹(shù)的應(yīng)用13%解：用100乘各頻率并由小到大排列得權(quán)數(shù)用Huffman算法求最優(yōu)二叉樹(shù)：前綴碼用00000傳送5；00001傳送6；0001傳送7；100傳送3；101傳送4；001傳送2；11傳送1；01傳送0（頻率越高傳送的前綴碼越短）。10%證明：乘：由運(yùn)算表可知運(yùn)算*是封閉的。群：即要證明，這里有43=64個(gè)等式需要驗(yàn)證但：①e是幺元，含e的等式一定成立。②ab=a*b=b*a，如果對(duì)含a，b的等式成立，則對(duì)含a、b、ab的等式也都成立。③剩下只需驗(yàn)證含a、b等式，共有23=8個(gè)等式。即：(a*b)*a=ab*a=b=a*(b*a)=a*ab=b；(a*b)*b=ab*b=a=a*(b*b)=a*e=a；(a*a)*a=e*a=a=a*(a*a)=a*e=a；(a*a)*b=e*b=b=a*(a*b)=a*ab=b；(b*b)*a=e*a=a=b*(b*a)=b*ab=a；(b*b)*b=e*b=b=b*(b*b)=b*e=b；(b*a)*a=ab*a=b=b*(a*a)=b*e=b；(b*a)*b=ab*b=a=b*(a*b)=b*ab=a。幺：e為幺元逆：e-1=e；a-1=a；b-1=b；(ab)-1=ab。所以<B4,*>為群。試卷八試題與答案填空15%（每小題3分）n階完全圖Kn的邊數(shù)為。右圖的鄰接矩陣A=。圖的對(duì)偶圖為。完全二叉樹(shù)中，葉數(shù)為nt，則邊數(shù)m=。設(shè)<{a,b,c},*>為代數(shù)系統(tǒng)，*運(yùn)算如下：*abcaabcbbaccccc

則它的幺元為；零元為；a、b、c的逆元分別為。選擇15%（每小題3分）圖相對(duì)于完全圖的補(bǔ)圖為（）。對(duì)圖G則分別為（）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。一棵無(wú)向樹(shù)T有8個(gè)頂點(diǎn)，4度、3度、2度的分枝點(diǎn)各1個(gè)，其余頂點(diǎn)均為樹(shù)葉，則T中有（）片樹(shù)葉。A、3；B、4；C、5；D、6設(shè)<A，+，·>是代數(shù)系統(tǒng)，其中+，·為普通的加法和乘法，則A=（）時(shí)<A，+，·>是整環(huán)。A、；B、；C、；D、。設(shè)A={1，2，…，10}，則下面定義的運(yùn)算*關(guān)于A封閉的有（）。x*y=max(x,y)；B、x*y=質(zhì)數(shù)p的個(gè)數(shù)使得；C、x*y=gcd(x,y)；(gcd(x,y)表示x和y的最大公約數(shù))；D、x*y=lcm(x,y)（lcm(x,y)表示x和y的最小公倍數(shù)）。證明45%1、設(shè)G是（n,m）簡(jiǎn)單二部圖，則。（8分）2、設(shè)G為具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，且則G是連通圖。（8分）3、設(shè)G是階數(shù)不小于11的簡(jiǎn)單圖，則G或中至少有一個(gè)是非平圖。（14分）4、記“開(kāi)”為1，“關(guān)”為0，反映電路規(guī)律的代數(shù)系統(tǒng)[{0，1}，+，·]的加法運(yùn)算和乘法運(yùn)算。如下：+01·01001000110101證明它是一個(gè)環(huán)，并且是一個(gè)域。（15分）生成樹(shù)及應(yīng)用10%1、（10分）如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先測(cè)算出它們之間的一些直接通信線(xiàn)路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間既能夠通信而且總造價(jià)最小。2、（10分）構(gòu)造H、A、P、N、E、W、R、對(duì)應(yīng)的前綴碼，并畫(huà)出與該前綴碼對(duì)應(yīng)的二叉樹(shù)，寫(xiě)出英文短語(yǔ)HAPPYNEWYEAR的編碼信息。5%對(duì)于實(shí)數(shù)集合R，在下表所列的二元遠(yuǎn)算是否具有左邊一列中的性質(zhì)，請(qǐng)?jiān)谙鄳?yīng)位上填寫(xiě)“Y”或“N”。MaxMin+可結(jié)合性可交換性存在幺元存在零元答案：填空15%（每小題3分）1、；2、；3、；4、；5、a，c，a、b、沒(méi)有選擇15%（每小題3分）題目12345答案AACDA，C證明45%（8分）：設(shè)G=（V，E），對(duì)完全二部圖有當(dāng)時(shí)，完全二部圖的邊數(shù)m有最大值。故對(duì)任意簡(jiǎn)單二部圖有。（8分）反證法：若G不連通，不妨設(shè)G可分成兩個(gè)連通分支G1、G2，假設(shè)G1和G2的頂點(diǎn)數(shù)分別為n1和n2，顯然。與假設(shè)矛盾。所以G連通。3、（14分）（1）當(dāng)n=11時(shí)，邊數(shù)條，因而必有或的邊數(shù)大于等于28，不妨設(shè)G的邊數(shù)，設(shè)G有k個(gè)連通分支，則G中必有回路。（否則G為k棵樹(shù)構(gòu)成的森林，每棵樹(shù)的頂點(diǎn)數(shù)為ni，邊數(shù)mi，則,矛盾）下面用反證法證明G為非平面圖。假設(shè)G為平面圖，由于G中有回路且G為簡(jiǎn)單圖，因而回路長(zhǎng)大于等于3。于是G的每個(gè)面至少由g()條邊圍成，由點(diǎn)、邊、面數(shù)的關(guān)系，得：而矛盾，所以G為非平面圖。（2）當(dāng)n>11時(shí)，考慮G的具有11個(gè)頂點(diǎn)的子圖，則或必為非平面圖。如果為非平面圖，則為非平面圖。如果為非平面圖，則為非平面圖。（15分）1）[{0，1}，+，·]是環(huán)①[{0，1}，+]是交換群乘：由“+”運(yùn)算表知其封閉性。由于運(yùn)算表的對(duì)稱(chēng)性知：+運(yùn)算可交換。群：（0+0）+0=0+（0+0）=0；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0……結(jié)合律成立。 幺：幺元為0。 逆：0，1逆元均為其本身。所以，<{0，1}，+>是Abel群。②<{0，1}，·>是半群乘：由“·”運(yùn)算表知封閉群：(0·0)·0=0·（0·0）=0；（0·0）·1=0·（0·1）=1；（0·1）·0=0·（1·0）=1；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0；…③·對(duì)+的分配律對(duì)Ⅰ0·（x+y）=0=0+0=(0·x)+(0·y)Ⅱ1·（x+y）當(dāng)x=y(x+y)=0則當(dāng)（）則所以均有同理可證：所以·對(duì)+是可分配的。由①②③得，<{0，1}，+，·>是環(huán)。（2）<{0，1}，+，·>是域因?yàn)?lt;{0，1}，+，·>是有限環(huán)，故只需證明是整環(huán)即可。①乘交環(huán)：由乘法運(yùn)算表的對(duì)稱(chēng)性知，乘法可交換。②含幺環(huán)：乘法的幺元是1③無(wú)零因子：1·1=1≠0因此[{0，1}，+，·]是整環(huán)，故它是域。樹(shù)的應(yīng)用20%1、（10分）解：用庫(kù)斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹(shù)。算法略。結(jié)果如圖：樹(shù)權(quán)C(T)=23+1+4+9+3+17=57即為總造價(jià)五、（10分）由二叉樹(shù)知H、A、P、Y、N、E、W、R對(duì)應(yīng)的編碼分別為000、001、010、011、100、101、110、111。顯然{000，001，010，011，100，101，110，111}為前綴碼。英文短語(yǔ)HAPPYNEWYEAR的編碼信息為000001010010011100101001001101001111六、5%MaxMin+可結(jié)合性YYY可交換性YYY存在幺元NNY存在零元NNN試卷九試題與答案填空30%（每空3分）選擇合適的論域和謂詞表達(dá)集合A=“直角坐標(biāo)系中，單位元（不包括單位圓周）的點(diǎn)集”則A=。集合A={,{}}的冪集P(A)=。設(shè)A={1，2，3，4}，A上二元關(guān)系R={<1，2>，<2，1>，<2，3>，<3，4>}畫(huà)出R的關(guān)系圖。設(shè)A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},則=。=。設(shè)|A|=3，則A上有個(gè)二元關(guān)系。A={1，2，3}上關(guān)系R=時(shí)，R既是對(duì)稱(chēng)的又是反對(duì)稱(chēng)的。偏序集的哈斯圖為，則=。設(shè)|X|=n，|Y|=m則（1）從X到Y(jié)有個(gè)不同的函數(shù)。（2）當(dāng)n,m滿(mǎn)足時(shí)，存在雙射有個(gè)不同的雙射。是有理數(shù)的真值為。Q：我將去上海，R：我有時(shí)間，公式的自然語(yǔ)言為。公式的主合取范式是。若是集合A的一個(gè)分劃，則它應(yīng)滿(mǎn)足。選擇20%（每小題2分）設(shè)全集為I，下列相等的集合是（）。A、；B、；C、；D、。設(shè)S={N，Q，R}，下列命題正確的是（）。A、；B、；C、；D、。設(shè)C={{a},,{a,b}}，則分別為（）。A、C和{a,b}；B、{a,b}與；C、{a,b}與{a,b}；D、C與C下列語(yǔ)句不是命題的有（）。x=13；B、離散數(shù)學(xué)是計(jì)算機(jī)系的一門(mén)必修課；C、雞有三只腳；D、太陽(yáng)系以外的星球上有生物；E、你打算考碩士研究生嗎？的合取范式為（）。A、；B、；C、D、。設(shè)|A|=n，則A上有（）二元關(guān)系。A、2n；B、n2；C、；D、nn；E、。設(shè)r為集合A上的相容關(guān)系，其簡(jiǎn)化關(guān)系圖（如圖），則[I]r產(chǎn)生的最大相容類(lèi)為（）；A、；B、；C、；D、[II]A的完全覆蓋為（）。A、；B、；C、；D、。集合A={1，2，3，4}上的偏序關(guān)系圖為則它的哈斯圖為（）。下列關(guān)系中能構(gòu)成函數(shù)的是（）。A、；B、；C、；D、。10、N是自然數(shù)集，定義（即x除以3的余數(shù)），則f是（）。A、滿(mǎn)射不是單射；B、單射不是滿(mǎn)射；C、雙射；D、不是單射也不是滿(mǎn)射。簡(jiǎn)答題15%1、(10分)設(shè)S={1,2,3,4,6,8,12,24}，“”為S上整除關(guān)系，問(wèn)：（1）偏序集的Hass圖如何？（2）偏序集的極小元、最小元、極大元、最大元是什么?2、（5分）設(shè)解釋R如下：DR是實(shí)數(shù)集，DR中特定元素a=0，DR中特定函數(shù)，特定謂詞，問(wèn)公式的涵義如何？真值如何？邏輯推理10%或者邏輯難學(xué)，或者有少數(shù)學(xué)生不喜歡它；如果數(shù)學(xué)容易學(xué)，那么邏輯并不難學(xué)。因此，如果許多學(xué)生喜歡邏輯，那么數(shù)學(xué)并不難學(xué)。五、10%設(shè)X={1,2,3,4,5}，X上的關(guān)系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}，用Warshall方法，求R的傳遞閉包t(R)。六、證明15%每一有限全序集必是良序集。（7分）設(shè)是復(fù)合函數(shù)，如果滿(mǎn)射，則也是滿(mǎn)射。（8分）答案填空20%（每小題2分）1、；2、；3、見(jiàn)右圖；4、{<1,2>,<2,4>,<3,3>,<1，3>，<2,4>,<4,2>}、{<1,4>,<2,2>}；5、29；6、{<1,1>,<2,2>,<3,3>；7、{<a,b>,<a,d>,<a,e>,<b,d>,<b,e>,<a,c>,<a,f>,<a,g>,<c,f>,<c,g>}；8、mn、n=m、n!；9、假；10、我將去上海當(dāng)且僅當(dāng)我有空；11、；12、。選擇20%（每小題2分）題目12345678910答案A、DCBA、EB、DCB、D；CABD簡(jiǎn)答題15%1、（10分）（1）≤={<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>，<2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>}covS={<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,8>,<4,12>,<6,12>,<8,24>,<12,24>}Hass圖為（2）極小元、最小元是1，極大元、最大元是24。2、（5分）解：公式A涵義為：對(duì)任意的實(shí)數(shù)x,y,z，如果x<y則(x-z)<(y-z)A的真值為：真（T）。邏輯推理10%解：設(shè)P：邏輯難學(xué)；Q：有少數(shù)學(xué)生不喜歡邏輯學(xué)；R：數(shù)學(xué)容易學(xué)符號(hào)化：證：① P② T①E③ P④ T②③I⑤ T④E（10分）解： 1時(shí)，[1,1]=1,A=2時(shí)，A[1,2]=A[4,2]=1A=3時(shí)，A的第三列全為0，故A不變4時(shí)A[1,4]=A[2,4]=A[4,4]=1A=5時(shí)，A的第五行全為0，故A不變。所以t(R)={<1,1>,<1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>}。證明15%1、（7分）證明：設(shè)，全序集。若不是良序集，那么必有一子集，在B中不存在最小元素，由于B是一有限集合，故一定可找出兩元素x,y是無(wú)關(guān)的，由于是全序集。所以x,y必有關(guān)系，矛盾。故必是良序集。2、（8分）證明：設(shè)，由于滿(mǎn)射，故必有使得，由復(fù)合函數(shù)定義知，存在使得，又因?yàn)間是函數(shù)，必對(duì)任，必使，任每個(gè)z在g作用下都是Y中元素的一個(gè)映象，由Z的任意性，所以g是滿(mǎn)射。試卷十試題與答案填空10%（每小題2分）若P，Q為二命題，真值為1，當(dāng)且僅當(dāng)。對(duì)公式中自由變?cè)M(jìn)行代入的公式為。的前束范式為。設(shè)x是謂詞合式公式A的一個(gè)客體變?cè)珹的論域?yàn)镈，A（x）關(guān)于y的自由的，則被稱(chēng)為全稱(chēng)量詞消去規(guī)則，記為US。與非門(mén)的邏輯網(wǎng)絡(luò)為。選擇30%（每小題3分）下列各符號(hào)串，不是合式公式的有（）。A、；B、；C、；D、。下列語(yǔ)句是命題的有（）。A、2是素?cái)?shù)；B、x+5>6；C、地球外的星球上也有人；D、這朵花多好看呀！。下列公式是重言式的有（）。A、；B、；C、；D、下列問(wèn)題成立的有（）。若，則；B、若，則；C、若，則；D、若，則。命題邏輯演繹的CP規(guī)則為（）。在推演過(guò)程中可隨便使用前提；B、在推演過(guò)程中可隨便使用前面演繹出的某些公式的邏輯結(jié)果；C、如果要演繹出的公式為形式，那么將B作為前提，設(shè)法演繹出C；D、設(shè)是含公式A的命題公式，，則可用B替換中的A。命題“有的人喜歡所有的花”的邏輯符號(hào)化為（）。設(shè)D：全總個(gè)體域，F(xiàn)（x）：x是花，M(x)：x是人，H(x,y)：x喜歡yA、；B、；C、；D、。公式換名（）。A、；B、；C、；D、。給定公式，當(dāng)D={a,b}時(shí)，解釋?zhuān)ǎ┦乖摴秸嬷禐?。A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=1下面蘊(yùn)涵關(guān)系成立的是（）。A、；B、；C、；D、。10、下列推理步驟錯(cuò)在（）。① P② US①③ ES②④ UG③⑤ EG④A、①→②；B、②→③；C、③→④；D、④→⑤。邏輯判斷28%1、（8分）下列命題相容嗎？2、（10分）用范式方法判斷公式是否等價(jià)。3、（10分）下列前提下結(jié)論是否有效？今天或者天晴或者下雨。如果天晴，我去看電影；若我去看電影，我就不看書(shū)。故我在看書(shū)時(shí)，說(shuō)明今天下雨。計(jì)算12%1、（5分）給定3個(gè)命題：P：北京比天津人口多；Q：2大于1；R：15是素?cái)?shù)。求復(fù)合命題：的真值。2、（7分）給定解釋I：D={2，3}，L（x,y）為L(zhǎng)(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,求謂詞合式公式的真值。邏輯推理20%1、（10分）所有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)。2、（10分）符號(hào)化語(yǔ)句：“有些病人相信所有的醫(yī)生，但是病人都不相信騙子，所以醫(yī)生都不是騙子”。并推證其結(jié)論。答案填空15%（每小題3分）1、P，Q的真值相同；2、；3、；4、；5、。選擇30%（每小題3分）題目12345678910答案B、CA、CBC、DCDAB、CB、DC邏輯判斷28%1、（8分）① P②A P③B T①②I④ P⑤ T④E⑥ T⑤I⑦F T③⑥I所以不相容。2、（10分）所以?xún)墒降葍r(jià)。3、設(shè)P：今天天晴，Q：今天下雨，R：我不看書(shū)，S：我看電影符號(hào)化為：① P② P③ T①②I④ T③I⑤ P⑥ T⑤E⑦ T④⑥I結(jié)論有效。計(jì)算12%1、（5分）解：P，Q是真命題，R是假命題。2、（7分）邏輯推理20%1、（10分）解：設(shè)R(x)：x是實(shí)數(shù)，Q(x)：x是有理數(shù)，I(x)：x是整數(shù)符號(hào)化：前提：，結(jié)論：① P② ES①③ P④ US③⑤ T②I⑥ T④⑤I⑦ T②I⑧ T⑥⑦I⑨ EG⑧2、解：F(x)：x是病人，G(x)：x是醫(yī)生，H(x)：x是騙子，L(x,y)：x相信y符號(hào)化：前提：結(jié)論：⑴ P⑵ ES⑴⑶ T⑵I⑷ T⑵I⑸ P⑹ US⑸⑺ T⑶⑹I⑻ T⑺E⑼ US⑷⑽ US⑻⑾ T⑼⑽I⑿ UG⑾卷十一試題與答案填空20%（每小題2分）1、稱(chēng)為命題。2、命題P→Q的真值為0，當(dāng)且僅當(dāng)。3、一個(gè)命題含有4個(gè)原子命題，則對(duì)其所有可能賦值有種。4、所有小項(xiàng)的析取式為。5、令P（x）：x是質(zhì)數(shù)，E（x）：x是偶數(shù)，Q（x）：x是奇數(shù)，D（x，y）：x除盡y.則的漢語(yǔ)翻譯為。6、設(shè)S={a，b,c}則S6的集合表示為。7、P（P()）=。8、=。9、設(shè)R為集合A上的關(guān)系，則t（R）=。10、若R是集合A上的偏序關(guān)系，則R滿(mǎn)足。選擇20%（每小題2分）下列命題正確的有（）。若是滿(mǎn)射，則是滿(mǎn)射；B、若是滿(mǎn)射，則都是滿(mǎn)射；C、若是單射，則都是單射；D、若單射，則是單射。設(shè)f，g是函數(shù)，當(dāng)（）時(shí)，f=g。A、；B、；C、；D、。下列關(guān)系，（）能構(gòu)成函數(shù)。A、；B、；C、；D、。下列函數(shù)（）滿(mǎn)射；（）單射；（）雙射（）；一般函數(shù)（）。A、；B、（除以3的余數(shù)）；C、；D、。集合A={1，2，3，4}上的偏序關(guān)系為，則它的Hass圖為（）。設(shè)集合A={1，2，3，4，5}上偏序關(guān)系的Hass圖為則子集B={2，3，4}的最大元（）；最小元（）；極大元（）；極小元（）；上界（）；上確界（）；下界（）；下確界（）。無(wú)，4，2、3，4，1，1，4，4；B、無(wú)，4、5，2、3，4、5，1，1，4，4；C、無(wú)，4，2、3，4、5，1，1，4，4；D、無(wú)，4，2、3，4，1，1，4，無(wú)。設(shè)R，S是集合A上的關(guān)系，則下列（）斷言是正確的。自反的，則是自反的；B、若對(duì)稱(chēng)的，則是對(duì)稱(chēng)的；C、若傳遞的，則是傳遞的；D、若反對(duì)稱(chēng)的，則是反對(duì)稱(chēng)的設(shè)X為集合，|X|=n，在X上有（）種不同的關(guān)系。A、n2；B、2n；C、；D、。下列推導(dǎo)錯(cuò)在（）。① P② US①③ ES②④ UG③A、②；B、③；C、④；D、無(wú)。10、“沒(méi)有不犯錯(cuò)誤的人”的邏輯符號(hào)化為（）。設(shè)H（x）：x是人，P（x）：x犯錯(cuò)誤。A、；B、；C、；D、。命題演繹28%1、（10分）用反證法證明。2、（8分）用CP規(guī)則證明。3、（10分）演繹推理：所有的有理數(shù)都是實(shí)數(shù)，所有的無(wú)理數(shù)也是實(shí)數(shù)，虛數(shù)不是實(shí)數(shù)。因此，虛數(shù)既不是有理數(shù)，也不是無(wú)理數(shù)。8%將化為與其等價(jià)的前束范式。五、8%A={a,b,c,d}，R={<a,b>,<b,c>,<b,d>,<c,b>}為A上的關(guān)系，利用矩陣乘法求R的傳遞閉包，并畫(huà)出t（R）的關(guān)系圖。六、證明16%（8分）設(shè)A={1，2，3，4}，在P（A）上規(guī)定二元關(guān)系如下：P（A）證明R是P（A）上的等價(jià)關(guān)系并寫(xiě)出商集P（A）/R。（8分）設(shè)f是A到A的滿(mǎn)射，且，證明f=IA。答案填空20%（每小題2分）能夠斷真假的陣述句；2、P的真值為1，Q的真值為0；3、24=16；4、永真式；5、任意兩數(shù)x、y,如果x是偶數(shù)且能除盡y，則y一定是偶數(shù)；6、S110={a,b}；7、；8、；9、；10、自反性、反對(duì)稱(chēng)性、傳遞性二、選擇20%（每小題2分）題目12345678910答案A、DBC、DC、D；A、D；D；BCAADCB、D三、命題演繹28%1、（10分）證明：⑴ P（附加前提）⑵ T⑴E⑶ P⑷ T⑶E⑸ P⑹ T⑷⑸E⑺ T⑹E⑻ T⑺I⑼ T⑵⑻I⑽ P⑾ T⑽E⑿ T⑾E⒀ T⑼⑿I2、（8分）① P（附加前提）② P③ T①②I④ P⑤ T③④I⑥ T⑤E⑦ CP3、證明：設(shè)Q（x）：x是有理數(shù)，R(x)：x是實(shí)數(shù)，N(x)：x是無(wú)理數(shù)，C(x)：x是虛數(shù)。前提：結(jié)論：⑴ P⑵ US⑴⑶ P⑷ US⑶⑸ P⑹ US⑸⑺ T⑹E⑻ T⑵⑺I⑼ T⑷⑺I⑽ T⑻⑼I⑾ T⑽E⑿ UG⑾四、8%解：五、8%解：所以t（R）={<a,b>,<a,c>,<a,d>,<b,b>,<b,c>,<b,d>,<c,b>,<c,c>,<c,d>}關(guān)系圖為六、證明16%1、（8分）證明：⑴P（A），由于，所以，即R自反的。⑵P（A），若，則，，R是對(duì)稱(chēng)的。⑶P（A），若：，即：所以R是傳遞的。由⑴⑵⑶知，R是等價(jià)關(guān)系。P（A）/R={[]R，[{1}]R，[{1，2}]R，[{1，2，3}]R，[{1，2，3，4}]R}2、（8分）證明：因?yàn)閒是滿(mǎn)射，所以，存在使得，又因?yàn)閒是函數(shù)，所以即由所以，又，所以由a的任意性知：f=IA。卷十二試題與答案填空20%（每空2分）設(shè)集合A={1，2，3，4，5，6，7，8，9，10}，定義A上的二元關(guān)系“≤”為x≤y=x|y,則=。設(shè)，定義A上的二元運(yùn)算為普通乘法、除法和加法，則代數(shù)系統(tǒng)<A,*>中運(yùn)算*關(guān)于運(yùn)算具有封閉性。設(shè)集合S={α，β，γ，δ，ζ}，S上的運(yùn)算*定義為*αβγδζααβγδζββδαγδγγαβαβδδαγδγζζδαγζ則代數(shù)系統(tǒng)<S，*>中幺元是，β左逆元是，無(wú)左逆元的元素是。在群坯、半群、獨(dú)異點(diǎn)、群中滿(mǎn)足消去律。設(shè)<G,*>是由元素生成的循環(huán)群，且|G|=n，則G=。拉格朗日定理說(shuō)明若<H,*>是群<G,*>的子群，則可建立G中的等價(jià)關(guān)系R=。若|G|=n,|H|=m則m和n關(guān)系為。設(shè)f是由群<G,☆>到群<,*>的同態(tài)映射，是中的幺元，則f的同態(tài)核Ker(f)=。選擇20%（每小題2分）1、設(shè)f是由群<G,☆>到群<,*>的同態(tài)映射，則ker(f)是（）。A、的子群；B、G的子群；C、包含；D、包含G。2、設(shè)<A，+，·>是環(huán)，，a·b的關(guān)于“+”的逆元是（）。A、(-a)·(-b)；B、(-a)·b；C、a·(-b)；D、a·b。3、設(shè)<A，+，·>是一代數(shù)系統(tǒng)且<A，+>是Abel群，如果還滿(mǎn)足（）<A，+，·>是域。A、<A，·>是獨(dú)異點(diǎn)且·對(duì)+可分配；B、<A-{}，·>是獨(dú)異點(diǎn)，無(wú)零因子且·對(duì)+可分配；C、<A-{}，·>是Abel群且無(wú)零因子；D、<A-{}，·>是Abel且·對(duì)+可分配。4、設(shè)<A，+，·>是一代數(shù)系統(tǒng)，+、·為普通加法和乘法運(yùn)算，當(dāng)A為（）時(shí)，<A，+，·>是域。A、；B、；C、；D、。5、設(shè)<A,>是一個(gè)格，由格誘導(dǎo)的代數(shù)系統(tǒng)為，則（）成立。A、；B、；C、；D、。6、設(shè)<A,>是偏序集，“”定義為：，則當(dāng)A=（）時(shí)，<A,>是格。A、{1,2,3,4,6,12}；B、{1,2,3,4,6,8,12,14}；C、{1,2,3,…，12}；D、{1,2,3,4}。7、設(shè)是由格<A,>誘導(dǎo)的代數(shù)系統(tǒng)，若對(duì)，當(dāng)時(shí)，有（）<A,>是模格。A、；B、；C、；D、。8、在（）中，補(bǔ)元是唯一的。A、有界格；B、有補(bǔ)格；C、分配格；D、有補(bǔ)分配格。9、在布爾代數(shù)中，當(dāng)且僅當(dāng)（）。A、；B、；C、；D、。10、設(shè)是布爾代數(shù)，f是從An到A的函數(shù)，則（）。f是布爾代數(shù)；B、f能表示成析取范式，也能表示成合取范式；C、若A={0，1}，則f一定能表示成析取范式，也能表示成合取范式；D、若f是布爾函數(shù)，它一定能表示成析（合）取范式。三、8%設(shè)A={1，2}，A上所有函數(shù)的集合記為AA,是函數(shù)的復(fù)合運(yùn)算，試給出AA上運(yùn)算的運(yùn)算表，并指出AA中是否有幺元，哪些元素有逆元。四、證明42%設(shè)<R,*>是一個(gè)代數(shù)系統(tǒng)，*是R上二元運(yùn)算，，則0是幺元且<R,*>是獨(dú)異點(diǎn)。（8分）設(shè)<G,*>是n階循環(huán)群，G=(a)，設(shè)b=ak，則元素b的階為，這里d=GCD(n,k)。（10分）證明如果f是由<A,☆>到<B,*>的同態(tài)映射，g是由<B,*>到<C,△>的同態(tài)映射，則是由<A,☆>到<C,△>的同態(tài)映射。（6分）設(shè)<A，+，·>是一個(gè)含幺環(huán)，且任意都有a·a=a，若|A|≥3則<A，+，·>不可能是整環(huán)。（8分）K={1,2,5,10,11,22,55,110}是110的所有整因子的集合，證明：具有全上界110和全下界1的代數(shù)系統(tǒng)<K,LCM,GCD,ˊ>是一個(gè)布爾代數(shù)。（）。（10分）五、布爾表達(dá)式10%設(shè)是布爾代數(shù)上的一個(gè)布爾表達(dá)式，試寫(xiě)出其析取范式和合取范式。（10分）答案：一、填空20%（每空2分）1、LCM（x,y）；2、乘法；3、α、δ，γ、ζ；4、群；5、；6、、；7、二、選擇20%（每小題2分）題目12345678910答案BB，CDABAADCC，D三、8%解：因?yàn)閨A|=2，所以A上共有22=4個(gè)不同函數(shù)。令，其中：為AA中的幺元，和有逆元。四、證明42%1、（8分）證明：[幺]，即[乘]，由于+，·在R封閉。所以即*在R上封閉。[群]因此，〈R，*〉是獨(dú)異點(diǎn)。2、（10分）證明：（1）（2）若b的階不為n1，則b階m<n1，且有，則有，即，即，有因子，這與矛盾。由（1）、（2）知，元素b的階為3、（6分）所以是由<A,☆>到<c,△>的同態(tài)映射。4、（8分）證明：反證法：如果<A，+，·>是整環(huán)，且|A|≥3，則且即有且，這與整環(huán)中無(wú)零因子矛盾。所以<A，+，·>不可能是整環(huán)。5、（10分）代數(shù)系統(tǒng)<K,LCM,GCD,ˊ>是由格<K,|>誘導(dǎo)的，其Hasst圖為Hass圖中不存在與五元素格和同構(gòu)的子格。所以<K,|>格是分配格。（2）即任元素都有補(bǔ)元，所以<K,|>有補(bǔ)格。<K,LCM,GCD,’>是布爾代數(shù)。五、布爾表達(dá)式10%解：函數(shù)表為：00000011010101111001101111011110析取范式：合取范式：試卷十三試題與答案填空10%（每小題2分）1、，*表示求兩數(shù)的最小公倍數(shù)的運(yùn)算（Z表示整數(shù)集合），對(duì)于*運(yùn)算的幺元是，零元是。2、代數(shù)系統(tǒng)<A,*>中，|A|>1，如果分別為<A,*>的幺元和零元，則的關(guān)系為。3、設(shè)<G,*>是一個(gè)群，<G,