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

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

2、p成假的賦值是：2、設(shè)A=a,b，B=1,2,3，求：AB=BA=3、一棵無(wú)向樹(shù)T有2個(gè)4度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，其余的結(jié)點(diǎn)都是樹(shù)葉，問(wèn)T有片樹(shù)葉?4、指出公式(z) (P(x)($x)R(x,z)($y)Q(x,y)R(x,y)中的約束變?cè)妥杂勺冊(cè)?、.A=1,2,3,4，A上二元關(guān)系R和S分別為：R=, S=, RS =二、綜合題(每小題10分，共 80 分)得分評(píng)閱人 1、用等價(jià)演算證明：p(qr)(pq)r2、求命題公式(pq)r的主合取范式并求命題公式的成假賦值3、將下列命題符號(hào)化。并討論它們的真值（1）凡是人都要休息。（2）每個(gè)自然數(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上的等價(jià)關(guān)系R定義為：R=,IA畫出關(guān)系圖，找出所有等價(jià)類，總結(jié)等價(jià)類和關(guān)系圖的關(guān)系。.6、無(wú)向圖G如圖所示。 寫出G的鄰接矩陣。 求G中長(zhǎng)度為3的路的總數(shù)，其中有多少條回路。 求G的連通矩陣。7、求帶權(quán)3,4,5,6,7,8,9的最優(yōu)二叉樹(shù)T。8、某單位按編制有7個(gè)工作空缺：p1，p2，p7，有10個(gè)申請(qǐng)者：a1，a2，a10。它們能勝任的工作集合依次是p1, p5, p6，p2, p6, p7，p3, p4，p1, p5，p6, p7，p3，p2, p3，p1, p3，p1，p5。如果規(guī)定每個(gè)申請(qǐng)者最多只能安排

4、一個(gè)工作。試給出一種方案使分配到工作的申請(qǐng)者最多。離散數(shù)學(xué)B卷答案一填空題1成真的賦值是：00，10，11成假的賦值是：012、AB=,BA=,3、T有9片葉子4、約束變?cè)簒，y，z，自由變?cè)簒，y5、,二、綜合題1、p(qr)p(qr)(條件等價(jià)式)(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要休息?！胺彩侨硕家菹??！狈?hào)化為：(x)(R(x)S(x)它的真值為：真。 （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)它的真值為：真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)系圖每一個(gè)連通分支的結(jié)點(diǎn)構(gòu)成的集合是一個(gè)等價(jià)類?；蛘哒f(shuō)，每一個(gè)等價(jià)類導(dǎo)出了關(guān)系圖的一個(gè)連通分支。6、解：鄰接矩陣（2） A=，A2=A3=長(zhǎng)度為3的路的總條數(shù)66條，其中回路12條。（3） C4= A0+A1+A2+A3=，G的連通矩陣為P=7、最優(yōu)樹(shù)的權(quán)為：W(T)=(34)473(56)3(89)2=116。8、解：按題意構(gòu)造一個(gè)二部圖G=，其中X= p1，p2，p7，Y=a1，a2，a10，E表