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

/2007～2008學年第一學期《離散數(shù)學》期末試卷（B）年級專業(yè) 班級學號 姓名____________題號一二三四總分得分適用年級專業(yè)：2006級軟件工程專業(yè)試卷說明：閉卷考試，考試時間120分鐘一．判斷題（共10小題，每題1分，共10分）在各題末尾的括號內畫表示正確，畫表示錯誤：1．設p、q為任意命題公式，則(pq)pp()2．x(F(y)G(x))F(y)xG(x)。()3．初級回路一定是簡單回路。()4．自然映射是雙射。()5．對于給定的集合及其上的二元運算，可逆元素的逆元是唯一的。()6．群的運算是可交換的。()7．自然數(shù)集關于數(shù)的加法和乘法<N，+，>構成環(huán)。()8．若無向連通圖G中有橋，則G的點連通度和邊連通度皆為1。()9．設A={a,b,c},則A上的關系R={<a,b>,<a,c>}是傳遞的。()10．設A、B、C為任意集合，則A(BC)=(AB)C。()二、填空題（共10題，每題3分，共30分）11．設p：天氣熱。q：他去游泳。則命題“只有天氣熱，他才去游泳”可符號化為。12．設M(x)：x是人。S(x)：x到過月球。則命題“有人到過月球”可符號化為。13．pq的主合取范式是。14．完全二部圖Kr,s（r<s）的邊連通度等于。15．設A={a,b}，,則A上共有個不同的偏序關系。16．模6加群<Z6，>中，4是階元。17．設A={1,2,3,4,5}上的關系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階圈的點色數(shù)是。三、運算題（共5小題，每小題8分，共40分）21．求xF(x)yG(x,y)的前束范式。22．已知無向圖G有11條邊，2度和3度頂點各兩個，其余為4度頂點，求G的頂點數(shù)。23．設A={a,b,c,d,e,f}，R=IA{<a,b>,<b,a>}，則R是A上的等價關系。求等價類[a]R、[c]R及商集A/R。24．求圖示帶權圖中的最小生成樹，并計算最小生成樹的權。25．設R*為正實數(shù)集，代數(shù)系統(tǒng)<R*,+>、<R*,·>、<R*,/>中的運算依次為普通加法、乘法和除法運算。試確定這三個代數(shù)系統(tǒng)是否為群？是群者，求其單位元及每個元素的逆元。四、證明題（共3小題，共20分）26（8分）在自然推理系統(tǒng)P中構造下述推理的證明：前題：p(qr)，sq，ps結論：r27（6分）設<G,>是群，H={a|aGgG，ag=ga},則<H,>是G的子群。28．（6分）設G是n(3)階m條邊、r個面的極大平面圖，則r=2n-4。2007-2008學年第一學期《離散數(shù)學》期末試卷（B）答案適用年級專業(yè)：2006級軟件工程專業(yè)試卷說明：閉卷考試，考試時間120分鐘一．判斷題（共10小題，每題1分，共10分）在各題末尾的括號內畫表示正確，畫表示錯誤：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三、運算題（共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．解：設圖G有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=sase4au，[e]R={e}，[f]R={f}，A/R={{a,b},{c},y4ukym0,{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分）證：設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