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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)南昌大學(xué)20072008學(xué)年第一學(xué)期期末考試試卷試卷編號：( B)卷課程編號：課程名稱：離散數(shù)學(xué)考試形式： 閉卷適用班級：姓名：學(xué)號：班級：學(xué)院：專業(yè)：考試日期：題號一二三四五六七八九十總分累分人 簽名題分2080 100得分考生注意事項(xiàng)：1、本試卷共4頁，請查看試卷中是否有缺頁或破損。如有立即舉手報告以便更換。 2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。填空題(每題4 分，共 20 分)得分評閱人 1、使得公式q(pq)p成真的賦值是：使得公式q(pq)

2、p成假的賦值是：2、設(shè)A=a,b，B=1,2,3，求：AB=BA=3、一棵無向樹T有2個4度結(jié)點(diǎn)，3個3度結(jié)點(diǎn)，其余的結(jié)點(diǎn)都是樹葉，問T有片樹葉?4、指出公式(z) (P(x)($x)R(x,z)($y)Q(x,y)R(x,y)中的約束變元和自由變元。5、.A=1,2,3,4，A上二元關(guān)系R和S分別為：R=, S=, RS =二、綜合題(每小題10分，共 80 分)得分評閱人 1、用等價演算證明：p(qr)(pq)r2、求命題公式(pq)r的主合取范式并求命題公式的成假賦值3、將下列命題符號化。并討論它們的真值（1）凡是人都要休息。（2）每個自然數(shù)都有比它大的自然數(shù)。4、用CP規(guī)則證明。 (x

3、)(F(x)R(x)(x)F(x)(x)R(x)5、設(shè)A=1,2,3,4,5，A上的等價關(guān)系R定義為：R=,IA畫出關(guān)系圖，找出所有等價類，總結(jié)等價類和關(guān)系圖的關(guān)系。.6、無向圖G如圖所示。 寫出G的鄰接矩陣。 求G中長度為3的路的總數(shù)，其中有多少條回路。 求G的連通矩陣。7、求帶權(quán)3,4,5,6,7,8,9的最優(yōu)二叉樹T。8、某單位按編制有7個工作空缺：p1，p2，p7，有10個申請者：a1，a2，a10。它們能勝任的工作集合依次是p1, p5, p6，p2, p6, p7，p3, p4，p1, p5，p6, p7，p3，p2, p3，p1, p3，p1，p5。如果規(guī)定每個申請者最多只能安排

4、一個工作。試給出一種方案使分配到工作的申請者最多。離散數(shù)學(xué)B卷答案一填空題1成真的賦值是：00，10，11成假的賦值是：012、AB=,BA=,3、T有9片葉子4、約束變元：x，y，z，自由變元：x，y5、,二、綜合題1、p(qr)p(qr)(條件等價式)(pq)r(結(jié)合律)(pq)r(德摩根律)(pq)r2、(pq)r(pq)r(pqr)(pqr)(pr)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)0,2,4,5,6使得命題公式(pq)r成假的賦值是：000,010,100,101,110。3、（1）設(shè)R(x)：x是人

5、。S(x)：x要休息。“凡是人都要休息。”符號化為：(x)(R(x)S(x)它的真值為：真。 （2）解：設(shè)N(x)：x是自然數(shù)。G(x,y)：x比y大?！懊總€自然數(shù)都有比它大的自然數(shù)?！狈柣癁椋?x)(N(x)($y)(N(y)G(y,x)它的真值為：真4、證明：(x)F(x)P(附加前提)F(c)US(x)(F(x)R(x)PF(c)R(c)USR(c) T假言推理(x)R(x)UG(x)F(x)(x)R(x)CP5、解：R的關(guān)系圖如圖4.34所示。1R=2R=1,2，3R=4R=3,4，5R=5關(guān)系圖每一個連通分支的結(jié)點(diǎn)構(gòu)成的集合是一個等價類。或者說，每一個等價類導(dǎo)出了關(guān)系圖的一個連通分支。6、解：鄰接矩陣（2） A=，A2=A3=長度為3的路的總條數(shù)66條，其中回路12條。（3） C4= A0+A1+A2+A3=，G的連通矩陣為P=7、最優(yōu)樹的權(quán)為：W(T)=(34)473(56)3(89)2=116。8、解：按題意構(gòu)造一個二部圖G=，其中X= p1，p2，p7，Y=a1，a2，a10，E表