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

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

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

3、。3設(shè)是偏序格，其中N是自然數(shù)集合，“”是普通的數(shù)間“小于等于” 關(guān)系，則 有（ ）。A、a ； B、b ； C、max(a，b) ； D、min(a，b)。4連通非平凡的無向圖G有一條歐拉回路當(dāng)且僅當(dāng)圖G ( )。A、只有一個(gè)奇度結(jié)點(diǎn)； B、只有兩個(gè)奇度結(jié)點(diǎn)； C、只有三個(gè)奇度結(jié)點(diǎn)； D、沒有奇度結(jié)點(diǎn)。5設(shè)無向圖是連通的且 若（ ）則G是樹。 A、m=n+1 ； B、n=m+1 ； C、 ； D、 。三、12%符號(hào)化語句：“有些病人相信所有的醫(yī)生，但是病人都不相信騙子，所以醫(yī)生都不是騙子”。并推證其結(jié)論。解: 設(shè)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)結(jié)論：(x)(B(x)¬C(x)制表如下：編號(hào)公式依據(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%：設(shè)，偏序集的Hass圖為求 A中最小元與最大元； 的上界和上確界，下界和下確界。解：（1）A中最小元：沒有；最大元： x1（2）上界x1 x3上確界 x3 下界無 下確界無（注：離散數(shù)學(xué)及應(yīng)用（溫武）127頁概念，自己去研究）五、8%：求集合的并與交。（注：寫這個(gè)還真麻煩，丑，呃）六、15% 已知某樹有2個(gè)2度結(jié)點(diǎn)、3個(gè)3度結(jié)點(diǎn)、4個(gè)4度結(jié)點(diǎn)，問有幾個(gè)葉子點(diǎn)（無其它度數(shù)點(diǎn)）解：設(shè)共有k個(gè)葉子點(diǎn)，總邊數(shù)為x，則2+3+4

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