國家開放大學(xué)《離散數(shù)學(xué)(本)》形考任務(wù)4參考答案

#國家開放大學(xué)《離散數(shù)學(xué)(本)》下載作業(yè)參考答案一、公式翻譯題(每小題4分，共16分)1．將語句“我會英語，并且會德語．”翻譯成命題公式．參考答案：設(shè)p.我學(xué)英語Q：我學(xué)法語則命題公式為:pAQ2．將語句“如果今天是周三，則昨天是周二．”翻譯成命題公式．參考答案：設(shè)P：今天是周三Q：昨天是周二則命題公式為：PfQ.將語句“C3次列車每天上午9點發(fā)車或者10點發(fā)車”翻譯成命題公式.參考答案：設(shè)P：C3次列車每天上午9點發(fā)車Q：C3次列車每天上午10點發(fā)車則命題公式為：1(P-Q).將語句“小王是個學(xué)生，小李是個職員，而小張是個軍人．”翻譯成命題公式．參考答案：設(shè)P：小王是個學(xué)生Q：小李是個職員R：而小張是個軍人則命題公式為：PAQAR二、計算題(每小題12分，共84分).設(shè)集合A={{a},a,b},B={a,}試計算：(1)AcB； (2)AuB； (3)A-(AcB)參考答案：AcB={a}AuB={{a},a,b}(3)A-(AcB)={{a},a,b}-{a}={a,b}.設(shè)集合A={2,3,6,12,24,36},B為A的子集，其中B={6,12},R是A上的整除關(guān)系，試(1)寫出R的關(guān)系表達式；(2)畫出關(guān)系R的哈斯圖；(3)求出B的最大元、極大元、最小上界.參考答案：(1)R={<2,2>,<2,6>,<2,12>,<2,24>,<3,3>,<3,6>,<3,12>,<3,24>,<6,6>,<6,12>,<6,24>,<12,12>,<12,24>,<24,24>}(2)關(guān)系R的哈斯圖(3)B的最大元素：12極大元素：12最小上屆：12.設(shè)G=<卜，E>，V={v1,v2,v3,v4}，E={(v1,v2)，(v1,v3)，(v1,v4)，(v2,vJ，(v3,9,試(1)給出G的圖形表示；(2)寫出其鄰接矩陣；(3)求出每個結(jié)點的度數(shù);(4)畫出其補圖的圖形。參考答案：G的圖形表示

(2)鄰接矩陣(2)鄰接矩陣01111010(3)每個結(jié)點的度數(shù)Deg(v1)=3Deg(v2)=2Deg(v3)=3Deg(v4)=2(4)其補圖的圖形vl劍.求P一(Q八R)的合取范式與主析取范式.參考答案：P-(QaR)二口Pv(QaR)二([PvQ)a([PvR)合取范式二([PvQ)v(RaiR)a([PvR)=(口PvQ)v(RaiR)a(]PvR)v(QaiQ)=(qPvQvR)A(]PvQVqR)A(qPVqQvR)主合取范式=(qPa[Qa[R)v(qPa[QaR)v(qPa[Qa[R)(qPaQaR)V(PA]QaR)v(PaQa]R)v(PaQaR)主析取范式.試畫一棵帶權(quán)為1,2,3,3,4的最優(yōu)二叉樹,并計算該最優(yōu)二叉樹的權(quán).

參考答案:最優(yōu)二叉樹的權(quán)為1X3+2X3+3X2+3X2+4X2=29.試利用Kruskal算法求出如下所示賦權(quán)圖中的最小生成樹（要求寫出求解步驟），并求此最小生成樹的權(quán).參考答案：W(v2,v6)=l,i￡(v2,v6)W(v4,v5)=l,選(v4,v5)W(v1,v6)=2,選(vl,v6)W(v3,v5)=2,選(v3,v5)W(v2,v3尸4,選(v2,v3)生成樹的權(quán)W（T）=1+1+2+2+4=10.設(shè)謂詞公式（土）尸（羽y）T（Vz）Q（x,y,z）,試（1）寫出量詞的轄域;（2）指出該公式的自由變元和約束變元。參考答案：(1)3x的轄域為P(x,y)fVzQ(x,