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

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

三 四 五 六 七 八 九 十 總100

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

個不同的劃分，并給出三個劃分塊的劃分 4、設(shè)A=1,2，求：A×P(A）= 5、無向樹T有8片樹葉，2個3度分枝點，其余的分枝點都是4度點，問T有 個4度分枝點？第1頁共7頁二、綜合題（1080分）得分 評人1、有向圖G.⑴寫出G.（2)求G3其中有多少條回路。（3）求G的可達性矩陣。2、用等價演算證明：p→(q∨r）(p∧q）→r3、求命題公式(p→q）→(p∨q）的主析取范式，并求命題公式的成真賦值第2頁共7頁4、將下列命題符號化.并討論它們的真值（1）有些實數(shù)是有理數(shù).(2）每個自然數(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ī)定每個申請者最多只能安排一個工作。試給出一種方案使分配到工作的申請者最多。離散數(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度分枝點二、綜合題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長度為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é)合律）(德·摩根律）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ù)（（）)它的真值為：真（2）設(shè)N（x)：x是自然數(shù)。G（x，y）:x比y大.“每個自然數(shù)都有比它大的自然數(shù)。"符號化為：(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解：是因為11前綴碼.

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

，…，p

,Y=a,a

，…,a

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