南昌大學(xué)《離散數(shù)學(xué)》考試試卷

1、- -南昌大學(xué)科技學(xué)院20112012學(xué)年第一學(xué)期期末考試試卷試卷編號(hào)：(B)卷課程編號(hào)：課程名稱：離散數(shù)學(xué)考試形式:閉卷適用班級(jí)：姓名：學(xué)號(hào)：班級(jí)：學(xué)院：專業(yè)：考試日期：題號(hào)-一一-二二三四五六七八九十總分累分人題名得分考生注意事項(xiàng)：1.本試卷共旦頁(yè)，請(qǐng)查看試卷中是否有缺頁(yè)或破損。如有立即舉手報(bào)告以便更換。2.考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。一、填空題(每小題3分，本題共15分)1設(shè)R是集合A上的相容關(guān)系，則R所具有的關(guān)系的二個(gè)特性是設(shè)命題公式G=(PTQ),(QTR)T(PTR)，則公式G的類型為。設(shè)A,B是集合，且A=0,1,2,B=a,b，

2、則A到B上的全域關(guān)系A(chǔ)xB=有限圖G是樹的一個(gè)等價(jià)定義是：.設(shè)K6是有6個(gè)點(diǎn)的完全圖，則K6有條邊。二、選擇題(每小題3分，本題共15分)1在由3個(gè)元素組成的集合上，它的冪集有()個(gè)元素。(A)3(B)8(C)9(D)5122設(shè)R為實(shí)數(shù)集合，映射：RTR,(x)=2x+h則Q是().(A)入射而非滿射(B)滿射而非入射(C)雙射(D)既不是入射也不是滿射.3設(shè)命題公式G=(P,Q),HQ,p，則G與H的關(guān)系是()。(A)GnH(B)HnG(C)G=H(D)以上都不是.4已知命題GP(QR)，則所有使G取真值為1的解釋是()。(A)(0,0,0),(0,0,1),(1,0,0);(B)(0,1,

3、0),(1,0,1),(1,1,0);(C)(1,0,0),(1,0,1),(1,1,0);(D)(1,1,0),(1,0,1),(1,1,1).5設(shè)I是如下一個(gè)解釋：D=a,b，卩(aa)卩b)卩(ba)卩(bb)，則在解釋I1010下取真值的公式是().(A)3xVyP(x,y).(B)VxVyP(x,y).(C)VxP(x,x).(D)Vx3yP(x,y).三、計(jì)算題(共4*12分)設(shè)集合A=1,2,3，A上的關(guān)系R=(1,1),(1,2),(1,3),(2,2),(3,2),(3,3),畫出R的關(guān)系圖；寫出Rc的關(guān)系矩陣.求關(guān)系R的傳遞閉包t(R)。畫出下圖G的最小生成樹；將圖G中所有

4、邊的權(quán)值改成1得到的圖記為G，0求G的鄰接矩陣。3.求A=(pq)r的主析取范式和主合取范式.設(shè)一階邏輯公式G，(Vx)(Vy)(z)(p(x,z)p(y,z)(u)q(x,y,u).試將G化成與其等價(jià)的前束范式。四證明題(共22分)1、(本題10分)若XxX，YxY，則X二Y.2、(本題12分)甲、乙、丙、丁四人參加拳擊比賽，如果甲獲勝，則乙失敗；如果丙獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。所以如果丙獲勝，則丁不失敗。請(qǐng)用推理方法，證明有效結(jié)20042005第一學(xué)期考試卷離散數(shù)學(xué)課程閉卷課程類別：必修考試時(shí)間序號(hào)一一二三四五六七八九十總分得分評(píng)卷人、單項(xiàng)選擇題(本大題共10小題，每小題

5、2分，共20分)1.下列不是命題的是。A.7能被3整除.5是素?cái)?shù)當(dāng)且僅當(dāng)太陽(yáng)從西邊升起.x加7小于0.D.華東交通大學(xué)位于南昌北區(qū).設(shè)p:王平努力學(xué)習(xí)，q:王平取得好成績(jī)，命題“除非王平努力學(xué)習(xí)，否則他不能取得好成績(jī)”的符號(hào)化形式為。A.pqB.pqC.qpD.qp下面4個(gè)推理定律中，不正確的為。A.A=(AVB)(附加律)B(AVB)AA=B(析取三段論)C(AB)AA=B(假言推理)D(AB)AB=A(拒取式)設(shè)解釋I如下，個(gè)體域D=1,2,F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1在解釋I下,下列公式中真值為1的是。A.Vx,yF(x,y)B.,xVyF(x,y)C.V

6、xVyF(x,y)D.,x,yF(x,y)下列四個(gè)命題中哪一個(gè)為真？。- - -A.eB.$aC.$D.匸設(shè)S=a,b,c,d,R=va,a,vb,b,vd,d,則R的性質(zhì)是。A自反、對(duì)稱、傳遞的B.對(duì)稱、反對(duì)稱、傳遞的C自反、對(duì)稱、反對(duì)稱的D.只有對(duì)稱性設(shè)A=a,b,c,貝V下列是集合A的劃分的是。A.b,c,cBa,b,a,cC.a,b,cDa,b,c8設(shè)集合(2)a+b2a,b,Q)關(guān)于普通數(shù)的乘法，不正確的有。A.結(jié)合律成立B.有幺元C任意元素有逆元D.交換律成立設(shè)A是非空集合,P(A)是A的冪集，G是集合交運(yùn)算，則代數(shù)系統(tǒng)P(A),G的幺元是。AP(A)BCAD.E10下列四組數(shù)據(jù)中

7、，不能成為任何4階無(wú)向簡(jiǎn)單圖的度數(shù)序列的為。A2,2,2,2B.1,1,1,3C1,1,2,3D.1,2,2,3二、填空題(本題共10小題，每小題2分，共20分)TOC o 1-5 h z命題公式pq的真值為假，當(dāng)且僅當(dāng)。公式pf(qr)在聯(lián)結(jié)詞全功能集，a，中等值形式之一為。G(y)的前束范式為。設(shè)集合A=1，4，B=2，4，則P(A)-P(B)=。R是非空集合上的偏序關(guān)系，當(dāng)且僅當(dāng)R具有。6設(shè)函數(shù)f(x)=x+1,g(x)=2x2,貝Vfog=。7.設(shè)=(134)(256),t=(25)(1643),則ot=。8命題“設(shè)G為任意的n階簡(jiǎn)單的哈密爾圖，貝OVu,veV(G),均有d(u)+d

8、(v)2n”的真值為無(wú)向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中每一個(gè)頂點(diǎn)的度數(shù)都為設(shè)樹T有m個(gè)頂點(diǎn)，n條邊，則T中頂點(diǎn)與邊的關(guān)系為。三、證明下式(6X2=12分)1、判斷下面推理是否正確。如果你學(xué)習(xí)，那么你離散數(shù)學(xué)不會(huì)不及格。如果你不熱衷于玩游戲，那么你將學(xué)習(xí)。但你離散數(shù)學(xué)不及格。因此你熱衷于玩游戲2、在一階謂詞邏輯中構(gòu)造下面推理的證明。前提：xF(x)，Vx(F(x)VG(x)H(x)結(jié)論：xH(x)3.謂詞公式，VxF(x)Ty四、用等值演算法求公式(pVq)人(pq)(qp)的主合取范式與主析取范式。(10分)五、設(shè)R1和R2是集合X=0,1,2,3,4上的關(guān)系，R1=|y=2x，R2=|x=y

9、+1寫出叫、R2，寫出R2的關(guān)系矩陣，并求出R1R2o(8分)六、設(shè)集合A=2,3,4,6,8，12,24,R為A上的整除關(guān)系,（1）畫出偏序集（A,R）的哈斯圖；（2）出集合A中的最大元、最小元、極大元、極小元；（3）寫出A的子集B=2,3,6，12的上界、下界、最小上界、最大下界。（8分）七、設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算*x，yZ有x*y=x,y-2。證明：vZ,*是一個(gè)群。（10分）八、平面圖G有兩個(gè)連通分支，其頂點(diǎn)數(shù)為12,邊數(shù)為34,問(wèn)G有多少個(gè)面?（6分）九、對(duì)下圖,1）求其鄰接矩陣；（2）長(zhǎng)度小于3的通路和回路的總數(shù)。（6分）v520042005第一學(xué)期補(bǔ)考試卷離散數(shù)學(xué)課程

10、閉卷課程類別：必修考試時(shí)間序號(hào)一一二三四五六七八九十總分得分評(píng)卷人一、單項(xiàng)選擇題(本大題共10小題，每小題2分，共20分)1.下列不是命題的是。學(xué)生要努力學(xué)習(xí).5是素?cái)?shù)當(dāng)且僅當(dāng)太陽(yáng)從西邊升起.x70.D.7能被3整除.2.與命題pV(qAp)等值的公式是。A.pB.qC.pVqD.pAq3使命題公式pf(pAq)為假的賦值是p,q分別為。A.(0,0)B.(0,1)C.(1,0)D.(1,1)在命題邏輯中,任何命題公式的主析取范式都。A.存在且唯一B.存在但不唯一C.不一定存在D.不存在對(duì)于任意集合A、B,A包含于B當(dāng)且僅當(dāng)A-B=0是。A假命題B真命題C是一階公式但不是命題D.均不屬于A、B

11、、C設(shè)S=1,2,3,4,R=v1,1,v2,2,v3,3,則R的性質(zhì)是A自反、對(duì)稱、傳遞的B自反、對(duì)稱、反對(duì)稱的C對(duì)稱、反對(duì)稱、傳遞的D.只有對(duì)稱性- - -7設(shè)A=a,b,c，則下列是集合A的劃分的是。A.b,c,cBa,c,b,cC.a,c,bDa,c,b下述*運(yùn)算為實(shí)數(shù)集上的運(yùn)算，其中可交換且可結(jié)合的運(yùn)算是Aa*b=a+2bBa*b=a+b-abCa*b=aDa*b=la+bl無(wú)向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中每一個(gè)頂點(diǎn)的度數(shù)都為。A不同B.相同C.奇數(shù)D.偶數(shù)10下列四組數(shù)據(jù)中，不能成為任何4階無(wú)向簡(jiǎn)單圖的度數(shù)序列的為。A.2,2,2,2B.2,2,2,3C.1,1,1,3D.1,2

12、,2,3二、將下列命題符號(hào)化(4*2=8分)1、除非你認(rèn)真復(fù)習(xí)，否則你將不及格2、張三和李四都是學(xué)生三、證明下面的式子(8X2=16分)1.用附加前提證明法證明下面的推理。前提：p，qr，q(ps)結(jié)論：rs2、在一階謂詞邏輯中構(gòu)造下面推理的證明。前提：Vx(G(x)VF(x)M(x)，,xG(x)結(jié)論：,xM(x)四、A，B，C是集合，證明An（B-C）=（A-C）n（B-C）（10分）五、求公式（xF（x，y）T,yG（y）TxH（x，y）的前束范式。（6分）六、設(shè)R和R2是集合X=0,1,2,3,4上的關(guān)系，R1=|y=x+1，R2=|y=x2寫出叫、R2，寫出R2的關(guān)系矩陣，并求出R1

13、R2o（10分）七、集合a,b,c,d上的二元運(yùn)算*的運(yùn)算表如下：*abcdaabcdbbbbbccbcaddbaa（1）判斷*是否是可結(jié)合的、可交換的？（2）指出關(guān)于*的幺元、零元、冪等元。（3）哪些元素有逆元？逆元是什么？（12分）八、設(shè)X是實(shí)數(shù)的乘法運(yùn)算，Z為整數(shù)集合，x,yeZ，在Z上定義二元運(yùn)算*：x*y=x+y-2，利用群的定義證明：vZ,*是一個(gè)群。（10分）九、已知平面圖G有三個(gè)連通分支，其頂點(diǎn)數(shù)為21，邊數(shù)為33,問(wèn)G有多少個(gè)面？（8分）20042005學(xué)年第1學(xué)期試卷一、判斷題：(10分，在括號(hào)內(nèi)劃“丿”或“X”)()1“如果太陽(yáng)從西邊出來(lái)，則2+2=4”，此命題值為假。(

14、)2(1,3,3,3)可以成為無(wú)向簡(jiǎn)單圖的度數(shù)序列。()3.有一個(gè)函數(shù)f：XtY,若f具有反函數(shù)，則f一定是單射。()4.(PaQ)(P,Q)是永真式。()5在某集合上二元運(yùn)算中，若某元素存在左右逆元，則該元素逆元唯()6.命題公式的主析取范式為0，則其主合取范式為1。()7.有向圖的關(guān)聯(lián)矩陣中所有元素之和為該圖度之和。()8.初級(jí)回路一定是簡(jiǎn)單回路。()9若關(guān)系R具有自反性，則一定不具有反自反性。()10.Vx(A(x)yH(x,y)在具體的解釋中其值是確定的。二、填空(共30分)TOC o 1-5 h z設(shè)A=1,2,P(A)表示A的冪集，則P(A)A=。在一階邏輯中符號(hào)化命題:“所有的人

15、都是要死的”(只能用存在量詞)P(x)VyR(x,y)的前束范式是：n階有向完全圖中所有頂點(diǎn)的度數(shù)之和為已知從A至【A/R的函數(shù)g:AtA/R為自然映射，A=1,2,3,R=EA,則g(1)=。設(shè)函數(shù)f(x)=2x+1,g(x)=x2-2,貝Ufog=。Klein四元群的運(yùn)算表如下，其有個(gè)子群。TOC o 1-5 h zeabceeabcaaecbbbceaccbae8R,+為代數(shù)系統(tǒng)，給定bez,令函數(shù)f：RfR,且f(x)=bx,當(dāng)b滿足時(shí)，f是R,+的自同構(gòu)。9.若IP(AUB)I=256,IP(A)I=64,IB1=3,貝VIABl=。10下圖為無(wú)向圖，并且是平面圖，畫出它的一種平面嵌

16、入。V2V3V4三、(6分)設(shè)A、B、C為任意集合，證明：(AUBUC)n(AUB)-(AU(B-C)HA)=B-A四、(8分)求(，pAq)Tr的主合取范式、主析取范式以及成假賦值。五、(8分)設(shè)Z為整數(shù)，在Z上定義二元運(yùn)算，對(duì)任意的x,yeZ,定義:xAy二x+y+10證明：Z,是群。六、（8分）在一階邏輯自然推理系統(tǒng)中，構(gòu)造下面推理的證明。個(gè)體域是人的集合?！懊總€(gè)喜歡步行的人都不喜歡坐汽車，每個(gè)人或者喜歡坐汽車或者喜歡騎自行車，有的人不喜歡騎自行車。因而有的人不喜歡步行。”七、（10分）設(shè)集合A=1,2,3,4上的二元關(guān)系R1與R2定義如下:R1=,，R2=,，1）寫出R1的關(guān)系矩陣，并判斷R1具有哪些性質(zhì)？2）求出R1oR23）畫出t（R2）的關(guān)系圖。