南昌大學(xué)本科離散試卷及答案1

南昌大學(xué)2007~2008學(xué)年第一學(xué)期期末考試試卷試卷編號(hào): （A）課程編號(hào)： 課程名稱：離散數(shù)學(xué) 考試形式： 閉卷適用班級(jí)： 姓名： 學(xué)號(hào)： 班級(jí)學(xué)院： 專業(yè)： 考試日期:題號(hào) 一 題分 20 80得分

三 四 五 六 七 八 九 十 總100

累分人簽名考生注意事項(xiàng)：1、本試卷共5頁，請(qǐng)查看試卷中是否有缺頁或破損。如有立即舉手報(bào)告以便更換。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。一、填空題（420分）得分 評(píng)閱人1、使得公式p→(q∨r)成真的賦值是 使得公式p→(q∨r)成假的賦值是： 2、設(shè)個(gè)體域?yàn)镈=1,2,3，試消去公式（x）P(x)∨（y)Q（y)量詞的等價(jià)式 3、4個(gè)元素的集合共有

個(gè)不同的劃分，并給出三個(gè)劃分塊的劃分 4、設(shè)A=1,2，求：A×P(A）= 5、無向樹T有8片樹葉，2個(gè)3度分枝點(diǎn)，其余的分枝點(diǎn)都是4度點(diǎn)，問T有 個(gè)4度分枝點(diǎn)？第1頁共7頁二、綜合題（1080分）得分 評(píng)人1、有向圖G.⑴寫出G.（2)求G3其中有多少條回路。（3）求G的可達(dá)性矩陣。2、用等價(jià)演算證明：p→(q∨r）(p∧q）→r3、求命題公式(p→q）→(p∨q）的主析取范式，并求命題公式的成真賦值第2頁共7頁4、將下列命題符號(hào)化.并討論它們的真值（1）有些實(shí)數(shù)是有理數(shù).(2）每個(gè)自然數(shù)都有比它大的自然數(shù)。5、證明x)(F）∨G(x)，(）(（x）→R(x)（x）（）（x)F(x)第3頁共7頁6、設(shè)A=1,2,3，4，ARR，22,2,334求R.70、1,(2）01，11,000,0010,0011第4頁共7頁8710a2，…,a10p1,p5，p6,p2,p6，p7p3，p4p1，p5p6，p7p3p，p3p1，p3p1，p5.如果規(guī)定每個(gè)申請(qǐng)者最多只能安排一個(gè)工作。試給出一種方案使分配到工作的申請(qǐng)者最多。離散數(shù)學(xué)A卷答案一填空題1、成真的賦值是：000，001，010，011，101，110，111，成假的賦值是:100.2、(x）P（x）∨（y）(y）（P（1)∧(2)∧P（3）∨（Q（1)∨Q(2)∨Q(3))31，2，3,4，1，3,2，4，1,4,2,3，2,3，1,4，2，4,1，3，3,4,1，21+C1C21C2+1=1+4+6+3+1=15種4 4 2 44111,2,12,2，1，25T24度分枝點(diǎn)二、綜合題M=1、解：⑴ M=R 000

1 1 00 0 01 0 10 0 044第5頁共7頁110111011110011011011000 ，A3=01100

0 0 0

0 0 0 0 44

44長(zhǎng)度為3的路有8條,其中回路3條。3321111123321111123111111002、p→(q∨r）p∨（q∨r）（p∨q）∨r（p∧q)∨r(p∧q)→r

2 2 0 0

44

P=00

1 1 10 0 1（條件等價(jià)式）（結(jié)合律）(德·摩根律）3、(p∨q）∨（p∨q）（p∧q)∨(p∧q)∨(p∧q）(主析取范式）∑0，2，3使得命題公式(p→q)→（p∨q)成真的賦值是：00,10，11。4（1）解:R(x)：xQ(x）:x是有理數(shù)。“有些實(shí)數(shù)是有理數(shù)（（）)它的真值為：真（2）設(shè)N（x)：x是自然數(shù)。G（x，y）:x比y大.“每個(gè)自然數(shù)都有比它大的自然數(shù)。"符號(hào)化為：(x)(N（x)→(y)（N(y)∧G（y，x)）它的真值為：真5證明：⑴（x)R（x)⑵R(c）⑶(x)(G（x)→R（x))⑷G（c）→R(c)⑸G(c)⑹⑺F（c)∨G（c)⑻F(c)⑼(x)F（x)

PUS⑴PUS⑶TPUS⑹TUG⑻、6、r(R)=1,2,2,1，2,33,4，1,1,2，23，3,〈4，4sR)=〈1,2,12,〈3,4，，R2=RR=1,1,1,3,2，22,4〉R3R2=1，12,R4=R2R=1,1,1,32,2〉,2，4〉=R2tR)=R∪R2∪R3∪R=1,，1，2，1，31，42，1，2,2,2,,2,4，〈3,4〉第6頁共7頁7解：是因?yàn)?1前綴碼.

01,10，11，000,111，不是111的前綴。01,11,000,0010,0011是8、解:按題意構(gòu)造一個(gè)二部圖G=〈X，E,Y〉,其中X=p1,p

，…，p

,Y=a,a

，…,a

，E表示合格工作崗位關(guān)系。如圖所示