1、2006 2006 （閉卷）70 學時任課班級：114051-4任課班級：114051-4、111051-2任課教師：孫明 PAGE 5離散數學（A 卷）閉卷、70 學時一、填空選擇題 (每空1分，共26分)1p q rA,B,C。供選擇的答案A：無；全體賦值；010，100，101，111；010，100，101，110，111。B：無；全體賦值；000，001，011；000，010，110。C：重言式；矛盾式；可滿足式。2、在公式（x)(P( y) Q(x, y) (y)R(x, y) 中， x 的轄域是 P(z)Q(x,z) ，y的轄域是R(x,z)。3Z+=xxZX0,1, ,2是

2、Z+的 3 個劃分。3 =xxZ+=S,S,S,S=Z+-SZ+,121212133AB.劃分對應的是Z+上的C,對應的是Z+上的D,對應的是Z+123上的 E.供選擇的答案A:( ) , .1,23C:( ),E:( )整除關系；全域關系；包含關系；小于等于關系；恒等關系；含有兩個等價類的等價關系；以上關系都不是。4 、 設 f f (x) x x gRR,g(x)=x+2,則 fg(x) 為(x22x 3x122x 3f (x) 2x f(x)f (x) 0 x fRRB是A，f-1,g-1C.B供 選 擇 的 答 案 A；單射不滿射；滿射不單射；（，C（ ：不是反函數；是反函數；BC5、

3、設 G=0，1，2，3，若為模 4 乘法，則構成 A.BC4 階群，且是。G 中的 2 階元是 D，E4 階元是。E供 選 擇 的 答 案 A；群；B：；無限。C：Klein；（，（ 0；13；2。6、設（A,）是代數系統，二元運算和對于A是封閉的。如果對于A中任意的元素滿足交換、結合和吸收，則稱是格。7、6 個頂點 11 條邊的所以可能的非同構的連通的簡單的非平面圖有4個，其中有2個含子圖有 2個含與K5同胚子圖。二、計算題（每題5分，任選6題，共30分）1P(A)AxxR 3 2x2 x2答：P(A)=,-1,1,2,-1,1,-1,2,1,2,-1,1,22、設 S1，2，3，4，R 是

4、 S 上的二元關系，其關系矩陣為10011000求R 的關系表達式。Rdom R=?,ran R=? 00011000RR 中有幾個有序對？的關系圖中有幾個環？答：關系表達示：,domR=1,2,3,4,ranR=1,4 7 13、SQQ，Q 為有理數集，*為 S 上的二元運算，任意，S 有*運算在 S 上具有哪些主要性質；*S 逆元。答： *a=0bQ或者1，01，0為*運算的單位元。對任意 a,bQQ，只要a0 都存在逆元；不存在零元。4D1-1圖 1-1D4并指出其中有多少條是回路？其A 000A 000020001101010100000000201111120000000011121

5、323003001A4= 002000342 4 23 7 條為回路。3555、當 n 和 m 為何值時，完全二部圖 Kn,m 是歐拉圖；哈密頓圖；平面圖；非平面圖。答：nmn=mn=2；n=3，m=36T73，T3能畫出幾棵具有此種度數的非同構的無向樹？53Tx3Tn=7+x, 邊數m=n-1=6+x,由握手定理的方程2m=12+2x=3x+7,解出x=5,T的度數列為 1，1，1，1，1，3，3，3，3，3。有兩棵非同構的樹。71-2GGT,求G 的對應于 T 的基本回路系統。對應生成樹的弦分別為 e6,e7,e8,e10,e11。設它們對應的基本回路分別為 C1,C2,C3,C4,C5，

6、從對應的弦開始，按逆時針（也可都按順時針）的順序寫出它們，分別為 e11e3e5e2e9此圖的圈秩為 5，基本回路系統為C1,C2,C3,C4,C5。三、證明題（每題6 分，任選4 題，共24 分）1和21設HH 是群的兩個互不包含的子群證明G 中存在一個元素，1和21H H 1H1 H2,aH1,aH，又因為，所以存在HHH111bH2,bH aH ,是的子111群，可推出 bH1,這與 bH1 矛盾。同理可證，a*bH22、證明歐拉圖中必沒有割邊。設歐拉圖中含有割邊。由于歐拉圖中每一個頂點的度數為偶數，所以割邊的兩個端點也是偶數度頂點。刪去割邊后，構成兩個連通分支，每個連通分支都含有割邊的

7、一個端點；此時每一個連通分支中僅有一個奇數度頂點，這與已知矛盾。所以，歐拉圖中沒有割邊。3、設aL,SxxL證明L 的子格。x,ySxa和ya,所以ya,xyayS, xyS,因此是的子格。4G 6 G 3 6 G a，那么，另5 G a 鄰接，要么在圖a 5 個結點分成兩類，將會必有一類至少含有三個頂點。不妨假3 的子圖（這里圖G 或者是 。如果邊(b,c),(c,d),(b,d)中有一條邊在 *擇優 3 個頂點鄰接。如果邊 (b,c),(c,d),(b,d)G*G*的補圖（G）中，因3 個頂點鄰接。5nmm=2n-2.G*G G 于是 n=n*=r，由歐拉公式可知，n-m+r=2=n-m+

8、n 得 m=2n-26K5和K3,3答：畫圖舉例。四、應用題（每題 10 分，共 20 分）1、在自然推理系統 F 中，證明下面推理：（個體域為人類集合P(x)：x 喜歡步行； Q(x)：x 喜歡乘汽車； R(x)：x 喜歡騎自行車；本題符號化為 前題：x(P(x)R(x), x(R(x)Q(x)，x 結論： x P(x)x Q(x)前提引入x(R(x)Q(x)前提引入 Q(c) EI 規則R(c) Q(c) UI規則 x(P(x) R(x)前提引入 P(c) R(c)UI規則 R(c)析取三段論 P(c)拒取式 x P(x)EG規則2、今有n 個人，已知他們中的任何二人和起來認識其余的n-2 n3nn4nnV,V,V,Vn,V=V,V,V,VnV123123iVE，于是的無向簡單圖jG=V,VVV與VVV（ki,kj）ijijkViVVjK相鄰，與Vj不相鄰。