離散數(shù)學(xué)南昌大學(xué)軟件學(xué)院試卷軟工A

1、2007 2008學(xué)年第一學(xué)期離散數(shù)學(xué)期末試卷（A）年級(jí)專業(yè) 班級(jí) 學(xué)號(hào) 姓名_題號(hào)一二三四總分得分適用年級(jí)專業(yè)：2006級(jí)軟件工程專業(yè)試卷說明：閉卷考試，考試時(shí)間120分鐘一、 單項(xiàng)選擇題（共20小題，每小題1分，共20分）1下列語句中只有 不是命題。CA今年元旦會(huì)下雪。B1+1=10。 C嫦娥一號(hào)太棒了！ D嫦娥奔月的神話已成為現(xiàn)實(shí)。2pq的主合取范式是 。B A(pq)(pq) B(pq)(pq) C(pq)(pq) D(pq)(pq)3與p q等值的命題公式是 。D Apq Bpq Cpq Dpq4在一階邏輯中使用的量詞只有 個(gè)。B A1 B2 C3 D45xA(x) 。C A$xA(

2、x) BxA(x) C$xA(x) D$xA(x)6若|A|=4，則|P(A)|= 。C A4 B8 C16 D647設(shè)A、B、C為任意集合，集合的對(duì)稱差運(yùn)算不具有的性質(zhì)是 。D AAB = BA B(AB)C = B(AC) CAA = DAA = A8二元關(guān)系是 。B A兩個(gè)集合的笛卡兒積 B序偶的集合 C映射的集合 D以上都不是9下面關(guān)于函數(shù)的敘述中正確的是 。DA函數(shù)一定是滿射 B函數(shù)一定是單射 C函數(shù)不是滿射就單射 D函數(shù)是特殊的關(guān)系10半群中的二元運(yùn)算一定滿足= 。B A交換律 B結(jié)合律 C分配律 D冪等律11環(huán)中有 個(gè)二元運(yùn)算。B A一 B二 C三 D四12群與獨(dú)異點(diǎn)的區(qū)別是 。

3、C A滿足交換律 B滿足結(jié)合律 C每個(gè)元素都有逆元 D滿足分配律13九階輪圖的點(diǎn)色數(shù)是 。BA2 B3 C4 D914設(shè)N、Q、Z、R分別表示非負(fù)整數(shù)集、有理數(shù)集、整數(shù)集和實(shí)數(shù)集，表示數(shù)的加法，則下面的代數(shù)系統(tǒng)中， 不是群。AA B C D15簡(jiǎn)單通路是沒有 的通路。A A重復(fù)邊 B重復(fù)頂點(diǎn) C平行邊 D環(huán)16設(shè)個(gè)體域?yàn)镹（非負(fù)整數(shù)集），下列公式為真的是 。BA$y x (xy = 1) B$y x (xy = x) Cx $y (x+y=0) Dx $y (x y)17非平凡樹一定是 。B A正則圖 B二部圖 C歐拉圖 D哈密頓圖18環(huán)中的 運(yùn)算只要求滿足 。B A交換律 B結(jié)合律 C分配律

4、 D冪等律19集合A上的等價(jià)關(guān)系與 一 一 對(duì)應(yīng)。B A集合A的子集 B集合A的劃分 C集合A到A的雙射 D集合A與A的單射20全序關(guān)系一定不是 。A A等價(jià)關(guān)系 B偏序關(guān)系 C線序關(guān)系 D整除關(guān)系二、填空題（共10題，每題2分，共20分）11 設(shè)S(x)：x是計(jì)算機(jī)學(xué)院的學(xué)生。L(x)：x學(xué)離散數(shù)學(xué)。則“計(jì)算機(jī)學(xué)院的學(xué)生都要學(xué)離散數(shù)學(xué)?！笨煞?hào)化為 ： _ x(S(x)L(x) _。 12 設(shè)A=a,b,c，A上的等價(jià)關(guān)系R=, IA ，則商集A/R=_ a , b , c13設(shè)B=，則冪集P(B) = _ , 。 14xA(x) $yB(x,y)的前束范式是_u$v (A(u) B(x,v

5、)或 x$y(A(x) B(u,y)15設(shè)集合A=0，1，則A上可定義的二元運(yùn)算有_16_個(gè)。16設(shè)A=1，2，3，4，A上關(guān)系R=,IA ，則t(R)=_ , IA17設(shè)函數(shù)f：NN，f =x -1，函數(shù)h：NN，h(x)=x2+1，則復(fù)合函數(shù)foh (x) = _(x -1)2+118完全二部圖Kr,s（rs）的最大度D(Kr,s) = _S_，最小度d(Kr,s)= _ r _。19設(shè)一棵樹有4個(gè)2度頂點(diǎn)，3個(gè)3度頂點(diǎn)，其余頂點(diǎn)都是1度頂點(diǎn)，則該樹有_5_片樹葉。20命題公式(p(pq)的成假賦值是_00，01，10，11三、運(yùn)算題（共5小題，每小題8分，共40分）21求命題公式(pq)

6、 (q r)的主析取范式，并指出其類型。解：(pq) (q r) (p q ) (q r) (p r) q (p ( q q ) r) ( p p ) q ( r r ) ) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) 該公式是可滿足式22設(shè)A=a,b,c,d,e,f， A上的偏序關(guān)系：R=, IA 畫出該偏序關(guān)系的哈斯圖，并求A的極大元、極小元、最大元和最小元。解：極大元為d、e、f；極小元為a；無最大元；最小元為a23設(shè)個(gè)體域D=a,b,c，消去一階公式 x（

7、F(x) $yG(y)）中的量詞 ，并在下述解釋下求其真值：F(a)= F(b)=1 , F(c)= 0，G(a)=1， G(b)=G(c)=0。 解：x（F(x) $yG(y)）$ xF(x) $yG(y)（F(a) F(b) F(c)）（G(a) G(b) G(c)）（1 1 0）（1 0 0） 1 1124畫一棵葉帶權(quán)為1、2、3、3、5、6、7的最優(yōu)二元樹T，并計(jì)算樹權(quán)W(T)。解： W(T) = 7125設(shè)Z為整數(shù)集合，V=，*是二元運(yùn)算，定義為： x*y=x+y-xy說明V是含幺半群而不是群。解：（1）*運(yùn)算在Z上封閉：（2）*運(yùn)算可結(jié)合，對(duì)任意a、b、cZa*(b*c) = a*

8、(b+c-bc) = a+ b+c-bc -a(b+c-bc) = a+b+c-ab-ac-bc+abc(a*b)*c = (a+b-ab)*c = a+b-ab+c- (a+b-ab) c = a+b+c-ab-ac-bc+abc所以a*(b*c) =(a*b)*c（3）*運(yùn)算的幺元是0（4）任意xZ，x*1=1*x=1，所以1是零元，它沒有逆元。由上述可知，故是含幺半群而不是群。四、證明題（共3小題，共20分）26（10分）在一階邏輯中構(gòu)造下面推理的證明： 前提：x(F(x) G(x) ，x (G(x) R(x)，$xR(x)結(jié)論：$xF(x)（10分）證: $xR(x) 前提引入 R(c

9、) EI x (G(x) R(x) 前提引入 G(c) R(c) UI G(c) 析取三段論 x(F(x) G(x) 前提引入 F(c) G(c) UI F(c) 拒取式 $xF(x) EG27（5分）證明，若非空集合A上的關(guān)系R和S是反對(duì)稱的，則RS也是反對(duì)稱的。證: 任取，xyRSRSRSRS。故RS是對(duì)稱的。28（5分）若無向圖G中恰有兩個(gè)奇度頂點(diǎn)，證明這兩個(gè)奇度頂點(diǎn)必連通。證: 用反證法。假設(shè)G中兩個(gè)奇度頂點(diǎn)u和v不連通，則u和v分別處于G的兩不同連通分支G1和G2中，因而G1和G2作為獨(dú)立的圖時(shí)，均只有一個(gè)奇度頂點(diǎn)，這是不可能的，故這兩個(gè)奇度頂點(diǎn)必連通。2007 2008學(xué)年第一學(xué)期

10、離散數(shù)學(xué)期末試卷（A）答 案適用年級(jí)專業(yè)：2006級(jí)軟件工程專業(yè)試卷說明：閉卷考試，考試時(shí)間120分鐘一、 單項(xiàng)選擇題（共20小題，每小題1分，共20分）1C 2B 3D 4B 5C 6C 7D 8B 9D 10B11B 12C 13B 14A 15A 16B 17B 18B 19B 20A二、填空題（共10題，每題2分，共20分）11 x(S(x)L(x) 12 a , b , c13 , 14u$v (A(u) B(x,v)或 x$y(A(x) B(u,y) 15 16 16 , IA17 (x -1)2+1 18 s , r19 5 2000，01，10，11三、運(yùn)算題（共5小題，每小題

11、8分，共40分）21解：(pq) (q r) (p q ) (q r) (p r) q (p ( q q ) r) ( p p ) q ( r r ) ) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) (p q r) 該公式是可滿足式22 解：極大元為d、e、f；極小元為a；無最大元；最小元為a23 解：x（F(x) $yG(y)）$ xF(x) $yG(y)（F(a) F(b) F(c)）（G(a) G(b) G(c)）（1 1 0）（1 0 0） 1 1124 解： W(T)

12、= 7125 解：（1）*運(yùn)算在Z上封閉：（2）*運(yùn)算可結(jié)合，對(duì)任意a、b、cZa*(b*c) = a*(b+c-bc) = a+ b+c-bc -a(b+c-bc) = a+b+c-ab-ac-bc+abc(a*b)*c = (a+b-ab)*c = a+b-ab+c- (a+b-ab) c = a+b+c-ab-ac-bc+abc所以a*(b*c) =(a*b)*c（3）*運(yùn)算的幺元是0（4）任意xZ，x*1=1*x=1，所以1是零元，它沒有逆元。由上述可知，故是含幺半群而不是群。四、證明題（共3小題，共20分）26（10分）證: $xR(x) 前提引入 R(c) EI x (G(x) R(x) 前提引入 G(c) R(c) UI