2022年秋國(guó)開(kāi)《離散數(shù)學(xué)》形考任務(wù)4各章綜合練習(xí)

離散數(shù)學(xué)下載作業(yè)

姓名：____________

學(xué)號(hào)：____________

得分：____________

教師簽名：____________

提交作業(yè)方式有以下三種，請(qǐng)務(wù)必與輔導(dǎo)教師溝通后選擇：

1.將此次作業(yè)用A4紙打印出來(lái)，手工書(shū)寫(xiě)答題，字跡工整，解答題要有

解答過(guò)程，完成作業(yè)后交給輔導(dǎo)教師批閱.

2.在線(xiàn)提交word文檔.

3.自備答題紙張，將答題過(guò)程手工書(shū)寫(xiě)，并拍照上傳.

一、公式翻譯題（每小題4分，共16分）

1.將語(yǔ)句"我會(huì)英語(yǔ)，并且會(huì)德語(yǔ).”翻譯成命題公式.

設(shè)P：我會(huì)英語(yǔ)Q：我會(huì)德語(yǔ)

則命題公式為：PAQ

2.將語(yǔ)句“如果今天是周三，則昨天是周二翻譯成命題公式.

設(shè)P：今天是周三Q：明天是周二

則命題公式為：P-Q

3.將語(yǔ)句“小王是個(gè)學(xué)生，小李是個(gè)職員.”翻譯成命題公式.

設(shè)P：C3次列車(chē)每天上午9點(diǎn)發(fā)車(chē)

Q：C3次列車(chē)每天上午10點(diǎn)發(fā)車(chē)

4.將語(yǔ)句“如果明天下雨，我們就去圖書(shū)館.“翻譯成命題公式.

設(shè)P:小王是個(gè)學(xué)生

Q：小李是個(gè)職員

R：小張是個(gè)軍人

則命題公式為：PAQAR

二、計(jì)算題(每小題12分，共84分)

1.設(shè)集合A={a,4c},B={{a,b},b},試計(jì)算

⑴ACB；(2)A-B；(3)4X8.

⑴AB={a}

⑵AB={{a},a,b,}

⑶A-(AB)={{a},b,b}

2.設(shè)6=<，，E>,IZ=｛vi,V2,V3,V4,V5）,^｛（VbVs）,（VI,V5）,（V2,V3）,（V3,V4）,

（V4,V5）｝,試

（1）給出G的圖形表示；

（2）求出每個(gè)結(jié)點(diǎn)的度數(shù)；

（3）畫(huà)出其補(bǔ)圖的圖形.

(1)R={<2,2>,<3,3>,<6,6>,<12,12>,<24,24>,<36,36>,<2,6>,<3,6>,

<2,12>,<3,12>,<6,12>,<2,24>,<3,24>,<6,24><12,24>,

<2,36><3,36>,<6,36>,<12,36>}

(2)R的哈斯圖

(3)集合B的最大元為12,極大元為12,最小上界為12

3.試畫(huà)一棵帶權(quán)為1,2,3,3,4的最優(yōu)二叉樹(shù),并計(jì)算該最優(yōu)二叉樹(shù)的權(quán).

(1)G的圖形表示如圖所示：

(2)鄰接矩陣：

(3)deg(v1)=3

deg(v2)=2

deg(v3)=3

deg(v4)=2

(4)補(bǔ)圖如圖所示：

V3V4

4.求出如下所示賦權(quán)圖中的最小生成樹(shù)（要求寫(xiě)出求解步驟），并求此最

小生成樹(shù)的權(quán).

解：P-(RAQ)PV(RAQ)(PVQ)八(PVR)(合

取范式)

P—(RAQ)

1PV(RAQ)

(-1PA(QVQ))V(RAQ)

(-IPA-1Q)V(PAQ)V(RAQ)

((-1PAnQ)A(RVR))V(PAQ)VRAQ)

(-1PAnQA7R)VPA-iQAR)VPAQ)V(RAQ)

(PA-iQA-iR)V(PA-)QAR)

V((-|PAQ)A(-|RVR))V(RAQ)

(-1PA-iQA-iR)V(-)PA-)QAR)V(nPAnQAnR)V(-|PAQAR)V(RA

Q)

(-1PAnQA-iR)V(-|PAnQAR)V(-|PAnQAqR)V(-)PAQAR)V(n

PVP)ARAQ)

(nPA-iQA-iR)V(-jPA-iQAR)V(nPAnQAnR)V(nPAQAR)V(PA

RAQ)(主析取范式)

5.求出如圖所示賦權(quán)圖中的最小生成樹(shù)（要求寫(xiě)出求解步驟），并求此最小生

成樹(shù)的權(quán).

最優(yōu)二叉樹(shù)如圖所示:

權(quán)為13+23+32+32+42=29

6.求P-(QAR)的析取范式與合取范式.

解：用Kruskal算法求產(chǎn)生的最小生成樹(shù)。步驟為:

w(v2,V6)=l,選(V2,V6)

w(V4,v5)=l,選(V4,V5)

w(Vl,V6)=2^(Vl,V6)

w(V3,V5)=2,選(v3,V5)

w(V2,V3)=4,選(V2,V3)

最小生成樹(shù)如圖所示：

最小生成樹(shù)的權(quán)w(T)=1+1+2+2+4=10.

7.求(PVQ)-R的析取范式與合取