離散數(shù)學期末考試試題配答案模擬題2

1、模擬題2廣東技術師范學院模擬試題 科 目：離散數(shù)學 考試形式：閉卷 考試時間: 120 分鐘系別、班級： 姓名： 學號： 一、填空20%（每空2分）：1若對命題P賦值1，Q賦值0，則命題（表示雙條件）的真值為 0 。2命題“如果你不看電影，那么我也不看電影”（P：你看電影，Q：我看電影）的符號化為 ¬P¬Q3公式的對偶公式為_¬（PQ）（P¬（Q¬S）_。4圖 的對偶圖為 5.若關系R是等價關系，則R滿足_自反性，對稱性，傳遞性_。 6代數(shù)系統(tǒng)是群，則它滿足_結合律，有幺元 ，每個元素都有遞元_。 7若連通平面圖共有r個面，其中，則它滿足的Eu

2、ler公式為_v-e+r=2_。8. n個結點的無向完全圖Kn的邊數(shù)為 n（n-1）/2 ，歐拉圖的充要條件是 頂點都是偶頂點且是連通的 。9. 設I為整數(shù)集合，R=<x, y>| xy（mod3），則1=_ ，-2,1,4，_ 。10代數(shù)系統(tǒng)是環(huán)，若對運算“· ”還滿足a，bR，使得ab0，可換，含幺元 則是整環(huán)。二、選擇10%（每小題2分）1集合對（ ）運算封閉。A、加法； B、減法； C、乘法； D、 。2設I為整數(shù)集合，m是任意正整數(shù)，是由模m的同余類組成的同余類集合，在上定義運算，則代數(shù)系統(tǒng)最確切的性質是 ）。A、封閉的代數(shù)系統(tǒng)； B、半群； C、幺元； D、群

3、。3設是偏序格，其中N是自然數(shù)集合，“”是普通的數(shù)間“小于等于” 關系，則 有（ ）。A、a ； B、b ； C、max(a，b) ； D、min(a，b)。4連通非平凡的無向圖G有一條歐拉回路當且僅當圖G ( )。A、只有一個奇度結點； B、只有兩個奇度結點； C、只有三個奇度結點； D、沒有奇度結點。5設無向圖是連通的且 若（ ）則G是樹。 A、m=n+1 ； B、n=m+1 ； C、 ； D、 。三、12%符號化語句：“有些病人相信所有的醫(yī)生，但是病人都不相信騙子，所以醫(yī)生都不是騙子”。并推證其結論。解: 設A(x):x是病人，B(x):x是醫(yī)生，C(x):x是騙子，D(x,y):x相信

4、y前提：(x)(A(X)(y)(B(y)D(x,y)(x)(y)(A(x)(y)¬D(x,y)結論：(x)(B(x)¬C(x)制表如下：編號公式依據(jù)（1）(x)(A(x)(y)(B(y)D(x,y)前提（2）A(a)(y)(B(y)D(a,y)(1),Es（3）A(a),(y)(B(y)D(a,y)(2)（4）(x)(y)(A(x)C(y)¬D(x,y)前提（5）(y)(A(a)C(y)¬D(a,y)(4),Us（6）A(a)(y)(C(y)¬D(a,y)(5)（7）(y)(C(y)¬D(a,y)(3)(6)（8）B(d)D(a,d)

5、(3),Us（9）C(e)¬D(a,e)(7),Us（10）B(d)¬C(e)(8)(9)（11）(x)(B(x)¬C(x)(10),UG四、8%：設，偏序集的Hass圖為求 A中最小元與最大元； 的上界和上確界，下界和下確界。解：（1）A中最小元：沒有；最大元： x1（2）上界x1 x3上確界 x3 下界無 下確界無（注：離散數(shù)學及應用（溫武）127頁概念，自己去研究）五、8%：求集合的并與交。（注：寫這個還真麻煩，丑，呃）六、15% 已知某樹有2個2度結點、3個3度結點、4個4度結點，問有幾個葉子點（無其它度數(shù)點）解：設共有k個葉子點，總邊數(shù)為x，則2+3+4

6、+k=x+12×23×34×4k=2x解得：k=13，x=21七、8% 若圖G不連通，則G的補圖是連通的。證明：G不連通，則G的連通分支有G1，G2，Gm,(m2)在補圖非G中找兩個頂點，u，v有兩種情況：u，v落在G的不同連通分支中，uGi，vGj，ij；(u,v)是補圖非G的一條邊，故u，v連通。u，v都在Gi中，則找另一個連通分支Gj，在Gj找任意一個頂點w，(u,w),(w,v)是G的邊，則u，v在補圖非G邊連通。八、10% 求圖中的一棵最小生成樹。解：2九、9% 若集合（，），（，），（，），1、證明R是X上的等價關系。2、求出X關于R的商集。證明：1.自反性（x1，y1）x，由于x1+y1=y1+x1，所以（x1，y1），（x1，y1）R對稱性（x1，y1），（x2，y2）R,要證明（x2，y2），（x1，y1）R因為x1+y2=x2+y1及自反性，可得:x2+y1=x1+y2所以具有對