國(guó)家開(kāi)放大學(xué)電大《離散數(shù)學(xué)(本)》形考作業(yè)參考答案

國(guó)家開(kāi)放大學(xué)《離散數(shù)學(xué)（本）》形考作業(yè)參考答案一、公式翻譯題（每小題4分，共16分）1.將語(yǔ)句“我會(huì)英語(yǔ)，并且會(huì)德語(yǔ).”翻譯成命題公式.參考答案：設(shè)p.我學(xué)英語(yǔ)Q:我學(xué)法語(yǔ)則命題公式為:p/\Q2.將語(yǔ)句“如果今天是周三，則昨天是周二.”翻譯成命題公式.參考答案：設(shè)P：今天是周三Q：昨天是周二則命題公式為：P-Q3.將語(yǔ)句“C3次列車每天上午9點(diǎn)發(fā)車或者10點(diǎn)發(fā)車”翻譯成命題公式.參考答案：設(shè)P：C3次列車每天上午9點(diǎn)發(fā)車Q：C3次列車每天上午10點(diǎn)發(fā)車則命題公式為：I（PJQ）4.將語(yǔ)句“小王是個(gè)學(xué)生，小李是個(gè)職員，而小張是個(gè)軍人.”翻譯成命題公式.參考答案：設(shè)P：小王是個(gè)學(xué)生Q：小李是個(gè)職員R:而小張是個(gè)軍人則命題公式為：PAQAR二、計(jì)算題(每小題12分，共84分)1.設(shè)集合厶={同，a,b},B={a,)試計(jì)算：(1)AQB；(2)AEB；(3)A-(AQB)參考答案：(1)4QB={a}(2)AE8=({a},a,b}(3)A(/lQB)=({a},a,b}-{a}={a,b}2.設(shè)集合厶={2,3,6,12,24,36},B^A的子集，其中8={6,12},R是A上的整除關(guān)系，試(1)寫(xiě)出R的關(guān)系表達(dá)式；(2)畫(huà)出關(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的哈斯圖VA(3)B的最大元素：12極大元素：12最小上屆：123.設(shè)G=<V,E>,V={vv2,v3,v4）?（吃吃）},試（1）給出G的圖形表示；（2）寫(xiě)出其鄰接矩陣；（3）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（4）畫(huà)岀其補(bǔ)圖的圖形。參考答案：（1）G的圖形表示v2

v3(2)鄰接矩陣0111101011011010(3)每個(gè)結(jié)點(diǎn)的度數(shù)Deg(v1)=3Deg(v2)=2Deg(v3)=3Deg(v4)=2(4)其補(bǔ)圖的圖形5.v2‘v34.求P^（Q/\R）的合取范式與主析取范式.參考答案：PT（Q/\R）=-]PV(QAR)hh=(-|PVQ)A合取范式=(-]PVQ)V(RA-]R)A(-]PVH)=(-1PVQ)V(RA-i/?)A(-1PVR)V(QAQ)q=(-|PVQVR)A(-|PVQV-]R)A(〔P0QWR)主合取范式=(-]PAQA-]R)V(iPA-]QAR)V(-|PAQA-]R)(-]PAQAR)nnV15.試畫(huà)一棵帶權(quán)為1,2,3,3,4的最優(yōu)二叉樹(shù)，并計(jì)算該最優(yōu)二叉樹(shù)的權(quán).參考答案：最優(yōu)二叉樹(shù)的權(quán)為1x3+2x3+3x2+3x2+4x2=296.試?yán)肒ruskal算法求出如下所示賦權(quán)圖中的最小生成樹(shù)（要求寫(xiě)出求解步驟），并求此最小生成樹(shù)的權(quán).參考答案:W(v2,v6)=1,選(v2,v6)W(v4,v5)=1,選(v4,v5)W(v1,v6)=2,選(v1,v6)W(v3,v5)=2,選(v3,v5)W(v2,v3)=4,選(v2,v3)(PAQAR)V(PAQAR)V(PAQAqR)V(PAQAR)主析取范式最小生成樹(shù)，如圖生成樹(shù)的權(quán)W(T)=1+1+2+2+4=107.設(shè)謂詞公式($x)F(x,y)T%)O(x,y,z),試(1)寫(xiě)出量詞的轄域；(2)指出該公式的自由變?cè)图s束變?cè)?。參考答案?1)$x的轄域?yàn)镻(x,y)-