《離散數(shù)學(xué)》考試題庫及答案

《離散數(shù)學(xué)》考試題庫及答案一、填空20%（每小題2分）1．設(shè)（N：自然數(shù)集，E+正偶數(shù)）則。2．A，B，C表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為ABCABC3．設(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)系，則下列說法正確的是（）A．若R，S是自反的，則是自反的；B．若R，S是反自反的，則是反自反的；C．若R，S是對稱的，則是對稱的；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}}06、設(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長度為3的通路有（）條。A．0； B．1； C．2； D．3。9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（）10、在一棵樹中有7片樹葉，3個(gè)3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)則該樹有（）個(gè)4度結(jié)點(diǎn)。A．1； B．2； C．3； D．4。三、證明26% R是集合X上的一個(gè)自反關(guān)系，求證：R是對稱和傳遞的，當(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ù)先算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。（９分）試卷一答案：一、填空20%（每小題2分）1、{0，1，2，3，4，6}；2、；3、1；4、；5、1；6、{<1,1>,<1,.3>,<2,2>,<2,4>}；7、{<a.b>,<a,c>,<a,d>,<b,d>,<c,d>}IA；8、9、a；a,b,c,d；a,d,c,d；10、c;二、選擇20%（每小題2分）題目12345678910答案CDB、CCADCADBA三、證明26%證：“”若由R對稱性知，由R傳遞性得“”若，有任意，因若所以R是對稱的。若，則即R是傳遞的。證，有，又★★★<C,★>是<G1,★>的子群。證：①設(shè)G有r個(gè)面，則，即。而故即得。（8分）②彼得森圖為，這樣不成立，所以彼得森圖非平面圖。（3分）邏輯推演16%證明：① P（附加前提）② T①I③ P④ T②③I⑤ T④I⑥ T⑤I⑦ P⑧ T⑥⑦I⑨ CP2、證明① P（附加前提）② US①③ P④ US③⑤ T②④I⑥ UG⑤⑦ CP計(jì)算18%解：，， t(R)={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c.>,<b,d>,<c,d>}解：用庫斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：樹權(quán)C(T)=23+1+4+9+3+17=57即為總造價(jià)。試卷二試題與答案一、填空20%（每小題2分）P：你努力，Q：你失敗?！俺悄闩?，否則你將失敗”的翻y譯為；“雖然你努力了，但還是失敗了”的翻譯為。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上既不是對稱的又不是反對稱的關(guān)系R=；A上既是對稱的又是反對稱的關(guān)系R=。*abcabcabcbbcccb6、設(shè)代數(shù)系統(tǒng)<A，*>，其中A={a，b，c},則幺元是；是否有冪等性；是否有對稱性。7、4階群必是群或群。8、下面偏序格是分配格的是。9、n個(gè)結(jié)點(diǎn)的無向完全圖Kn的邊數(shù)為，歐拉圖的充要條件是。10、公式的根樹表示為。二、選擇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．自反性、對稱性、傳遞性；B．反自反性、反對稱性；C．反自反性、反對稱性、傳遞性；D．自反性。6、設(shè)為普通加法和乘法，則（）是域。A．B．C．D．=N。7、下面偏序集（）能構(gòu)成格。8、在如下的有向圖中，從V1到V4長度為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ù)對任意有，證明：若f是A到B的滿射，則g是從B到的單射。（10分）若無向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定連通。（8分）設(shè)G是具有n個(gè)結(jié)點(diǎ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)二叉樹。（7分）試卷二答案：填空20%（每小題2分）1、；2、T3、4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>}6、a；否；有7、Klein四元群；循環(huán)群8、B9、；圖中無奇度結(jié)點(diǎn)且連通10、選擇20%（每小題2分）題目12345678910答案B、DD；DDBDABBBB、C證明46%1、（9分）S自反的，由R自反，，S對稱的S傳遞的由（1）、（2）、（3）得；S是等價(jià)關(guān)系。2、11分證明：設(shè)P(x)：x是個(gè)舞蹈者；Q(x)：x很有風(fēng)度；S(x)：x是個(gè)學(xué)生；a：王華上述句子符號(hào)化為：前提：、結(jié)論：……3分① P② P③ US②④ T①I⑤ T③④I⑥ T①I⑦ T⑤⑥I⑧ EG⑦ ……11分３、１0分證明：。4、8分證明：設(shè)G中兩奇數(shù)度結(jié)點(diǎn)分別為u和v，若u，v不連通，則G至少有兩個(gè)連通分支G1、G2，使得u和v分別屬于G1和G2，于是G1和G2中各含有1個(gè)奇數(shù)度結(jié)點(diǎn)，這與圖論基本定理矛盾，因而u，v一定連通。5、8分證明：證G中任何兩結(jié)點(diǎn)之和不小于n。反證法：若存在兩結(jié)點(diǎn)u，v不相鄰且,令，則G-V1是具有n-2個(gè)結(jié)點(diǎn)的簡單圖，它的邊數(shù),可得，這與G1=G-V1為n-2個(gè)結(jié)點(diǎn)為簡單圖的題設(shè)矛盾，因而G中任何兩個(gè)相鄰的結(jié)點(diǎn)度數(shù)和不少于n。所以G為Hamilton圖.計(jì)算14%d7分解：子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6>{[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]}{[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]}{[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]}Z6的左陪集：Z6。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。則謂詞的自然語言是。謂詞的前束范式為。選擇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⑤推理過程中錯(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ù)（）是單射而非滿射。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ì)。自反、對稱、傳遞；B、什么性質(zhì)也沒有；C、反自反、反對稱、傳遞；D、自反、對稱、反對稱、傳遞。設(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、可滿足式；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、寫出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、反對稱性、反自反性；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③ P④ T②③I⑤ T④I⑥ T⑤I⑦ P⑧ T⑥⑦I⑨ CP2、① P（附加前提）② T①E③ ES②④ P⑤ US④⑥ T③⑤I⑦ EG⑥⑧ CP14%證明：自反性：對稱性：傳遞性：即由（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)。命題“對于任意給定的正實(shí)數(shù)，都存在比它大的實(shí)數(shù)”令F(x)：x為實(shí)數(shù)，則命題的邏輯謂詞公式為。謂詞合式公式的前束范式為。將量詞轄域中出現(xiàn)的和指導(dǎo)變元交換為另一變元符號(hào)，公式其余的部分不變，這種方法稱為換名規(guī)則。設(shè)x是謂詞合式公式A的一個(gè)客體變元，A的論域?yàn)镈，A(x)關(guān)于y是自由的，則被稱為存在量詞消去規(guī)則，記為ES。選擇25%（每小題2.5分）下列語句是命題的有（）。明年中秋節(jié)的晚上是晴天；B、；C、當(dāng)且僅當(dāng)x和y都大于0；D、我正在說謊。下列各命題中真值為真的命題有（）。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、稱為B的前件；B、稱B為的有效結(jié)論C、當(dāng)且僅當(dāng)；D、當(dāng)且僅當(dāng)。A，B為二合式公式，且，則（）。A、為重言式；B、；C、；D、；E、為重言式?！叭丝偸且赖摹敝^詞公式表示為（）。（論域?yàn)槿倐€(gè)體域）