中國地質大學大二計算機專業(yè)離散數(shù)學試卷及答案2

試卷類別AAB

中國地質大學（武漢）考試出題專用紙 教務處制考試課程名稱： 離散數(shù)學 學時：80考試方式：開卷，閉卷，筆試，口試，其它考試內容：（201）判斷下列公式的類型：((P∧Q)→P)是 式；((P→Q)∧(Q→P))≡(P≡Q)是 式使用班級191051-4使用學期2006 下

(P→Q)→(Q→P))是 式。(P∨Q)∧(Q∨R)的對偶式為。若集合A的元素個數(shù)|A|=8，則其冪集的元素個數(shù)|P(A)|= 。某班有學生60人其中有38人學習VB語言有16人學習C++語言有21人學習JAVA語言，有3個人這三種語言都學習，有2個人這三種語言都不學習，問僅學習兩門語的學生人數(shù)是 。5.設A={1,2,3,4}上的關系R={(1,2),(2,4),(3,3),(1,3)}，則r(R)= ，t(R)= 。設A={1,2,3}，則在A上有 個不同的分劃。設集合A={1,2,3,4,5}，B={a,b}，則有 個不同的從A到B的函數(shù)；有 個不同的從A到B的滿射；有 個不同的從A到B的內射。集合A={a,b,c}上總共可定義的二元運算的個數(shù)是 。9.設<G;⊙

11<G;

>的階為 ，任課教師吳杰系主任審核簽字

11 11 115的周期為 。當n取 值時，n階完全圖Kn為歐拉圖。K中含3條邊的不同構生成子圖有 個。4設G=(n,m)，且G中每個結點的度數(shù)不是k就是k+1，則G中度數(shù)為k的結點的個是 。設有56盞燈，擬公用一個電源，則至少需要有六插頭的接線板數(shù)是 。（80）1.（6）求命題公式((P→Q)∧(R→P))∨((R→Q)→P)的主析取范式和主合取范式。（6分）求謂詞公式xP(x)→(Q(y)→ (yR(y)→xS(x)))的前束合取范式。（9）符號化下列命題并推論其結論：（使用全總個體域）（7）設N是自然數(shù)集合，定義Nρ：ρ={（x,y）|x∈N,y∈N,x+y數(shù)}，證明ρ是一個等價關系。PAGEPAGE22006下離散數(shù)學（A）參考答案（201）矛盾重言可滿足2.(P∧Q)∨(Q∧R)3.2564.115.{1，2，（3，，4（12，（1，3）}{1，2，（2，，2（31，（3，1）}1，2，（3，，3（1）}6.57.323008.5129.5510.奇數(shù)11.312.n(k+1)-2m13.11（80）1.主析取范式：(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式：(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)2.前束合取范式：xzu((P(x)∨Q(y)∨R(z))∧(P(x)∨Q(y)∨S(u)))令P(x)：xQ(x)：xR(x)：xx((P(x)∧Q(x))→R(x)),x(P(x)∧Q(x))|-x(P(x)∧R(x))證明：(1)x(P(x)∧Q(x))P(2)P(a)∧Q(a)ES(1)(3)P(a)I(2)(4)x((P(x)∧Q(x))→R(x))P(5)(P(a)∧Q(a))→R(a)US(4)(6)R(a)I(2)(5)(7)P(a)∧R(a)I(3)(6)(8)x(P(x)∧R(x))EG(7)（1）對任意x∈N,x+x(x,x)∈ρ,所以ρ是自反的；對任意x,y∈N,若(x,y)∈ρ,x+y是偶數(shù)，則y+x(y,x)∈ρ,所以是對稱的；對任意x,y,z∈N,若(x,y)∈ρ且(y,z)∈ρ，即x+y，y+zx+z=(x+y)+(y+z)-2y(x,z)∈ρ,所以ρ是可傳遞的；由(1)(2)(3)知ρ是等價關系。5.（1）是f1(x)=log2x（2）否 （3）否f:A→Bf(A)B封閉性，對于任意的b,b∈f(A)，a,a∈A，使得f(a)=b,f(a)=b1 2 1 2 1 1 2 2所以，b*b=f(a)*f(a)=f(aοa)（因為f）1 2 1 2 1 2b*b∈f(A)，所以<f(A);*>是<B;*>的子代數(shù)。1 2（1）e∈HH對于任意的a,b∈H,x∈G，有(a*b)*x=x*(a*b)，即a*b∈H，所以H*a∈H，有a1∈H，因此<H;*>是<G;*>的子群。（2）對于任意的a∈H,b∈G有b*a*b1=b*(a*b1)=b*(b1*a)=e*a=a∈H;因此，<H;*>是群<G;*>的正規(guī)子群。 12（1）是偏序關系，哈斯圖如右： 4 62 3（2）是格 19.v表示顏色(i=1,2…6)V={v,v,…,v}，E={(u,v)|u,v∈Vui 1 2 6≠v并且u與v搭配}u,v∈V,d(u)+d(v)≥6,所以G是哈密頓圖，因而G中存在哈密頓回路，不妨設vvvvvvv為其中一條，在這種回路上每個頂點代表的顏色都能與它相鄰頂點代表的1234561vv,v與v,v與v361 2 3 4 5 610.（用反證法證明）設|V|=n。因為T=〈V,E〉是一棵樹，所以|E|=n-1。由歐拉握手定理可得deg(v)=2|E|=2n-2。vVT1

deg(v)2(n-1)+1>2n-2。得出矛盾。11.（1）根據(jù)歐拉公式n-m+f=2，得f=m-n+2而對于結點數(shù)n≥3G，有m≤3n-6，所以f≤2n