離散數(shù)學(xué)南昌大學(xué)軟件學(xué)院試卷

/2007～2008學(xué)年第一學(xué)期《離散數(shù)學(xué)》期末試卷（B）年級專業(yè) 班級學(xué)號 姓名____________題號一二三四總分得分適用年級專業(yè)：2006級軟件工程專業(yè)試卷說明：閉卷考試，考試時(shí)間120分鐘一．判斷題（共10小題，每題1分，共10分）在各題末尾的括號內(nèi)畫表示正確，畫表示錯(cuò)誤：1．設(shè)p、q為任意命題公式，則(pq)pp()2．x(F(y)G(x))F(y)xG(x)。()3．初級回路一定是簡單回路。()4．自然映射是雙射。()5．對于給定的集合及其上的二元運(yùn)算，可逆元素的逆元是唯一的。()6．群的運(yùn)算是可交換的。()7．自然數(shù)集關(guān)于數(shù)的加法和乘法<N，+，>構(gòu)成環(huán)。()8．若無向連通圖G中有橋，則G的點(diǎn)連通度和邊連通度皆為1。()9．設(shè)A={a,b,c},則A上的關(guān)系R={<a,b>,<a,c>}是傳遞的。()10．設(shè)A、B、C為任意集合，則A(BC)=(AB)C。()二、填空題（共10題，每題3分，共30分）11．設(shè)p：天氣熱。q：他去游泳。則命題“只有天氣熱，他才去游泳”可符號化為。12．設(shè)M(x)：x是人。S(x)：x到過月球。則命題“有人到過月球”可符號化為。13．pq的主合取范式是。14．完全二部圖Kr,s（r<s）的邊連通度等于。15．設(shè)A={a,b}，,則A上共有個(gè)不同的偏序關(guān)系。16．模6加群<Z6，>中，4是階元。17．設(shè)A={1,2,3,4,5}上的關(guān)系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>}，則R的傳遞閉包t(R)=。.18．已知有向圖D的度數(shù)列為(2,3,2,3)，出度列為(1,2,1,1)，則有向圖D的入度列為。19．n階無向簡單連通圖G的生成樹有條邊。20．7階圈的點(diǎn)色數(shù)是。三、運(yùn)算題（共5小題，每小題8分，共40分）21．求xF(x)yG(x,y)的前束范式。22．已知無向圖G有11條邊，2度和3度頂點(diǎn)各兩個(gè)，其余為4度頂點(diǎn)，求G的頂點(diǎn)數(shù)。23．設(shè)A={a,b,c,d,e,f}，R=IA{<a,b>,<b,a>}，則R是A上的等價(jià)關(guān)系。求等價(jià)類[a]R、[c]R及商集A/R。24．求圖示帶權(quán)圖中的最小生成樹，并計(jì)算最小生成樹的權(quán)。25．設(shè)R*為正實(shí)數(shù)集，代數(shù)系統(tǒng)<R*,+>、<R*,·>、<R*,/>中的運(yùn)算依次為普通加法、乘法和除法運(yùn)算。試確定這三個(gè)代數(shù)系統(tǒng)是否為群？是群者，求其單位元及每個(gè)元素的逆元。四、證明題（共3小題，共20分）26（8分）在自然推理系統(tǒng)P中構(gòu)造下述推理的證明：前題：p(qr)，sq，ps結(jié)論：r27（6分）設(shè)<G,>是群，H={a|aGgG，ag=ga},則<H,>是G的子群。28．（6分）設(shè)G是n(3)階m條邊、r個(gè)面的極大平面圖，則r=2n-4。2007-2008學(xué)年第一學(xué)期《離散數(shù)學(xué)》期末試卷（B）答案適用年級專業(yè)：2006級軟件工程專業(yè)試卷說明：閉卷考試，考試時(shí)間120分鐘一．判斷題（共10小題，每題1分，共10分）在各題末尾的括號內(nèi)畫表示正確，畫表示錯(cuò)誤：1．()2．()3．()4．()5．()6．()7．()8．()9．()10．()二、填空題（共10題，每題3分，共30分）11．qp12．x(M(x)S(x))13．(pq)(pq)14．r15．316．317．.R18．（1,1,1,2）19．n-120．3三、運(yùn)算題（共5小題，每小題8分，共40分）21．解：xF(x)yG(x,y)xF(x)yG(w,y)x(F(x)yG(w,y))xy(F(x)G(w,y))22．解：設(shè)圖G有n個(gè)頂點(diǎn)m條邊，則2m=2(2+3)+4(n-4)，即22=10+4(n-4)解之得n=7。23．解：[a]R={a,b}，[c]R={c}，[d]R=fqyo0vk，[e]R={e}，[f]R={f}，A/R={{a,b},{c},isiralm,{e},{f}}24．解：最小生成樹T如圖中紅線所示，W(T)=1225．解：僅<R*,·>是群。其單位元為1。任意xR*，其逆元為1/x。四、證明題（共3小題，共20分）26證明：①ps前提引入②p①，化簡③p(qr)前提引入④qr②③，假言推理⑤s①，化簡⑥sq前提引入⑦q⑤⑥，假言推理=8\*GB3⑧r④⑦，析取三段論27（6分）證：設(shè)e是G的單位元，gG,eg=ge，所以eH,故H非空。（1）a,bH,gG，有ag=ga,bg=gb,那么(ab)g=a(bg)=a(gb)=(ag)b=(ga)b=g(ab)所以abH。（2）aH,gG，有ag=ga，a-1G。a-1g=a-1ge=a-1gaa-1=a-1(ga)a-1=a-1(ag)a-1=(a-1a)ga-1